Kevin R. Hutson

Terrri L. Schlosser

Douglas R. Shier

Abstract: The classic Bellman-Ford algorithm for calculating shortest paths can be easily adapted to a distributed environment in which the computations are performed locally by identical processors at each network node. A distributed shortest-path algorithm is particularly appropriate for use in communication networks to capitalize on local information rather than rely on a central controller. This paper discusses the behavior of a synchronous version of the distributed Bellman-Ford algorithm in a dynamic environment in which communication link costs can undergo change. Several algorithms are described that mitigate or eliminate the occurrence of looping, which is responsible for degrading the performance of distributed shortest-path algorithms. We provide theoretical and computational evidence to show that two proposed algorithms offer improvements upon the original and modified Bellman-Ford algorithms.

Key Words: adaptive routing, communication networks, distributed computing, looping, shortest paths, trees