Adaptive and dynamic message routing system for multinode wormhole networks

• US 5,602,839 A
• Filed: 11/09/1995
• Issued: 02/11/1997
• Est. Priority Date: 11/09/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Annapareddy, Narasimhareddy, Brady, James T., Finney, Damon W.
• Primary Examiner(s): Kizou, Hassan
• Application Number:
  US08/555,539
• Time in Patent Office: 460 Days
• Field of Search: 370/54, 370/58.2, 370/58.3, 370/60, 370/60.1, 370/85.13, 370/94.1, 370/94.2, 370/94.3, 370/85.14, 370/92
• US Class Current: 370/405
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/40 Wormhole routing
• CPC Class Codes: H04Q 3/665 Circuit arrangements therefor

Abstract

In a multinode communication or multiprocessor network, messages are communicated from one node to another using an adaptive and dynamic routing scheme. The routing scheme includes two-level multi-path routing tables at each node to ensure efficient delivery of the messages. An entry in the level-1 table identifies a group of nodes and entry in the level-2 table identifies the address for each node within that group. The routing scheme also includes a deflection counter in each message header to avoid endless rerouting of messages and an exponential backoff and retry policy to avoid deadlocks.

Claims

1. A wormhole network, comprising:

a plurality of nodes interconnected by communication links, said nodes divided into groups where each of said groups includes a predetermined number of said nodes not included in the other groups, each node having a local node address and a group address and further having access to a processor and memory;

each node including a level-1 table, said level-1 table comprising message delivery directions for delivering a message from a node of a group to another group in the network; and

each node including a level-2 table, said level-2 table comprising message delivery directions for delivering said message from a node of a group to the other nodes within said group.

2. A wormhole network according to claim 1 wherein each of said message delivery directions in said level-1 table includes the most preferred message delivery direction for delivering a message from a node of a group to another group in the network.

3. A wormhole network according to claim 2 wherein said message delivery directions in said level-2 table include most preferred message delivery directions for delivering a message from a node of a group to the other nodes within said group.

4. A wormhole network according to claim 3 wherein said message comprises a message header, said message header including a destination address, said destination address having a destination group address and a destination local node address.

5. A wormhole network according to claim 4 wherein said destination group address is used as an index into a level-1 table of a node receiving said message to select a message delivery direction if said destination group address does not match the node group address.

6. A wormhole network according to claim 5 wherein said destination local node address is used as an index into a level-2 table of a node receiving said message to select a message delivery direction if said destination group address matches the node group address.

7. A wormhole network according to claim 6 wherein said message header further comprises a deflection counter, said deflection counter is decremented by a node receiving said message if the node is not the destination node and the most preferred message delivery direction for delivering the message in the level-1 table of said node is unavailable.

8. A wormhole network according to claim 7 further comprising a backup and retry means for resending an unsuccessfully terminated message.

9. A method of delivering messages in a wormhole network from a source node to a destination node where each message includes a group address and a local node address for the destination node, comprising the steps of:

dividing nodes in said network into groups where each group comprises a plurality of the nodes not included in the other groups;

storing a level-1 routing table at each node for providing message delivery directions from a node to every other group in the network;

storing a level-2 routing table at each node for providing message delivery directions from a node of a group to the other nodes of said group; and

routing said message from the source node to the destination node using the level-1 table and level-2 table.

10. A method of delivering messages in a wormhole network according to claim 9 wherein said message delivery directions in said level-1 table includes the most preferred message delivery directions for delivering a message from a node of a group to other groups in the network.

11. A method of delivering messages in a wormhole network according to claim 10 wherein said message delivery directions in said level-2 table includes the most preferred message delivery directions for delivering a message from a node of a group to the other nodes within said group.

12. A method of delivering messages in a wormhole network according to claim 11 wherein said message comprises a message header, said message header including a destination address, said destination address having a destination group address and a destination local node address.

13. A method of delivering messages in a wormhole network according to claim 12 wherein said destination group address is used as an index into a level-1 table of a node receiving said message if said destination group address does not match the node group address.

14. A method of delivering messages in a wormhole network according to claim 13 wherein said destination local node address is used as an index into a level-2 table of a node receiving said message if said destination group address matches the node group address.

15. A method of delivering messages in a wormhole network according to claim 14 wherein said message header further comprises a deflection counter, said deflection counter is decremented by a node receiving said message if the node is not the destination node and the most preferred message delivery direction in the level-1 table is unavailable.

16. A method of delivering messages in a wormhole network according to claim 15 further comprising a backoff-and-retry means for resending an unsuccessfully terminated message.

17. A wormhole network comprising:

a plurality of nodes interconnected by communication links, said nodes divided into gateway nodes and local nodes where each of said gateway nodes controls message delivery to a predetermined number of said local nodes, each gateway node is identified by a gateway node address and each local node is identified by a local node address and a gateway node address, each of said nodes further having access to a processor and memory;

a level-1 table stored at each gateway node, said level-1 table comprising message delivery directions, including the most preferred message delivery directions, for delivering a message from a gateway node to other gateway nodes in the network, said message comprising a message header, said message header including a destination address, said destination address having a destination gateway node address and a destination local node address;

a level-2 table stored at each local node, said level-2 table comprising message delivery directions, including the most preferred message delivery directions, for delivering said message among the local nodes controlled by a gateway node; and

wherein said destination gateway node address is used as an index into a level-1 table of a gateway node receiving said message if said destination gateway node address does not match the gateway node address of the gateway node receiving said message.

18. A wormhole network according to claim 17 wherein said destination local node address is used as an index into a level-2 table of a node receiving said message if said destination gateway node address matches the gateway node address of the gateway node receiving said message.

19. A wormhole network according to claim 18 wherein said message header further comprises a deflection counter, said deflection counter is decremented by a gateway node receiving said message if the gateway node is not the destination gateway node and the most preferred message delivery direction in the level-1 table is unavailable.

20. A wormhole network according to claim 19 further comprising a backup and retry means for resending an unsuccessfully terminated message.

21. A method of delivering messages in a wormhole network from a source node to a destination node where each message comprises a message header, said message header including a destination address, said destination address having a destination gateway node address and a destination local node address comprising the steps of:

dividing nodes in said network into gateway nodes and local nodes where each gateway node controls message delivery to a predetermined number of local nodes;

storing a level-1 routing table at each gateway node for providing message delivery directions, including the most preferred message delivery directions, from a gateway node to the other gateway nodes in the network;

storing a level-2 routing table at each local node for providing message delivery directions, including the most preferred message delivery directions, from a local node of a gateway node to the other local nodes of said gateway node;

routing said message from the source node to the destination gateway node using the level-1 table at each gateway node used in the network for message delivery;

routing said message from the destination gateway node to the destination local node using the level-2 table at each local node used in the network for message delivery; and

wherein said destination gateway address is used as an index into a level-1 table of a gateway node receiving said message if said destination gateway address does not match the gateway node address.

22. A method of delivering messages in a wormhole network according to claim 21 wherein said destination local node address is used as an index into a level-2 table of a local node receiving said message if said destination gateway address matches the gateway node address.

23. A method of delivering messages in a wormhole network according to claim 22 wherein said message header further comprises a deflection counter, said deflection counter is decremented by a node receiving said message if the node is not the destination node and the most preferred message delivery direction from that node to the next node is unavailable.

24. A method of delivering messages in a wormhole network according to claim 23 further comprising a backup and retry means for resending an unsuccessfully terminated message.