Shortest path first with emergency exits

ABSTRACT

Under heavy and dynamic traffic, the SPF routing algorithm often suffers from wild oscillation and severe congestion, and results in degradation of the network performance. In this paper, we present a new routing algorithm (SPF-EE) which attempts to eliminate the problems associated with the SPF algorithm by providing alternate paths as emergency exits. With the SPF-EE algorithm, traffic is routed along the shortest-paths under normal condition. However, in the presence of congestion and resource failures, the traffic can be dispersed temporarily to alternate paths without route re-computation. Simulation experiments show that the SPF-EE algorithm achieves grater throughput, higher responsiveness, better congestion control and fault tolerance, and substantially improves the performance of routing in a dynamic environment.

REFERENCES

• McQU80: J. McQuillan, I. Richer, E. Rosen, The New Routing Algorittlm for the ARPANET, IEEE trans, on comm., Vol. COM-28, No. 5, pp 711-719, May 1980.
• ROSE80: E. Rosen, The Updating Protocol of ARPANET's New Routing Algorithm, Computer Networks, Vol. 4, pp t 1-19, 1980.
• BERT82: D. Bertsekas, Dynamic Behavior of Shortest Path Routing Algorithms for Communication Networks, IEEE trans, on automatic control, Vol. AC-27, No.I, Feb. 1982.
• WANG90: Z. Wang, J. Crowcrofl, Analysis of Shortest- Path Routing Algorithms in a Dynamic Environment, Research Notes RN/90/31, Computer Science Dept, University College London, March 1990.
• SEEG86: 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.
• KHAN89: 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
• JACO88: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, 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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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

General Terms:
Algorithms, Design