Stabilization of General Loop-Free Routing

✍ Scribed by Jorge A. Cobb; Mohamed G. Gouda

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 223 KB
• Volume: 62
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2001.1830

✦ Synopsis

We present a protocol for maintaining a spanning tree that is maximal with respect to any given (bounded and monotonic) routing metric. This protocol has two interesting adaptive properties. First, the protocol is stabilizing: starting from any state, the protocol stabilizes to a state where a maximal tree is present. Second, the protocol is loop-free: starting from any state where a spanning tree is present, the protocol stabilizes, without forming any loops, to a state where a maximal tree is present. The stabilization time of this protocol is Oðn degÞ, where n is the number of nodes, and deg is the node degree in the network.