Distributed routing algorithm performance in hostile environments

The authors consider the problem of optimum shortest-path routing in a communications network consisting of multiple nodes and links located in a hostile environment. The robustness of the routing algorithm to node or link failures is of interest here. The type of environment suggests that use of distributed or noncentralized algorithms in which convergence of the network to the shortest-path routing tables is of primary concern. Two distributed routing algorithms (that of L.R. Ford, Jr., and D.R. Fulkerson, Flows in Networks. Princeton, NJ: Princeton Univ. Press, 1962, and that of P.M. Merlin and S. Segall, IEEE Trans. Commun. vol. COM-27, 1280-7, Sept. 1979) are examined in terms of speed and overhead. Computer simulations measure algorithm performance in a simple network and also in a satellite shell network. Both algorithms discussed have advantages and disadvantages, but the Merlin and Segall algorithm is shown to provide exclusive freedom from packet looping