Adapting receiver thresholds to improve rate-based flow control

• US 6,657,954 B1
• Filed: 03/31/1999
• Issued: 12/02/2003
• Est. Priority Date: 03/31/1999
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Makrucki, Brad Alan, Martin, James John, Case, Ralph Benjamin, Bird, Raymond F.
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Phan, Tri H.
• Application Number:
  US09/282,691
• Time in Patent Office: 1,707 Days
• Field of Search: 370/229, 370/230, 370/230.1, 370/231, 370/232, 370/233, 370/234, 370/235, 370/252, 370/465, 370/466, 370/468, 370/235.1, 370/236.1, 370/236.2, 709/223
• US Class Current: 370/229
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A technique for adapting receiver thresholds to improve rate-based flow control in a data communications network. With this invention, the flow control process becomes self-calibrating such that threshold values are dynamically adjusted to adapt to current network conditions, without requiring user intervention. Several different indicators of network conditions are monitored, and appropriate adjustments are made to the threshold(s) upon detecting these specific indicators. One monitor enables the threshold to increase when the network is uncongested, enabling the sender to increase its transmission rate. Conversely, the threshold is lowered if the network is congested, so that the transmission rate will be decreased. Another monitor balances bandwidth allocation among connections sharing a bottleneck resource, by lowering the threshold (and therefore decreasing the send rate) when a connection uses a high share of the resource. A third monitor detects the presence of traffic from protocols not using adaptive receiver thresholds, and adjusts the threshold (including an upper and lower threshold bound) in order to compete fairly for resources with these other protocols. The monitors may be implemented individually or in combination.

Claims

1. Computer readable code for adapting receiver thresholds to improve rate-based flow control in a data communications network, said computer readable code embodied on one or more computer readable media and comprising:

computer readable code means for programmatically detecting whether a foreign protocol is operating in said network, said foreign protocol being a protocol that does not use adaptive rate-based flow control;

computer readable code means for programmatically setting a receiver threshold to a maximum value when said foreign protocol is detected; and

computer readable code means for using said receiver threshold for rate-based flow control when responding to a rate request received from a sender of data, further comprising;

computer readable code means for comparing said receiver threshold to an amount of network delay experienced over a recent time interval when receiving a sequence of at least two of said rate requests from said sender; and

computer readable code means for responding to said received rate request by sending a response, to said sender, indicating that a rate of sending said data should be decreased if said computer readable code means for comparing determines that said amount of network delay exceeds said receiver threshold, but that said rate of sending said data can be increased otherwise.

4. Computer readable code for adapting receiver thresholds according to claim 1, wherein said computer readable code means for programmatically detecting further comprises:

computer readable code means for programmatically monitoring an average value of a delay change sum, wherein said delay change sum reflects said amount of network delay experienced over said recent time interval;

computer readable code means for programmatically monitoring a variance in said delay change sum;

computer readable code means for programmatically monitoring whether said sent responses which indicate that said rate should be decreased are actually resulting in a decrease in said amount of network delay;

computer readable code means for programmatically determining that said foreign protocol is detected when said monitored average value is higher than an expected average value;

computer readable code means for programmatically determining that said foreign protocol is detected when said monitored variance is larger than an expected variance; and

computer readable code means for programmatically determining that said foreign protocol is detected when said sent responses which indicate that said rate should be decreased are not actually resulting in said decrease.

13. Computer readable code for adapting receiver thresholds according to claim 1, wherein said computer readable code means for programmatically setting operates to allow said sender to compete for resources more fairly with another sender who is using said foreign protocol.

2. Computer readable code for adapting receiver thresholds to improve rate-based flow control in a data communications network, said computer readable code embodied on one or more computer readable media and comprising:

computer readable code means for programmatically monitoring a percentage of rate-based flow-control increase messages sent by a receiver to a sender during a recent interval;

computer readable code means for using said percentage of increase messages to programmatically interpolate a receiver threshold between a maximum value and a minimum value; and

computer readable code means for using said receiver threshold for rate-based flow control when responding to a rate request received from said sender, further comprising;

computer readable code means for comparing said receiver threshold to an amount of network delay experienced over a recent time interval when receiving a sequence of at least two of said rate requests from said sender; and

computer readable code means for responding to said received rate request by sending, as a response to said sender, a rate-based flow-control message indicating that a rate of sending data by said sender should be decreased if said computer readable code means for comparing determines that said amount of network delay exceeds said receiver threshold, and for sending a rate-based flow-control message indicating that said rate can be increased otherwise.

14. Computer readable code for adapting receiver thresholds according to claim 2, wherein said computer readable code means for programmatically interpolating operates to allow said sender to increase said rate when congestion is not being experienced in said data communications network.

3. Computer readable code for adapting receiver thresholds to improve rate-based flow control in a data communications network, said computer readable code embodied on one or more computer readable media and comprising:

computer readable code means for programmatically monitoring a link utilization rate of a connection during a recent interval to determine whether excess bandwidth capacity is available;

computer readable code means for using said link utilization rate to programmatically adjust a receiver threshold such that, when said computer readable code means for programmatically monitoring determines that there is excess bandwidth capacity available, said receiver threshold is increased; and

computer readable code means for using said receiver threshold for rate-based flow control when responding to a rate request received from a sender of data, further comprising;

computer readable code means for comparing said receiver threshold to an amount of network delay experienced over a recent time interval when receiving a sequence of at least two of said rate requests from said sender; and

computer readable code means for responding to said received rate request by sending, as a response to said sender, a rate-based flow-control message indicating that a rate of sending said data by said sender should be decreased if said computer readable code means for comparing determines that said amount of network delay exceeds said receiver threshold, and for sending a rate-based flow-control message indicating that said rate can be increased otherwise.

15. Computer readable code for adapting receiver thresholds according to claim 3, wherein said computer readable code means for using said link utilization rate operates to balance bandwidth allocation among connections that are sharing a bottlenecked link.

5. A system for adapting receiver thresholds to improve rate-based flow control in a data communications network, comprising:

means for programmatically detecting whether a foreign protocol is operating in said network, said foreign protocol being a protocol that does not use adaptive rate-based flow control; and

means for programmatically setting a receiver threshold to a maximum value when said foreign protocol is detected; and

means for using said receiver threshold for rate-based flow control when responding to a rate request received from a sender of data, further comprising;

means for comparing said receiver threshold to an amount of network delay experienced over a recent time interval when receiving a sequence of at least two of said rate requests from said sender; and

means for responding to said received rate request by sending a response, to said sender, indicating that a rate of sending said data should be decreased if said means for comparing determines that said amount of network delay exceeds said receiver threshold, but that said rate of sending said data can be increased otherwise.

8. The system for adapting receiver, thresholds according to claim 5, wherein said means for programmatically detecting further comprises:

means for programmatically monitoring an average value of a delay change sum, wherein said delay change sum reflects said amount of network delay experienced over said recent time intervals;

means for programmatically monitoring a variance in said delay change sum;

means for programmatically monitoring whether said sent responses which indicate that said rate should be decreased are actually resulting in a decrease in said amount of network delay;

means for programmatically determining that said foreign protocol is detected when said monitored average value is higher than an expected average value;

means for programmatically determining that said foreign protocol is detected when said monitored variance is larger than an expected variance; and

means for programmatically determining that said foreign protocol is detected when said sent responses which indicate that said rate should be decreased are not actually resulting in said decrease.

16. The system for adapting receiver thresholds according to claim 5, wherein said means for programmatically setting operates to allow said sender to compete for resources more fairly with another sender who is using said foreign protocol.

6. A system for adapting receiver thresholds to improve rate-based flow control in a data communications network, comprising:

means for programmatically monitoring a percentage of rate-based flow-control increase messages sent by a receiver to a sender during a recent interval;

means for using said percentage of increase messages to programmatically interpolate a receiver threshold between a maximum value and a minimum value; and

means for using said receiver threshold for rate-based flow control when responding to a rate request received from said sender, further comprising;

means for comparing said receiver threshold to an amount of network delay experienced over a recent time interval when receiving a sequence of at least two of said rate requests from said sender; and

means for responding to said received rate request by sending, as a response to said sender, a rate-based flow-control message indicating that a rate of sending data by said sender should be decreased if said means for comparing determines that said amount of network delay exceeds said receiver threshold, and for sending a rate-based flow-control message indicating that said rate can be increased otherwise.

17. The system for adapting receiver thresholds according to claim 6, wherein said means for programmatically interpolating operates to allow said sender to increase said rate when congestion is not being experienced in said data communications network.

7. A system for adapting receiver thresholds to improve rate-based flow control in a data communications network, comprising:

means for programmatically monitoring a link utilization rate of a connection during a recent interval to determine whether excess bandwidth capacity is available;

means for using said link utilization rate to programmatically adjust a receiver threshold such that, when said means for programmatically monitoring determines that there is excess bandwidth capacity available, said receiver threshold is increase; and

means for using said receiver threshold for rate-based flow control when responding to a rate request received from a sender of data, further comprising;

means for comparing said receiver threshold to an amount of network delay experienced over a recent time interval when receiving a sequence of at least two of said rate requests from said sender; and

means for responding to said received rate request by sending, as a response to said sender, a rate-based flow-control message indicating that a rate of sending said data by said sender should be decreased if said means for comparing determines that said amount of network delay exceeds said receiver threshold, and for sending a rate-based flow-control message indicating that said rate can be increased otherwise.

18. The system for adapting receiver thresholds according to claim 7, wherein said means for using said link utilization rate operates to balance bandwidth allocation among connections that are sharing a bottlenecked link.

9. A method for adapting receiver thresholds to improve rate-based flow control in a data communications network, comprising the steps of:

programmatically detecting whether a foreign protocol is operating in said network, said foreign protocol being a protocol that does not use adaptive rate-based flow control;

programmatically setting a receiver threshold to a maximum value when said foreign protocol is detected; and

using said receiver threshold for rate-based flow control when responding to a rate request received from a sender of data, further comprising the steps of;

comparing said receiver threshold to an amount of network delay experienced over a recent time interval when receiving a sequence of at least two of said rate requests from said sender; and

responding to said received rate request by sending a response, to said sender, indicating that a rate of sending said data should be decreased if said comparing step determines that said amount of network delay exceeds said receiver threshold, but that said rate of sending said data can be increased otherwise.

12. The method for adapting receiver thresholds according to claim 9, wherein said programmatically detecting step further comprises the steps of:

programmatically monitoring an average value of a delay change sum, wherein said delay change sum reflects said amount of network delay experienced over said recent time intervals;

programmatically monitoring a variance in said delay change sum;

programmatically monitoring whether said sent responses which indicate that said rate should be decreased are actually resulting in a decrease in said amount of network delay;

programmatically determining that said foreign protocol is detected when said monitored average value is higher than an expected average value;

programmatically determining that said foreign protocol is detected when said monitored variance is larger than an expected variance; and

programmatically determining that said foreign protocol is detected when said sent responses which indicate that said rate should be decreased are not actually resulting in said decrease.

19. The method for adapting receiver thresholds according to claim 9, wherein said programmatically setting step operates to allow said sender to compete for resources more fairly with another sender who is using said foreign protocol.

10. A method for adapting receiver thresholds to improve rate-based flow control in a data communications network, comprising the steps of:

programmatically monitoring a percentage of rate-based flow-control increase messages sent by a receiver to a sender during a recent interval;

using said percentage of increase messages to programmatically interpolate a receiver threshold between a maximum value and a minimum value; and

using said receiver threshold for rate-based flow control when responding to a rate request received from said sender, further comprising the steps of;

comparing said receiver threshold to an amount of network delay experienced over a recent time interval when receiving a sequence of at least two of said rate requests from said sender; and

responding to said received rate request by sending, as a response to said sender, a rate-based flow-control message indicating that a rate of sending data by said sender should be decreased if said comparing step determines that said amount of network delay exceeds said receiver threshold, and for sending a rate-based flow-control message indicating that said rate can be increased otherwise.

20. The method for adapting receiver thresholds according to claim 10, wherein said programmatically interpolating step operates to allow said sender to increase said rate when congestion is not being experienced in said data communications network.

11. A method for adapting receiver thresholds to improve rate-based flow control in a data communications network, comprising the steps of:

programmatically monitoring a link utilization rate of a connection during a recent interval to determine whether excess bandwidth capacity is available;

using said link utilization rate to programmatically adjust a receiver threshold such that, when said programmatically monitoring step determines that there is excess bandwidth capacity available, said receiver threshold is increased; and

using said receiver threshold for rate-based flow control when responding to a rate request received from a sender of data, further comprising the steps of;

comparing said receiver threshold to an amount of network delay experienced over a recent time interval when receiving a sequence of at least two of said rate requests from said sender; and

responding to said received rate request by sending, as a response to said sender, a rate-based flow-control message indicating that a rate of sending said data by said sender should be decreased if said comparing step determines that said amount of network delay exceeds said receiver threshold, and for sending a rate-based flow-control message indicating that said rate can be increased otherwise.

21. The method for adapting receiver thresholds according to claim 11, wherein said step of using said link utilization rate operates to balance bandwidth allocation among connections that are sharing a bottlenecked link.