System for performing deadlock free message transfer in cyclic multi-hop digital computer network using a number of buffers based on predetermined diameter

• US 5,878,227 A
• Filed: 07/01/1996
• Issued: 03/02/1999
• Est. Priority Date: 07/01/1996
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Wade, Jon P., Heller, Steven K.
• Primary Examiner(s): Luu, Le Hien
• Application Number:
  US08/674,277
• Time in Patent Office: 974 Days
• Field of Search: 395/800.29, 395/200.73, 395/200.65, 395/200.68, 370/248, 370/232, 370/473, 370/415, 370/406, 370/418, 370/230, 370/229
• US Class Current: 709/235
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 12/56 Packet switching systems

Abstract

In brief summary, the invention provides a new message packet transfer system, which may be used in, for example, a multiprocessor computer system. The message packet transfer system comprises a plurality of switching nodes interconnected by communication links to define at least one cyclical packet transfer path having a predetermined diameter. The switching nodes may be connected to, for example, digital data processors and memory to form processing nodes in an multiprocessor computer system, and/or to other sources and destinations for digital data contained in the message packets. The switching nodes transfer message packets each from a respective one of the switching nodes as a respective source switching node to a respective one of the switching nodes as a respective destination switching node. At least one of the switching nodes has a plurality of buffers for buffering a corresponding plurality of message packets that it (that is, the at least one of the switching nodes) receives from another of said switching nodes during a message transfer operation, which ensures that deadlock does not occur during the message transfer operation.

Claims

1. A message packet transfer system comprising a plurality of switching nodes interconnected by communication links to define at least one cyclical packet transfer path having a predetermined diameter, the switching nodes transferring message packets each from a respective one of the switching nodes as a respective source switching node to a respective one of the switching nodes as a respective destination switching node, at least one of the switching nodes comprising:

A. a number of buffers, the number being a function of the predetermined diameter; and

B. an interface configured to receive message packets from at least one other of said switching nodes during a message transfer operation, buffer them in said buffers, and transfer ones of said message packets for which the at least one of said switching nodes is not the destination switching node to at least a second other of said switching nodes, thereby to ensure that deadlock does not occur during the message transfer operation.

2. A message packet transfer system as defined in claim 1 in which, in said at least one switching node, one of said buffers operates as a destination buffer to buffer message packets received by said at least one of said switching nodes as a destination switching node.

3. A message packet transfer system as defined in claim 2 in which, in said at least one switching node, another of said buffers operates as an intermediate buffer to buffer message packets received by said at least one of said switching nodes for which said at least one of said switching nodes is not a destination switching node.

4. A message packet transfer system as defined in claim 3 in which the interface includes:

C. a destination message packet transfer element configured to transfer message packets received from said at least one other of said switching node for which said at least one switching node is a destination switching node to said destination buffer for buffering, and

D. an intermediate message packet transfer element configured to transfer message packets received from said at least one other of said switching nodes for which said at least one switching node is not a destination switching node to said intermediate buffer for buffering.

5. A message packet transfer system as defined in claim 4 in which said interface further transfers message packets to at least a second other of said switching nodes, said interface transferring message packets from said intermediate buffer to said at least a second other of said switching nodes.

6. A message packet transfer system as defined in claim 5 in which the at least one switching node is connected to a message packet generator configured to provide message packets for transfer by said at least one switching node, the interface further selectively transferring message packets received from one of the message packet generator or the intermediate buffer to said at least a second other of said switching nodes.

7. A message packet transfer system as defined in claim 1 in which the number of said buffers is selected to correspond to the predetermined diameter.

8. A message packet transfer system as defined in claim 1 in which the switching nodes transfer message packets over said communication links in one or more hops, in each hop one of said message packets being transferred by one of said switching nodes to another of said switching nodes, in said at least one of said switching nodes a buffer selected to buffer received message packet being a function of the number of hops for the message packet from the source switching node to the at least one of said switching nodes.

9. A message packet transfer system as defined in claim 1 in which a plurality of the switching nodes each have a plurality of buffers configured to buffer a corresponding plurality of message packets received thereby from respective ones of at least one other of said switching nodes during said message transfer operation.

10. A message packet transfer method for effecting the transfer of message packets in a system comprising a plurality of switching nodes interconnected by communication links to define at least one cyclical packet transfer path having a predetermined diameter, the switching nodes transferring message packets each from a respective one of the switching nodes as a respective source switching node to a respective one of the switching nodes as a respective destination switching node, the method comprising the steps of:

A. establishing a number of buffers, the number being a function of the predetermined diameter; and

B. receiving message packets from at least one other of said switching nodes during a message transfer operation, buffering the received message packets in said buffers, and transferring ones of said message packets for which the at least one of said switching nodes is not the destination switching node to at least a second other of said switching nodes, thereby to ensure that deadlock does not occur during the message transfer operation.

11. A message packet transfer method as defined in claim 10 in which, in said at least one switching node, one of said buffers is enabled to operate as a destination buffer to buffer message packets received by said at least one of said switching nodes as a destination switching node.

12. A message packet transfer method as defined in claim 11 in which, in said at least one switching node, another of said buffers is enabled to operate as an intermediate buffer to buffer message packets received by said at least one of said switching nodes for which said at least one of said switching nodes is not a destination switching node.

13. A message packet transfer method as defined in claim 12 in which said at least one switching node, during said message packet receiving step, performs the steps of:

C. transferring message packets received from said at least one other of said switching node for which said at least one switching node is a destination switching node to said destination buffer for buffering, and

D. transferring message packets received from said at least one other of said switching nodes for which said at least one switching node is not a destination switching node to said intermediate buffer for buffering.

14. A message packet transfer method as defined in claim 13 in which said interface is further enabled to transfer message packets to at least a second other of said switching nodes, said interface being enabled to transfer message packets from said intermediate buffer to said at least a second other of said switching nodes.

15. A message packet transfer method as defined in claim 14 in which the at least one switching node is connected to a message packet generator configured to provide message packets for transfer by said at least one switching node, the interface further being selectively enabled to transfer message packets received from one of the message packet generator or the intermediate buffer to said at least a second other of said switching nodes.

16. A message packet transfer method as defined in claim 10 in which the number of said buffer is selected to correspond to the predetermined diameter.

17. A message packet transfer method as defined in claim 10 in which the switching nodes transfer message packets over said communication links in one or more hops, in each hop one of said message packets being transferred by one of said switching nodes to another of said switching nodes, in said at least one of said switching nodes a buffer being selected to buffer received message packet being a function of the number of hops for the message packet from the source switching node to the at least one of said switching nodes.

18. A message packet transfer method as defined in claim 10 in which a plurality of the switching nodes each have a plurality of buffers configured to buffer a corresponding plurality of message packets received thereby from respective ones of at least one other of said switching nodes during said message transfer operation.

19. A message packet transfer computer program product for use in connection with a system comprising a plurality of switching nodes interconnected by communication links to define at least one cyclical packet transfer path having a predetermined diameter, the switching nodes transferring message packets each from a respective one of the switching nodes as a respective source switching node to a respective one of the switching nodes as a respective destination switching node, at least one of the switching nodes including a computer, the message packet transfer computer program product comprising a computer-readable medium including:

A. a buffer establishment module configured to enable said computer to establish a number of buffers, the number being a function of the predetermined diameter and

B. an interface module configured to enable said computer to buffer a corresponding plurality of message packets received by said computer from at least one other of said switching nodes during a message transfer operation, thereby to ensure that deadlock does not occur during the message transfer operation.

20. A message packet transfer computer program product as defined in claim 19 in which said buffer establishment module enables said computer to operate one of said buffers as a destination buffer to buffer message packets received by said computer as a destination switching node.

21. A message packet transfer computer program product as defined in claim 20 in which said buffer establishment module enables said computer to operate another of said buffers as an intermediate buffer to buffer message packets received by said computer to be transferred to another of said switching nodes as a destination switching node.

22. A message packet transfer computer program product as defined in claim 21 in which the interface module enables the computer to:

C. transfer message packets received from said at least one other of said switching node for which said at least one switching node is a destination switching node to said destination buffer for buffering, and

D. transfer message packets received from said at least one other of said switching nodes for which said at least one switching node is not a destination switching node to said intermediate buffer for buffering.

23. A message packet transfer computer program product as defined in claim 22 in which said interface module further enables said computer to transfers message packets to at least a second other of said switching nodes, said interface module enabling the computer to transfer message packets from said intermediate buffer to said at least a second other of said switching nodes.

24. A message packet transfer computer program product as defined in claim 23 in which the at least one switching node is connected to a message packet generator configured to provide message packets for transfer by said at least one switching node, the interface module further enabling the computer to selectively transfer message packets received from one of the message packet generator or the intermediate buffer to said at least a second other of said switching nodes.

25. A message packet transfer computer program product as defined in claim 19 in which the number of said buffer is selected to correspond to the predetermined diameter.

26. A message packet transfer computer program product as defined in claim 19, in which the switching nodes transfer message packets over said communication links in one or more hops, in each hop one of said message packets being transferred by one of said switching nodes to another of said switching nodes, the message packet transfer computer program product in said at least one of said switching nodes a buffer selected to buffer received message packet being a function of the number of hops for the message packet from the source switching node to the at least one of said switching nodes.

27. A switching node for use in a message packet transfer system comprising a plurality of other switching nodes interconnected by communication links to define at least one cyclical packet transfer path having a predetermined diameter, the switching nodes transferring message packets each from a respective one of the switching nodes as a respective source switching node to a respective one of the switching nodes as a respective destination switching node, the switching node comprising:

A. a number of buffers, the number being a function of the predetermined diameter; and

B. an interface configured receive message packets from at least one other of said switching nodes during a message transfer operation, buffer them in said buffers, and transfer ones of said message packets for which the switching node is not the destination switching node to at least a second other of said switching nodes, thereby to ensure that deadlock does not occur during the message transfer operation.

28. A switching node for use in a message packet transfer system comprising a plurality of other switching nodes interconnected by communication links to define at least one cyclical packet transfer path having a predetermined diameter, the switching nodes transferring message packets each from a respective one of the switching nodes as a respective source switching node to a respective one of the switching nodes as a respective destination switching node, the switching node comprising:

A. a computer; and

B. a control subsystem for controlling the computer, the control subsystem comprising;

i. a buffer establishment module configured to enable the computer to establish a number of buffers, the number being a function of the predetermined diameter; and

ii. an interface module configured so enable the computer to receive message packets from at least one other of said switching nodes during a message transfer operation, buffer them in said buffers, and transfer ones of said message packets for which the switching node is not the destination switching node to at least a second other of said switching nodes, thereby to ensure that deadlock does not occur during the message transfer operation.

29. A control subsystem for controlling a computer in a switching node, the switching node comprising one of a plurality of switching nodes interconnected by communication links in a message packet transfer system, the communication links interconnecting the switching nodes to define at least one cyclical packet transfer path having a predetermined diameter, the switching nodes transferring message packets each from a respective one of the switching nodes as a respective source switching node to a respective one of the switching nodes as a respective destination switching node, the control subsystem comprising:

A. a buffer establishment module configured to enable the computer to establish a number of buffers, the number being a function of the predetermined diameter; and

B. an interface module configured so enable the computer to receive message packets from at least one other of said switching nodes during a message transfer operation, buffer them in said buffers, and transfer ones of said message packets for which the switching node is not the destination switching node to at least a second other of said switching nodes, thereby to ensure that deadlock does not occur during the message transfer operation.

30. A system for distributing code stored on a computer readable medium and executable by a computer, the code including a plurality of modules each configured to control the computer, the code comprising:

A. a buffer establishment module configured to enable said computer to establish a number of buffers, the number being a function of the predetermined diameter; and

B. an interface module configured to enable said computer to buffer a corresponding plurality of message packets received by said computer from at least one other of said switching nodes during a message transfer operation, thereby to ensure that deadlock does not occur during the message transfer operation.