Compact routing with name independence

ABSTRACT

This paper is concerned with compact routing in the name independent model first introduced by Awerbuch et al. [1] for adaptive routing in dynamic networks. A compact routing scheme that uses local routing tables of size Õ(n^1/2), O(log² n)-sized packet headers, and stretch bounded by 5 is obtained. Alternative schemes reduce the packet header size to O(log n) at cost of either increasing the stretch to 7, or increasing the table size to Õ(n^2/3). For smaller table-size requirements, the ideas in these schemes are generalized to a scheme that uses O(log² n)-sized headers, Õ(k²n^2/k)-sized tables, and achieves a stretch of min[1 + (k-1)(2^k/2-2), 16k²+4k ], improving the best previously-known name-independent scheme due to Awerbuch and Peleg [3].

REFERENCES

• 1: 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]
• 2: Baruch Awerbuch , Amotz Bar Noy , Nathan Linial , David Peleg, Improved routing strategies with succinct tables, Journal of Algorithms, v.11 n.3, p.307-341, Sep. 1990 [doi>10.1016/0196-6774(90)90017-9]
• 3: B. Awerbuch and D. Peleg. Sparse partitions. In Proc. 31st IEEE Symp. on Found. of Comp. Science, pages 503--513, 1990.
• 4: Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
• 5: J. L. Carter and M. Wegman. Universal classes of hash functions. J. Comput. and Syst. Sci., 18:143--154, 1979.
• 6: 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]
• 7: 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]
• 8: 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
• 9: C. Gavoille and M. Gengler. Space-efficiency of routing schemes of stretch factor three. In 4th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 162--175, July 1997.
• 10: 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]
• 11: 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
• 12: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 13: L. Lovasz. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383--390, 1975.
• 14: David Peleg, Distance-dependent distributed directories, Information and Computation, v.103 n.2, p.270-298, April 1993 [doi>10.1006/inco.1993.1020]
• 15: C. Plaxton, R. Rajaraman, and A. Richa. Accessing nearby copies of replicated objects in a distributed environment. Theory of Computing Systems, 32:241--280, 1999.
• 16: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece [doi>10.1145/380752.380798]
• 17: 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]
• 18: 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.

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
compact routing, distributed lookup tables, stretch