A Failsafe Distributed Routing Protocol.

摘要

An algorithm for constructing and adaptively maintaining routing tables in communication networks is presented. The algorithm can be employed in store-and-forward as well as line switching networks, uses distributed computation, provides routing tables that are loop-free for each destination at all times, adapts to changes in network flows and is completely failsafe. The latter means that after arbitrary failures and additions, the network recovers in finite time in the sense of providing routing paths between all physically connected nodes. Complete rigorous proofs of all these properties are provided. (Author)