Deadlock-free packet switching networks

ABSTRACT

Deadlock is one of the most serious system failures that can occur in a computer system or a network. Deadlock states have been observed in existing computer networks emphasizing the need for carefully designed flow control procedures (controllers) to avoid deadlocks. Such a deadlock-free controller is readily found if we allow it global information about the overall network state. Generally, this assumption is not realistic, and we must resort to deadlock free local controllers using only packet and node information. We present here several types of such controllers, we study their relationship and give a proof of their optimality with respect to deadlock free controllers using the same set of local parameters.

REFERENCES

• 1: S.B. Akers, "On the Construction of (d,k) Graphs," IEEE Trans. E. C.14 (1965), p. 448.
• 2: B.W. Arden and H. Lee, "A Multitree Structured Network," Proc. IEEE COMPCON 78, Washington, D. C., pp. 201-210, Sept. 1978.
• 3: H. Friedman, "A Design for (d,k) Graphs," IEEE Trans. E. C.15 (1966), pp. 253-254.
• 4: K. D. Gunther, "Prevention of Buffer Deadlocks in Packet Switching Networks," IFIP-IIASA workshop on data communications, Ladenberg, Austria, g.15-g.19, Sept., 1975.
• 5: M.G. Gouda, "Protocol machines," Ph. D thesis, Dept. of C. S., Univ. of Waterloo, Waterloo, Canada, 1977.
• 6: Stephen R. Kimbleton , G. Michael Schneider, Computer Communication Networks: Approaches, Objectives, and Performance Considerations, ACM Computing Surveys (CSUR), v.7 n.3, p.129-173, Sept. 1975 [doi>10.1145/356651.356653]
• 7: A. Giessler, J. Haenle, A Koenig, and E. Pade, "Free Buffer Allocation - an Investigation by Simulation," Computer Networks, 2 (1978), pp.191-208.
• 8: L. Kleinrock, Queueing Systems Vol. II: Computer Applications, Wiley, N. Y., 1976.
• 9: D .E . Morgan and D. J. Taylor, "Computer network reliability and availability: the state of the art," Conf. Rec. 1978 IEEE Intl. Conf. on Communications, 1, pp. 3.3.1-3.3.5, Toronto, June, 1978.
• 10: E. Raubold and J. Haenle, "A Method of Deadlock-Free Resource Allocation and Flow Control in Packet Networks," Proc. ICCC 76 Toronto, Ont., Canada, Aug., 1976, pp. 483-487.
• 11: H. S. Stone, "Parallel Processing with the Perfect Shuffle," IEEE Trans. Comput.20 (1971), pp. 153-161.
• 12: R. M. Storwick, "Improved Construction Techniques for (d,k) Graphs," IEEE Trans. Comput.19 (1970) pp. 1214-1216.
• 13: S Toueg and K. Steiglitz, "Some results in the design of packet switching networks," unpublished memorandum, Princeton Univ, Dept. of EECS, May 1979.
• 14: S. Toueg and K. Steiglitz, "The Design of Small-Diameter Networks by Local Search," to appear, IEEE Trans. Computers.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Deadlocks

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

General Terms:
Algorithms, Design, Theory