Enhancing the computation of distributed shortest paths on real dynamic networks

Gianlorenzo D'Angelo 1 Mattia D'Emidio 2 Daniele Frigioni 2 Daniele Romano 2
1 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 : The problem of finding and updating shortest paths in distributed networks is considered crucial in today's practical applications. In the recent past, there has been a renewed interest in devising new efficient distance-vector algorithms as an attractive alternative to link-state solutions for large-scale Ethernet networks, in which scalability and reliability are key issues or the nodes can have limited storage capabilities. In this paper we present Distributed Computation Pruning (DCP), a new technique, which can be combined with every distance-vector routing algorithm based on shortest paths, allowing to reduce the total number of messages sent by that algorithm and its space occupancy per node. To check its effectiveness, we combined DCP with DUAL (Diffuse Update ALgorithm), one of the most popular distance-vector algorithm in the literature, which is part of CISCO's widely used EIGRP protocol, and with the recently introduced LFR (Loop Free Routing) which has been shown to have good performances on real networks. We give experimental evidence that these combinations lead to a significant gain both in terms of number of messages sent and memory requirements per node.
Type de document :
Communication dans un congrès
Guy Even and Dror Rawitz. 1st Mediterranean Conference on Algorithms, Dec 2012, Ein-Gedi, Israel. Springer, 7659, pp.148-158, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-34862-4_11〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00755395
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : mercredi 21 novembre 2012 - 10:43:34
Dernière modification le : lundi 4 décembre 2017 - 15:14:09
Document(s) archivé(s) le : vendredi 22 février 2013 - 03:47:19

Fichier

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

Identifiants

Collections

Citation

Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Daniele Romano. Enhancing the computation of distributed shortest paths on real dynamic networks. Guy Even and Dror Rawitz. 1st Mediterranean Conference on Algorithms, Dec 2012, Ein-Gedi, Israel. Springer, 7659, pp.148-158, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-34862-4_11〉. 〈hal-00755395〉

Partager

Métriques

Consultations de la notice

230

Téléchargements de fichiers

137