Stabilizing Hierarchical Routing.

Hierarchical routing provides a less expensive algorithm compared to the traditional all-pairs routing algorithms. We present an algorithm in this paper which benefits from the lower memory requirement, faster routing table lookup, and less costly broadcast exemplified by hierarchical routing, and yet maintains routing capability of all pairs of connected nodes even in the presence of faults, such as link/node failures and repairs, and corruption of program variables. Additionally, this algorithm solves the problem of cluster partitioning where nodes that are supposed to be in the same subset of the network, become isolated due to link or node failures. Being self-stabilizing, starting from an arbitrary state (with possibly corrupted routing tables), the protocol is guaranteed to reach a configuration with routing tables containing valid entries in a finite time. The protocol automatically updates the shortest paths in the face of dynamically changing link weights. The proposed protocol also dynamically allocates/deallocates storage for the routing information as the network size changes. The algorithm works on an arbitrary topology and under a distributed daemon model. [ABSTRACT FROM AUTHOR]