A heuristic approach to service restoration in MPLS networks

This paper proposes a new approach to providing fault tolerance in MPLS networks based on the concept of "domain protection" where protection paths for all working paths that terminate in an egress router are calculated simultaneously. The proposed scheme guarantees that every protected node is connected to two protection paths placed in a way that no single link failure would cause simultaneous loss of connectivity between a node and the egress router on both protection paths. The use of dual protection paths permits decoupling the protection path placement from the working path placement thus allowing much greater flexibility than other previously proposed schemes. Several heuristics to improve the quality and reduce the cost of the protection path placement are proposed and evaluated. The simulation results show that the algorithm together with the heuristic extensions achieves protection which is less costly or comparable to two other proposed MPLS protection schemes-RSVP backup tunnels and fast reroute-while exhibiting comparatively lower algorithmic complexity.