Compact roundtrip routing with topology-independent node names

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 Õ(√⁻¹n^2/k) and stretch min((2^k/2 −1)(k + √), 16^{k 2}+ 8 k − 8), for any directed network with polynomially-sized edges, both in the topology-independent node-name mode^l. These are the first topology-independent results that apply to routing in directed networks.

REFERENCES

• 1: Marta Arias , Lenore J. Cowen , Kofi A. Laing , Rajmohan Rajaraman , Orjeta Taka, Compact routing with name independence, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777442]
• 2: B. Awerbuch , A. Bar-Noy , N. Linial , D. Peleg, Compact distributed data structures for adaptive routing, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.479-489, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73053]
• 3: B. Awerbuch and D. Peleg. Sparse partitions. In Proc. 31st IEEE Symp. on Found. of Comp. Science, pages 503--513, 1990.
• 4: Lenore J. Cowen, Compact routing with minimum stretch, Journal of Algorithms, v.38 n.1, p.170-183, Jan. 2001 [doi>10.1006/jagm.2000.1134]
• 5: Lenore J. Cowen , Christopher G. Wagner, Compact roundtrip routing for digraphs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.885-886, January 17-19, 1999, Baltimore, Maryland, United States
• 6: Lenore J. Cowen , Christopher G. Wagner, Compact roundtrip routing in directed networks (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.51-59, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343516]
• 7: M. Crovella. Personal communication, 2002.
• 8: D. Dor , S. Halperin , U. Zwick, All pairs almost shortest paths, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.452, October 14-16, 1996
• 9: Tamar Eilam , Cyril Gavoille , David Peleg, Compact routing schemes with low stretch factor (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.11-20, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277702]
• 10: Pierre Fraigniaud , Cyril Gavoille, Routing in Trees, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.757-772, July 08-12, 2001
• 11: Cyril Gavoille, Routing in distributed networks: overview and open problems, ACM SIGACT News, v.32 n.1, March 2001 [doi>10.1145/568438.568451]
• 12: Cyril Gavoille , Marc Gengler, Space-efficiency for routing schemes of stretch factor three, Journal of Parallel and Distributed Computing, v.61 n.5, p.679-687, May 2001 [doi>10.1006/jpdc.2000.1705]
• 13: Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564877]
• 14: Kazuo Iwama , Akinori Kawachi, Compact routing with stretch factor of less than three (brief announcement), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.337, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.362158]
• 15: Kazuo Iwama , Masaki Okita, Compact routing for average-case networks, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571868]
• 16: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 17: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 18: David Peleg, Distance-dependent distributed directories, Information and Computation, v.103 n.2, p.270-298, April 1993 [doi>10.1006/inco.1993.1020]
• 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.
• 20: R. Rajaraman. Personal communication, 2002.
• 21: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 22: Liam Roditty , Mikkel Thorup , Uri Zwick, Roundtrip spanners and roundtrip routing in directed graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.844-851, January 06-08, 2002, San Francisco, California
• 23: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 24: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 25: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]
• 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.
• 27: C. Wagner. Drawing with Bezier Curves and Routing on Digraphs. PhD thesis, Dept. of Mathematical Sciences, Johns Hopkins University, 1999.
• 28: Ben Y. Zhao , Yitao Duan , Ling Huang , Anthony D. Joseph , John Kubiatowicz, Brocade: Landmark Routing on Overlay Networks, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.34-44, March 07-08, 2002
• 29: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001
• 30: Uri Zwick, Exact and Approximate Distances in Graphs - A Survey, Proceedings of the 9th Annual European Symposium on Algorithms, p.33-48, August 28-31, 2001

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph labeling; Path and circuit problems; Trees; Network problems

Keywords:
Compact Routing, Digraphs, Distributed Lookup Tables, Stretch