Routing in Networks with Low Doubling Dimension
Authors:
- C. GavoilleCGC. Gavoille
- A.V. GoldbergAGA.V. Goldberg
- D. MalkhiDMD. Malkhi
- 3 August 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636927,p. 75
Abstract
This paper studies compact routing schemes for networks with low doubling dimension. Two variants are explored, name-independent routing and labeled routing. The key results obtained for this model are the following. First, we provide the first name-independent solution. Specifically, we achieve constant stretch and polylogarithmic storage. Second, we obtain the first truly scale-free solutions, namely, the network’s aspect ratio is not a factor in the stretch. Scale-free schemes are given for three problem models: name-independent routing on graphs, labeled routing on metric spaces, and labeled routing on graphs. Third, we prove a lower bound requiring linear storage for stretch \gt 3 schemes. This has the important ramification of separating for the first time the name-independent problem model from the labeled model for these networks, since compact stretch-1+e labeled schemes are known to be possible.Keywords
This publication has 7 references indexed in Scilit:
- Bypassing the embedding2004
- Compact and localized distributed data structuresDistributed Computing, 2003
- Sparse communication networks and efficient routing in the planeDistributed Computing, 2001
- Routing in distributed networksACM SIGACT News, 2001
- Distributed Computing: A Locality-Sensitive Approach2000
- Undirected single-source shortest paths with positive integer weights in linear timeJournal of the ACM, 1999
- Improved routing strategies with succinct tablesJournal of Algorithms, 1990