The revised ARPANET routing metric

ABSTRACT

The ARPANET routing metric was revised in July 1987, resulting in substantial performance improvements, especially in terms of user delay and effective network capacity. These revisions only affect the individual link costs (or metrics) on which the PSN (packet switching node) bases its routing decisions. They do not affect the SPF (“shortest path first”) algorithm employed to compute routes (installed in May 1979). The previous link metric was packet delay averaged over a ten second interval, which performed effectively under light-to-moderate traffic conditions. However, in heavily loaded networks it led to routing instabilities and wasted link and processor bandwidth. The revised metric constitutes a move away from the strict delay metric: it acts similar to a delay-based metric under lightly loads and to a capacity-based metric under heavy loads. It will not always result in shortest-delay paths. Since the delay metric produced shortest-delay paths only under conditions of light loading, the revised metric involves giving up the guarantee of shortest-delay paths under light traffic conditions for the sake of vastly improved performance under heavy traffic conditions.

REFERENCES

• 1: ARPANET Performance Analysis Report. Quarterly Report 11, BBN, Aug. 1987.
• 2: MILNET Routing Improvements: Measurements and Analysis of the $PF Metric Patch. BBN Report 6719, BBN, Feb. 1988.
• 3: D. P. Bertsekas. Dynamic Behavior of Shortest Path Routing Algorithms for Communication Networks. IEEE Transactions on Automatic Control, AC-27:60- 74, Feb. 1982.
• 4: E. W. Dijkstra. A Note on Two Problems in Connection with Graphs. Numerische Mathematik, 1:269- 271, 1959.
• 5: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 6: V. Haimo, M. Gardner, I. I_x>obeek, and M. Frishkopf. Multi-Path Routing: Modeling and Simulation. BBN Report 6363, BBN, Sep. 1986.
• 7: A. Khanna. Short-Term Modifications to Routing and Congestion Control. BBN Report 6714, BBN, Feb. 1988.
• 8: J. M. McQuillan, G. Falk, and I. Richer. A Review of the Development and Performance of the ARPANET Routing Algorithm. IEEE Transactions on Communications, 1802-1811, De~c. 1978.
• 9: J. M. McQuillan, I. Richer, and E. C. Rosen. ARPANET Routing Algorithm Improvements: First Semiannual Technical Report. BBN Report 3803, BBN, Apr. 1978.
• 10: J. M. McQuillan, I. Richer, and E. C. Rosen. The New Routing Algorithm for the ARPANET. IEEE Transactions on Communications, 711-719, May 1980.
• 11: J.M. McQuillan, I. Richer, E. C. Rosen, and D. P. Bertsekas. ARPANET Routing Algorithm Improvements: 2nd Semiannual Technical Report. BBN Report 3940, BBN, Oct. 1978.
• 12: J.M. McQuillan, I. Richer, E. C. Rosen, and J. G. Herman. ARPANET Routing Algorithm Improvements: 3rd Semiannual Technical Report. BBN Report 3940, BBN, Oct. 1978.
• 13: E. C. Rosen. The Updating Protocol of ARPANET's New Routing Algorithm. Computer Networks, 4:11- 19, Feb. 1980.
• 14: J. A. Zinky, A. Khanna, and G. Vichniac. Performance of the Revised Routing Metric for ARPANET and MILNET. Submitted to MILCOM 89, March 1989.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

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

          Nouns: ARPANET

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

General Terms:
Algorithms, Design, Performance, Theory