Name Independent
Routing For Growth Bounded Networks
|
|
|
|
|
Abstract A weighted undirected network is Δ-growth-bounded
if the number of nodes at distance 2r around any given node is at most Δ
times the number of nodes at distance r around the node. Given a weighted
undirected network with arbitrary node names and ε > 0, we present a
routing scheme that routes along paths of stretch 1+ ε and uses with
high probability only O( (1/ ε)O(log Δ) log5 n)
bit routing tables per node. |
||
|
[SPAA 05 version pdf] |
||