×

Enhancing the computation of distributed shortest paths on real dynamic networks. (English) Zbl 1347.68017

Even, Guy (ed.) et al., Design and analysis of algorithms. First Mediterranean conference on algorithms, MedAlg 2012, Kibbutz Ein Gedi, Israel, December 3–5, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-34861-7/pbk). Lecture Notes in Computer Science 7659, 148-158 (2012).
Summary: 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 this paper we present Distributed Computation Pruning (DCP), a new technique, which can be combined with every distance-vector 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, 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.
For the entire collection see [Zbl 1259.68004].

MSC:

68M10 Network design and communication in computer systems
68W15 Distributed algorithms
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI HAL