PARALLEL DATA LAB 

PDL Abstract

On Hierarchical Routing in Doubling Metrics

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

http:/www.pdl.cmu.edu

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