Requirements for deadlock-free, adaptive packet routing

ABSTRACT

This paper studies the problem of deadlock-free packet routing in parallel and distributed architectures. We present three main results. First, we show that the standard technique of ordering the queues so that every packet always has the possibility of moving to a higher ordered queue is not necessary for deadlock-freedom. Second, we show that every deadlock-free, adaptive packet routing algorithm can be restricted, by limiting the adaptivity available, to obtain an oblivious algorithm which is also deadlock-free. Third, we show that any packet routing algorithm for a cycle or torus network which is free of deadlock and which uses only minimal length paths must require at least three queues in some node. This matches the known upper bound of three queues per node for deadlock-free, minimal packet routing on cycle and torus networks.

REFERENCES

• 1: Baruch Awerbuch , Shay Kutten , David Peleg, Efficient deadlock-free routing, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.177-188, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112616]
• 2: Robert Cypher and Luis Gravano. Adaptive, deadlock-free packet routing in torus networks with minimal storage. Technical Report RJ 8571, IBM Almaden Research Center, January 1992. Also to appear in Proc. 1992 Intl. Conf. on Parallel Processing.
• 3: W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 4: Sergio A. Felperin, Hern&n Laflitte, Guillermo Buranits, and Jorge L.C. Sanz. Deadlock-free minimal packet routing in the torus network. Technical Report TR:91-22, IBM Argentina, CRAAG, 1991.
• 5: B. Garish, P.M. Merlin, and P.J. Schweitzer. Minimal buffer requirements for avoiding store-an& forward deadlock. Technical Report RC 6672, IBM T.J. Watson Research Center, August 1977.
• 6: Inder S. Gopal. Prevention of store-and-forward deadlock in computer networks. IEEE Transactions on Communications, 33(12):1258-1264, December 1985.
• 7: Luis Gravano, Gustavo D. Pifarr~, Sergio A. Felperin, and Jorge L.C. Sanz. Adaptive deadlock-free worm-hole routing with all minimal paths. Technical Report TR:91-21, IBM Argentina, CRAAG, 1991.
• 8: K.D. Giinther. Prevention of deadlocks in packetswitched data transport systems. IEEE Transactions on Communications, 29(4), April 1981.
• 9: Peter A.J. Hilbers and Johan J. Lukkien. Deadlockfree message routing in multicomputer networks. Distributed Computing, 3:178-186, 1989.
• 10: C. R. Jesshope , P. R. Miller , J. T. Yantchev, High performance communications in processor networks, Proceedings of the 16th annual international symposium on Computer architecture, p.150-157, April 1989, Jerusalem, Israel
• 11: P. Kermani and L. Kleinrock. Virtual Cut- Through: A new computer communication switching technique. Computer Networks, 3:267-286, 1979.
• 12: Smaragda Konstantinidou, Adaptive, minimal routing in hypercubes, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.139-153, March 1990, Boston, Massachusetts, United States
• 13: S. Konstantinidou , L. Snyder, The chaos router: a practical application of randomization in network routing, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.21-30, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97452]
• 14: Yishay Mansour , Boaz Patt-Shamir, Greedy packet scheduling on shortest paths (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.165-175, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112615]
• 15: P.M. Merlin and P.J. Schweitzer. Deadlock avoidance in store-and-forward networks. 1: Store-andforward deadlock, iEEE Transactions on Communications, 28(3):345-354, March 1980.
• 16: Yoram Ofek , Moti Yung, Principle for high speed network control: congestion-and deadlock-freeness, self-routing, and a single buffer per link, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.161-175, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93414]
• 17: Gustavo D. Pifarré , Luis Gravano , Sergio A. Felperin , Jorge L. C. Sanz, Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.278-290, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113405]
• 18: Sam Toueg and Kenneth Steiglitz. Some complexity results in the design of deadlock-free packet switching networks. SIAM Journal on Computing, 10(4):702-712, November 1981.
• 19: Sam Toueg and Jeffrey D. Ullman. Deadlock-free packet switching networks. SIAM Journal on Computing, 10(3):594-611, August 1981.
• 20: J. Yantchev and C.R. Jesshope. Adaptive, low latency, deadlock-free packet routing for networks of processors. IEE Proc., Pt. E, 136(3):178-186, May 1989.

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.1 Network Architecture and Design
          Subjects: Distributed networks

  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, Reliability, Verification