Abstract

Distributed algorithms for shortest-path problems are important in the context of routing in computer communication networks. We present a protocol that maintains the shortest-path routes in a dynamic topology, that is, in an environment where links and nodes can fail and recover at arbitrary times. The novelty of this protocol is that it avoids the bouncing effect and the looping problem that occur in the previous approaches of the distributed implementation of Bellman-Ford algorithm. The bouncing effect refers to the very long duration for convergence when failures happen or weights increase, and the nonterminating exchanges of messages, or counting-to-infinity behavior, in disconnected components of the network resulting from failures. The looping problems cause data packets to circulate and, thus, waste bandwidth. These undesirable effects are avoided without any increase in the overall message complexity of previous approaches required in the connected part of the network. The time complexity is better than the distributed Bellman-Ford algorithm encountering failures. The key idea in the implementation is to maintain only loop-free paths, and search for the shortest path only from this set.

Keywords

Computer scienceShortest path problemPath vector protocolDistributed computingRouting protocolNetwork packetConstrained Shortest Path FirstRouting (electronic design automation)Private Network-to-Network InterfaceMathematical optimizationNetwork topologyPath (computing)Convergence (economics)Computer networkLink-state routing protocolTopology (electrical circuits)K shortest path routingMathematicsTheoretical computer science

Affiliated Institutions

Related Publications

Publication Info

Year
1989
Type
article
Pages
224-236
Citations
191
Access
Closed

External Links

Social Impact

Social media, news, blog, policy document mentions

Citation Metrics

191
OpenAlex

Cite This

C. Cheng, Richard D Riley, S. P. R. Kumar et al. (1989). A loop-free extended Bellman-Ford routing protocol without bouncing effect. , 224-236. https://doi.org/10.1145/75246.75269

Identifiers

DOI
10.1145/75246.75269