Article

Optimal scale-free compact routing schemes in networks of low doubling dimension

Authors:

Goran Konjevod,

Andréa W. Richa,

Donglin XiaAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 939 - 948

Published: 07 January 2007 Publication History

Abstract

We present optimal-stretch scale-free compact routing schemes for networks of low doubling dimension, in both the name-independent and name-dependent models. Our name-independent algorithm is the first scale-free name-independent compact routing scheme to achieve asymptotically optimal stretch, closing the gaps left by the work of Abraham et al. (ICDCS'06) and Konjevod et al. (PODC'06). Our name-dependent algorithm is the first scale-free optimal-stretch name-dependent compact routing scheme that uses optimal [log n]-bit routing labels, in spite of the limited routing label information. We define a simple hierarchical decomposition technique based on ball-packings. Our algorithms rely on a novel combination of ball-packings and hierarchical r-nets, which we see as a contribution in its own right.

References

[1]

I. Abraham and C. Gavoille. Object location using path separators. In Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing. ACM Press, July 2006.

Digital Library

[2]

I. Abraham, C. Gavoille, A. V. Goldberg, and D. Malkhi. Routing in networks with low doubling dimension. In 26^th ICDCS. IEEE Computer Society Press, July 2006. To appear.

Digital Library

[3]

I. Abraham, C. Gavoille, and D. Malkhi. Routing with improved communication-space trade-off. In Proceedings of the 18th International Conference on Distributed Computing, volume 3274 of Lecture Notes in Computer Science, pages 305--319, 2004.

[4]

I. Abraham, C. Gavoille, and D. Malkhi. On space-stretch trade-offs: Lower bounds. In Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architecture. ACM Press, July 2006.

Digital Library

[5]

I. Abraham, C. Gavoille, and D. Malkhi. On space-stretch trade-offs: Upper bounds. In Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architecture. ACM Press, July 2006.

Digital Library

[6]

I. Abraham and D. Malkhi. Name independent routing for growth bounded networks. In Proceedings of the 17th Annual ACM Symposium on Parallel Algorithms and Architecture, pages 49--55, 2005.

Digital Library

[7]

I. Abraham, D. Malkhi, and O. Dobzinski. Land: stretch (1 + ε) locality-aware networks for DHTs. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 550--559, 2004.

Digital Library

[8]

B. Awerbuch and D. Peleg. Sparse partitions. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 503--513, 1990.

[9]

B. Awerbuch and D. Peleg. Routing with polynomial communication-space trade-off. SIAM J. Discret. Math., 5(2):151--162, 1992.

Digital Library

[10]

H. T.-H. Chan, A. Gupta, B. Maggs, and S. Zhou. On hierarchical routing in doubling metrics. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 762--771, 2005.

Digital Library

[11]

L. Cowen. Compact routing with minimum stretch. Journal of Algorithms, 38:170--183, 2001.

Digital Library

[12]

T. Eilam, C. Gavoille, and D. Peleg. Compact routing schemes with low stretch factor. Journal of Algorithms, 46:97--114, 2003.

Digital Library

[13]

P. Fraigniaud and C. Gavoille. Routing in trees. In 28^th ICALP, volume 2076 of LNCS, pages 757--772. Springer, 2001.

Digital Library

[14]

C. Gavoille. Routing in distributed networks: Overview and open problems. ACM SIGACT News--Distributed Computing Column, 32(1):36--52, 2001.

Digital Library

[15]

C. Gavoille and N. Hanusse. Compact routing tables for graphs of bounded genus. In 26^th ICALP, volume 1644 of LNCS, pages 351--360. Springer, July 1999.

Digital Library

[16]

C. Gavoille and D. Peleg. Compact and localized distributed data structures. Journal of Distributed Computing, 16:111--120, 2003.

Digital Library

[17]

A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals and low-distortion embeddings. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 534--543, 2003.

Digital Library

[18]

G. Konjevod, A. Richa, and D. Xia. Optimal-stretch name-independent compact routing in doubling metrics. In Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing, 2006.

Digital Library

[19]

G. Konjevod, A. Richa, and D. Xia. Compact routing in networks of low doubling dimension. Manuscript available at http://thrackle.eas.asu.edu/papers/compact.ps.gz, 2007.

[20]

D. Peleg. Distributed Computing: A Locality-Sensitive Approach. Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, 2000.

Digital Library

[21]

A. Slivkins. Distance estimation and object location via rings of neighbors. In Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing, pages 41--50, 2005.

Digital Library

[22]

A. Slivkins. Distributed approaches to triangulation and embedding. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 640--649, 2005.

Digital Library

[23]

I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In In Proceeding of the 2001 ACM SIGCOMM, 2001.

Digital Library

[24]

K. Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 281--290, 2004.

Digital Library

[25]

M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM, 51(6):993--1024, 2004.

Digital Library

[26]

M. Thorup and U. Zwick. Compact routing schemes. In Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architecture, pages 1--10, 2001.

Digital Library

Cited By

Chan TGupta AMaggs BZhou S(2016)On Hierarchical Routing in Doubling MetricsACM Transactions on Algorithms10.1145/291518312:4(1-22)Online publication date: 16-Aug-2016
https://dl.acm.org/doi/10.1145/2915183
Konjevod GRicha AXia D(2016)Scale-Free Compact Routing Schemes in Networks of Low Doubling DimensionACM Transactions on Algorithms10.1145/287605512:3(1-29)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1145/2876055
Abraham IChechik SGavoille CPeleg D(2016)Forbidden-Set Distance Labels for Graphs of Bounded Doubling DimensionACM Transactions on Algorithms10.1145/281869412:2(1-17)Online publication date: 12-Feb-2016
https://dl.acm.org/doi/10.1145/2818694
Show More Cited By

Optimal scale-free compact routing schemes in networks of low doubling dimension
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Scale-Free Compact Routing Schemes in Networks of Low Doubling Dimension

We consider compact routing schemes in networks of low doubling dimension, where the doubling dimension is the least value α such that any ball in the network can be covered by at most 2^α balls of half radius. There are two variants of routing-scheme ...
Compact routing with slack in low doubling dimension
PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing
We consider the problem of compact routing with slack in networks of low doubling dimension. Namely, we seek name-independent routing schemes with (1+ε) stretch and polylogarithmic storage at each node: since existing lower bound precludes such a scheme,...
Compact routing design in networks of low doubling dimension

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
240
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chan TGupta AMaggs BZhou S(2016)On Hierarchical Routing in Doubling MetricsACM Transactions on Algorithms10.1145/291518312:4(1-22)Online publication date: 16-Aug-2016
https://dl.acm.org/doi/10.1145/2915183
Konjevod GRicha AXia D(2016)Scale-Free Compact Routing Schemes in Networks of Low Doubling DimensionACM Transactions on Algorithms10.1145/287605512:3(1-29)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1145/2876055
Abraham IChechik SGavoille CPeleg D(2016)Forbidden-Set Distance Labels for Graphs of Bounded Doubling DimensionACM Transactions on Algorithms10.1145/281869412:2(1-17)Online publication date: 12-Feb-2016
https://dl.acm.org/doi/10.1145/2818694
Tang MLiu JZhang G(2011)Improved compact routing schemes for power-law networksProceedings of the 8th IFIP international conference on Network and parallel computing10.5555/2062932.2062937(44-58)Online publication date: 21-Oct-2011
https://dl.acm.org/doi/10.5555/2062932.2062937
Konjevod GRicha AXia DZhou LGavoille CFraigniaud P(2011)Randomized compact routing in decomposable metricsProceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1993806.1993879(351-352)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.1145/1993806.1993879
Gavoille CSommer CMeyer auf der Heide FRajaraman R(2011)Sparse spanners vs. compact routingProceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures10.1145/1989493.1989526(225-234)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/1989493.1989526
Abraham IChechik SGavoille CPeleg DRicha AGuerraoui R(2010)Forbidden-set distance labels for graphs of bounded doubling dimensionProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835743(192-200)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835743
Chan TGupta ATalwar K(2010)Ultra-low-dimensional embeddings for doubling metricsJournal of the ACM10.1145/1734213.173421557:4(1-26)Online publication date: 3-May-2010
https://dl.acm.org/doi/10.1145/1734213.1734215
Gupta ATalwar K(2008)How to complete a doubling metricProceedings of the 8th Latin American conference on Theoretical informatics10.5555/1792918.1792922(36-47)Online publication date: 7-Apr-2008
https://dl.acm.org/doi/10.5555/1792918.1792922
Gottlieb LRoditty LTeng S(2008)Improved algorithms for fully dynamic geometric spanners and geometric routingProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347148(591-600)Online publication date: 20-Jan-2008
https://dl.acm.org/doi/10.5555/1347082.1347148
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents