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.
- M. Arias, L. Cowen, K. Laing, R. Rajaraman, and O. Taka. Compact routing with name independence. To appear in SPAA, 2003.]] Google ScholarDigital Library
- 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 ScholarDigital Library
- B. Awerbuch and D. Peleg. Sparse partitions. In Proc. 31st IEEE Symp. on Found. of Comp. Science, pages 503--513, 1990.]]Google ScholarDigital Library
- L. Cowen. Compact routing with minimum stretch. J. of Algorithms, 38:170--183, 2001.]] Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- M. Crovella. Personal communication, 2002.]]Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- C. Gavoille. Routing in distributed networks: Overview and open problems. ACM SIGACT News Distributed Computing Column, 32(1):36--52, March 2001.]] Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- K. Iwama and M. Okita. Compact routing for average case networks. In 21st Annual ACM Symposium on Principles of Distributed Computing (PODC), 2002.]] Google ScholarDigital Library
- 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 ScholarDigital Library
- T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, San Mateo, CA, 1992.]] Google ScholarDigital Library
- D. Peleg. Distance-dependent distributed directories. Information and Computation, 103(2):270--298, 1993.]] Google ScholarDigital Library
- 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 ScholarCross Ref
- R. Rajaraman. Personal communication, 2002.]]Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- C. Wagner. Drawing with Bezier Curves and Routing on Digraphs. PhD thesis, Dept. of Mathematical Sciences, Johns Hopkins University, 1999.]]Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- U. Zwick. Exact and approximate distances in graphs-a survey. In Proc. of 9th European Symposium on Algorithms, pages 33--48, 2001.]] Google ScholarDigital Library
Index Terms
Compact roundtrip routing with topology-independent node names
Recommendations
Compact roundtrip routing with topology-independent node names
Consider a strongly connected directed weighted network with n nodes. This paper presents compact roundtrip routing schemes with O@?(n) sized local tables and stretch 6 for any strongly connected directed network with arbitrary edge weights. A scheme ...
Compact Routing on Random Power Law Graphs
DASC '09: Proceedings of the 2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure ComputingRouting table size and route length are two key metrics for evaluating a routing scheme, and there is an obvious tradeoff between them, i.e. the space-stretch tradeoff. The generic shortest-path routing takes an extreme position by only optimizing the ...
HDLBR: A name-independent compact routing scheme for power-law networks
Compact routing intends to achieve a good tradeoff between routing path length and storage overhead, and is recently considered as a main alternative to overcome the fundamental scaling limitations of the Internet routing system. It is generally ...
Comments