400 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 15, NO. 3, JUNE 2007Simple Pre-Provisioning Scheme to EnableFast RestorationMansoor Alicherry and Randeep BhatiaAbstract—Supporting fast restoration for general mesh topolo-gies with minimal network over-build is a technically challengingproblem. Traditionally, ring-based SONET networks have offeredclose to 50 ms restoration at the cost of requiring 100% over-build.Recently, fast (local) reroute has gained momentum in the contextof MPLS networks. Fast reroute, when combined with pre-provi-sioning of protection capacities and bypass tunnels, enables fasterrestoration times in mesh networks. Pre-provisioning has the ad-ditional advantage of greatly simplifying network routing and sig-naling. Thus, even for protected connections, online routing cannow be oblivious to the offered protection, and may only involvesingle shortest path computations.In this paper, we are interested in the problem of reserving theleast amount of the network capacity for protection, while guaran-teeing fast (local) reroute-based restoration for all the supportedconnections. We show that the problem is NP-complete, and wepresent efficient approximation algorithms for the problem. Thesolution output by our algorithms is guaranteed to use at mosttwice the protection capacity, compared to any optimal solution.These guarantees are provided even when the protection is for mul-tiple link failures. In addition, the total amount of protection ca-pacity reserved by these algorithms is just a small fraction of theamount reserved by existing ring-based schemes (e.g., SONET), es-pecially on dense networks. The presented algorithms are compu-tationally efficient, and can even be implemented on the networkelements. Our simulation, on some standard core networks, showthat our algorithms work well in practice as well.Index Terms—Approximation algorithms, fast shared restora-tion, local reroute, MPLS, optical, pre-provisioning.I. INTRODUCTIONMODERN backbone and transport networks are highlycomplex networks that strive to carry services with QoSguarantees. These networks support general topologies and dy-namic routing of bandwidth guaranteed connections, yet at thesame time they aim to provide fast recovery from network fail-ures. Traditionally, ring-based SONET networks have offeredclose to 50 ms restoration to bandwidth guaranteed services,using pre-reserved spare protection capacity and pre-plannedprotection paths. Pre-planning protection in rings has beenespecially attractive, because of the availability of exactly onebackup path between any two nodes, leading to very simpleand fast automatic protection switching mechanisms. However,in ring-based SONET networks these advantages come at theManuscript received October 25, 2004; revised August 16, 2005, and January5, 2006; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor A.Somani. A preliminary version of this paper appeared in IEEE INFOCOM 2004,Hong Kong.The authors are with Bell Labs, Lucent Technologies, Murray Hill, NJ 07974USA (e-mail: [email protected]).Digital Object Identifier 10.1109/TNET.2007.892844cost of reserving at least half the total capacity for protection,thus requiring 100% redundancy.Recently, mesh-based networks have received much atten-tion due to the increased flexibility they provide in routingconnections, thus leading to more efficient utilization of net-work resources. Also mesh networks are appealing due to thehigh degree of protection capacity sharing that is possible inthese networks, offering the promise of fast restoration timesof ring-based SONET networks for just a small fraction ofthe total capacity, reserved for protection. However, it hasremained a challenging problem to design such efficient pro-tection schemes for mesh networks. In general most protectionschemes, including those for SONET and ring-based schemes,have been designed to protect against a single link failure. Itis also a challenging problem to design efficient protectionschemes that protect against multiple link failures for meshnetworks.Recently, a fast (local) reroute [9] approach to restora-tion has gained momentum in the context of Multi-Pro-tocol-Label-Switching (MPLS) [5] networks. The MPLS fastor local reroute supports a local repair capability where upona node or link failure the first node upstream from the failurereroutes the effected Label Switch Paths (LSP) onto bypass(backup) tunnels with equivalent guaranteed bandwidths,thereby achieving faster restoration times. The MPLS fastreroute mechanism allows for bandwidth sharing betweenbypass tunnels protecting independent resources, thus resultingin efficient capacity utilization.Two different techniques for local protection in MPLSnetworks have been proposed [22]. The one-to-one backuptechnique [1], [13], [15] creates bypass LSPs for each protectedservice carrying LSP, at each potential point (link or node) oflocal repair. The facility backup technique [29] creates a bypasstunnel to protect a potential failure point (link or node), such thatby taking advantage of the MPLS label stacking mechanism, acollection of LSPs with similar backup constraints can be jointlyrerouted, over a single bypass tunnel. In general, the one-to-onebackup technique does not scale very well with the number ofsupported protected LSPs, since the number of bypass tunnelscan quickly become very large, not to mention the enormousload on signaling and routing to support these extra tunnels. Inaddition, for implementing the one-to-one backup technique,either extensive routing extensions are needed to propagatethe set of bypass LSPs and their attribute information [1],resulting in heavy load on the control plane, or the amountof achievable sharing of protection capacity is sacrificed, bylimiting the amount of state that is propagated in the routingupdates [13], thus requiring large amounts of spare capacityfor protection.1063-6692/$25.00 © 2007 IEEEALICHERRY AND BHATIA: SIMPLE PRE-PROVISIONING SCHEME TO ENABLE FAST RESTORATION 401The facility backup technique is free from many of the draw-backs of the one-to-one backup technique. In addition, whenused in conjunction with pre-computation and pre-reservationof protection bandwidth (and bypass tunnels), facility backupcan be implemented, without any or minimal routing extensions[29]. (In MPLS it is possible to pre-install a set of bypass tunnelsthat may share protection bandwidth, by assigning zero band-width [29] to each tunnel.)