Routing with Improved Communication-Space Trade-Off



Given a weighted undirected network with arbitrary node names, we present a family of routing schemes characterized by an integral parameter $\kappa \ge 1$. The scheme uses $\tO(n^{1/\kappa} \log D)$ space routing table at each node, and routes along paths of linear stretch $O(\kappa)$, where $D$ is the normalized diameter of the network. When $D$ is polynomial in $n$, the scheme has asymptotically optimal stretch factor. With the same memory bound, the best previous results obtained stretch $O(\kappa^2)$. Of independent interest, we also construct a single-source name-independent routing scheme for uniform weighted graphs with $O(1)$ stretch and $\tO(1)$ bits of storage. With the same stretch, the best previous results obtained memory $\tO(n^{1/9})$.