Evaluation of Performance for Optimized Routing in MPLS Network

Evaluation of Performance for Optimized Routing in MPLS Network

Neethu T U

Student,Dept. of Electronics and Communication The Oxford College of Engineering

Bangalore, India

Reema Sharma

Assistant Professor,Dept.of Electronics and Communication The Oxford College of Engineering

Bangalore, India

Abstract Emerging demand for the sophisticated services such as videoconferencing, Voice over Internet Protocol (VOIP) has led to tremendous need for high link capacity, low packet drop and delay. Multi Protocol Label Switching (MPLS) is going to provide next generation Quality of Service (QoS) and traffic engineering (TE) architecture for the Internet. In this work a routing algorithm for different MPLS topologies which can reduce the congestion by avoiding the critical path and reserving path for future request is proposed and designed. The packets are explicitly routed and we compare the results with IPv4 configurator for the performance evaluation using OMNET++ simulator.

KeywordsMPLS,Optimization,Routing,Omnet++,Traffic Engineering,QoS,Explicit, IPv4.

1. INTRODUCTION

   By 2015 the amount of Internet traffic is said to exceed more than one zettabytes. Service Providers will have to face the challenge and improve the performance by managing the internet traffic. Multi protocol label switching technology [2] came into existence to overcome the drawbacks of IP forwarding, by avoiding the routing table lookup for each routers. MPLS is considered as 2.5layer. The MPLS shim header is 32 bit as shown in Fig. 1. which consists of a 20 bit label, 3 bit Exp field for experimental use,1 bit Stack field and 8 bit Time to live field for preventing the looping. MPLS uses the concept of labels for packet forwarding in order to reduce the time complexity.

   The major issue widely discussed in the field of networking is the management and reservation of bandwidth. Load balancing is another issue where some portions of the network become over utilized leading to congestion in the network. As a result few alternate feasible paths remain underutilized. These issues are addressed by Traffic Engineering (TE) [3].Traffic engineering does not necessarily select the shortest path. MPLS network can implement traffic engineering simply and efficiently by establishing label switching path (LSP) between the source node and destination node. One of the unique feature of MPLS is Tunneling by which it can control the entire path of a packet without specifying the intermediate

   routers explicitly. For setting up LSP path a signaling protocol Resource Reservation Protocol (RSVP) with TE modifications (TE-RSVP) is used.

   Fig.1. MPLS Header

   When the IP packets arrive at the edge router which is termed as ingress router the label is attached or pushed to it and forwarded .The intermediate routers does the swapping operation and once the packet is about to reach the destination the edge router towards the destination detaches or pops the label and forwards the IP packet to destination. The difference between the IP forwarding and MPLS is mainly that the latter requires packet classification in each hop, whereas in MPLS, the classification is done by the ingress LSR when the label is attached. In MPLS the paths are predefined already, hence the packets will take the path specified and route the packets. This is called the explicit routing.

   The working of MPLS in Fig.2. is as follows, when host A send an IP packet to a host C, it sends an un-labeled packet. The ingress LSR, R1 examines the IP address of the destination and other information in the packet header and pushes a label into the packet and forwards the labeled packet to the out interface. R2 LSR now receives the labeled packet and examines the label and performs a table loop-up at the forwarding table to determine the new label and the out interface. R2 then swaps the old label with the new label and routed the new labeled packet to the out interface. The labeled packet will reach the egress LSR, R7. It then examines the label and performs a table loop-up at the forwarding table to find that the packet is to be sent to host C and then removes the label and sends an unlabelled packet to C.

   in a network and reduction in cost of path.This algorithm discusses about a critical link whose load is running above some threshold level.The path is considered to be more critical if it contains more number of demands for that link. Hence to distribute load and avoid critical links, BCRA calculates a weight and assign weights to links and route the request along the smallest amount weighted path using a shortest path algorithm.

   Fig.2. MPLS Architecture

   In section II , we present the details about the background study which is related with our work. Our proposed Optimized routing algorithm is described in section III. Section IV deals with the performance analysis and comparision of the parameters for the different MPLS topologies. Section V deals with the conclusion.

2. BACKGROUND STUDY

   1. Shortest Path First Algorithm (SPFA)

      SPFA[] is a frequently used algorithm for routing the packets in networking. This algorithm selects the shortest path always in order to transmit the packets.This may potentially lead to bottleneck paths which results in the poor utilization of the resources in the network.

   2. Widest Shortest Path Algorithm(WSPA)

      Author of [7] demonstrated widest shortest path algorithm which attempts to balance the load in a network. In WSPA the path which is feasible with least number of links is selected. If multiple such paths exist then the one with the largest residual bandwidth is given the priority, thus discouraging the use of already heavily loaded links. The drawback of WSPA is due to the path selection is performed among the shortest feasible path which are over utilized before switching to longer feasible paths.

   3. Minimum Interference Routing Algorithm(MIRA)

      MIRA proposed by the author[6] demonstrates on how to route a new connection over a path with minimum interferes for the possible future requests. MIRA exploits the knowledge of ingress-egress pairs in finding a feasible path. Here, a critical link, is identified as a link that can decrease the maximum flow value of one or more ingress-egress pair if critical link has been selected in a path. MIRA attempts to eliminate the critical link during a path selection MIRA considers the amount of interference on a particular ingress- egress pair (s,d) as the reduction in the maximal available bandwidth between (s,d). MIRA takes neither the current load condition on the paths nor load balancing throughout the network.

   4. Bandwidth Constrained Routing Algorithm(BCRA)

   Authors of [5] proposed an bandwidth constrained algorithm called BCRA which compromises between the load balancing

3. PROPOSED ALGORITHM

   In this we present our QoS routing algorithm for the bandwidth utilization and the congestion avoidance for the MPLS traffic engineering. We consider a network of n routers. An ingress-egress routers between which paths can be setup is considered to be the subset routers. In order to compute the explicit route, the ingress router need to have the knowledge about the current network topology and links reserved bandwidth. Here this information can be obtained using a link state routing protocol [1]. The network is designed as a directed graph G (N,L) where N is the set of nodes, L is set of links between the nodes. Consider P as the set of ingress- egress pairs. (s ,d ,B) [4] where s specifies the ingress router, d the egres router and B the amount of required bandwidth. The path setup requests arrive at the ingress router one at a time and there is no prior knowledge of future requests.

   1. Algorithm Detail

      INPUT: G = (N, L), a set P of all the source-destination pairs and LSP request R (s, d, B), which is a request for B bandwidth units between pair (s, d) and a set Q of all the source-destination pairs

      OUTPUT: A route from s to d with the bandwidth of B units.

      OFFLINE PHASE:

      1. All the combination of possible paths is calculated.

      2. Route all paths with the request of bandwidth of 1 unit.

      3. Link weight of a link is the total bandwidth used on the link divided by summation of total bandwidth used by all links.

         ONLINE PHASE:

         1. Compute the weight w(l) for all the links L according to equation (1) .

         2. Eliminate all the links whose residual bandwidth less than the requested bandwidth B.

         3. Now run Djikstras algorithm using w(l) as the weights in the network.

         4. Create an LSP from s to d with the B bandwidth units and the link capacity is updated .

         5. End.

   2. Topology details

      We consider two MPLS network topologies and calculate the path weights and find the shortest path. Fig.3a considers the MPLS network with IPv4 configuration which assigns the addresses to the network by itself and route the packets along the shortest path which leads to congestion.

      Fig.3a. MPLS topology using IPv4 configurator

      Here we observe that there are seven LSRs and we send the

   3. Link Weight and Path Weight Calculation

   Table I shows the calculation for the weights for each links in MPLS topolopy as in Fig.3b. From the calculation we determine the path 1-2-6-5 is less utilized.

   TABLE I. Link Weight values

   Links	Link weight
   1-2	0.18
   1-3	0.12
   2-4	0.12
   2-6	0.05
   3-7	0.12
   3-4	0.12
   5-4	0.12
   5-7	0.12
   5-6	0.06

   The link weight can be determined by the formula:

   voice and video packets of variable bytes from source host1, host2, host3 to destination host4,host5 and host6. The path along LSR1-LSR2-LSR6-LSR5 gets congested. Similarly in

   w(l) C(L) / R

   (1)

   the Fig. 3b. MPLS network which uses the explicit routes is considered. First we find all the possible paths from the entire source to destination and calculate the path weights. In both the topologies LSR1 is the ingress router where label is attached to the IP packet and LSR5 is the egress router which pops the label and transmits the packet to the destination hosts. In the topology using the explicit routing, packets are routed along the longest path 1-2-4-3-7-5 by avoiding the underutilization of shortest path.

   Fig.3b.MPLS topology using Explicit Routing

   where R is the residual link bandwidth. We observe from (1),

   that the weight of the link is directly proportional to critical links and hence higher the value of criticality, higher will be the weight of that particular link. Also, it is inversely proportional to the residual bandwidth, so when residual bandwidth is less, weight of the link will be more. In the proposed algorithm we are avoiding path with less weight, so as to balance traffic loads through underutilized paths[1] which is the longest path 1-2-4-3-7-5. This path weight is used to route LSP from ingress node S to egress node D. The constraint is to avoid the path with more less weight. However, if there are many such paths with the same minimum path weight, the algorithm would pick a shortest path between those result paths in order to reserve network bandwidth.

   TABLE III. Critical path value

   Node Pair	Possible Paths	Path Weight
   Host1 Host4	1-3-7-5	1.2
   	1-3-4-5	1.2
   	1-2-4-5	1.4
   	1-2-6-5	0.96
   	1-2-4-3-7-5	2.2

   From the Table II we find that the more path weight results in minimum interference in that particular path. 1-2-6-5 is the shortest path and leads to more interference hence we avoid this path and route packets in the the longest path 1-2-4-3-7-5 in order to avoid congestion and utilize bandwidth.

4. SIMULATION RESULTS

   Extensive OMNET++ simulations are considered for the evaluation of the performance parameters such queue length and queue time for the topologies in fig.3a and 3b.

   1. Queue Length

      Fig.4a. Queue length for MPLS topology using IPv4 configurator

      Queue length for the MPLS network using the ipv4 congigurator which chooses the shortest path to route the packets is shown in Fig.4a. from which we find that the queuelength is 10 for the LSR2 and LSR6 since the 1-2-6-5 is considered shortest path. This results in congestion in this path.

      Fig.4b. Queue length for MPLS topology using Explicit Routing

      The queue length for MPLS topology using the Explicit routing which utilizes the longest path 1-2-4-3-7-5 is shown in Fig.4b. Here the queuelength in the shortest path is 7 for LSR1 and 1 for LSR6.Since the longest path is utilized congestion in shorter path is avoided .

   2. Queue Time

   The amount of time the packets remain in the queue during the routing is shown in Fig.4c. and 4d. for the MPLS topologies with ipv4 configurator and explicit routing. The queue time for router LSR1 and LSR7 is shown graphically. LSR1 with ppp[1] interface has the queue time of 0.96ms shown by yellow line for the shortest path with configurator.

   Fig.4c. Queuing time for MPLS topology using IPv4 configurator

   For the MPLS network with explicit routing LSR1 with the ppp[0] interface has the queue time of 1.03ms which is shown by the green line and LSR7 with the ppp[1] interface has the queuetime of 0.03ms shown by red line since the longest path is utilized.

   Fig.4d. Queuing time for MPLS topology using Explicit Routing

5. CONCLUSION

In this paper we have proposed an optimized routing algorithm which reserves the shortest path for future requests.We have compared two network topologies and proved that the MPLS network in which routes can be explicitly defined makes use of the underutilized paths, and avoids the congestion. Whereas the topology which uses the IPV4 configuration selects the shortest or critical path and leads to congestion. MPLS traffic engineering which is used to provide the explicit routing is of more advantage in the optimization of network resources.

REFERENCES

1. Alidadi A., Mahdavi M., Hashmi M. R. A New Low-Complexity QoS Routing Algorithm for MPLS Traffic Engineering, Proceedings of the IEEE 9th Malaysia International Conference on Communications 2009.

2. E. Rosen, A. Vishwanathan, R. Callon, Multiprotocol Label Switching Architecture, in: IETF RFC 3031, January 2001.

3. Jaudelice C. de Oliveira , Caterina Scoglio, George Uhl Ian F. Akyildiz New Preemption Policies for DiffServ-Aware Traffic Engineering to Minimize Rerouting in MPLS Networks,, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 4, AUGUST 2004

4. Bin Wang, Xu Su, C. L. Philip Chen ,A New Bandwidth Guaranteed Routing Algorithm for MPLS Traffic Engineering, 2002 IEEE

5. Kotti, A. Hamza, R. Bouleimen, K,Bandwidth Constrained Routing Algorithm for MPLS Traffic Engineering, Networking and Services,

   ICNS, Third International Confernce on, 19-25 June 2007

6. M. Kodialam, T.V. Lakshman, Minimum interference routing with applications to MPLS traffic engineering, IEEE INFOCOM 2000,

   March 2000.

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