Given a weighted undirected network with arbitrary node names, we present a family of routing schemes characterized by an
integral parameter
κ ≥ 1. The scheme uses
[(O)\tilde](n1/k logD)\widetilde{O}(n^{1/\kappa} \log D) space routing table at each node, and routes along paths of linear stretch
O(
κ), 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(
κ
2).
Of independent interest, we also construct a single-source name-independent routing scheme for uniform weighted graphs with
O(1) stretch and
[(O)\tilde](1)\widetilde{O}(1) bits of storage. With the same stretch, the best previous results obtained memory
[(O)\tilde](n1/9)\widetilde{O}(n^{1/9}).
Full version appears as Technical Report #RR-1330-04 of Bordeaux University [1].