Dynamic multi-path routing and how it compares with other dynamic routing algorithms for high speed wide area network

ABSTRACT

In this paper we describe briefly a dynamic multi-path routing scheme that has been considered for connection oriented homogeneous high speed networks. The fundamental objective of the scheme is to bridge the gap between routing and congestion control as the network becomes congested. Because propagation delay far out shadows queueing and transmission delay in high speed networks, the proposed routing scheme works as a shortest path (minimum hop) first algorithm under light traffic conditions. However as the shortest path becomes congested, the source node uses multiple paths when and if available in order to distribute the load and reduce packet loss. The scheme is a cross between Alternate Path routing and Trunk Reservation. We compare the performance of the proposed scheme with the Shortest Path Only algorithm, the Alternate Path routing algorithm, the Random Routing algorithm, and the Trunk Reservation scheme. The throughput and packet loss performance are compared via simulations. These have been carried out concentrating on a 5 node network with varying traffic patterns, the intention being to gain insight into the strengths and weaknesses of the various schemes.

REFERENCES

• BAH90: Bahk, S. and Zarki, M. E., "Routing in ATM Networks", 7th International Teletraftic Congress, New Jersey, 1990
• BER87: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• RUD80: Rudin, H. and Mueller, H., "Dynamic Routing and Flow Control", IEEE Trans. on Comm., Vol. Com-28, No. 7, July 1980.
• SUN77: Carl A. Sunshine, Source routing in computer networks, ACM SIGCOMM Computer Communication Review, v.7 n.1, p.29-33, January 1977 [doi>10.1145/1024853.1024855]
• WOO88: Woodruff, G.M., Rogers, R.G.H., and Richards, P.S., "A Congestion Control Framework for High Speed Integrated Packetized Transport", Proceedings of iEEE Globecom'88, 1988.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Connection machines

  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