Analysis of shortest-path routing algorithms in a dynamic network environment

ABSTRACT

In a dynamic network environment under heavy traffic load, shortest-path routing algorithms, particularly those that attempt to adapt to traffic changes, frequently exhibit oscillatory behaviors and cause performance degradation. In this paper we first examine the problems from the perspective of control theory and decision making, and then analyze the behaviors of the shortest-path routing algorithms in details.

REFERENCES

• 1: [1] J. M. McQuillan and D. C. Walden, "The ARPA Network Design Decision", Computer Networks, Vol. 1, pp. 243-389, 1977.
• 2: William D. Tajibnapis, A correctness proof of a topology information maintenance protocol for a distributed computer network, Communications of the ACM, v.20 n.7, p.477-485, July 1977 [doi>10.1145/359636.359701]
• 3: [3] C. L. Hedrick, "An Introduction to IGRP", Preprint, RUTGERS, Centre for Computers and Information Services, The State University of New Jersey, Oct. 1989.
• 4: [4] J. M. McQuillan, et al., "The New Routing Algorithm for the ARPANET", IEEE Transactions on Communications, Vol. COM-28, May 1980.
• 5: J. Moy, OSPF specification, RFC Editor, 1989
• 6: [6] International Standards Organization, "Intra-Domain IS-IS Routing Protocol", ISO/IEC JTC1/SC6 WG2 N323, Sept. 1989.
• 7: [7] D. Bertsekas, "Dynamic Behavior of Shortest Path Routing Algorithms for Communication Networks", IEEE Transactions on Automatic Control, Vol. AC-27, No. 1, Feb. 1982.
• 8: A. Khanna , J. Zinky, The revised ARPANET routing metric, Symposium proceedings on Communications architectures & protocols, p.45-56, September 25-27, 1989, Austin, Texas, United States
• 9: [9] H. Sorenson, "Parameter Estimation", Marcel Dekker, Inc., 1980.
• 10: [10] R. Luce, H. Raiffa, "Games and Decisions", John Wiley & Sons, Inc., 1957.
• 11: [11] R. Cyert, M. DeGroot, "Bayesian Analysis and Uncertainty in Economic Theory", Chapman and Hall, 1987.
• 12: [12] L. Kleinrock, "Queueing Systems", Volume II, John Wiley & Sons, 1976.
• 13: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 14: [14] J. Seeger, A. Khanna, "Reducing Routing Overhead in a Growing DDN", in Proc. of MILCOM'86, pp 15.3.1-15.3.13, Oct. 1986.
• 15: Z. Wang , J. Crowcroft, Shortest path first with emergency exits, Proceedings of the ACM symposium on Communications architectures & protocols, p.166-176, September 26-28, 1990, Philadelphia, Pennsylvania, United States

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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Measurement, Performance, Theory