Name independent routing for growth bounded networks
Ittai Abraham, Dahlia Malkhi · 2005
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 Δ)log5n) bit routing tables per node.