Compact distributed data structures for adaptive routing

ABSTRACT

In designing a routing scheme for a communication network it is desirable to use as short as possible paths for routing messages, while keeping the routing information stored in the processors' local memory as succinct as possible. The efficiency of a routing scheme is measured in terms of its stretch factor - the maximum ratio between the cost of a route computed by the scheme and that of a cheapest path connecting the same pair of vertices. This paper presents a family of adaptive routing schemes for general networks. The hierarchical schemes H Sk (for every fixed k ≥ 1) guarantee a stretch factor of O (k2 · 3k) and require storing at most O (knk log n) bits of routing information per vertex. The new important features, that make the schemes appropriate for adaptive use, are applicability to networks with arbitrary edge costs; name-independence, i.e., usage of original names; a balanced distribution of the memory; an efficient on-line distributed preprocessing.

REFERENCES

• ABLP88a: Baruch Awerbuch, Amotz Bar-Noy, Nati Linial, and David Peleg. Improved Routing Strategies with Succinct Tables. Technical Report MIT/LCS/TM-354, Massachusetts Institute of Technology, 1988.
• ABLP88b: Baruch Awerbuch, Amotz Bar-Noy, Nati Linial, and David Peleg. Memory- Balanced Rou~ing Strategies. Technical Report MiT/LCS/TM-369, Massachusetts Institu{e of Technology, 1988.
• FJ86: Greg N. Frederickson a~nd Ravi Janardan. Seperator-k,ased strategies for efficient message routing. In 27~h Annual Symposium on Foundalions of Computer Science, Toronto, Ontario, Canada, pages 428-437, IEEE, May 1986.
• FJ88: Greg N. Frederick:son and Ravi Janardan. Designing networks with compact routing tables. Algorithmica, 3:171-190, August 1988.
• KK77: L. Kleinrock and F. Karnoun. Hierarchical routing for large networks; performance evaluation and optimization. Computer Networks, 1:155-174, 1977.
• KK80: L. Kleinrock and F. Kamoun. Optimal clustering structulces for hierarchical topological design of 1;~rge computer networks. Computer Networks, 10:221-248, 1980.
• Lov75: L&szl5 Lovksz. On the ratio of optimal integral and fractional covers. Discrete Malhemalics, 13:383-390, 1975.
• Per82: R. Perlman. Hierarchical networks and the subnetwork partition problem. In 5th Conference on S~,stem Sciences, 1982.
• PU88: David Peleg , Eli Upfal, A tradeoff between space and efficiency for routing tables, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.43-52, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62217]
• SK85: N. Santoro and R. Khatib. Labelling and implicit routing in networks. The Computer Journal, 28.:5-8, 1985.
• Sun82: C.A. Sunshine. Addressing problems in multi-network systems. In IEEE INFO- COM, IEEE, 1982.
• Tan81: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• vLT86: J. van Leeuwen and R.B. Tan. Routing with compact routing tables. In G. Rozenberg and A. Salomaa, editors, The Book of L, pages 259-273., Springer-Verlag, New York, New York, 1986.
• vLT87: J. Van Leeuwen , R. B. Tan, Interval routing, The Computer Journal, v.30 n.4, p.298-307, Aug. 1987 [doi>10.1093/comjnl/30.4.298]
• Zim80: H. Zimmerman. OSI reference modelthe ISO model of architecture for open systems interconnection. {EEE Trans. Comm., 28:425-432, 1980.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

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

General Terms:
Algorithms, Design, Theory