# 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 },}