On the distributed Bellman–Ford algorithm and the looping problem

On the distributed Bellman–Ford algorithm and the looping problem

0.00 Avg rating0 Votes
Article ID: iaor200952677
Country: United States
Volume: 19
Issue: 4
Start Page Number: 542
End Page Number: 551
Publication Date: Oct 2007
Journal: INFORMS Journal On Computing
Authors: , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.