26th IEEE International Conference on Distributed Computing Systems (ICDCS'06)
Routing in Networks with Low Doubling Dimension
Lisboa, Portugal
July 04-July 07
ISBN: 0-7695-2540-7
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.
Citation:
Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, Dahlia Malkhi, "Routing in Networks with Low Doubling Dimension," icdcs, pp.75, 26th IEEE International Conference on Distributed Computing Systems (ICDCS'06), 2006