520 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 14, NO. 3, JUNE 2006LSRP: Local Stabilization in Shortest Path RoutingAnish Arora, Senior Member, IEEE, and Hongwei Zhang, Student Member, IEEEAbstract—We formulate a notion of local stabilization, by whicha system self-stabilizes in time proportional to the size of any per-turbation that changes the network topology or the state of nodes.The notion implies that the part of the network involved in thestabilization includes at most the nodes whose distance from theperturbed nodes is proportional to the perturbation size. Also, wepresent LSRP, a protocol for local stabilization in shortest pathrouting. LSRP achieves local stabilization via two techniques. First,it layers system computation into three diffusing waves each havinga different propagation speed, i.e., “stabilization wave” with thelowest speed, “containment wave” with intermediate speed, and“super-containment wave” with the highest speed. The contain-ment wave contains the mistakenly initiated stabilization wave, thesuper-containment wave contains the mistakenly initiated contain-ment wave, and the super-containment wave self-stabilizes itselflocally. Second, LSRP avoids forming loops during stabilization,and it removes all transient loops within small constant time. Tothe best of our knowledge, LSRP is the first protocol that achieveslocal stabilization in shortest path routing.Index Terms—Containment region, local stabilization, perturba-tion size, range of contamination, shortest path routing.I. INTRODUCTIONAWELL-KNOWN ideal in networking is the ability to with-stand failure or compromise of one or more regions in anetwork without impacting a large part of the network. Yet, inmany instances, we find that even a small fault-perturbed regionimpacts a large part of the network, as the effects of the faultspropagate to and contaminate far away nodes. An example isinter-domain routing in the Internet by the Border Gateway Pro-tocol (BGP), where faults at some edge routers can propagateacross the whole Internet [1], [2].Unbounded fault propagation decreases not only the There-fore, in large-scale networks such as the Internet and theemerging wireless sensor networks [2]–[4], it is desirable thatfaults be contained locally around the regions where they haveoccurred, and that the time taken for a system to stabilizeis a functionof the size of the fault-perturbed regions in-stead of the size of the system. We call this property-localstabilization.Local Stabilization in Routing: One problem where-localstabilization is critical but remains unsolved is the basic problemManuscript received October 7, 2003; revised January 25, 2005; approvedby IEEE/ACM TRANSACTIONS ON NETWORKING Editor A. Fumagalli. An ex-tended abstract containing some preliminary results of this paper appeared in2003 IEEE IFIP International Conference on Dependable Systems and Net-works (DSN-’2003). This work was supported in part by DARPA under Con-tract OSU-RF #F33615-01-C-1901, NSF grant CCR-034170, and two grantsfrom Microsoft Research.The authors are with the Department of Computer Science and Engineering,The Ohio State University, Columbus, OH 43210 USA (e-mail: [email protected]; [email protected]).Digital Object Identifier 10.1109/TNET.2006.876179of shortest path routing in networks. Generally speaking, thereare two categories of routing protocols: linkstate and distance-vector. In link-state protocols, each node maintains the topo-logical information of a whole network, and-local stabiliza-tion is impossible, since every single change in the networktopology has to be propagated to every node in the network.In distance-vector protocols, each node only maintains the dis-tance of and the next-hop on its shortest path to each destinationin the network. Thus,-local stabilization is conceivable in dis-tance-vector protocols.Distance-vector (and its variant, path-vector) protocols forthe Internet, such as Routing Information Protocol (RIP) andBGP, have long been studied [5]. Distance-vector protocols formobile ad hoc networks, such as Destination Sequenced Dis-tance-Vector (DSDV) and Ad hoc On-Demand Distance-Vector(AODV), have also been proposed [6]. In designing theseprotocols, researchers have typically concentrated on how toavoid routing loops and the count-to-infinity problem. Localstabilization is not guaranteed: small-scale local perturbations(such as memory overflow) can propagate globally across awhole network, due to the diffusing nature of these protocols[2], and result in severe instability [2], [7]. Moreover, thefault model has been typically limited to node and link faultssuch as crash, repair, and congestion; state corruption is notconsidered. However, several kinds of state corruption do ariseas a result of misconfiguration and faulty software, and areknown to be major causes for routing instability [1], [2], [8].And theoretically speaking, even simple faults such as nodecrash and message loss, can drive a network into arbitrary states[9]. Therefore,-local stabilization is desirable, and not onlyin the presence of node/link crash, repair, and congestion butalso in the presence of state corruption.Related Work: The concept of fault containment is proposedin [10], [11], and [3]. Nevertheless, [10] and [11] only considerfault containment for the major part of system states, which isnot strict enough to guarantee that the amount of work (for ex-ample, the number of protocol actions executed) needed for asystem to stabilize is a function of the perturbation size; [3]only considers the case where the impact of every fault is withinconstant distance from where it occurs, which is too strict to beapplied to problems such as routing, where the locality of theproblem1is not constant.A locally stabilizing protocol, GS, is proposed in [4] forclustering as well as shortest path routing in wireless sensornetworks where nodes are densely distributed. To achieve localstabilization, GStakes advantage of the high node distributiondensity and the geographic information on node distribution; thesensor network model assumed by GSmakes it inapplicable to1We regard the locality of a problem as the maximum minimum distance be-tween any two nodes that have to be involved in the definition of the problem.1063-6692/$20.00 © 2006 IEEEARORA AND ZHANG: LSRP: LOCAL STABILIZATION IN SHORTEST PATH ROUTING 521other general networks such as the Internet. In [10], algorithmsare proposed to contain