skip to main content
10.1145/872035.872042acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Compact roundtrip routing with topology-independent node names

Published:13 July 2003Publication History

ABSTRACT

This paper presents compact roundtrip routing schemes with local tables of size Õ(√n) and stretch 6 for any directed network with arbitrary edge weights; and with local tables of size Õ(√−1n2/k) and stretch min((2k/2 −1)(k + √), 16k 2+ 8 k − 8), for any directed network with polynomially-sized edges, both in the topology-independent node-name model. These are the first topology-independent results that apply to routing in directed networks.

References

  1. M. Arias, L. Cowen, K. Laing, R. Rajaraman, and O. Taka. Compact routing with name independence. To appear in SPAA, 2003.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. B. Awerbuch, A. Bar-Noy, N. Linial, and D. Peleg. Compact distributed data structures for adaptive network routing. In Proc. 21st ACM Symp. on Theory of Computing, pages 479--489, May 1989.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. B. Awerbuch and D. Peleg. Sparse partitions. In Proc. 31st IEEE Symp. on Found. of Comp. Science, pages 503--513, 1990.]]Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. L. Cowen. Compact routing with minimum stretch. J. of Algorithms, 38:170--183, 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. L. Cowen and W. Wagner. Compact roundtrip routing in digraphs. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages S885--886, 1999.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. L. J. Cowen and C. G. Wagner. Compact roundtrip routing in directed networks. In Proc. 19th ACM Symp. on Principles of Distrib. Computing, pages 51--59, 2000.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. M. Crovella. Personal communication, 2002.]]Google ScholarGoogle Scholar
  8. D. Dor, S. Halperin, and U. Zwick. All pairs almost shortest paths. In 37th Annual Symposium on Foundations of Computer Science, pages 452--461, Burlington, Vermont, 14--16 Oct. 1996. IEEE.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. T. Eilam, C. Gavoille, and D. Peleg. Compact routing schemes with low stretch factor. In 17th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 11--20, 1998.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. P. Fraigniaud and C. Gavoille. Routing in trees. In F. Orejas, P. G. Spirakis, and J. van Leeuwen, editors, 28th International Colloquium on Automata, Languages and Programming (ICALP), volume 2076 of Lecture Notes in Computer Science, pages 757--772. Springer, 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. C. Gavoille. Routing in distributed networks: Overview and open problems. ACM SIGACT News Distributed Computing Column, 32(1):36--52, March 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. C. Gavoille and M. Gengler. Space-efficiency of routing schemes of stretch factor three. Journal of Parallel and Distributed Computing, 61:679--687, 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. K. Hildrum, J. Kubiatowicz, S. Rao, and B. Zhao. Distributed object location in a dynamic network. In Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 41--52, 2002.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. K. Iwama and A. Kawachi. Compact routing with stretch factor of less than three. In 19th Annual ACM Symposium on Principles of Distributed Computing (PODC), page 337, 2000.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. K. Iwama and M. Okita. Compact routing for average case networks. In 21st Annual ACM Symposium on Principles of Distributed Computing (PODC), 2002.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, H. W. R. Gummadi, S. Rhea, W.Weimer, C. Wells, and B. Zhao. Oceanstore: An architecture for global-scale persistent storage. In Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2000.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, San Mateo, CA, 1992.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. D. Peleg. Distance-dependent distributed directories. Information and Computation, 103(2):270--298, 1993.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. C. Plaxton, R. Rajaraman, and A. Richa. Accessing nearby copies of replicated objects in a distributed environment. Theory of Computing Systems, 32:241--180, 1999.]]Google ScholarGoogle ScholarCross RefCross Ref
  20. R. Rajaraman. Personal communication, 2002.]]Google ScholarGoogle Scholar
  21. S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Schenker. A scalable content-addressable network. In Proceedings of the 2001 conference on applications, technologies, architectures, and protocols for computer communications, pages 161--172. ACM Press, 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. L. Roditty, M. Thorup, and U. Zwick. Roundtrip spanners and roundtrip routing in directed graphs. In Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, pages 844--851, Jan. 2002.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), pages 329--350, Nov. 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A scalable Peer-To-Peer lookup service for internet applications. In Proceedings of the 2001 ACM SIGCOMM Conference, pages 149--160, 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. M. Thorup and U. Zwick. Compact routing schemes. In Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 1--10. ACM, July 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. M. van Steen, F. Hauck, and A. Tanenbaum. A model for worldwide tracking of distributed objects. In Proceedings of the 1996 Conference on Telecommunications Information Networking Architecture (TINA 96), pages 203--212, Sept. 1996.]]Google ScholarGoogle Scholar
  27. C. Wagner. Drawing with Bezier Curves and Routing on Digraphs. PhD thesis, Dept. of Mathematical Sciences, Johns Hopkins University, 1999.]]Google ScholarGoogle Scholar
  28. B. Y. Zhao, Y. Duan, L. Huang, A. D. Joseph, and J. D. Kubiatowicz. Brocade: landmark routing on overlay networks. In First International Workshop on Peer-to-Peer Systems (IPTPS)/LNCS, pages 34--44, march 2002.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, UC Berkeley, Apr. 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. U. Zwick. Exact and approximate distances in graphs-a survey. In Proc. of 9th European Symposium on Algorithms, pages 33--48, 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Compact roundtrip routing with topology-independent node names

                Recommendations

                Comments

                Login options

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

                Sign in
                • Published in

                  cover image ACM Conferences
                  PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing
                  July 2003
                  380 pages
                  ISBN:1581137087
                  DOI:10.1145/872035

                  Copyright © 2003 ACM

                  Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

                  Publisher

                  Association for Computing Machinery

                  New York, NY, United States

                  Publication History

                  • Published: 13 July 2003

                  Permissions

                  Request permissions about this article.

                  Request Permissions

                  Check for updates

                  Qualifiers

                  • Article

                  Acceptance Rates

                  PODC '03 Paper Acceptance Rate51of226submissions,23%Overall Acceptance Rate740of2,477submissions,30%

                  Upcoming Conference

                  PODC '24

                PDF Format

                View or Download as a PDF file.

                PDF

                eReader

                View online with eReader.

                eReader