Loop-Free Routing Using Diffusing Computations

Abstract-A family of distributed algorithms for the dynamic computation of the shortest paths in a computer network or Memet is presented, validated, and analyzed. According to these algorithms, each node maintains a vector with its distance to every other node. Update messages from a node are sent only to its neighbors; each such message contains a dktance vector of one or more entries, and each entry specifies the length of the selected path to a network destination, as well as m indication of whether the entry constitutes an update, a query, or a reply to a previous query. The new algorithms treat the problem of distributed shortest-path routing as one of diffusing computations, which was firzt proposed by Dijkztra and Scholten. They improve on algorithms introduced previously by Chandy and Misra, JatYe and Moss, Merlin and Segatl, and the author. The new algorithms are shown to converge in finite time after an arbitrary sequence of link coat or topological changes, to be loop-free at every instan ~ and to outperform all other loop-free routing algorithms previously proposed from the standpoint of the combined temporal, message, and storage complexities. I