loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2003 International Conference on Dependable Systems and Networks (DSN'03)
LSRP: Local Stabilization in Shortest Path Routing
San Francisco, California
June 22-June 25
ISBN: 0-7695-1952-0
Anish Arora, Ohio State University
Hongwei Zhang, Ohio State University
We formulate a notion of local stabilization, by which a system self-stabilizes in time proportional to the size of any perturbation that changes the network topology or the state of nodes. The notion implies that the part of the network involved in the stabilization includes at most the nodes whose distance from the perturbed nodes is proportional to the perturbation size. Also, we present LSRP, a protocol for local stabilization in shortest path routing. LSRP achieves local stabilization via two techniques. First, it layers system computation into three diffusing waves with different propagation speeds, i.e., "stabilization wave" with the lowest speed, "containment wave" with intermediate speed, and "super-containment wave" with the highest speed. The containment wave contains mistakenly initiated stabilization wave, the super-containment wave contains mistakenly initiated containment wave, and the super-containment wave self-stabilizes itself locally. Second, LSRP avoids forming loops during stabilization, and it removes all transient loops within small constant time. To the best of our knowledge, LSRP is the first protocol that achieves local stabilization in shortest path routing.
Citation:
Anish Arora, Hongwei Zhang, "LSRP: Local Stabilization in Shortest Path Routing," dsn, pp.139, 2003 International Conference on Dependable Systems and Networks (DSN'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.