On Space-Stretch Trade-Offs: Upper Bounds

Ittai Abraham Cyril Gavoille Dahlia Malkhi
	Abstract One of the fundamental trade-offs in compact routing schemes is between the space used to store the routing table on each node and the stretch factor of the routing scheme -- the maximum ratio over all pairs between the cost of the route induced by the scheme and the cost of a minimum cost path between the same pair. All previous routing schemes required storage that is dependent on the diameter of the network. We present a new scale-free routing scheme, whose storage and header sizes are independent of the aspect ratio of the network. Our scheme is based on a decomposition into sparse and dense neighborhoods. Given an undirected network with arbitrary weights and n arbitrary node names, for any integer k ≥ 1 we present the first scale-free routing scheme with asymptotically optimal space-stretch tradeoff that does not require edge weights to be polynomially bounded. The scheme uses Õ(n^1/k) space routing table at each node, and routes along paths of asymptotically optimal linear stretch O(k).
	[SPAA 06 version pdf]