Method and apparatus for flow control in a reliable multicast communication system

• US 7,561,523 B1
• Filed: 09/09/2002
• Issued: 07/14/2009
• Est. Priority Date: 11/15/2001
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Pass, Alexander M., Slutsky, Irina P., Revsin, Vitaly S.
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): PATEL, CHANDRAHAS B
• Application Number:
  US10/237,344
• Time in Patent Office: 2,500 Days
• Field of Search: 370/229, 370/235, 370/236, 370/230, 370/252, 370/253
• US Class Current: 370/236
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A method and system for flow control in a reliable multicast communication protocol, in which a transmitting device transmits sets of multiple data transfer units (DTUs) referred to as “bursts.” The transmitting device continues transmitting DTUs within a burst independently with regard to the receipt of any acknowledgements (referred to herein as “status reports”) from a number of receiving devices. The transmitting device continues to transmit multiple bursts until the transmitting device reaches a predetermined limitation, referred to as a “burst sliding window” size. The transmitting device transmit DTUs in bursts while a total number of outstanding bursts that have not been acknowledged as received correctly does not exceed the size of the burst sliding window. The burst sliding window size may reflect transmission capacity of the transmitting device and/or receipt capacity of the receiving devices.

Claims

1. A method of transmitting data to multiple receiving devices over a network, comprising the steps of:

organizing a set of data transfer units into a plurality of subsets of said set of data transfer units, each subset including two or more data transfer units, each subset of said set of data transfer units for transmission by a transmitting device to multiple receiving devices, each subset being referred to as a burst,

wherein each of said two or more data transfer units within a respective burst contains information to enable a receiving device to detect an end of the respective burst;

in a first transmitting step, transmitting, by said transmitting device, a plurality of bursts to said multiple receiving devices;

in the event at least one of said multiple receiving devices detects the end of a transmitted burst, generating at least one status report message and transmitting said at least one status report message to said transmitting device,

wherein said at least one status report message includes at least one acknowledgement that at least one of the bursts transmitted in said first transmitting step has been received by said at least one of said multiple receiving devices;

monitoring, at said transmitting device, for receipt of at least one status report message from at least one of said multiple receiving devices, wherein each burst transmitted in said first transmitting step that has not been acknowledged as being received by said at least one of said multiple receiving devices is referred to as an outstanding burst;

determining a current number of outstanding bursts;

comparing said current number of outstanding bursts with a predetermined maximum number of outstanding bursts; and

in a second transmitting step, in the event said current number of outstanding bursts is less than said predetermined maximum number of outstanding bursts, transmitting, by said transmitting device, at least one additional burst to said multiple receiving devices.

2. The method of claim 1, further comprising suspending transmission of the bursts in the event that said current number of outstanding bursts is not less than said predetermined maximum number of outstanding bursts.

3. The method of claim 1, further comprising:

maintaining a current number of unconfirmed bursts, wherein said current number of unconfirmed bursts comprises the number of previously transmitted bursts for which status information has not been received from at least one receiving device;

comparing said current number of unconfirmed bursts with a predetermined maximum number of unconfirmed bursts; and

suspending transmission of the bursts in the event that said current number of unconfirmed bursts is not less than said predetermined maximum number of outstanding bursts.

4. The method of claim 1, further comprising:

maintaining a current number of unconfirmed bursts, wherein said current number of unconfirmed bursts comprises the number of previously transmitted bursts for which status information has not been received from at least one receiving device;

comparing said current number of unconfirmed bursts with a predetermined maximum number of unconfirmed bursts; and

suspending transmission of the bursts in the event that said current number of unconfirmed bursts is not less than said predetermined maximum number of unconfirmed bursts.

5. The method of claim 1, further comprising:

maintaining a current number of uncompleted bursts, wherein said current number of uncompleted bursts comprises the number of previously transmitted bursts for which at least one receiving device has provided status information indicating that at least one data transfer unit in the respective burst was not successfully received;

comparing said current number of uncompleted bursts with a predetermined maximum number of uncompleted bursts; and

suspending transmission of the bursts in the event that said current number of uncompleted bursts is not less than said predetermined maximum number of uncompleted bursts.

6. The method of claim 1, further comprising:

incrementing said current number of outstanding bursts in response to said transmitting of each burst; and

decrementing said current number of outstanding bursts in response to a determination that status information has been received from each receiving device indicating that all data transfer units within a previously transmitted burst were successfully received.

7. The method of claim 6, further comprising:

suspending transmission of the bursts in the event that said current number of outstanding bursts is not less than said predetermined maximum number of outstanding bursts; and

restarting transmission of the bursts in the event that said current number of outstanding bursts is decremented to a value less than said predetermined maximum number of outstanding bursts.

8. The method of claim 1, further comprising:

determining said predetermined maximum number of outstanding bursts in response to an amount of buffer resources available in said transmitting device for storing previously transmitted bursts.

9. The method of claim 1, further comprising:

determining said predetermined maximum number of outstanding bursts in response to an amount of buffer resources available in each of said multiple receiving devices for storing received bursts.

10. The method of claim 9, wherein said determining said predetermined maximum number of outstanding bursts is performed responsive to receiving said at least one status report message from at least one receiving device, wherein said status report message indicates a current amount of buffer resources available in said at least one receiving device.

11. The method of claim 1, further comprising:

incrementing said current number of outstanding bursts in response to said transmitting of each burst; and

decrementing said current number of outstanding bursts in response to a determination that status information has been received from each receiving device indicating that all data transfer units within a previously transmitted burst were successfully received and processed by at least one application program.

12. The method of claim 1 wherein the information contained in each of said two or more data transfer units to enable a receiving device to detect an end of a respective burst comprises a position of the data transfer unit within the respective burst.

13. A device for transmitting data to multiple receiving devices over a network, said device comprising:

at least one processor;

at least one computer program; and

at least one memory operative to store the computer program, said at least one memory being communicably coupled to said at least one processor;

wherein the processor executes the computer program out of the memory;

to organize a set of data transfer units into a plurality of subsets of said set of data transfer units, each subset including two or more data transfer units, each subset of said set of data transfer units for transmission to multiple receiving devices, each subset being referred to as a burst,

wherein each of said two or more data transfer units within a respective burst contains information to enable a receiving device to detect an end of the respective burst;

to transmit a plurality of bursts to said multiple receiving devices;

to monitor for receipt of at least one status report message from at least one of said multiple receiving devices, said at least one status report message being generated and transmitted by said at least one of said multiple receiving devices in response to detection of the end of at least one transmitted burst, said at least one status report message including at least one acknowledgement that at least one of the transmitted bursts has been received by said at least one of said multiple receiving devices,

wherein each transmitted burst that has not been acknowledged as being received by said at least one of said multiple receiving devices is referred to as an outstanding burst;

to determine a current number of outstanding bursts;

to compare said current number of outstanding bursts with a predetermined maximum number of outstanding bursts; and

in the event that said current number of outstanding bursts is less than said predetermined maximum number of outstanding bursts, to transmit at least one additional burst to said multiple receiving devices.

14. The device of claim 13, wherein said device further comprises at least one processor coupled to a program memory.

15. The device of claim 13, further operable to suspend transmission of the bursts in the event that said current number of outstanding bursts is not less than said predetermined maximum number of outstanding bursts.

16. The device of claim 13 wherein the information contained in each of said two or more data transfer units to enable a receiving device to detect an end of a respective burst comprises a position of the data transfer unit within the respective burst.

17. A device for transmitting data to multiple receiving devices over a network, comprising:

means for organizing a set of data transfer units into a plurality of subsets of said set of data transfer units, each subset including two or more data transfer units, each subset of said set of data transfer units for transmission to multiple receiving devices, each subset being referred to as a burst,

wherein each of said two or more data transfer units within a respective burst contains information to enable a receiving device to detect an end of the respective burst;

means for transmitting a plurality of bursts to said multiple receiving devices;

means for monitoring for receipt of at least one status report message from at least one of said multiple receiving devices, said at least one status report message being generated and transmitted by said at least one of said multiple receiving devices in response to detection of the end of at least one transmitted burst, said at least one status report message including at least one acknowledgement that at least one of the transmitted bursts has been received by said at least one of said multiple receiving devices,

wherein each transmitted burst that has not been acknowledged as being received by said at least one of said multiple receiving devices is referred to as an outstanding burst;

means for determining a current number of outstanding bursts;

means for comparing said current number of outstanding bursts with a predetermined maximum number of outstanding bursts; and

means for transmitting, in the event that said current number of outstanding bursts is less than said predetermined maximum number of outstanding bursts, at least one additional burst to said multiple receiving devices.

18. The device of claim 17, further comprising means for suspending transmission of the bursts in the event that said current number of outstanding bursts is not less than said predetermined maximum number of outstanding bursts.

19. The device of claim 17 wherein the information contained in each of said two or more data transfer units to enable a receiving device to detect an end of a respective burst comprises a position of the data transfer unit within the respective burst.

20. A method of providing status with regard to data received over a network, comprising the steps of:

providing an amount of receive buffer resources to a transmitting device, said receive buffer resources for storing at least a portion of a set of data transfer units, said set of data transfer units being organized into a plurality of subsets of said set of data transfer units, each subset being referred to as a burst,

wherein said amount of receive buffer resources represents a predetermined number of the bursts received from a transmitting device that can be stored prior to being processed by at least one application program,

wherein each of the received bursts includes two or more data transfer units, and

wherein each of said two or more data transfer units within a respective burst contains information to enable detection of an end of the respective burst;

receiving a plurality of bursts from said transmitting device; and

in response to detection of the end of at least one received burst, generating at least one status report message and transmitting said at least one status report message to said transmitting device,

wherein each of said status report messages indicates a receipt status of each data transfer unit within each previously received burst.

21. The method of claim 20, wherein each of said status report messages indicates said amount of receive buffer resources.

22. The method of claim 20, wherein each of said status report messages further indicates a processing status with regard to each of the received bursts, wherein said processing status indicates whether at least one application program has processed each of the received bursts.

23. The method of claim 20 wherein the information contained in each of said two or more data transfer units to enable detection of an end of a respective burst comprises a position of the data transfer unit within the respective burst.

24. A device for providing status with regard to data received over a network, said device comprising:

at least one processor;

at least one computer program; and

at least one memory operative to store the computer program, said at least one memory being communicably coupled to said at least one processor;

wherein the processor executes the computer program out of the memory;

to provide an amount of receive buffer resources to a transmitting device, said receive buffer resources for storing at least a portion of a set of data transfer units, said set of data transfer units being organized into a plurality of subsets of said set of data transfer units, each subset being referred to as a burst,

wherein said amount of receive buffer resources represents a predetermined number of bursts received from a transmitting device that can be stored prior to being processed by at least one application program,

wherein each of the received bursts includes two or more data transfer units, and

wherein each of said two or more data transfer units within a respective burst contains information to enable detection of an end of the respective burst;

to receive a plurality of bursts from said transmitting device; and

in response to detection of the end of at least one received burst, to generate at least one status report message, and to transmit said at least one status report message to said transmitting device,

wherein each of said status report messages indicates a receipt status of each data transfer unit within each previously received burst.

25. The device of claim 24, wherein each said status report message further indicates a processing status with regard to each of the received bursts, wherein said processing status indicates whether at least one application program has processed each of the received bursts.

26. The device of claim 24, further comprising at least one processor coupled to a program memory.

27. The device of claim 24 wherein the information contained in each of said two or more data transfer units to enable detection of an end of a respective burst comprises a position of the data transfer unit within the respective burst.

28. A device for providing status with regard to data received over a network, comprising:

means for providing an amount of receive buffer resources to a transmitting device, said receive buffer resources for storing at least a portion of a set of data transfer units, said set of data transfer units being organized into a plurality of subsets of said set of data transfer units, each subset being referred to as a burst,

wherein said amount of receive buffer resources represents a predetermined number of bursts received from a transmitting device that can be stored prior to being processed by at least one application program,

wherein each of the received bursts includes two or more data transfer units, and

wherein each of said two or more data transfer units within a respective burst contains information to enable detection of an end of the respective burst;

means for receiving a plurality of bursts from said transmitting device; and

means for generating at least one status report message and for transmitting said at least one status report message to said transmitting device in response to detection of the end of at least one received burst,

wherein each of said status report messages indicates a receipt status of each data transfer unit within each previously received burst.

29. The device of claim 28, wherein said means for transmitting said at least one status report message further comprises means for providing each of said status report messages with an indication of a processing status with regard to each of the received bursts, wherein said processing status indicates whether at least one application program has processed each of the received bursts.

30. The device of claim 28 wherein the information contained in each of said two or more data transfer units to enable detection of an end of a respective burst comprises a position of the data transfer unit within the respective burst.

31. A method of transmitting data over a network, comprising the steps of:

organizing a set of data transfer units into a plurality of subsets of said set of data transfer units, each subset of said set of data transfer units including two or more data transfer units, each subset of said set of data transfer units being referred to as a burst,

wherein each of said two or more data transfer units within a respective burst contains information to enable a receiving device to detect an end of the respective burst;

transmitting, by a transmitting device, a plurality of bursts over a network;

in the event at least one receiving device detects the end of at least one transmitted burst, generating at least one acknowledgement that said at least one transmitted burst has been received by said at least one receiving device, and transmitting said at least one acknowledgement over said network to said transmitting device, said at least one receiving device being communicably coupled to said network;

monitoring for receipt of at least one acknowledgement over said network,

wherein each of said transmitted plurality of bursts that has not been acknowledged as being received is referred to as an outstanding burst;

determining a current number of outstanding bursts;

comparing said current number of outstanding bursts with a specified maximum number of outstanding bursts; and

in the event said current number of outstanding bursts is less than said specified maximum number of outstanding bursts, transmitting at least one additional burst over said network.

32. The method of claim 31 wherein the information contained in each of said two or more data transfer units to enable a receiving device to detect an end of a respective burst comprises a position of the data transfer unit within the respective burst.