On Hierarchical Routing in Doubling Metrics (CMU-PDL-04-106)

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).