Compact Routing with Name Independence

Abstract

This talk discusses compact routing in the name independent model first introduced by Awerbuch et al. for adaptive routing in dynamic networks. Compact routing is the problem of finding good tradeoffs between the amount of space used to store routing tables and the length of the paths the routing algorithm specifies. For space we focus on the maximum space required per node in a network, and for path lengths we consider the stretch, which is defined as the maximum ratio of the length of a path taken between a pair of nodes, to the length of the optimal path between those two nodes. Our work presents solutions in the name-independent model, referring to our assumption that the graph may not be relabelled in a way that encodes topological information. A compact routing scheme that uses $\tilde{O}(n^{1/2})$-sized local routing tables, $O(\log^2 n)$-sized packet headers, and stretch bounded by 5 is obtained. Alternative schemes reduce the packet header size to $O(\log n)$ at cost of either increasing the stretch to 7, or increasing the table size to $\tilde{O}(n^{2/3})$. For smaller table-size requirements, the ideas in these schemes are generalized to a scheme that uses $O(\log^2 n)$-sized headers, $\tilde {O}(k^2n^{2/k})$-sized tables, and achieves a stretch of $\min\{ 1 + (k-1)(2^{k/2}-2), 16k^2+4k \}$, improving the best previously-known name-independent scheme due to Awerbuch and Peleg. This is joint work with M. Arias, L. Cowen, R. Rajmohan and O. Taka.