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 , 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.
Type de document :
Communication dans un congrès
11th International Symposium on Experimental Algorithms (SEA2012), Jun 2012, Bordeaux, France. Springer, 7276, pp.123-134, 2012, Lecture Notes in Computer Science. <10.1007/978-3-642-30850-5_12>
Liste complète des métadonnées


https://hal.inria.fr/hal-00729005
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : vendredi 7 septembre 2012 - 11:22:24
Dernière modification le : vendredi 7 septembre 2012 - 16:15:20
Document(s) archivé(s) le : samedi 8 décembre 2012 - 03:40:38

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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. Springer, 7276, pp.123-134, 2012, Lecture Notes in Computer Science. <10.1007/978-3-642-30850-5_12>. <hal-00729005>

Partager

Métriques

Consultations de
la notice

167

Téléchargements du document

213