Engineering a New Loop-Free Shortest Paths Routing Algorithm

摘要

We present LFR (Loop Free Routing), a new loop-free distance vector routing algorithm, which is able to update the shortest paths of a distributed network with n nodes in fully dynamic scenarios. If φ is the total number of nodes affected by a set of updates to the network, and φ is the maximum number of destinations for which a node is affected, then LFR requires O(φ · Δ) messages and O(n + φ • Δ) space per node, where Δ is the maximum degree of the nodes of the network. We experimentally compare LFR with DUAL, one of the most popular loop-free distance vector algorithms, which is part of CISCO'S EIGRP protocol and requires O(φ · Δ) messages and Θ(n · Δ) space per node. The experiments are based on both real-world and artificial instances and show that LFR is always the best choice in terms of memory requirements, while in terms of messages LFR outperforms DUAL on real-world instances, whereas DUAL is the best choice on artificial instances.