On the Communication Complexity of Distributed Name-Independent Routing Schemes

3 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : We present a distributed asynchronous algorithm that, for every undirected weighted $n$-node graph $G$, constructs name-independent routing tables for $G$. The size of each table is $\tO(\sqrt{n}\,)$, whereas the length of any route is stretched by a factor of at most~$7$ w.r.t. the shortest path. At any step, the memory space of each node is $\tO(\sqrt{n}\,)$. The algorithm terminates in time $O(D)$, where $D$ is the hop-diameter of $G$. In synchronous scenarios and with uniform weights, it consumes $\tO(m\sqrt{n} + n^{3/2}\min\set{D,\sqrt{n}\,})$ messages, where $m$ is the number of edges of $G$. In the realistic case of sparse networks of poly-logarithmic diameter, the communication complexity of our scheme, that is $\tO(n^{3/2})$, improves by a factor of $\sqrt{n}$ the communication complexity of \emph{any} shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [24 references]

https://hal.archives-ouvertes.fr/hal-00851217
Contributor : David Ilcinkas Connect in order to contact the contributor
Submitted on : Thursday, October 24, 2013 - 9:38:49 AM
Last modification on : Tuesday, February 9, 2021 - 3:00:04 PM
Long-term archiving on: : Wednesday, April 5, 2017 - 8:45:38 PM

File

disc-12.pdf
Files produced by the author(s)

Identifiers

• HAL Id : hal-00851217, version 1

Citation

Cyril Gavoille, Christian Glacet, Nicolas Hanusse, David Ilcinkas. On the Communication Complexity of Distributed Name-Independent Routing Schemes. DISC 2013, Oct 2013, Jérusalem, Israel. pp.418-432. ⟨hal-00851217⟩

Record views