Optimistic transmission flow control including receiver data discards upon inadequate buffering condition

[0002] “This patent application is a continuation-in-part of U.S. patent application Ser. No. 08/856,619, filed May 13, 1997, now U.S. Pat. No. 5,931,915, issued Aug. 3, 1999 and entitled: “METHOD FOR PROCESSING EARLY ARRIVAL MESSAGES WITHIN A MULTINODE ASYNCHRONOUS DATA COMMUNICATIONS SYSTEM”.

[0003] This Application relates to message processing systems. More particularly, this Application relates to a method for facilitating the transmission of messages from a source node to a destination node in a message processing system.

[0004] Message processing systems, for example, the multiprocessor data processing system 10 depicted in FIG. 1, require reliable message communication paths between respective ones of the processors 12₁. . . 12_j. The exemplary system 10 of FIG. 1 employs an exemplary communication medium or switch network 20 commonly coupled to the processors 12. The processors may require respective communication adapters 14₁. . . 14_jto control communications between each processor 12 and the medium 20 via respective connections 16₁. . . 16_j. Communication between, for example, software application(s) executing on the processors 12 of system 10 can thus be provided via medium 20. Storage medium 22 may be employed in the system to hold the applications, associated data, etc.

[0005] Because respective processors may be supporting different, but related application software partitions, messaging must be used as a form of communication between the processors. For example, messages may require transmission from a “source” node (e.g., processor 12₁) to a “destination” node (e.g., processor 12_j).

[0006] The asynchronous nature of the application software partitions on the source and destination nodes often results in a condition where the number of messages sent from a source node exceed the destination node's ability to handle them. Normally, the destination node is expected to post buffers to hold incoming messages. The messages can then be retrieved from the buffers and appropriately processed by the application software. This is illustrated in FIG. 2, which is a hybrid hardware/software diagram of a message processing system like that of FIG. 1 and which depicts a message source node 18₁and a message destination node 18_j. (The term “node” is used broadly herein to connote any identifiable combination of hardware and/or software to or from which messages are passed.) Source node 18₁has allocated therein send message buffers 30 within which are placed messages M(1), M(2) and M(3) which, for application reasons, are required to be sent through send message processing 32, across medium 20, to destination node 18_j.

[0007] Destination node 18_j, in anticipation of the arrival of messages from various sources in the system, can allocate or post receive buffers 40. In the example of FIG. 2, buffer B1 holds the first arriving message M(1), buffer B2 holds the second arriving message M(2) and buffer B3 holds the third arriving message M(3). Received message processing 42 then removes messages from their buffers and can then pass the messages to receive processing 44 (e.g., the application software partition executing at the destination node).

[0008] Those skilled in the art will understand that message ordering in a system can be imposed by using a particular protocol, e.g., messages sent from a particular source to a particular destination may be sequentially identified and the sequential indicia can be transmitted as control information along with the data portions of the messages.

[0009] The process of allocating or posting receive buffers 40 in destination node 18_jis often a dynamic one, and if more messages are arriving than there are buffers posted, buffer overrun can occur. Traditional solutions to avoid buffer overrun at the destination node include 1) data buffering with a pre-reservation protocol or, 2) adopting a convention wherein the destination node automatically discards packets assuming that the source node will retransmit them after a time-out. The first solution assumes a destination node that is frequently unprepared to accommodate data, and the second solution assumes a destination that is rarely unprepared to accommodate data.

[0010] A problem with the first solution occurs when message size is practically unbounded, or if the number of message sources is large. Large messages can be decomposed into smaller pieces and flow controlled into the buffers, if the overhead to do so is manageable. However, many sources present problems with buffer fragmentation or starvation. Distributed fairness protocols can be introduced to solve these problems, but at a price in complexity and additional overhead.

[0011] A problem with the time-out/retransmit solution is that should the destination be unable to accommodate the data for an extended period of time, many needless retransmits will occur, occupying otherwise useful bandwidth on the medium.

[0012] A third conventional solution to this problem is a rendezvous protocol. A rendezvous protocol involves the transmission from the source node of a control information packet relating to a message to be sent from the source node to the destination node. The control information may include an indication of the length of the entire data portion of the message to be sent, as well as indicia which identifies the message and/or its sequence. When a buffer of adequate length is allocated or posted at the destination node, an acknowledgment packet transmission is sent from the destination node to the source node, and the source node can thereafter reliably send the entire message to the destination node. This technique also makes conservative assumptions about the preparedness of the destination node to accommodate the data portion of the message. In conventional rendezvous protocols, the initial exchange of the control information and acknowledgment packets results in a loss of performance because two packets are now required to be exchanged between the source and destination nodes before any actual message data can be exchanged.

[0013] What is required, therefore, is a method, system, and associated program code and data structures, which prevent the performance degradation associated with packet retransmission after time-outs, or with standard rendezvous protocols in which an exchange of packets between source and destination nodes occurs before any actual message data is exchanged.

[0014] The shortcomings of the prior approaches are overcome by the present invention, which relates to a program product for facilitating the efficient transmission and flow control of messages from a source node to a destination node in a message processing system.

[0015] The present invention seeks to strike a balance between the ultra-conservatism of pure buffering and rendezvous, and the ultra-optimism of time-out/retransmit. The present invention assumes that the destination is generally able to accommodate data portions of messages, but if it is not, the time that it may take to become prepared may be very long. Such conditions often arise in multi-tasking systems where context swaps between processes are long and a process may be suspended for an unbounded period of time. To accommodate this type of environment, the present invention involves optimistically sending the data portion of a message along with control information, in an initial transmission from the source to the destination. However, it is not appropriate for the destination to discard the entire content of this transmission if it is unable to accommodate the data since there may be many time-out periods before the destination is subsequently able to accommodate the data. Therefore, the destination retains enough control information to identify the message to the source, but discards the data portion of the message (i.e., “runts” the message). The source does not time-out/retransmit, rather, it waits for the destination to notify it that it is prepared. At that time, the source retransmits the message, knowing the destination will be able to accommodate it. The number of retransmissions from the source node to the destination node is therefore bounded to one.

[0016] In that regard, in one aspect, the present invention relates to a flow control method for transmitting a plurality of messages from a source node to a destination node in a message processing system. The plurality of messages includes a first message comprising a data portion. The source node transmits the data portion of the first message, and control information of the first message, to the destination node. In response to the destination node being unable to accommodate the data portion of the first message, the destination node discards the data portion of the first message.

[0017] In further response to the destination node being unable to accommodate the data portion of the first message, the destination node retains at least some of the control information of the first message.

[0018] In response to the destination node being subsequently able to accommodate the data, the destination node uses at least some of the retained control information to transmit a first “pull” request to the source node to retransmit the data portion of the first message. In response to this pull request, the source node retransmits the data portion of the first message to the destination node.

[0019] The discarding process is repeated for messages subsequent to the first message, until the destination node becomes able to accommodate the data portion of the first message, as well as the data portions of the subsequent messages. In that regard, the present invention relates to, in another aspect, the destination node discarding the data portion of the first message (in response to being unable to accommodate the data portion) but retaining sequence indicia of the control information thereof, and sends a negative acknowledgment relating to the first message to the source node (i.e., “runts” the first message). Until it is able to accommodate any data portions of messages, the destination node discards respective data portions of subsequent messages that are received thereby, but retains the respective sequence indicia of the respective control information thereof, and sends respective negative acknowledgments relating thereto the source node.

[0020] As the destination node becomes able to accommodate the respective data portions of the first message and any of the subsequent messages, the destination node initiates, via respective pull requests to the source node, respective retransmissions of the respective data portions of the first message and said any of the subsequent messages. In response to respective pull requests from the destination node, the source node retransmits the respective data portions of the first message and said any of the subsequent messages to the destination node.

[0021] To control this operation at both the source and destination nodes, the source node maintains a message sent number, as well as an expected acknowledgment number, which is incremented as respective acknowledgments of successfully accommodated data portions of messages are received from the destination node. The destination node maintains a respective message number which is incremented as respective initial transmissions or retransmissions of data portions are successfully accommodated, as well as an expected “runt” number which is incremented as respective data portions of messages are discarded and negative acknowledgments transmitted to the source node therefor.

[0022] The herein disclosed flow control variant of the rendezvous protocol strikes a balance between the ultra-conservatism of pure buffering and rendezvous, and the ultra-optimism of time-out/retransmit, since it assumes that the destination is generally prepared, but if it is not, the time it may take to become prepared can be very long. This optimistic assumption leads to medium bandwidth savings, and further, the number of retransmits from the source node to the destination node is bounded to one.

[0023] The subject matter which is regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of practice, together with further objects and advantages thereof, may best be understood by reference to the following detailed description of the preferred embodiment(s) and the accompanying drawings in which:

[0024] FIG. 1 is an exemplary message processing system in the form of a multiprocessor data processing system having a plurality of processors coupled by a communication medium;

[0025] FIG. 2 is a hybrid hardware/software diagram of a message processing system having message source and destination nodes, and posted receive buffering for message reception at the destination node; and

[0026] FIG. 3 is a protocol diagram of the flow control technique of the present invention in which data portions of messages are discarded by the destination node and are later retransmitted from the source node in response to pull requests from the destination node.

[0027] As discussed above, FIG. 1 depicts an exemplary message processing system in the form of a multiprocessor data processing system 10 having a plurality of processors 12₁. . . 12_j. Each processor may have a respective communication adapter 14 for operating its respective connection 16 to a commonly connected medium or switch network 20. A storage medium 22 may also be provided in the system to hold and/or support application software and all relevant data structures, protocols, etc.

[0028] FIG. 2 is a hybrid hardware/software diagram of a generalized message processing system having a message source node 18₁and a message destination node 18_j. The term “node” is used broadly herein to connote any identifiable combination of hardware and/or software to or from which messages are passed.

[0029] It is assumed hereafter for illustrative simplicity that the application running on the message processing system requires messages 30 to be sent from the source node 18₁to the destination node 18_jvia the medium 20. (However, all nodes in an actual system are expected, though not required, to contain both the message sending and receiving capabilities discussed herein, since each node would generally be expected to send and receive messages in accordance with the message transmission modes disclosed herein.)

[0030] In accordance with the present invention, as illustrated in the protocol diagram of FIG. 3, a flow control method for transmitting a plurality of messages (msg_5, msg_6 and msg_7) from a source node to a destination node is depicted. To support this protocol, the source node maintains an expected acknowledgment number 210 and a sequence number 220. Further, the destination node maintains an expected message number 230, and an expected runt number 240. As discussed further below, these values are incremented at certain points during the operation of the protocol.

[0031] This exemplary protocol diagram assumes that msg_5 is the next sequential message to be transmitted from the source node to the destination node. Therefore, a transmission of msg_5102 occurs from the source node to the destination node. The destination node, in expectation of this msg_5, has its expected message number, as well as its expected runt number, set at the value 5. However, in accordance with the general condition described above, i.e., the inability of the destination node to accommodate the data portion of msg_5, (due, for example, to buffer unavailability) the message is “runted” and the data portion thereof discarded at the destination node. In response to this condition, the destination node may send a runt_5 message 104 to the source node, which is effectively a negative acknowledgment indicating that the data portion of msg_5 was not successfully accommodated. To properly prepare this message, the destination retains at least some control information (e.g., a sequence number) from the initial transmission 102 adequate to identify the message to the source. In one embodiment, the source may return an acknowledgment 106 to the destination relating to the negative acknowledgment 104.

[0032] In accordance with a second condition discussed above, i.e., the probable inability of the destination node to accommodate messages for longer periods of time, subsequent messages are also runted until this condition subsides. Therefore, the initial transmission 103 of msg_6 is similarly runted and a runt_6 message 105 is sent from the destination to the source, and is likewise followed by an acknowledgment from the source to the destination 107. Since msg_5 has not yet been successfully accommodated, the expected message number at the destination node has not been incremented. However, the expected runt number has been incremented twice, in view of the runts of both msg_5 and msg_6. Similarly, at the source node, since the messages have not yet been successfully accommodated and therefore acknowledged, the expected acknowledgment number has not been incremented, but the sequence number of messages initially sent has been incremented twice.

[0033] Eventually, the destination node becomes able to accommodate the messages by, for example, posting a buffer for msg_5, and a pull request 108 is transmitted from the destination to the source requesting a retransmission of the data portion of msg_5. Similarly, a buffer has been posted for msg_6, at the destination, and a pull request 109 can similarly be transmitted for msg_6. The retained control information (e.g., sequence number) is used to support the later transmission of these pull requests from the destination. (Note that the source node has at this time been awaiting receipt of the pull requests, and has not performed any time-out/retransmits. The source node is awaiting the ability of the destination node to accommodate the data portions, and is therefore not making any needless retransmissions.)

[0034] In response to the pull requests, retransmissions msg_5r110 and msg_6r111 occur from the source to the destination, at which time the expected message number is incremented at the destination, noting the successful accommodation of these data portions. In response, acknowledgments 112 and 113 are transmitted from the destination to the source, at which time the expected acknowledgment numbers are also incremented at the source.

[0035] With respect to the next sequential message, msg_7114, since a buffer has already been posted, no discard/retransmission cycle is necessary, the message is successfully accommodated at the destination, and an acknowledgment 115 is sent from the destination to the source acknowledging receipt of same. The expected acknowledgment number, sequence number, as well as the expected message number are incremented upon successful transmission and receipt, as depicted, but the expected runt number at the destination node has been pre-incremented upon the buffer posting, indicating that no runting of the next sequential message will be required due to buffer availability.

[0036] As discussed above, the source and destination nodes may each include a communication adapter to handle their interface to the communication medium. Further, Communication Subsystem Software (“CSS”) may be implemented at the nodes, which is a layer of software running over the communication adapter.

[0037] The destination nodes keep track of the expected runt numbers and expected message numbers on a per-path basis (i.e., per source node). The expected runt number is equal to the sequence number following the last runted message, or successfully received message. If a message arrives at the destination with a different sequence number than expected, the expected runt number is examined. Messages with sequence numbers less than the expected runt number are dropped. Messages with sequence numbers greater than or equal to the expected runt number are runted, and the expected runt number is updated to the following sequence number. This ensures that messages are not runted multiple times.

[0038] The techniques of the present invention therefore generally assume sequential sending and in-order receipt of messages between the source and destination.

[0039] The following, exemplary packet formats show a message packet, having control information in the first few fields thereof, followed by a data portion. Pull request, and pull reply message packets can be used to request a retransmission by the destination, and provide the retransmitted data from the source to the destination at the appropriate time, as discussed above. Further, an acknowledgment packet can be used as either a positive or negative acknowledgment, as discussed above. The formats depicted are followed by Exemplary Fields for the control information. The Exemplary Fields include, for example, a FLAGS field which can effect a positive or negative acknowledgment, as well as a SEQ. # field which specifies the sequence number assigned to the message.

[0040] Those skilled in the art will further recognize that the packets shown herein may include other facilitating control information, e.g., intramessage packet ordering information, and low-level flow control acknowledgments, and no limitation should be inferred from the absence of any such control information from these exemplary formats.

[0041] CONTROL

[0042] This field is taken from the send message descriptor and describes various characteristics of the message.

[0043] Kernel/-User Message

[0044] Destination Interrupt Requested

[0045] Pull Reply

[0046] Pull Request

[0047] Resend

[0048] Rendezvous Request

[0049] For more details refer to the definition of a send message descriptor.

[0050] The present invention can be included in an article of manufacture (for example, one or more computer program products) having, for example, computer usable media such as the media 22 of FIG. 1 or the memory/data structures presented above. The media has embodied therein, for example, computer readable program code means for providing and facilitating the mechanisms of the present invention. The article of manufacture can be included as part of a system or sold separately. Whether in the above-described article of manufacture, or within other memory components, the present invention also includes the formatted message, buffer, command and any other data structures discussed above which also facilitate the mechanisms of the present invention.

[0051] While the invention has been particularly shown and described with reference to preferred embodiments) thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention.