Name Independent Routing for Growth Bounded Networks
- Ittai Abraham ,
- Dahlia Malkhi
17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '05) |
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.