Flow control in a packet data communication system

• US 7,047,310 B2
• Filed: 02/25/2003
• Issued: 05/16/2006
• Est. Priority Date: 02/25/2003
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Agrawal, Rajeev, Ranjan, Rajeev, Bedekar, Anand S.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): Nguyen, Van Kim T.
• Application Number:
  US10/374,553
• Publication Number:
  US 20040165530A1
• Time in Patent Office: 1,176 Days
• Field of Search: 370230-235, 370/328, 370/338, 370/401
• US Class Current: 709/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9078 using an external memory or storage device
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A communication system that includes multiple nodes controls a flow of data from a first node of the multiple nodes to a second node of the multiple nodes without relying on an estimate of a rate at which data is drawn from a buffer of the second node and such that an overflow and an underflow of the buffer is avoided. The second node determines multiple flow control parameters, including a current occupancy (Q) of the buffer and an upper threshold (U) and a lower threshold (L) for an occupancy of the buffer and determines a desired data rate (r) based on the multiple flow control parameters. The desired data rate can be used to adjust a data rate for the flow of data. In another embodiment, the communication system further dynamically controls a rate at which flow control messages are conveyed by the second node to the first node.

Claims

1. A method for controlling a data rate for a transfer of data from a first node of a plurality of nodes in a communication system to a second node of the plurality of nodes, the method comprising:

determining whether a period of time has expired since an immediately preceding flow control message has been conveyed by the second node to the first node;

when the period of time has expired, determining a plurality of flow control parameters comprising a current occupancy (Q) of a buffer of the second node, an upper threshold (U) for an occupancy of the buffer, and a lower threshold (L) for an occupancy of the buffer; and

determining a desired data rate (r) based on the determined plurality of flow control parameters;

wherein the desired data rate can be used to adjust the data rate and wherein determining a desired data rate comprises;

determining a quantity (q) corresponding to an amount by which the current occupancy (Q) of the buffer exceeds the lower threshold (L);

determining a difference between the upper threshold (U) and the lower threshold (L);

determining a time period (C′

) based on a maximum data rate (R) for a transfer of data over an air interface, the upper threshold (U), and the lower threshold (L); and

when the quantity (q) is less than the difference between the upper threshold (U) and the lower threshold (L) and the quantity (q) is greater than zero, determining a desired data rate (r) based on the maximum data rate (R), the quantity (q), and the time period (C′

).

4. The method of claim 1, further comprising:

embedding, by the second node, the desired data rate (r) in a flow control message; and

conveying, by the second node to the first node, the flow control message.

5. The method of claim 4, further comprising adjusting, by the first node, the data rate at which the first node conveys data to the second node based on the desired data rate (r).

2. A method for controlling a data rate for a transfer of data from a first node of a plurality of nodes in a communication system to a second node of the plurality of nodes, the method comprising:

determining whether a period of time has expired since an immediately preceding flow control message has been conveyed by the second node to the first node;

when the period of time has expired, determining a plurality of flow control parameters comprising a current occupancy (O) of a buffer of the second node, an upper threshold (U) for an occupancy of the buffer, and a lower threshold (L) for an occupancy of the buffer; and

determining a desired data rate (r) based on the determined plurality of flow control parameters, wherein the desired data rate can be used to adjust the data rate and wherein determining a desired data rate comprises;

determining a quantity (q) corresponding to an amount by which the current occupancy (Q) of the buffer exceeds the lower threshold (L);

determining whether the quantity (q) is less than zero; and

when the quantity (q) is less than zero, determining a desired data rate based on a maximum data rate (R) for a transfer of data over an air interface.

3. A method for controlling a data rate for a transfer of data from a first node of a plurality of nodes in a communication system to a second node of the plurality of nodes, the method comprising:

determining whether a period of time has expired since an immediately preceding flow control message has been conveyed by the second node to the first node;

when the period of time has expired, determining a plurality of flow control parameters comprising a current occupancy (O) of a buffer of the second node, an upper threshold (U) for an occupancy of the buffer, and a lower threshold (L) for an occupancy of the buffer; and

determining a desired data rate (r) based on the determined plurality of flow control parameters, wherein the desired data rate can be used to adjust the data rate and wherein determining a desired data rate comprises;

determining a quantity (q) corresponding to an amount by which the current occupancy (Q) of the buffer exceeds the lower threshold (L);

determining a difference between the upper threshold (U) and the lower threshold (L); and

when the quantity (q) is greater than the difference between the upper threshold (U) and the lower threshold (L), determining a desired data rate approximately equal to zero.

6. A method for controlling a data rate for a transfer of data from a first node of a plurality of nodes in a communication system to a second node of the plurality of nodes, the method comprising:

determining whether a period of time has expired since an immediately preceding flow control message has been conveyed by the second node to the first node;

when the period of time has expired, determining a plurality of flow control parameters comprising a current occupancy (O) of a buffer of the second node, an upper threshold (U) for an occupancy of the buffer, and a lower threshold (L) for an occupancy of the buffer;

determining a desired data rate (r) based on the determined plurality of flow control parameters, wherein the desired data rate can be used to adjust the data rate;

determining a maximum size (B) of the buffer of the second node; and

adjusting, by the first node, a size of a buffer of the first node based on the maximum size (B) of the buffer of the second node.

7. A method for controlling a data rate for a transfer of data from a first node of a plurality of nodes in a communication system to a second node of the plurality of nodes, the method comprising:

determining whether a period of time has expired since a conveyance of a preceding flow control message from the second node to the first node;

determining a plurality of flow control parameters comprising a current occupancy (Q) of a buffer of the second node, an upper threshold (U) for an occupancy of the buffer, a lower threshold (L) for an occupancy of the buffer, a quantity (q) corresponding to an amount by which the current occupancy (Q) of the buffer exceeds the lower threshold (L), and a quantity (q₀) corresponding to a value determined for the quantity q with respect to the preceding flow control message;

determining at least one of whether a difference between the quantity (q) and the quantity (q₀) exceeds an adjustment threshold (d), whether the quantity (q) is less than or equal to zero (0), and whether the quantity (q) is greater than or equal to a difference between the upper threshold (U) and the lower threshold (L); and

determining to adjust the data rate when the period of time has expired and the difference between the quantity (q) and the quantity (q₀) exceeds the adjustment threshold (d), the quantity (q) is less than or equal to zero (0), or the quantity (q) is greater than or equal to a difference between the upper threshold (U) and the lower threshold (L).

8. The method of claim 7, wherein the method further comprises:

determining a desired data rate (r) based on the determined plurality of flow control parameters; and

wherein the desired data rate (r) can be used to adjust the data rate.

9. The method of claim 8, wherein determining the desired data rate (r) comprises, when the quantity (q) is less than a difference between the upper threshold (U) and the lower threshold (L) and the quantity (q) is greater than zero, determining the desired data rate (r) based on a maximum data rate (R) for a transfer of data over an air interface, the quantity (q), and a time period expiring between a conveyance of successive flaw control messages from the second node to the first node.

10. The method of claim 8, wherein determining the desired data rate (r) comprises, when the quantity (q) is less than or equal to zero, determining the desired data rate (r) based on a maximum data rate (R) for a transfer of data over an air interface.

11. The method of claim 8, wherein determining the desired data rate (r) comprises, when the quantity (q) is greater than or equal to the difference between the upper threshold (U) and the lower threshold (L), determining the desired data rate (r) approximately equal to zero.

12. The method of claim 7, further comprising adjusting, by the first node, the data rate at which the first node conveys data to the second node based on the desired data rate (r).

13. The method of claim 12, wherein adjusting comprises:

embedding, by the second node, the desired data rate (r) in a flow control message;

conveying, by the second node to the first node, the flow control message; and

in response to receiving the flow control message, adjusting, by the first node, the data rate at which the first node conveys data to the second node based on the desired data rate (r).

14. The method of claim 8, wherein the plurality of flow control parameters are determined based on a first set of data and comprise a first set of flow control parameters, wherein the period of time comprises a first period of time, wherein the desired data rate (r) comprises a first desired data rate (r₁), and wherein the method further comprises:

embedding, by the second node, the first desired data rate (r₁) in a flow control message;

conveying, by the second node to the first node, the flow control message;

determining whether a second period of time has expired since the conveyance of the flow control message;

when the second period of time has expired since the conveyance of the first flow control message, re-determining at least one of the plurality of flow control parameters based on a second set of data received subsequent to the first set of data to produce a second set of flow control parameters;

determining a second desired data rate (r₂) based on the second set of flow control parameters; and

wherein the second desired data rate (r₂) can be used to further adjust the data rate.

15. The method of claim 14, wherein the flow control message comprises a first flow control message and wherein the method further comprises:

embedding, by the second node, the second desired data rate (r₂) in a second flow control message; and

conveying, by the second node to the first node, the second flow control message.

16. The method of claim 15, further comprising adjusting, by the first node, the data rate at which the first node conveys data to the second node based on the second desired data rate (r₂).

17. A node in a wireless communication infrastructure, wherein the node receives data at a data rate from a different node in the communication system for transmission to a mobile station, the node comprising:

at least one memory device comprising a buffer that stores data intended for mobile station; and

a processor that determines whether a period of time has expired since the node conveyed an immediately preceding flow control message to the different node and, when the period of time has expired, determines a plurality of flow control parameters comprising a current occupancy in (Q) of the buffer, an upper threshold (U) for an occupancy of the buffer, and a lower threshold (L) for an occupancy of the buffer and determines a desired data rate (r) based on the determined plurality of flow control parameters, wherein the desired data rate can be used to adjust the data rate and wherein the processor determines a desired data rate by determining a quantity (q) corresponding to an amount by which the current occupancy (Q) of the buffer exceeds the lower threshold (L), determining a difference between the upper threshold (U) and the lower threshold (L), determining a time period (C′

) based on a maximum data rate (R) for a transfer of data over an air interface, the upper threshold (U), and the lower threshold (L), and when the quantity (q) is less than the difference between the upper threshold (U) and the lower threshold (L) and the quantity (q) is greater than zero, determining a desired data rate (r) based on a maximum data rate (R) for a transfer of data over an air interface, the quantity (q), and the time period (C′

).

20. The node of claim 17, wherein the processor further embeds the desired data rate (r) in a flow control message and conveys the flow control message to the different node.

21. The node of claim 17, wherein the processor further determines a maximum size (B) of the buffer of the second node and conveys the maximum size (B) of the buffer to the different node.

18. A node in a wireless communication infrastructure, wherein the node receives data at a data rate from a different node in the communication system for transmission to a mobile station, the node comprising:

at least one memory device comprising a buffer that stores data intended for mobile station; and

a processor that determines whether a period of time has expired since the node conveyed an immediately preceding flow control message to the different node and, when the period of time has expired, determines a plurality of flow control parameters comprising a current occupancy (O) of the buffer, an upper threshold (U) for an occupancy of the buffer, and a lower threshold (L) for an occupancy of the buffer and determines a desired data rate (r) based on the determined plurality of flow control parameters, wherein the desired data rate can be used to adjust the data rate and wherein the processor determines a desired data rate by determining a quantity (q) corresponding to an amount by which the current occupancy (Q) of the buffer exceeds the lower threshold (L), determining whether the quantity (q) is less than zero, and when the quantity (q) is less than zero, determining a desired data rate based on a maximum data rate (A) for a transfer of data over an air interface.

19. A node in a wireless communication infrastructure, wherein the node receives data at a data rate from a different node in the communication system for transmission to a mobile station, the node comprising:

at least one memory device comprising a buffer that stores data intended for mobile station; and

a processor that determines whether a period of time has expired since the node conveyed an immediately preceding flow control message to the different node and, when the period of time has expired, determines a plurality of flow control parameters comprising a current occupancy (O) of the buffer, an upper threshold (U) for an occupancy of the buffer, and a lower threshold (L) for an occupancy of the buffer and determines a desired data rate (r) based on the determined plurality of flow control parameters, wherein the desired data rate can be used to adjust the data rate and wherein the processor determines a desired data rate by determining a quantity (q) corresponding to an amount by which the current occupancy (Q) of the buffer exceeds the lower threshold (L), determining a difference between the upper threshold (U) and the lower threshold (L), and when the quantity (q) is greater than the difference between the upper threshold (U) and the lower threshold (L), determining a desired data rate approximately equal to zero.

22. A node in a wireless communication infrastructure, wherein the node receives data at a data rate from a different node in the communication system for transmission to a mobile station, the node comprising:

at least one memory device that stores an adjustment threshold (d) and that comprises a buffer that stores data intended for mobile station; and

a processor that determines whether a period of time has expired since the node conveyed a preceding flow control message to the different node;

determines a plurality of flow control parameters comprising a current occupancy (Q) of the buffer, an upper threshold (U) for an occupancy of the buffer, a lower threshold (L) for an occupancy of the buffer, a quantity (q) corresponding to an amount by which the current occupancy (Q) of the buffer exceeds the lower threshold (L), and a quantity (q₀) corresponding to a value determined for the quantity q with respect to the preceding flow control message, determines at least one of whether a difference between the quantity (q) and the quantity (q₀) exceeds the adjustment threshold (d), whether the quantity (q) is less than or equal to zero (0), and whether the quantity (q) is greater than or equal to a difference between the upper threshold (U) and the lower threshold (L), and determines to adjust the data rate when the period of time has expired and the difference between the quantity (q) and the quantity (q₀) exceeds the adjustment threshold (d), the quantity (q) is less than or equal to zero (0), or the quantity (q) is greater than or equal to a difference between the upper threshold (U) and the lower threshold (L).

23. The node of claim 22, wherein the processor further determines a desired data rate (r) based on the determined plurality of flow control parameters and wherein the desired data rate (r) can be used to adjust the data rate.

24. The node of claim 23, wherein when the quantity (q) is less than the difference between the upper threshold (U) and the lower threshold (L) and the quantity (q) is greater than zero, the processor determines the desired data rate (r) based on a maximum data rate (R) for a transfer of data over an air interface, the quantity (q) and a time period expiring between a conveyance of successive flow control messages by the node.

25. The node of claim 23, wherein when the quantity (q) is less than or equal to zero, the processor determines the desired data rate (r) based on a maximum data rate (R) for a transfer of data over an air interface.

26. The node of claim 23, wherein when the quantity (q) is greater than or equal to the difference between the upper threshold (U) and the lower threshold (L), the processor determines the desired data rate (r) approximately equal to zero.

27. The node of claim 23, wherein the processor further embeds the desired data rare (r) in a flow control message and conveys the flow control message to the different node.

28. The node of claim 23, wherein the plurality of flow control parameters are determined based on a first set of data and comprise a first set of flow control parameters, wherein the period chime comprises a first period of time, wherein the desired data rate (r) comprises a first desired data rate (r₁), and wherein processor further embeds the first desired data rate (r₁) in a flow control message, conveys the flow control message to the different node, determines whether a second period of time has expired since the conveyance of the flow control message and when the second period of time has expired since the conveyance of the first flow control message, re-determines at least one of the plurality of flow control parameters based on a second set of data received subsequent to the first set of data to produce a second set of flow control parameters and determines a second desired data rare (r₂) based on the second set of flow control parameters, wherein the second desired data rate can be used to further adjust the data rate.

29. The node of claim 28, wherein the flow control message comprises a first flow control message and wherein the processor further embeds the second desired data rate (r₂) in a second flow control message and conveys the second flow control message to the different node.