Engineering a new algorithm for distributed shortest paths on dynamic networks

Serafino Cicerone 1 Gianlorenzo D'Angelo 1, 2 Gabriele Di Stefano 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 study the problem of dynamically updatingall-pairs shortest paths in a distributed network while edge update operations occur to the network. We consider the practical case of a dynamic network in which an edge update can occur while one or more other edge updates are under processing. A node of the network might be affected by a subset of these changes, thus being involved in the concurrent executions related to such changes. In this paper, we provide a new algorithm for this problem, and experimentally compare its performance with respect to those of the most popular solutions in the literature: the classical distributed Bellman-Ford method, which is still used in real network and implemented in the RIP protocol, and DUAL, the Diffuse Update ALgorithm, which is part of CISCO's widely used EIGRP protocol. As input to the algorithms, we used both real-world and artificial instances of the problem. The experiments performed show that the space occupancy per node required by the new algorithm is smaller than that required by both Bellman-Ford and DUAL. In terms of messages, the new algorithm outperforms both Bellman-Ford and DUAL on the real-world topologies, while on artificial instances, the new algorithm sends a number of messages that is more than that of DUAL and much smaller than that of Bellman-Ford.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2012, <10.1007/s00453-012-9623-9>
Liste complète des métadonnées


https://hal.inria.fr/hal-00728876
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : jeudi 6 septembre 2012 - 19:03:24
Dernière modification le : vendredi 7 septembre 2012 - 09:44:31
Document(s) archivé(s) le : vendredi 7 décembre 2012 - 03:43:45

Fichier

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

Identifiants

Collections

Citation

Serafino Cicerone, Gianlorenzo D'Angelo, Gabriele Di Stefano, Daniele Frigioni, Vinicio Maurizio. Engineering a new algorithm for distributed shortest paths on dynamic networks. Algorithmica, Springer Verlag, 2012, <10.1007/s00453-012-9623-9>. <hal-00728876>

Partager

Métriques

Consultations de
la notice

184

Téléchargements du document

149