An Efficient Fault Tolerance Model for Path Recovery
in MPLS Networks

Arunkumar C K

An Efficient Fault Tolerance Model for Path Recovery in MPLS Networks

Arunkumar C K
M.Tech student, Dept. of ECE, Dayananda Sagar College of Engineering, VTU, Banglore, India

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

Abstract

Increasing demand of complex and data demanding Internet services has negatively affected the quality of service of data transfers in the network. Multiprotocol Label Switching (MPLS) is an architecture developed to combine the dynamic nature of IP routing protocols and the efficiency of label switching. A significant issue in nowadays networks is the support of real-time services or multimedia applications even in the presence of node or link failures. MPLS employs basic techniques for network protection from such failures: (i) protection switching where a pre-computed alternative path (usually disjoint from the working path) is set up for every flow, and (ii) rerouting where an alternative path is dynamically recomputed after a fault is detected. For both techniques, the alternative path can be either global or local. In recent years several algorithms have been developed to provide fault recovery in virtual-circuit based networks, including MPLS. The effectiveness of the recovery depends on the choice of the protection mechanism that the algorithm implements. The two mechanisms present both advantages and disadvantages depending on the application or the topology of the network they are employed upon. We are combining the above mentioned techniques to develop a new routing algorithm to handle single or multiple faults in MPLS network. This approach achieves less recovery time, reduced packet loss, and high throughput.

Keywords

MPLS, Fault tolerance, Rerouting.

INTRODUCTION

There has been a greater need for designing the internet for internet service providers to fulfil the demands of their customers and provide faster reliable and differentiated services. Internet traffic engineering is emerging as a key tool for achieving these goals in a cost-effective manner. Traffic engineering mainly aims at maximizing operational network efficiency.

The emergence of Multi-Protocol Label Switching (MPLS) with its efficient support of explicit routing provides basic mechanisms for facilitating traffic engineering. When a packet enters an MPLS network the ingress router adds label (identifier) on it. The egress router is responsible to remove the label and receives IP packet. A label switched path is ingress to egress switched path built by MPLS capable nodes which an IP packet flows through the network and which are identified by the labels.

MPLS is a connection oriented network, so it is prone to failures. Failures may be of different type’s link/node failure, hardware/software failure, power failure etc. we are considering link/node failure in our study. Failures in link/node leads to large amount of data drops hence link protection must be carried out.

When a fault is detected in active LSP the traffic must be switched to an alternate LSP. Faults can also affect on network operation and QoS, which degrades the network performance. Hence fault tolerance mechanisms are employed for network resilience. Fault tolerance is the ability of a network to operate in proper manner under failures. Protection switching and Rerouting are the existing approaches for fault recovery techniques in MPLS network.

In protection switching, back-up path (alternate path) is pre-computed and pre-established before fault detection. This pre-computation and pre-establishment of back-up path reduces the time delay during switching. This recovery scheme holds good for simple network services. As the number of nodes in the network grows network complexity increases and the probability of occurrence of fault also increases. At this time protection switching does not holds well, Rerouting can be best performed under multiple fault tolerance. Rerouting algorithms compute backup path dynamically at failure points, this is little time consuming. Both mechanisms have their advantages and disadvantages. Based on the type of protection required the recovery method can be selected.

In this paper we propose a new QoS routing algorithm for data protection in MPLS network. This algorithm is evaluated to get simulation results for above mentioned performance criteria. The obtained results satisfy the performance metrics and overcome the disadvantages of previous works.

RELATED WORK

Gallager developed the theory for perfect load balancing through the formulation of the minimum delay routing problem (MDRP). Some heuristic techniques were developed to approximate the Gallager perfect load balancing conditions in an attempt to increase the possibility of practical adoption into production networks. Within the context of MPLS networks, several methods were developed to remove congestion and load balance the network, similar to minimum interference routing algorithm (MIRA), dynamic load balancing algorithm (DYLBA), MPLS adaptive traffic engineering (MATE),and fast acting traffic engineering algorithm (FATE), However, these techniques focused on load balancing by shifting traffic from congested links to less utilized links using centralized rerouting. These techniques share the property that rerouting is done based on end-to-end basis which means rerouting is done completely for all of the path starting from the source up to the destination.

The following discussion gives brief note on previous proposed algorithms. There are several algorithms have been proposed for protection switching and rerouting mechanisms. Let us have a look on some of them once.

Haskin’s algorithm performs on local path restoration technique. In local path restoration protection against a link or neighbour node failure can be done and time required for failure propagation can be reduced.

Makam’s algorithm performs global restoration technique. In this the backup path is completely disjoint from label switched path. When a fault detected a fault indication signal (FIS) is used to convey the information about the occurrences of fault.

PROPOSED ALGORITHM

As mentioned in the above discussion our proposed algorithm is the combination of protection switching and rerouting. An alternate path is pre-computed and pre-established that maintained by ingress LSR. Send alive messages to core LSR. If the node does not acknowledge for alive messages then send fault indication signal (FIS) to ingress LSR. If any fault found in LSP immediately an FIS message is transferred to ingress LSR, the ingress LSR switches the traffic to alternate path. If faults occur in alternate LSP then the traffic is switched to second alternate path. Each time we have to update shortest path tree using single source shortest path and array of length in every node when finds through FIS. After original LSP recovered, the traffic follows LSP.

Algorithm:

Begin: Establish working, alternative path, second path and backward LSPs.

Compute: SPT, Compute FIS (if it is there) any Array of lengths, Array with the pre-established paths in Ingress LSR, Set both working-LSP as available, Set alternative-LSP as available Protocol running on Ingress LSR.

Failure occurs check:

Step 1: When FIS information is received.

Step 2: Check whether If (failure is in working path) the path is found against failure link,

Step 3: Set working-LSP as NOT available

Step 4: If (failure is in alternative path)

Step 5: Set alternative-LSP as NOT available

Step 6: If (working-LSP IS available &&-_alternative-LSP IS available)

Step 7: Update SPT using single source shortest path and array of lengthsIn every node when finds out through FIS.

Step 8: If (working-LSP IS NOT available && alternative-LSP IS available)

Step 9: If so terminate algorithm

Step 10: if FIS received through alternative path then

Step 11: switch traffic to second alternative path

SIMULATION RESULTS

In this section we will evaluate the results of the implementation of QoS routing algorithm for protection of data flow in MPLS network. The simulations are performed on Network Simulator (NS2). The aim of this experiment is to evaluate packet delivery ratio (PDR), Recovery time and Throughput.

Figure 4 gives the results for packet delivery ratios. Packet delivery ratio is the number of packets delivered at the egress router to the average value of packets sent. The proposed algorithm is able to recover from faults with less packet loss compared to other algorithms. Usually number of faults increases when the number of nodes increases. The packet delivery ratio decreases with increase in number of nodes. But our proposed system achieves less packet loss compared to others.

Fig.5 shows throughput analysis for the proposed algorithm. Increase in packet loss gives reduced throughput. But we have achieved better PDR which reduces packet loss and gives good throughput.

Fig.6 shows the results for fault recovery time v/s number of faults for the proposed algorithm. As the number of faults increases in the network fault detection and recovery time also increases. Combination of protection switching and rerouting algorithm is able to achieve less recovery time.

Fig.7 shows the results for fault recovery time v/s number of faults of without proposed algorithm. As we can see fault recovery time of the proposed model has improvements when compared both figures.

CONCLUSION AND FUTURE WORK

Our goal in this paper was to use the combination of protection switching and rerouting which is capable of combating multiple faults. The results showed improvements in overall system throughput. Also the proposed algorithm tries to recover quickly than other techniques.

We showed that this model has many advantages compared to other techniques because of its ability of fast reaction to congestion due to the new introduced partial rerouting technique. The technique is suitable for large networks because if the diameter of the network is more then there is a possibility getting more and more alternative paths.

Figures at a glance


Figure 1	Figure 2	Figure 3	Figure 4


Figure 5	Figure 6	Figure 7

References

Afek, Y Bremler-Barr, A, Kaplan, H, Cohen, E, Merritt, “Restoration by Path Concatenation, Fast Recovery of MPLS Paths”, Proceedings ofthe twentieth annual ACM symposium on Principles of Distributed Computing, pp. 43--52.2001.

Ahn, G. Jang J, Chun, W. “An Efficient Rerouting Scheme for MPLS-Based Recovery and Its Performance Evaluation”, TelecommunicationSystems, 19(3-4), pp. 481--495.2002.

Bartos R Raman, M, “A Heuristic Approach to Service Restoration in MPLS Networks”, Proceeding of ICC 2001, pp. 117--121. 2001.

Bartos R Raman, M, “A Scheme for Fast Restoration in MPLS Networks, “Proceedings of the Twelfth IASTED International Conference onParallel andDistributed Computing Systems (PDSC), pp. 488--493.November 2000.

Bartos, R, Raman, M Gandhi, A, “New Approaches to Service Restoration in MPLS-Based networks”, Proceedings of EUROCON 2001InternationalConference on Trends in Communications, pp.58--61. 2001.

Capone, A., Fratta, L., Martignon, F, “Dynamic Routing of Bandwidth Guaranteed Connections in MPLS Networks”. Wireless andOpticalCommunications, 1(1), pp. 75--86. 2003.

Chen, J., Chiou, C.C, Wu, S.L. “A Fast Path Recovery Mechanism for MPLS Networks”, Proceeding of ICOIN 2005, pp 58--65. 2005.Chen T.M., Oh, T.H.: Reliable Services in MPLS.IEEE Communications Magazine, vol. 37, pp. 58--62. December 1999.

Fall, K., Varadhan, K. “The network simulator -ns-2.The VINT project”t. UC Berkeley, LBL, USC/ISI, and Xerox PARC, http://www.isi.edu/nsnam/ns/.

Gonfa, L.H,“Enhanced Fast Rerouting Mechanisms for Protected Traffic in MPLS Network”s. Phd Thesis, Technical University of Catalonia, February 2003.

Hadjiona, M, Georgiou, Ch., Papa, M., Vassiliou, V, “A Hybrid Fault-Tolerant Algorithm for MPLS Networks”, Technical Report TR-07-06, Department ofComputer Science, University of Cyprus, December 2007.

http://www.cs.ucy.ac.cy/~chryssis/MPLS-TR.pdf.

Haskin, D Krishnan, R, “A Method for Setting an Alternative Label Switched Paths to Handle Fast Reroute”. Internet Draft 2000.

Hong, D.W., Hong, C.S. “A Rerouting Scheme with Dynamic Control”.

E. C. Rosen, A. Viswanathan, and R. Callon, "Multi protocol Label Switching Architecture", 1999.

Ahn, G., Jang, J., Chun, W, “An Efficient Rerouting Scheme for MPLS-Based Recovery and Its Performance Evaluation”. TelecommunicationSystems, 19(3-4), pp. 481--495 2002.

Chen T.M., Oh, T.H, “Reliable Services in MPLS. IEEE Communications Magazine”, vol.37, pp. 58--62. December 1999.

Fall, K., Varadhan, K., The network simulator -ns-2.The VINT project. UC Berkeley, LBL, USC/ISI, and Xerox PARC,http://www.isi.edu/nsnam/ns/.

Gonfa, L.H. “Enhanced Fast Rerouting Mechanisms for Protected Traffic in MPLS Network”. Phd Thesis, Technical University of Catalonia, February 2003

Haskin, D., Krishnan, R, “A Method for Setting an Alternative Label Switched Paths to Handle Fast Reroute”. Internet draft 2000.