A path-oriented routing strategy for packet switching networks with end-to-end protocols

ABSTRACT

A path-oriented routing strategy is proposed for packet switching networks with end-to-end internal protocols. It allows switch pairs to communicate over multiple paths (for better network throughput), while maintaining knowledge of user connections at the network's endpoints only. The most significant aspect of this strategy lies in its flow assignment method. A distributed loop-free shortest path algorithm assigns a number to a path at the time it is created and this number remains valid through shortest path changes. Consequently, existing traffic can be maintained on existing paths, while new traffic is assigned to the current shortest paths. Stable multiple path routing is thus achieved without packet disordering. Abnormal conditions such as trunk failure and recovery and trunk congestion are dealt with by tagging routing updates with update causes. Simulation of this routing strategy shows that maximum network throughput (under a certain congestion constraint) can be increased substantially compared to a single path routing strategy.

REFERENCES

• 1: Ahuja, V. "Routing and Flow Control in Systems Network Architecture." IBM $yst. d. Ye, 2 (1979): 298-314.
• 2: Aubin, R. "Including Processing and Propagation Delay to Routing in Packet Switching Networks." PPO~. Int. Conf. C~mm~nicati~ns' Chicago, 1985, pp. 107-111.
• 3: Bertsekas, D.P. "Optimal Routing and Flow Control Methods for Communication Networks." In Analysis and Optimization of Systems, pp, 615-643. Edited by F. Bensoussan and J.-L. Lions. Berlin: Springer-Verlag, 1983.
• 4: Donald Watts Davies , W. L. Price , D. L. Barber , C. M. Solomonides, Computer Networks and Their Protocols, John Wiley & Sons, Inc., New York, NY, 1979
• 5: Jaffe, J.M. and Moss, F.H. "A Responsive Distributed Routing Algorithm for Computer Networks." I~EE lnans. Communic. COM-3d, 7 (July 1982): 1758-1762.
• 6: Kaliszewski, J.M. "/he New Routing Algorithm on the SITA Data Transport Network." In Pepformance of Computer-Communication Systems, pp. 415-431. Edited by H. Rudin and W. Bux. Amsterdam: North-Holland, 1984.
• 7: Kleinrock, L. "Principles and Lessons in Packet Communications." PPOC. I~~E 66, 11 (November 1978): 1320-1329.
• 8: Majithia, J.C.; Irland, M.; Grange, J.-L.; Cohen, M.; and O'Donnell, C.O. "Experiments in Congestion Control Techniques." In {}OW ContPo} in ComputeP NetwoPk$, pp. 211-234. Edited by J.-L. Grange and M. Glen. Amsterdam: North-Holland, i979.
• 9: Merlin, D.M. and Segall, A. "A Failsafe Distributed Routing Protocol." fEE{ Tnan$. Communic. C~X-27, 9 (September 1979): 1280-1287.
• 10: Seligman, D.R. "Traffic Routing in a Computer Network." ?8PfoPNance 7, 2 (April 1984): 59-64.
• 11: 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]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Management, Theory