Recent Research and Comparison of QoS Routing Algorithms for MPLS Networks

Headnote

Abstract

MPLS enables service providers to meet challenges brought about by explosive growth and provides the opportunity for differentiated services without necessitating the sacrifice of the existing infrastructure. MPLS is a highly scalable data carrying mechanism which forwards packets to outgoing interface based only on label value .MPLS network has the capability of routing with some specific constraints for supporting desired QoS. In this paper we will compare recent QoS Routing Algorithms for MPLS Networks. We are presenting simulation results which will focus on the computational complexity of each algorithm, performances under a wide range of workload, topology and system parameters.

Keywords

Multimedia applications, MPLS, QoS Routing, Path Selection, Traffic Engineering

(ProQuest: ... denotes formulae omitted.)

1. Introduction

The continuing expansion and popularity of the internet is forcing routers in the core network to support the interconnection of more and more networks. Continual increase in number of users, demand for higher connection speed, increase in traffic volumes, increasing number of ISP networks, voice and data convergence on a single network infrastructure has motivated a traffic directing technology that promises a more efficient routing scheme based on assignments of labels to routed packets. The technology is named as Multi Protocol Label Switching (MPLS) which is used for delivery of IP services.

MPLS is an efficient encapsulation mechanism which uses labels appended to packets for transport of data. Labels can be used as designators, for example, IP Prefixes, ATM VC or a bandwidth guaranteed path. In traditional IP routing, packets undergo analysis at each hop, followed by forwarding decision using network header analysis and then lookup in routing table. In an MPLS network [1], packets carrying data are assigned with labels on each node and the forwarding decision is totally based on these label headers. This is different from the conventional routing mechanism. Packet header is analyzed only once while they enter the MPLS cloud from then the forwarding decision is 'label-based' that ensures fast packet transmission between local-local and localremote nodes.

This ensures end-to-end circuits over ANY type of transport medium using ANY network layer protocol. In view of the fact that MPLS supports Internet Protocol revised versions (IPv4 and IPv6), IPX, AppleTalk at Layer3; Ethernet, Token Ring, Fiber Distributed Data Interface (FDDI), Asynchronous Transfer Mode (ATM), Frame Relay, and PPP (Point to Point Protocol) at Layer 2, it is referred as 'Layer 2.5 protocol'.

The core technology intents to remove protocoldependency on specific data link layer technologies such as ATM, Frame Relay, Ethernet, and Synchronous Optical Network (SONET). This avoids the need of multiple layer 2 networks for different types of traffic. It was intended for providing a unified data carrying service for circuit-based and packet switching clients.

1.1 MPLS Architecture

1.2 MPLS Elements

MPLS elements include:

Forward Equivalence Class (FEC): This class includes a cluster of packets of a specific application forwarded in its switch path over the same pathway (with same forwarding treatment). Every packet of a particular class hold same service requirement. Every type of data traffic is assigned with a new FEC and is done only once while they enter the MPLS cloud.

Ingress Label Edge Router (LER): It exists on the perimeter of an MPLS cloud and is an entry point where the data packet originates from its source. This edge router imposes label (PUSH) and forward packets to destination through the domain. After setting up LSP and assigning labels, this ingress edge router initiates packet-forwarding process in MPLS core network.

Egress Label Edge Router (LER): It exists on the perimeter of an MPLS network and is an exit point where the data packet reaches its destination. This edge router performs label disposition or removal (POP) and forwards IP packet to destination. It disposes label from the arrived packet only when bottom-of-stack indicator identifies if the encountered label is bottom label of the stack or not.

Label Switch Router (LSR): This router receives a labeled packet, swaps it with an outgoing one, and forwards the new packet to an appropriate interface. Depending on its location in MPLS domain, this router performs label disposition (removal, POP), label imposition (addition, PUSH) or label swapping (replacing the top label in a stack with a new outgoing label value). When the data stream (files or multimedia traffic) arrives from the access network to the MPLS core, it is segregated into separate FEC in this router. As an acknowledgement of label bindings, LSR creates entries in Label Information Base. This table comprises of I/O ports and I/O port labels indicating the label-FEC mapping.

Label Switch Path (LSP): LSP is the path traversed by a packet from source to destination through an MPLS-enabled network. The path is simplex type or one-way characteristic. This allows packets to be switched from one edge to the other by traversing several intermediate switch routers. Every network location needs LSPs to be established for data transfer. For example, packet data from LER1 traverses among several intermediate nodes to LER2 using LSP1, then another path LSP2 is set out for packet transfer to other end directly, which is the shortest path to arrive the destination. However, path switching is derived from IGP routing information and may diverge from Interior Gateway Protocol preferred path to the target network.

2. Issues of QOS Control in MPLS

One of the key issues in providing QoS guarantees is how to determine paths that satisfy QoS constraints. Solving this problem is known as QoS routing or constrained based routing. The research community has extensively studied the QoS routing problem, resulting in many QoS routing algorithms. Routing in general involves two entities, namely the routing protocol and the routing algorithm. The routing protocol manages the dynamics of the routing process, capturing the state of the network and its available network resources and distributing this information throughout the network. The routing algorithm uses this information to compute paths that optimize a criterion.

In the MPLS networks, to set up a hop by hop LSP, the Label Distribution Protocol has been proposed. One new technique proposed to implement explicit routing is the Constraint based routing using Label Distribution Protocol (CR-LDP). CR-LDP builds upon LDP protocol, which is already part of MPLS[2]. On the other hand, Differentiated Services (DiffServ) is a scalable class of service architecture proposed by the IETF, which provides scalable QoS guarantee. The DiffServ networks can support different service models including the Expedited Forwarding (EF), the assured forwarding (AF) and the Best Effort (BE). By integrating the DiffServ and MPLS, a very attractive strategy to backbone network service providers with scalable QoS and traffic engineering capabilities can be obtained. The DiffServ provides scalable edge to edge QoS , while MPLS performs traffic engineering to evenly distribute traffic load on available links and fast rerouting to route around node and link failures.[3] DS-TE (DiffServ- Aware MPLS traffic Engineering ) has been standardized and implemented as one of the MPLS traffic Engineering methods. Based on the CSPF, this function not only automatically adjusts the LSP bandwidth but also dynamically reroutes the LSP's, when a certain physical link on the current LSP routes becomes short of capacity.

To execute the function of DS-TE, the routers need to have high functionality as each LSP needs to monitor the traffic statistics and compute the suitable bandwidth. To guarantee QoS, the routers need to have traffic shaping function in each LSP. Because the routers generally have many LSPs, such functions in each LSP generates large load on the routers.

The CSPF(Constrained Shortest Path First) is a "greedy" algorithm that adopts the route which has sufficient capacity one at a time with no reference to any other LSPs which treat the same traffic class being placed. Therefore , the LSP from the particular edge router sometimes occupies much capacity ahead. It generates the unfair capacity assignment for the LSPs between all the pairs of edge routers. Based on these issues , it is assumed that it is difficult for Network Service Provider's to adopt the function of DS-TE in their MPLS networks.

So, it is desirable that the edge routers have LSPs statically configured for the traffic class, and the edge routers determine the route and distribute the traffic over their networks. And the traffic accommodated in the network should be taken into account for admission control.

3. Literature Survey

First, we will review some of the most popular algorithms [4] proposed in the literature, such as the Min-Hop Algorithm (MHA), the Widest Shortest Path Algorithm (WSP) , Shortest widest Path First , Dynamic Online Routing algorithm (DORA), the Minimum Interference Routing Algorithm (MIRA), Profile Based Routing (PBR) and the Virtual Flow Deviation (VFD) algorithm. We describe in some detail MIRA and VFD algorithms. These algorithms take explicitly into account the topological layout of the ingress and egress points of the network. The VFD algorithm, considers also the traffic statistics. More precisely, VFD exploits the knowledge of the layout of the ingress/egress nodes of the network, and uses the statistics information about the traffic offered to the network in order to forecast future connections arrivals.

3.1 Minimum Hop Algorithm

The Min-hop algorithm (MHA)[5] routes a new connection along the path, between source and destination, with the minimum number of feasible links. This scheme, based on the Dijkstra's algorithm, is simple and computationally efficient. However, being the cost given to each link independent of the current link load, MHA tends to use the same paths until saturation is reached before switching to other paths with less utilized links. This can result in an unbalanced routing with heavily loaded bottlenecks.

3.2. Widest shortest path algorithm

The Widest Shortest Path Algorithm (WSP) [6], is an improvement of the Min-Hop algorithm, as it attempts to load-balance the network traffic. In fact, WSP chooses a feasible path with minimum hop count and, if there are multiple such paths, the one with the largest residual bandwidth, thus discouraging the use of already heavily loaded links. However, WSP still has the same drawbacks as MHA since the path selection is performed among the shortest feasible paths which are used until saturation before switching to other feasible paths.

3.3 Shortest Widest Path First Algorithm

The Shortest widest Path First [7] looks as the opposite of the (WSP) where the first criterion is now taken to be the path with the maximum residual bandwidth and if more than one path is selected then the one with the smallest number of hops is chosen.

3.4 Minimum Interference Routing Algorithm

The Minimum Interference Routing Algorithm (MIRA)[8] uses the knowledge of ingress egress label switching router that is potential traffic source destination pairs. It makes the routing decision for a demand based on the "interference" level it would have on the future demand from other sourcedestination. This interference level is used as the link weight to calculate the shortest path for a new demand. The novelty of this algorithm results in the less chosen the critical links to other sourcedestination pairs. However, it has two major drawbacks. The first is complexity to calculate the maximum flow between any source-destination pairs and the link weight of all links.

3.5 Dynamic Online Routing Algorithm

DORA is a dynamic online routing algorithm for the construction of bandwidth guaranteed paths in MPLS- enabled networks. The main goal of DORA is to avoid routing over links that have high potential to be part of any other path and have low residual available bandwidth.

The operation of DORA lies into two stages. The first stage calculates the called path potential value (PPV) array associated with a source- destination pair. The second stage combines PPV with residual link bandwidth to form a weight value for each link of the path. This value is then used to compute a weight optimized network path. The potential of a link being more likely to be included in a path than other links is characterized by an associated PPV. Formally, for each source - destination pair, we associate to each link an integer called the PPV with an initial value zero. Each source -destination pair (S,D) is associated with an array, PPV(S,D) . When a path could be constructed over a link L for a given source destination pair (S1, D1), we reduce PPV(S1,D1) (L) by 1. When a path could be constructed over the same link L for a different source destination pair (S2, D2), we increment PPV(S1,D1) (L) by 1. Since there are many paths between a given sourcedestination pair, we consider only disjoint paths. The computation of PPV arrays for each source - destination pair forms the first stage of the algorithm.[9]

In the second stage, all links with a residual bandwidth less than the required bandwidth will be removed. The PPV and the current residual bandwidth of each link are combined together to form the link weight. The content of the link weight is controlled by a parameter called BWP (Bandwidth Proportion). Finally by running Dijkstra's algorithm a weight optimized path on the residual topology can be computed.

3.6 Widest Dynamic Online Routing Algorithm

WDORA [9] is a dynamic online routing algorithm for the construction of bandwidth guaranteed paths in MPLS- enabled networks. The main difference between DORA and WDORA is that in the computation of the set of the disjoined paths between source and destination pairs , if more than one path exists with the same length having a common link, the path with the largest bandwidth is chosen as compared to shortest path as in DORA.

3.7 Profile Based Routing

The Profile-Based Routing algorithm (PBR)[10] exploits, like MIRA, the topological information about ingress/egress nodes of the network. Moreover, it takes into account network traffic statistics by estimating network traffic profiles, obtained by measurements of service-level agreements established with network users, as a prediction of future traffic distribution. PBR is based on an offline preprocessing step that determines the amount of bandwidth allocated to each traffic class on network links. Based on this allocation PBR performs an admission control on incoming connections. This feature considerably reduces the complexity of the computation performed online upon a new connection request.

3.8 Virtual Flow Deviation Algorithm

Virtual Flow Deviation (VFD), which keeps into account the information of the ingress and egress nodes of the network and the traffic statistics. More precisely, VFD exploits the knowledge of the disposition of the ingress/egress nodes of the network, and uses the statistics information about the traffic offered to the network through each ingress point in order to forecast future connection arrivals. For every connection request, VFD creates a set of virtual calls based on the observed traffic statistics. These virtual calls represent the calls which are likely to request resources to the network in the immediate future, and will thus interfere with the current one. In order to improve the global resource utilization, VFD routes the current call together with the virtual calls using the Flow Deviation method [11]. .

In order to take into account the future traffic offered to the network, VFD thus routes not only the real call, but also a certain number of virtual calls, which represent an estimate (based on measured traffic statistics) of the connection requests that will probably interfere with the current, real call. The number of these virtual calls, as well as the origin and the bandwidth requested should reject as closely as possible the real future network conditions.

All the information concerning network topology and estimated offered load must be used to produce a path selection which uses at the best the network resources and minimizes the number of rejected calls. Such a path selection is performed in VFD by the Flow Deviation algorithm, which allows determining the optimal routing of all the flows entering the network through all the different source/destination pairs.

3.9 Virtual Calls

To implement VFD it should be determined how many virtual calls [12] should be generated, their source/destination pairs, and their bandwidth requests. In this process, we can easily measure and assign to each S-T pair the two following parameters:

* The average traffic offered by the S-T pair defined as the average number of connections entering the network through the node Si with destination Ti

* The probability distribution of the bandwidth requested at each S-T pair, estimated as the ratio between the number of calls which have requested bandwidth units and the total number of calls considered for the estimation.

Upon a new call request the process for generating Nv associated virtual calls, is activated. The real call and the virtual calls are then offered to the network. The procedure to route the new traffic operates in two steps. In the first step an initial feasible flow assignment is obtained. Calls are routed one by one starting from the real call. A call can be either defined as ACTIVE, if a feasible path has been found, or NON ACTIVE otherwise. This step is repeated until all calls have been considered. The procedure stops if the real call cannot be routed. In step two the routing of all ACTIVE calls is optimized using the Flow Deviation Method. Then step one is repeated for the NON ACTIVE calls. If at least one NON ACTIVE call is declared ACTIVE the step two is repeated and the procedure is iterated until either all calls are ACTIVE or step one does not define any new call as ACTIVE. At the end of the procedure the real call has been routed on an optimal path considering an expected future evolution of the network traffic load.

4. Employing advanced routing algorithms

Advance routing algorithms are very difficult for implementing on router because router has limited memory, CPU speed and functions of operating system. So advanced routing algorithms are implemented on server with centralized model. Server get network information from distributed protocol such as OSPF-TE, IS-IS- TE to compute the optimal path. It uses SNMP, telnet etc. to control ingress- egress pairs to setup new LSP.

Some typical projects are working with advanced routing algorithms on MPLS with server.[13]

RATES (traffic Engineering Server) are developed by bell laboratories. RATES uses TE-server to compute optimization paths based on MIRA, then COPS server setup paths by COPS protocol. RATES use CORBA for distribution programming.

MATE: MPLS Adaptive Traffic Engineering: Different MATE functions Are: Filtering and Distribution function: Facilitate traffic shifting among LSPs in a way that reduces the possibilities of having packets out of order. Traffic Engineering function: Decides on when and how to shifttraffic among LSPs. It consists of two phases: monitoring phase and engineering phase. Measurement and Analysis function: Obtains one-way LSP statistics such as packet delay and packet loss, done by having ingress node transmit probe packet periodically to the egress node which returns them back to ingress node. TEQUILA (Traffic Engineering for Quality of Service in the Internet at Large Scale) is the project of European collaborative. It proposes an architecture providing QOS on internet. It has main components such as control plane, data plane and management plane etc. These enhancements allow per flow path selection and Qos parameters to be taken into account by the routing algorithm to satisfy the QOS requirement for every admitted connection and achieving global efficiency in resource utilization.

5. Parameters of the Simulation

In this section comparison of the performance of the Virtual Flow Deviation algorithm with that of the Min-Hop Algorithm and MIRA referring to two different network scenarios is done. Also a network topology consisting of 14 nodes and 28 links having a capacity of 4.8 Mbps and 1.2 Mbps with four distinguished pairs of source destination: (S0, D0), (S1, D1), (S2, D2) and (S3, D3 )is used to compare the performances of SPF-TE, DORA, WDORA, WSPF, SPF . This is the same topology used to show performances of MIRA [8] compared to SPF and WSPF. The various performance criteria's are mentioned as a function of the load submitted to the network. Here load is defined in equation (1) in the same manner as presented in [14][9].

... (1)

Where ... is the network cumulative connection request arrival rate with ... representing the class s connection request. C represents the total network capacity equal to the sum of all link capacities. 1/µ represents the average connection duration. In the simulation, b is fixed to 1.1 Mbps.

5.1 Comparison of the Algorithms

We observe that out of VFD, MHA and MIRA ,all the algorithms except VFD algorithm fails to achieve good performance when the traffic statistics at each ingress point are different or when an ingress node offers to the network a traffic significantly higher than other nodes. Also, all the algorithms fail to consider traffic statistics which can be easily measured at each ingress node. The performance function is nothing but is the percentage of rejected calls versus the average total load offered to the network. The first scenario is illustrated in Figure 5. In this network the links are unidirectional with capacity equal to 120 bandwidth units[12]. The network traffic, offered through the source nodes S1, S2 and S3, is unbalanced as the traffic offered by sources S2 and S3 is four times that offered by S1. Each connection requires a bandwidth uniformly distributed between 1 and 3 units.

In this simple topology only one path is available to route connections between S1-T1 and S3-T3, while connections S2-T2 can choose between two different paths. This case evidentiates the main limitation of MIRA that does not consider the information about the total load offered to the network. Since the links (1,2),(2,3) and (8,9) are critical for S2-T2, the route selected by MIRA follows the path with the minimum number of critical links(5-8-9-6 in the example). Unfortunately this interferes with the path (7-8-9-10) that carries the high load of S3-T3. This choice will penalize the performance as shown in Figure 6.

VFD achieves the best performance since it exploits the information on the unbalanced load. The performance of MHA and MIRA are exactly the same. In fact MIRA operates for the connections between S2-T2 the same path selection of MHA, since the path (5-8-9-6) is shorter than (5-1-2-3-6).

The second network considered [12] is shown in Figure 7 where a balanced traffic is offered at S1 and S2. All links have the same capacity (120 bandwidth units) and are bidirectional. The critical links identified by MIRA are (0,1),(0,2),(0,3),(1,4),(2,4),(3,4) for connections S2- T2 and (1,0),(1,2),(1,4),(0,3),(2,3),(4,3) for connections S1-T1. This leads to have only the path (1-2-3) available for connections S1-T1 and the path (0,2,4) for connections S2-T2.This is a very limiting way of operation that penalizes MIRA. As shown in Figure 8, VFD can reach a more balanced routing using all the available paths with no limitation.

To compare the other algorithms, the blocking Probability, Response Time and Path Length are the criteria which are used. Blocking Probability is defined as the ratio of the number of rejected connection requests to the total number of requests issued to the network. Response Time is defined as the sum of the path computation time and the time needed to actually establish this path if it exists. Average Length is defined as the number of hops forming the selected route.

In Figure 9, Cumulative Network Load versus blocking probability is plotted for SPF-TE, DORA, WDORA, WSPF, SPF. While different algorithms performance is very close, WDORA outperforms them slightly because of the fact that WDORA selects routes having largest residual capacities which results in routes with more probability of still being feasible for future requests. Also blocking probability is highest in case of SPF.

In Figure 10, Cumulative Network Load versus response time is plotted for SPF-TE, DORA, WDORA, WSPF, SPF. For low workloads SPF-Te is the most powerful among all the algorithms but its performance is deteriorating for high workload. Also algorithms can be arranged from more powerful to least powerful as follows: WSPF, WDORA and DORA other than SPF-TE.

Figure 11 shows the plot of average route length of accepted connections versus cumulative network load. It is observed that SPF-TE is the best algorithm as it uses optimal routes. Considering the difference between DORA and WDORA[9] and SPF- TE and WSPF, WSPF and WDORA satisfies the other future requests for connections as it chooses the broadest among the shortest routes.

6. Conclusion

We have analyzed the performance of online QOS routing algorithms for bandwidth guaranteed connections in MPLS and label switched networks. We have observed that amongst all algorithms, VFD allows to achieve lower connection rejection rates than existing algorithms, especially in more critical network operations with unbalanced traffic offered at the ingress nodes. VFD algorithm allows to reduce remarkably the blocking probability in most scenarios with respect to the other proposed algorithms. Also WDORA is the new routing algorithm which performs better in terms of blocking probability, path length and response time in comparison with other algorithms.

References

References

[1] S. Chen and K. Nahrstedt. An Overview of Quality-of- Service Routing for the Next Generation High-Speed Networks: Problems and Solutions, 1998.

[2] Mohammad Hossien Yaghmae, Ali Asghar Safaeei, Quality of Service Routing in MPLS Networks Using Delay And Bandwidth Constraints.

[3] Takeshi USui, Yoshinori Kitatsuji, Hidetoshi Yokota, A Study on traffic management cooperating with IMS in MPLS networks, Springer, telecommun Syst, DOI 10.1007/s11235-011-9511-7.

[4] E.Rosen, A.Viswanathan, and R.Callon. Multiprotocol Label Switching Architecture. In RFC 3031, January 2001.

[5] D.O.Awduche, L.Berger, D.Gain, T.Li, G.Swallow, and V.Srinivasan. Extensions to RSVP for LSP Tunnels. In Internet Draftdraft-ietf-mpls-rsvp-lsp-tunnel-04.txt, September 1999.

[6] R.Guerin, D.Williams, and A.Orda. QOS Routing Mechanisms and OSPF Extensions. In Proceedings of Globecom, 1997.

[7] P.STEEKISTE; Q. MA. On Path Selection for Traffic with Bandwidth Guarantees, in proceedings of the IEEE International conference of Network Protocols, October 1997.

[8] Murali S. Kodialam and T. V. Lakshman. Minimum Interference Routing with Applications to MPLS Traffic Engineering. In Proceedings of IEEE INFOCOM (2), pages 884-893, 2000.

[9] Karima Maalaoui, Abdelfettah Belghith, Jean- Marie Bonnin, Miled Tezeghdanti Performance evaluation of QOS Routing Algorithms. IEEE 2005 0-7803-8735-X/05

[10] Antonio Capone Luigi Fratta, Fabio Martignon "Dynamic online QOS routing schemes: Performance and bounds"2005

[11] L.Fratta, M.Gerla, and L.Kleinrock. The Flow Deviation Method: An Approach to Store-and-forward Network Design. In Networks 3, pages 97{133, 1973.

[12] Virtual Flow Deviation: Dynamic Routing of Bandwidth Guaranteed Connections Antonio Capone, Luigi Fratta, Fabio Martignon DEI, Politecnico di Milano Piazza L. da Vinci 32, 20133 Milan, Italy Capone, fratta, [email protected] .

[13] Tran Cong Hung, Nguyen Hoang Thanh, Nguyen Duc Thang, Hae Won Jung, Tae II Kim, Sung Hei Kim, Woo Jin Yang," Advanced Routing Algorithms and Load Balancing on MPLS" ISBN 978-89-5519-131-8 93560 Feb. 12-14, 2007 ICACT2007

[14] M. TEZEGHDANTI. Ingenierie de traffic intra- aire et multi-aires pour les reseaux dorsaux IP. Thesis, IRISA/INRIA- ENST Bretagne, December 2003.