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

• US 6,480,897 B1
• Filed: 12/29/1997
• Issued: 11/12/2002
• Est. Priority Date: 05/13/1997
• Status: Expired due to Term

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Benner, Alan F., Joseph, Douglas J., Kampf, Francis A., Desnoyers, Christine M.
• Primary Examiner(s): Rinehart, Mark H.
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US08/998,965
• Time in Patent Office: 1,779 Days
• Field of Search: 370/79, 370/85.13, 370/230, 370/94.1, 370/276, 370/216, 370/229.95, 370/237, 370/395, 370/229, 395/180, 395/182.16, 395/706, 709/233, 709/237, 709/200, 709/236, 709/245, 709/231, 709/232, 709/216, 709/105, 709/222, 709/235, 371/32, 380/45, 380/42, 710/100, 340/825.44, 375/219
• US Class Current: 709/237
• CPC Class Codes: G06F 15/17368 non hierarchical topologies

Abstract

A program product for a message processing system in which messages are transmitted from source nodes to destination nodes. A transmission flow control technique is disclosed in which the source node optimistically sends control information and a data portion of a message, and wherein a destination node discards the data portion of the message if it is unable to accommodate it. The destination node, however, retains enough of the control information to identify the message to the source node, and when the destination node is subsequently able to accommodate the data portion, the destination node issues a request to the source node to retransmit the data portion of the message. Discarding of one message is followed by discards of sequential messages, until the destination node is able to accommodate the data portions of messages. The flow control technique disclosed herein is used, for example, in an environment where buffers are posted to accommodate messages at the destination node, and is particularly suited for conditions arising in multi-tasking systems where the destination node is generally assumed to be prepared to accommodate data, however, if not prepared, is likely not prepared for long periods of time.

Claims

1. An article of manufacture comprising a computer useable medium having computer readable program code means embodied therein for flow-controlling a plurality of messages from a source node into a destination node in a message processing system, the plurality of messages including a first message comprising a data portion, the computer readable program code means in said article of manufacture comprising:

code means for the source node transmitting (102) the data portion of the first message, and related control information, to the destination node;

code means for, in response to the destination node receiving but being unable to retain, due to conditions therein, the data portion of the first message, the destination node discarding the data portion of the first message; and

code means for, in response to the destination node thereafter being able to retain, due to changed conditions therein, the data portion of the first message, the destination node initiating a retransmission (110) of the data portion of the first message from the source node using said related control information.

2. The article of manufacture of claim 1, further comprising:

code means for, in response to the destination node being unable to retain the data portion of the first message, the destination node retaining at least some of the related control information.

3. The article of manufacture of claim 2, wherein said code means for the destination node initiating a retransmission (110) of the data portion of the first message includes:

code means for the destination node using the retained at least some of the related control information to transmit (108) a first pull request to the source node to retransmit the data portion of the first message.

4. The article of manufacture of claim 3, further comprising:

code means for, in response to the first pull request, the source node retransmitting (110) the data portion of the first message to the destination node.

5. The article of manufacture of claim 4, further comprising:

code means for, in response to the destination node being unable to retain the data portion of the first message, the destination node sending (104) a first negative acknowledgment to the source node; and

code means for, in response to the source node receiving the first negative acknowledgment, the source node waiting for receipt of the first pull request before retransmitting (110) the data portion of the first message.

6. The article of manufacture of claim 5, further comprising:

code means for the source node transmitting (106) to the destination node a first acknowledgment of the first negative acknowledgment; and

code means for the destination node retransmitting (112) to the source node a first acknowledgment of the retransmitted (110) first data portion of the first message.

7. The article of manufacture of claim 1, wherein the plurality of messages includes a second message, sequential to the first message, and comprising a data portion, the article of manufacture further comprising:

code means for, subsequent to said transmitting (102) the data portion of the first message, the source node transmitting (103) the data portion of the second message, and related control information, to the destination node;

code means for, in response to the destination node being unable to retain the data portion of the first message, the destination node also discarding the data portion of the second message; and

code means for, in response to the destination node thereafter being able to retain the data portion of the second message, the destination node initiating a retransmission (111) of the data portion of the second message from the source node.

8. The article of manufacture of claim 7, wherein the first and second messages are sequentially identified, and are generally expected to arrive at the destination node in the same order in which they were transmitted from the source node, and wherein the control information of the first and second messages comprises respective sequence indicia thereof.

9. The article of manufacture of claim 7, wherein the plurality of messages includes at least one message subsequent to the second message, each of which is transmitted to the destination node, and wherein respective data portions of the at least one message are retained in response to the destination node'"'"'s ability to retain them, or are discarded by the destination node in response to the destination node'"'"'s inability to retain them and not retransmitted thereto until the destination node initiates respective retransmissions thereof due to its subsequent ability to retain them.

10. The article of manufacture of claim 1, wherein the destination node is unable to retain the data portion of the first message due to buffer unavailability, and wherein the destination node is thereafter able to retain the data portion of the first message due to buffer availability.

11. An article of manufacture comprising a computer useable medium having computer readable program code means embodied therein for flow-controlling a plurality of sequential messages from a source node into a destination node in a message processing system, each of the plurality of messages including a first data portion and related control information including respective identifying indicia thereof, the computer readable program code means in said article of manufacture comprising:

code means for initially transmitting the respective data portions and the respective control information of a first message and at least one subsequent message of the plurality of messages from the source node to destination node; and

code means for, in response to the destination node receiving but being unable to retain, due to conditions therein, the data portion of the first message;

the destination node discarding the data portion of the first message but retaining the identifying indicia of the control information thereof, and sending a negative acknowledgment relating to the first message to the source node using said control information, and

until it is able to retain, due to changed conditions therein, any data portions of messages, the destination node discarding respective data portions of the at least one subsequent message as they are received thereby but retaining the respective identifying indicia of the respective control information thereof, and sending respective negative acknowledgments relating thereto to the source node using said respective control information.

12. The article of manufacture of claim 11, further comprising:

code means for, as the destination node becomes able to retain the respective data portions of the first message and any of the at least one subsequent message, the destination node initiating, via respective pull requests to the source node, respective retransmissions of the respective data portions of the first message and said any of the at least one subsequent message.

13. The article of manufacture of claim 12, further comprising:

code means for, in response to said respective pull requests from the destination node, the source node retransmitting the respective data portions of the first message and said any of the at least one subsequent message to the destination node.

14. The article of manufacture of claim 13, further comprising:

code means for the destination node incrementing an expected runt number as respective data portions of messages are discarded and negative acknowledgments transmitted to the source node therefor.

15. The article of manufacture of claim 14, further comprising:

code means for the destination node incrementing an expected message number as respective initial transmissions or retransmissions of data portions of messages are successfully retained; and

code means for the destination node respectively acknowledging the successful retention of the respective initial transmissions or retransmissions of the data portions of messages to the source node.

16. The article of manufacture of claim 15, further comprising:

code means for the source node incrementing a message sent number as respective initial transmissions of data portions of messages are made.

17. The article of manufacture of claim 16, further comprising:

code means for the source node incrementing an expected acknowledgment number as respective acknowledgments of successfully retained initially transmitted or retransmitted data portions of messages are received from the destination node.

18. The article of manufacture of claim 11, further comprising:

code means for, in response to the destination node being able to retain the data portion of the first message;

the destination node retaining, and acknowledging to the source node the successful retention of, the data portion of the first message.

19. The article of manufacture of claim 18, wherein the destination node is unable to retain the data portions of messages due to buffer unavailability, and wherein the destination node is able to retain data portions of messages due to buffer availability.