GGHI13
Summary
Gavoille, Cyril, Glacet, Christian, Hanusse, Nicolas and Ilcinkas, David (2013) On the Communication Complexity of Distributed Name-Independent Routing Schemes. In $27^{th}$ International Symposium on Distributed Computing (DISC). oct. Springer, page 12. ((URL)) (PDF)
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 {$\tilde{O}(\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 {$\tilde{O}(\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 {$\tilde{O}(m\sqrt{n} + n^{3/2}\min\{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 {$\tilde{O}(n^{3/2})$}, improves by a factor of {$\sqrt{n}$} the communication complexity of any shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest.
Bibtex entry
@INPROCEEDINGS { GGHI13,
AUTHOR = { Gavoille, Cyril and Glacet, Christian and Hanusse, Nicolas and Ilcinkas, David },
TITLE = { On the Communication Complexity of Distributed Name-Independent Routing Schemes },
BOOKTITLE = { $27^{th}$ International Symposium on Distributed Computing (DISC) },
PUBLISHER = { Springer },
LOCATION = { Jerusalem, Israel },
VOLUME = { 8205 },
SERIES = { Lecture Notes in Computer Science },
PAGES = { 12 },
MONTH = { oct },
YEAR = { 2013 },
KEYWORDS = { compact routing, distributed },
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 {$\tilde{O}(\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 {$\tilde{O}(\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 {$\tilde{O}(m\sqrt{n} + n^{3/2}\min\{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 {$\tilde{O}(n^{3/2})$}, improves by a factor of {$\sqrt{n}$} the communication complexity of any shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest. },
URL = { http://hal.archives-ouvertes.fr/hal-00851217/ },
PDF = { http://hal.archives-ouvertes.fr/hal-00851217/PDF/disc-12.pdf },
}