A tradeoff between space and efficiency for routing tables

ABSTRACT

Two conflicting goals play a crucial role in the design of routing schemes for communication networks. A routing scheme should use as short as possible paths for routing messages in the network, 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 length of a route computed by the scheme and that of a shortest path connecting the same pair of vertices. Most previous work has concentrated on finding good routing schemes (with a small fixed stretch factor) for special classes of network topologies. In this work we study the problem for general networks, and look at the entire range of possible stretch factors. The results exhibit a tradeoff between the efficiency of a routing scheme and its space requirements. We present almost tight upper and lower bounds for this tradeoff. Specifically, we prove that any routing scheme for general n-vertex networks that achieves a stretch factor k ≥ 1 must use a total of &OHgr;(n1+1/2k+4) bits of routing information in the networks. This lower bound is complemented by a family H(k) of hierarchical routing schemes (for every fixed k ≥ 1), which guarantee a stretch factor of &Ogr;(k), require storing a total of &Ogr;(n1+1/k) bits of routing information in the network and name the vertices with &Ogr;(log2 n)-bit names.

REFERENCES

• A: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• BJ: A E Baratz , J M Jaffe, Establishing virtual circuits in large computer networks, Computer Networks and ISDN Systems, v.12 n.1, p.27-34, August 1986 [doi>10.1016/0169-7552(86)90081-4]
• BLP: A. Bar-Noy, N. Linial and D. peleg, in preparation.
• FJ1: Greg N Frederickson , Ravi Janardan, Optimal message routing without complete routing tables, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.88-97, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10598]
• FJ2: G.N, Frederickson amd R. J~nard~n, Separator-B~sed Strategies for Efficient Message Routing, 27th Sj~mp. on Foundations of Computer Sci~,nce, 1986, 428-437'.
• KK1: L. Kleinrock and F. Kamoun, llierarchica, Rounting; for largge Net,- works; Perforlnance Evalvation and Optimization, computer Networks 1, (1977), pp. 155-174.
• KK2: L. Kleinrock and F. K~moun, ()ptimM Clusteriltg Structures tbr {-{ierarchical TopologicM Design of I,arge Comptlter N~tworks, N~,twork.,. 10, (,1980), pp. 221-248.
• PS: D. Peleg and A. Sch~ffer, Gral~h Spanners, Manuscript:, Septentbcr 1987.
• PUl: David Peleg , Jeffrey D. Ullman, An optimal synchronizer for the hypercube, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.77-85, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41847]
• PUp1: D. Peleg and E. l. Jpfa. l, Efficient Message Passing Using Succit~ct Ronting Tables, Research R. eport RJ 57(~,q, IBM Almaden, August 1987.
• PUp2: D. Peteg and E. Upfal, A Tradeoff Between Space and Efficiency for Routing Tables, Research Report R J 5859. IBM Almaden, October 1987.
• P: R. Perlman, Hierarchical Network.a and the Subnetwork Partition Problem, 5th Conf. on S3'stem Scie~ices. 1982.
• SK: N. Saxttoro and R,. Khatib, Labelling and implicit. Routing i~ Networks. The Computer journal 28. (1985). pp. 5 8.
• S: C.A. Sunshine, Addressing problems in Multi-Network Systems, 1EEE IN- FOCOM, 1982.
• vLT1: J. van Leeuwen and R.B. Tart. Routing with Compact Routing Tables, Tech. Report RUU-CS-83-1f3. University of Utrechl;, Utrecht, tlte Netherlands, November 1983.
• vLT2: J. van Leeuwen and R.B. Tan, Interval Routing, Tech. Report RUU-('S- 85-16, University of Utrecht, Utrecht. the Netherlands, May 1985.

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.0 General
          Subjects: Data communications
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Algorithms, Design, Performance, Theory