Compact Name-Independent Routing with Minimum Stretch

Ittai Abraham Cyril Gavoille Dahlia Malkhi Noam Nisan Mikkel Thorup

Abstract Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a $\widetildeO(\sqrt{n})$ space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long at the shortest paths. This is optimal in a very strong sense. It is known that no compact routing using $o(n)$ space per node can route with stretch below 3. Also, it is known that any stretch below 5 requires $\Omega(\sqrt{n})$ space per node.