Routing with
Improved Communication-Space Trade-Off
|
Ittai Abraham Cyril Gavoille Dahlia Malkhi |
|
|
|
Abstract 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 Õ(n1/ κ
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 Õ(1)
bits of storage. With the same stretch, the best previous results obtained memory
Õ(n1/9). |
||