loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Ittai Abraham, Hebrew University of Jerusalem
Cyril Gavoille, University of Bordeaux, Bordeaux, France.
Andrew V. Goldberg, Microsoft Research - Silicon Valley
Dahlia Malkhi, Hebrew University of Jerusalem
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
Usage of this product signifies your acceptance of the Terms of Use.