Engineering a new loop-free shortest paths routing algorithm

Gianlorenzo d'Angelo 1, 2 Mattia d'Emidio 1 Daniele Frigioni 1 Vinicio Maurizio 1
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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 Phi is the total number of nodes affected by a set of updates to the network, and phi is the maximum number of destinations for which a node is affected, then LFR requires O(Phi*Delta) messages and O(n + phi*Delta) space per node, where Delta 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(Phi*Delta) messages and Θ(n*Delta) 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 require- ments, while in terms of messages LFR outperforms DUAL on real-world instances, whereas DUAL is the best choice on artificial instances.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [20 references]  Display  Hide  Download
Contributor : Gianlorenzo d'Angelo <>
Submitted on : Friday, September 7, 2012 - 11:22:24 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Saturday, December 8, 2012 - 3:40:38 AM


Files produced by the author(s)




Gianlorenzo d'Angelo, Mattia d'Emidio, Daniele Frigioni, Vinicio Maurizio. Engineering a new loop-free shortest paths routing algorithm. 11th International Symposium on Experimental Algorithms (SEA2012), Jun 2012, Bordeaux, France. pp.123-134, ⟨10.1007/978-3-642-30850-5_12⟩. ⟨hal-00729005⟩



Record views


Files downloads