A Speed-Up Technique for Distributed Shortest Paths Computation

Gianlorenzo D'Angelo 1, 2 Mattia D'Emidio 1 Daniele Frigioni 1 Vinicio Maurizio 1
1 UNIVAQ - University of L'Aquila [Italy]
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 propose a simple and practical speed-up 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. We combine the new technique with two algorithms known in the literature: DUAL, which is part of CISCO's widely used EIGRP protocol, and the recent DUST, which has been shown to be very effective on networks with power law node degree distribution. We give experimental evidence that these combinations lead to an important gain in terms of the number of messages sent by DUAL and DUST at the price of a little increase in terms of space occupancy per node.
Type de document :
Communication dans un congrès
Beniamino Murgante and Osvaldo Gervasi and Andrés Iglesias and David Taniar and Bernady O. Apduhan. 11th International Conference on Computational Science and Its Applications (ICCSA 2011), Jun 2011, Santander, Spain. Springer, 6783, pp.578-593, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-21887-3_44〉
Liste complète des métadonnées
https://hal.inria.fr/hal-00644049
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : mercredi 23 novembre 2011 - 14:51:50
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : vendredi 24 février 2012 - 02:27:07

Fichier

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

Identifiants

Collections

INRIA | I3S | UNICE | UNIV-COTEDAZUR

Citation

Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Vinicio Maurizio. A Speed-Up Technique for Distributed Shortest Paths Computation. Beniamino Murgante and Osvaldo Gervasi and Andrés Iglesias and David Taniar and Bernady O. Apduhan. 11th International Conference on Computational Science and Its Applications (ICCSA 2011), Jun 2011, Santander, Spain. Springer, 6783, pp.578-593, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-21887-3_44〉. 〈hal-00644049〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

272

Téléchargements de fichiers

208

Contact


archive-ouverte@inria.fr