A loop-free shortest-path routing algorithm for dynamic networks

作者：D'Angelo Gianlorenzo; D'Emidio Mattia^*; Frigioni Daniele

来源：Theoretical Computer Science, 2014, 516: 1-19.

DOI：10.1016/j.tcs.2013.11.001

• Distributed networks
• Loop-free routing
• Shortest-path
• Dynamic algorithms

This work introduces Loop-Free Routing (LFR), a new loop-free distance-vector routing algorithm, which is able to update the shortest paths of a distributed network in fully dynamic scenarios.
This work also provides an evaluation based on simulations of LFR and Diffuse Update ALgorithm (DUAL), one of the most popular loop-free distance-vector algorithms, which is part of CISCO's widely used Enhanced Interior Gateway Routing Protocol (EIGRP). The simulations are performed on dynamic scenarios based on both real-world and controlled instances. The simulations show that LFR is always the best choice in terms of memory requirements, while in terms of messages sent LFR outperforms DUAL on real-world networks, whereas DUAL is the best choice on controlled scenarios.

• 出版日期2014-1-9
• 单位Perugia