On Hierarchical Routing in Doubling Metrics
Abstract
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(<i<X</i<) at most α if every ball can be covered by 2 α balls of half its radius. (A doubling metric is one whose doubling dimension dim(<i<X</i<) is a constant.) We consider the metric space induced by the shortest-path distance in an underlying undirected graph G . We show how to perform (1 + τ)-stretch routing on such a metric 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 the graph, and δ is the maximum degree of the graph 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).
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 16, 2016
- Source ID
- 10.1145/2915183
Entities
People
- Anupam K. Gupta
- Bruce M. Maggs
- Shuheng Zhou
- T.-h. Hubert Chan
Organizations
- Army Research Office
- Carnegie Mellon University
- Duke University
- National Science Foundation
- University of Hong Kong
- University of Michigan