A fast distributed shortest path algorithm for a class of hierarchically structured data networks

A distributed algorithm is presented which finds the shortest path from every node in the network to a given destination node. The network topology is assumed to be organizable into a generalized balanced-tree hierarchy (BH). The BH topology is introduced and characterized, and it is shown that most large interconnected data networks are of this type. It is also shown that the algorithm converges in an asynchronous environment. Therefore, some of the difficulties associated with synchronizing the order of events can be avoided in the actual implementation of the proposed algorithm