A new responsive distributed shortest-path rounting algorithm

ABSTRACT

Distributed shortest-path routing algorithms based on the Ford-Fulkerson method are simple to implement but they suffer from the cost-dependent looping problem: when link costs increase, routing table loops may form and convergence to correct paths may be too slow, depending on link costs. This problem can be eliminated if constraints are imposed on the order in which routing tables are updated at different nodes but the resulting internode protocols tend to be relatively complex. Furthermore, update constraints may restrict a node's ability to obtain alternate paths quickly in an environment where topology changes are frequent. In this paper, a new distributed shortest-path routing scheme based on the Ford-Fulkerson method is presented. Under the new scheme, each node uses partial topology information to eliminate the cost-dependent looping problem. No update constraints are imposed and no assumptions are made regarding link costs. In the worst case, the new scheme responds to link cost changes in O(D) update steps, where D is the diameter of the network after the occurrence of the changes.

REFERENCES

• 1: Mischa Schwartz, Telecommunication networks: protocols, modeling and analysis, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: M. Schwartz and T. E. Stern, "Rou~ing techniques used in computer communication networks," ~EEE Trans. Communications COM-28 pp. 539-552 (April 1980).
• 3: J.M. McQuillan, G. Falk, and I. Richer, "A Review of the Development and Performance of the ARPANET Routing Algorithm," iEEE Trans. Communications COM-26, No. 12 pp. 1802-1811 (December, 1978).
• 4: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 5: P. M. Merlin and A. Segall, "A Failsafe Distributed Routing Protocol," IEEE Trans. Communications COM-2f, No. 9 pp. 1280-1287 (September, 1979).
• 6: J. M. Jaffe and F. H. Moss, "A Responsive Distributed Routing Algorithm for Computer Networks," IEEE Trans. Communications COM-S0, No. 7 pp. 1758- 1762 (July, 1982).
• 7: 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]
• 8: Jacob Hagouel, Issues in routing for large and dynamic networks, 1983
• 9: J. M. McQuillan and D. C. Walden, "The ARPANET Design Decisions," Computer Networks l(August, 1977).
• 10: T. Cegrell, "A Routing Procedure for 1;he TIDAS Message-Switching Network," IEEE Trans. Communications COM-33, No. 6 pp. 575-585 (June, 1975).
• 11: T.E. Stern, "An Improved Algorithm for Distributed Computer Networks," Proc. IEEE Intnl. Symposium on Circuits and Systems, pp. 2-6 (April, 1!}80).
• 12: K. G. Shin , M.-S. Chen, Performance analysis of distributed routing strategies free of ping-pong type looping, IEEE Transactions on Computers, v.36 n.2, p.129-137, Feb. 1987 [doi>10.1109/TC.1987.1676875]
• 13: J. Garcia-Luna-Aceves, "A New Minimum-Hop Routing Algorithm," Proc. INFOCOM '87, pp. 170- 180 (1987).
• 14: J. Gaxcia-Luna-Aceves, "A Fail-Safe Routing Algorithm for Multihop Packet-Radio Networks," Proc. INFOCOM '86, pp. 434-443 (1986).
• 15: B. Rajagopalan and M. Faiman, "A New Responsive Distributed Shortes~Path Routing Algorithm," Technical Report, UIUCDC$-R-89-1505, Dept. of Computer Science, University of Nlinois, Urbana, (~9s9).

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

  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

General Terms:
Algorithms