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.