## Routing with Improved Communication-Space Trade-Off

### Authors

- Ittai Abraham, Hebrew University of Jerusalem, School of Computer Science and Engineering
- Cyril Gavoille, University of Bordeaux, Laboratoire Bordelais de Recherche en Informatique
- Dahlia Malkhi, Hebrew University of Jerusalem, School of Computer Science and Engineering

### Abstract

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})$.