IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 15, NO. 2, APRIL 2007 359Fast Local Rerouting for HandlingTransient Link FailuresSrihari Nelakuditi, Member, IEEE, Sanghwan Lee, Yinzhe Yu, Zhi-Li Zhang, Member, IEEE, andChen-Nee Chuah, Senior Member, IEEEAbstract—Link failures are part of the day-to-day operationof a network due to many causes such as maintenance, faultyinterfaces, and accidental fiber cuts. Commonly deployed linkstate routing protocols such as OSPF react to link failures throughglobal link state advertisements and routing table recomputa-tions causing significant forwarding discontinuity after a failure.Careful tuning of various parameters to accelerate routing con-vergence may cause instability when the majority of failuresare transient. To enhance failure resiliency without jeopardizingrouting stability, we propose a local rerouting based approachcalled failure insensitive routing. The proposed approach preparesfor failures using interface-specific forwarding, and upon a failure,suppresses the link state advertisement and instead triggers localrerouting using a backwarding table. With this approach, when nomore than one link failure notification is suppressed, a packet isguaranteed to be forwarded along a loop-free path to its destina-tion if such a path exists. This paper demonstrates the feasibility,reliability, and stability of our approach.Index Terms—Fast rerouting, interface-specific forwarding,transient failures.I. INTRODUCTIONTHE Internet has seen tremendous growth in the past decadeand has now become the critical information infrastruc-ture for both personal and business applications. It is expectedto be always available as it is essential to our daily commer-cial, social, and cultural activities. Service disruption for evena short duration could be catastrophic in the world of e-com-merce, causing economic damage as well as tarnishing the repu-tation of a network service provider. In addition, many emergingservices such as Voice over IP and virtual private networks forfinance and other real-time business applications require strin-gent service availability and reliability. Unfortunately, failuresare fairly common in the everyday operation of a network dueManuscript received July 29, 2004; revised December 11, 2005; approved byIEEE/ACM TRANSACTIONS ON NETWORKING Editor T. Griffin. This work wassupported in part by the National Science Foundation under Grant ANI-0073819and Grant ITR-0085824 and CAREER Award NCR-9734428 and Award CNS-0448272.S. Nelakuditi is with the Department of Computer Science and Engi-neering, University of South Carolina, Columbia, SC 29205 USA (e-mail:[email protected]).S. Lee is with the Kookmin University, Seongbuk-gu, Seoul 136-702, SouthKorea (e-mail: [email protected]).Y. Yu was with the Department of Computer Science, University of Min-nesota, Minneapolis, MN 55455 USA. He is now with Microsoft, Redmond,WA 98052 USA (e-mail: [email protected]).Z.-L. Zhang is with the Department of Computer Science, University of Min-nesota, Minneapolis, MN 55455 USA (e-mail: [email protected]).C.-N. Chuah is with the Department of Electrical and Computer Engineering,University of California, Davis, CA 95616 USA (e-mail: [email protected]).Digital Object Identifier 10.1109/TNET.2007.892851to various causes such as maintenance, faulty interfaces, andaccidental fiber cuts [1], [2]. Moreover, it was observed thatmost failures are transient (i.e., short-lived): 50% last less thana minute. Hence, there is a growing demand for failure resilientrouting protocols that ensure high service availability and relia-bility despite transient link failures.The link-state routing protocols such as OSPF and ISIS,which are commonly deployed in today’s networks, react tolink failures by having routers detect adjacent link failures, dis-seminate link-state changes, and then recompute their routingtables using the updated topology information. Recent studies[1], [3] have reported that the resumption of forwarding after alink failure typically takes several seconds. During this period,some destinations could not be reached and the packets tothose destinations would be dropped. In today’s high-speednetworks, even a short recovery time can cause huge packetlosses. For example, if an OC-48 link is down for 10 s, closeto 3 million packets (assuming an average packet size of 1 kB)could be lost! Such discontinuity in packet forwarding has anadverse effect on the performance of TCP, in particular whendelay bandwidth product is large. Furthermore, such servicedisruption, albeit relatively short, is deemed unacceptable formany continuous media applications such as carrier-gradeVoice over IP.There have been some proposals [3]–[5] for accelerating theconvergence of link-state routing protocols. The general recipecalls for fine tuning of several parameters associated with linkfailure detection, link-state dissemination and routing table re-computation. Although these remedies can improve the conver-gence time of routing protocols, they run the risk of introducinginstability in the network, in particular, in the face of frequenttransient link failures. Faster convergence requires immediateadvertisement of a failure event that may last only a few sec-onds; just as the new routing tables are computed, they needto be recomputed again due to new link-state updates. More im-portantly, such advertisements of internal link-state changes cancause a large churn of external routes due to hot-potato routingoften employed in the Internet [6]. On the other hand, delayedadvertisement of a failure by the adjacent node would increaseforwarding discontinuity; other nodes that are unaware of thefailure continue to route packets along the failed link whichget dropped at the adjacent node. The fundamental problemwith these schemes is that they react after the failure of a linkand forwarding is disrupted till the optimal routes are globallyrecomputed.Multiprotocol label switching (MPLS)-based approaches tofailure recovery [7] leverage explicit routing for fast rerouting.An explicitly routed protection LSP (label switched path) is1063-6692/$25.00 © 2007 IEEE360 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 15, NO. 2, APRIL 2007set up to provide a backup path for each vulnerable physicallink. The protection LSP acts as a parallel virtual link. Whenthe physical link fails, the upstream node switches traffic fromthe physical link to the virtual link. The label stacking capa-bility of