Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-04-106, December 2004.
Anupam Gupta, Bruce M. Maggs, Shuheng Zhou
Dept. Electrical and Computer Engineering
Carnegie Mellon University
We study the problem of routing in doubling metrics, and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables (i.e., with a small amount of routing information stored at each vertex). We say that a metric (X,d) has doubling dimension dim(X) at most α if every set of diameter D can be covered by 2α sets of diameter D/2. (A doubling metric is one whose doubling dimension dim(X) is a constant.) For a connected graph G, whose shortest path distances dG induce the doubling metric (X, dG), we show how to perform (1 + τ)-stretch routing on G for any 0 < τ ≤ 1 with routing tables of size at most (α/τ)O(α)logΔlogδ bits with only (α/τ)O(α) log Δ entries, where Δ is the diameter of G and δ is the maximum degree of G. Hence the number of routing table entries is just τ-O(1)logΔ for doubling metrics. These results extend and improve on those of Talwar (2004).
KEYWORDS: doubling metrics, bounded growth, hierarchical routing, decomposition
FULL PAPER, TR VERSION: pdf / ps