Routing with Polynomial Communication-Space Trade-Off

This paper presents a family of memory-balanced routing schemes that use relatively short paths while storing relatively little routing information. The quality of the routes provided by a scheme is measured in terms of their stretch, namely, the maximum ratio between the length of a route connecting some pair of processors and their distance. The hierarchical schemesHₖ (for every integer k 1) presented in this paper guarantee a stretch factor of O (k²) on the length of the routes and require storing at most O (k n^1/k n D) bits of routing information per vertex in an n-processor network with diameter D. The schemes are name independent and applicable to general networks with arbitrary edge weights. This improves on previous designs whose stretch bound was exponential in k. The proposed schemes are based on a new efficient solution to a certain graph-theoretic problem concerning sparse graph covers. The new cover technique has already found several other applications in the area of distributed computing.