Message tracking in a parallel network employing a status word at each node which reflects a message's progress

• US 5,404,565 A
• Filed: 02/15/1994
• Issued: 04/04/1995
• Est. Priority Date: 08/07/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lackritz, Neal M., Gould, Joel M.
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): GECKIL, MEHMET B
• Application Number:
  US08/197,004
• Time in Patent Office: 413 Days
• Field of Search: 395/200, 395/800, 395/725, 370/94.1-94.3, 370/85.13, 370/60
• US Class Current: 709/237
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus

Abstract

A multiple node network is described wherein messages are transmitted between source and intermediate nodes to a destination node, the network including a message progress reporting system which employs a status word that enables the source node to determine a message'"'"'s progress. Each parent node comprises a status word register for reporting a status word that indicates the progress of the message. The parent node further includes a routing mechanism for receiving a status word from a child node that indicates the message'"'"'s progress in the child node and at succeeding nodes thereafter. The routing mechanism updates the status word in the status word register in accordance with the received status word. The routing mechanism further transmits the updated status word from the parent node to a source node upon the parent node having received status words from all child nodes to which the parent node transmitted the message whereby each succeeding parent node does not transmit its status word until all succeeding nodes have accumulated their status words and reported upward in the tree.

Claims

1. A multiple node network comprising (i) a source node wherein a message is originated, (ii) a destination node where inter-node transmission of said message is terminated and (iii) one or more intermediate node(s) through which said message travels before arriving at said destination node, said intermediate node(s) being connected between said source node and said destination node, said network including a message progress reporting system wherein a received status word enables a source node to determine a message'"'"'s transmission progress through said multiple node network, a node comprising:

transmitter means coupled via communication links to a plurality of child nodes, for transmitting a message to at least one said child node;

status word logic means for storing a status word which indicates transmission progress of said message;

receiving means connecting a child node to said status word logic means, for receiving a status word from said child node, said status word indicating said message'"'"'s transmission progress at least at said child node, and for creating an updated status word in said status word logic means in accordance with said status word received from said child node;

child register means coupled to said receiving means for indicating when a status word has been received from each child node to which said message was transmitted; and

transmitter means for transmitting said updated status word from said status word logic means to a source node when said child register means indicates receipt of status words from all child nodes to which said message was transmitted and said status word logic means has updated said status word in accordance with said received status words.

2. The multiple node network as recited in claim 1 wherein said receiving means OR'"'"'s a received status word from a child node, on a bit-wise basis, with a stored status word contained within said status word logic means to update said stored status word.

3. The multiple node network as recited in claim 2, wherein said transmitter means transmits to a source node only a single status word for each message.

4. The multiple node network as recited in claim 3, said parent node further comprising:

destination register means coupled to said transmitter means for indicating child nodes to which a message was transmitted.

5. The multiple node network as recited in claim 4, said parent node further comprising:

means coupled to said destination register means and said transmitter means, and for manifesting a value indicating that all child nodes have responded with a status word, said manifesting operative to enable said transmitter means to transmit said updated status word.

6. A system for reporting message progress in a network that comprises a plurality of nodes, said system including source nodes and destination nodes, a source node providing a message to a destination node, the combination comprising:

a. transmission means in each destination node for transmitting to a respective source node, a multi-bit status word which indicates progress of a message up to and at said destination node;

b. receiving means in a said respective source node for accumulating a said multi-bit status word, associated with a message, from status words received from all destination nodes to which said message was transmitted, said receiving means including child register means for indicating that a status word has been received from all destination nodes to which said message was transmitted, said accumulating employing a logical "or" operation of corresponding bits of said multi-bit status words receiving from all said destination nodes so as to create a single status word indicating progress of said message; and

c. means at each said source node for parsing a received, accumulated, status word to ascertain a said message'"'"'s progress.

7. A system as recited in claim 6, wherein said network includes a plurality of parent and child nodes, a plurality of levels of said parent and child nodes comprising a tree arrangement of nodes, no child node transmitting more than one status word per message to its parent node.

8. A system as recited in claim 7, wherein each said parent node only transmits a status word after status words from all of child nodes receiving a message from said parent node, have been received by a said parent node.

9. A system as recited in claim 8, wherein each said parent node includes a child node register which indicates child nodes to which a message has been transmitted.

10. A system as recited in claim 9, wherein each said multi-bit status word includes data indicative of a message'"'"'s transmission progress from input to output in a node.

11. A system as recited in claim 10, wherein each said multi-bit status word further includes data indicating a number of levels of a tree over which a message has traversed.