On the Distributed Bellman-Ford Algorithm and the Looping Problem
Kevin R. Hutson, Terri L. Schlosser, Douglas R. Shier
INFORMS Journal on Computing · 2007 · Volume 19 · Issue 4
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.
Keywords
adaptive routing, communication networks, distributed computing, looping, shortest paths, trees
Enable JavaScript for citation tools and additional paper interactions.