Yih Huang and Philip K. McKinley
February, 1998
Traditionally, link-state routing (LSR) uses two costly techniques to achieve its robustness and responsiveness: message forwarding on every communication link in the broadcast of network status updates, and the periodic broadcast of local status by every router. In this paper, we present a novel LSR protocol, called Tree-based LSR (T-LSR), which reduces the operational overhead of LSR as follows. A leader router is elected to periodically broadcast network status on behalf of all the other routers in the network, and a spanning tree is constructed to support these broadcasts. We prove the correctness of the T-LSR protocol, namely, its ability to maintain consistent routing information and leader preferences throughout the network under any combination of network component failures, partitioning scenarios, and undetected transmission errors. The results of a simulation study demonstrate that the T-LSR protocol imposes a small fraction of the overhead of conventional LSR during periods of normal operation, and incurs moderate overhead during adverse periods when an election is in progress or the spanning tree is under repair or construction.
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format.