Method of routing a plurality of messages in a multi-node computer network

• US 5,111,198 A
• Filed: 12/18/1990
• Issued: 05/05/1992
• Est. Priority Date: 03/24/1988
• Status: Expired due to Term

• Current Assignee: TM Patents LP
• Original Assignee: Thinking Machines Corporation (Oracle Corporation)
• Inventors: Kuszmaul, Bradley C.
• Primary Examiner(s): Yusko, Donald J.
• Assistant Examiner(s): Magistre, Dervis
• Application Number:
  US07/629,026
• Time in Patent Office: 504 Days
• Field of Search: 340/835.02, 340/825.03, 340/825.5, 340/825.52, 370/58.2, 370/58.3, 370/61, 370/85.2, 370/91, 370/92, 370/93, 370/94.1, 370/15, 370/60
• US Class Current: 370/410
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/24 Multipath

Abstract

A message is generated at each of a plurality of source nodes, each message comprising at least address information identifying a first or destination node Di, and address information identifying a source node Si. The address information for the destination node is then used to route each message through the nodes of the communication network toward its destination node. At each node where two messages meet that are addressed to the same destination node, a second two messages are generated in place of the first two messages. One of these messages is routed toward the destination node while the other is routed toward an auxiliary node Ai whose address is specified in the message. If any further collisions take place between two messages routed to the same destination node, again two more messages are generated in place of the two colliding messages and one is routed toward the destination node while the other is routed toward another auxiliary node. The messages routed to the auxiliary node contain address information sufficient to route a message from the destination node to all the source nodes that originally addressed it.

Claims

1. In a data communication network in which messages are routed among a plurality of nodes, a method of routing messages from different source nodes to a common destination node comprising the steps of

a. generating a message at each of i source nodes, each said message comprising at least the information Di, Si, where Di is address information for the destination node for the message generated at the ith source node, and Si is address information for ith source node,

b. routing each message toward its destination node,

c. at a node where at least a first two messages meet that are addressed to the same destination node D1 and comprise at least the information D1, S1 and D1, S2, where D1 is address information for the destination of the two messages and S1 and S2 are address information for the source nodes of the two messages, generating a second two messages in place of the first two messages, the first said message comprising at least the information D1, A1 and the second message comprising at least the information A1, S1, S2, where A1 is address information for an auxiliary node that is neither a destination node nor a source node,

d. routing the first of said second messages toward the destination node, D1,

e. routing the second of said second messages toward the auxiliary node, A1, whose address is specified in said second message,

f. upon receipt of a message at a destination node, D1, generating a message in response thereto, said message comprising at least address information for an auxiliary node specified by the message received at the destination node,

g. routing said message from the destination node through the nodes of the communication network toward said auxiliary node identified by the address information A1, using address information for the auxiliary node specified by the first of said second messages, and

h. after receipt at node A1 of a message from the destination node and the second message comprising at least the information A1, S1, S2, generating two messages, one addressed to node S1 and the other to node S2.

2. The method of claim 1 wherein the address of the auxiliary node is generated at the time the first two messages meet.

3. The method of claim 1 wherein the address of an auxiliary node is part of the message routed from each source node.

4. In a data communication network in which messages are routed among a plurality of nodes, a method of routing messages from different source nodes to a common destination node comprising the steps of:

a) generating a message at each source node, said message comprising at least address information for said destination node and address information for said source node,

b) routing each message through the nodes of the communication network toward its destination node,

c) at a node where at least a first two messages meet that are addressed to the same destination node, generating a second two messages in place of the first two messages,

a first of said second messages comprising at least address information for said destination node and address information for a first auxiliary node that is neither a source node nor a destination node, and

a second of said second messages comprising address information for said first auxiliary node and address information for each of the source nodes identified in the first messages,

d) routing the first of said second messages toward the destination node whose address is specified in said second message,

e) routing the second of said second messages toward the first auxiliary node,

f) upon receipt of a message at the destination node, generating a message in response thereto that is addressed to an auxiliary node specified in the message received at the destination node,

g) routing said message from the destination node through the nodes of the communication network toward said first auxiliary node using address information for the auxiliary node specified by the first of said second messages, and

h) after receipt at said first auxiliary node of said message from the destination node and the second of said second messages, generating two messages one addressed to the source node of the first of the first two messages and the other addressed to the source node of the second of the first two messages.

5. The method of claim 4 wherein the address of the auxiliary node is generated at the time the first two messages meet.

6. The method of claim 4 wherein the address of an auxiliary node is part of the message routed from each source node.

7. In a data communication network in which messages are routed among a plurality of nodes, a method of routing messages from different source nodes to a common destination node comprising the steps of

a. generating a message at each of i source nodes, each said message comprising at least the information Di, Si, Ai, where Di is address information for the destination node for the message generated at the ith source node, Si is address information for ith source node, and Ai is address information for an auxiliary third node uniquely associated with the ith source node and neither a destination node nor a source node,

b. routing each message toward its destination node,

c. at a node where at least a first two messages meet that are addressed to the same destination node D1 and comprise at least the information D1, S1, A1 and D1, S2, A2, where D1 is address information for the destination of the two messages, S1 and S2 are address information for the source nodes of the two messages and A1 and A2 are address information for the auxiliary nodes associated with the two source nodes, generating a second two messages in place of the first two messages, the first said message comprising at least D1, A1, A2 and the second message comprising at least the information A1, S1, S2,

d. routing the first of said second messages toward the destination node, D1,

e. routing the second of said second messages toward the auxiliary node, A1, whose address is specified in said second message,

f. upon receipt of a message at a destination node, D1, generating a message in response thereto, said message comprising at least address information for an auxiliary node specified by the message received at the destination node,

g. routing said message from the destination node through the nodes of the communication network toward said auxiliary node identified by the address information A1, using address information for the auxiliary node specified by the first of said second messages, and

h. after receipt at node A1 of said message from the destination node and the second message comprising at least the information A1, S1, S2, generating two messages, one addressed to node S1 and the other to node S2.

8. In a data communication network in which messages are routed among a plurality of nodes, a method of routing messages from different source nodes to a common destination node comprising the steps of:

a) generating a message at each source node, said message comprising at least address information for said destination node, address information for said source node and address information for a first auxiliary node that is neither a source node nor a destination node,

b) routing each message through the nodes of the communication network toward its destination node,

c) at a node where at least a first two messages meet that are addressed to the same destination node, generating a second two messages in place of the first two messages,

a first of said second messages comprising at least address information for said destination node and address information for each of said first auxiliary nodes identified in the first two messages, and

a second of said second messages comprising address information for one of said first auxiliary nodes identified in the first two messages and address information for each of the source nodes identified in the first two messages,

d) routing the first of said second messages toward the destination node whose address is specified in said second message,

e) routing the second of said second messages toward the first auxiliary node whose address is specified in both of said second messages,

f) upon receipt of a message at the destination node, generating a message in response thereto that is addressed to an auxiliary an auxiliary node whose address is specified in the message received at the destination node,

g) routing said message from the destination node through the nodes of the communication network toward said first auxiliary node using address information for the auxiliary node specified by the first of said second messages, and

h) after receipt at said first auxiliary node of said message from the destination node and the second of said second messages, generating two messages one addressed to the source node of the first of the first two messages and the other addressed to the source node of the second of the first two messages.