Method and apparatus for network congestion control based on transmission rate gradients

• US 10,263,894 B2
• Filed: 03/31/2015
• Issued: 04/16/2019
• Est. Priority Date: 04/23/2014
• Status: Active Grant

• Current Assignee: Bequant S.L.
• Original Assignee: Bequant S.L.
• Inventors: Lopez Serrano, Jose, Pineiro Blanca, Luis, Lopez Serrano, Guillermo
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): Andrews, III, Hoyet H
• Application Number:
  US15/304,971
• Publication Number:
  US 20170195231A1
• Time in Patent Office: 1,477 Days
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/127 by using congestion prediction
• 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/16 in connection oriented networks, e.g. frame relay
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/18 End to end
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A method and apparatus for congestion control for acknowledged communication over networks detects congestion based on trends of flight size and transmission rate in order to adapt a congestion window in accordance with a detection result. Such congestion detection enables, for example, distinguishing between the congestion with or without unfair competition. Moreover, the measured transmission rate or its trend can be filtered to compensate for time variations. An end node or a proxy can be used for congestion control.

Claims

1. A method for congestion control in a data communication protocol employing acknowledged communication in which a transmitting node transmits data to a receiving node and the receiving node acknowledges receipt of the data, wherein a congestion window specifies a maximum amount of unacknowledged data which the transmitting node may transmit before reception of a positive acknowledgement for all or part of that data, the method to be performed by the transmitting node and comprising:

measuring a flight size indicating an amount of data sent by the transmitting node and not yet acknowledged by the receiving node;

measuring a transmission rate, the transmission rate corresponding to a same time instant as the flight size;

determining a trend of the flight size;

determining a trend of the transmission rate, wherein the trend is derived from a transmission rate gradient calculation, in which either the transmission rate measurements or the transmission rate gradient calculations or both, are filtered to reduce their temporal variability;

detecting whether there is a congestion according to the determined trend of the transmission rate and the trend of the flight size;

upon positive detection of the congestion, modifying the congestion window; and

transmitting data while respecting the congestion window size, wherein;

the step of detecting whether there is a congestion includes detecting whether there is any of a congestion with unfair competition and a congestion without unfair competition,

the congestion with unfair competition is positively detected when the trend of the flight size is either increasing or substantially stable and the trend of the transmission rate is decreasing, and negatively detected otherwise, and

the congestion without unfair competition is positively detected when the trend of the flight size is increasing and the trend of the transmission rate is substantially stable, and negatively detected otherwise.

2. The method according to claim 1, wherein the step of modifying the congestion window includes increasing the congestion window size upon positively detecting the congestion with unfair competition.

3. The method according to claim 2, wherein

the communication protocol is TCP, and

the increase of the congestion window size upon positively detecting the congestion with unfair competition is performed if the transmitting node is in TCP congestion avoidance congestion control state and not performed otherwise.

4. A method for congestion control in a data communication protocol employing acknowledged communication in which a transmitting node transmits data to a receiving node and the receiving node acknowledges receipt of the data, wherein a congestion window specifies a maximum amount of unacknowledged data which the transmitting node may transmit before reception of a positive acknowledgement for all or part of that data, the method to be performed by the transmitting node and comprising:

measuring a flight size indicating an amount of data sent by the transmitting node and not yet acknowledged by the receiving node;

measuring a transmission rate, the transmission rate corresponding to a same time instant as the flight size;

determining a trend of the flight size;

determining a trend of the transmission rate, wherein the trend is derived from a transmission rate gradient calculation, in which either the transmission rate measurements or the transmission rate gradient calculations or both, are filtered to reduce their temporal variability;

detecting whether there is a congestion according to the determined trend of the transmission rate and the trend of the flight size;

upon positive detection of the congestion, modifying the congestion window; and

transmitting data while respecting the congestion window size, wherein;

the step of detecting whether there is a congestion includes detecting whether there is a congestion with unfair competition;

the congestion with unfair competition is positively detected when the trend of the flight size is either increasing or substantially stable and the trend of the transmission rate is decreasing, and negatively detected otherwise; and

the step of modifying the congestion window includes changing from a current congestion control state to a new congestion control state upon positively detecting the congestion with unfair competition, wherein the current and the new congestion control states specify respectively a current and a new rule for increasing the congestion window size upon receipt of data acknowledgements when neither congestion nor data losses have been detected, and

the new rule specifies a faster rate of increasing the congestion window size than the current rule.

5. The method according to claim 4, wherein

the communication protocol is TCP,

the change from a current congestion control state to a new congestion control state upon positively detecting the congestion with unfair competition is performed if the current congestion control state is TCP congestion avoidance and not performed otherwise, and

the new congestion control state is TCP slow start.

6. The method according to claim 4, wherein

in the steps of determining a trend of the flight size and a trend of the transmission rate, the trends of the flight size and the transmission rate are determined over a time period starting at an instant before and closest to a most recent change from a previous congestion control state to the current congestion control state, wherein the previous and the current congestion control states specify respectively a previous and a current rule for increasing the congestion window size upon receipt of data acknowledgements when neither congestion nor data losses have been detected, and the previous congestion control state specifies a faster rate of increasing the congestion window size than the current congestion control state.

7. The method according to claim 4, wherein

in the step of determining a trend of the flight size, the trend of the flight size is determined over a time period starting at an instant after and closest to a most recent reduction of the congestion window size due to a detected congestion;

and

in the step of determining a trend of the transmission rate, the trend of the transmission rate is determined over a time period starting at an instant before and closest to said most recent reduction of the congestion window size due to a detected congestion.

8. A method for congestion control in a data communication protocol employing acknowledged communication in which a transmitting node transmits data to a receiving node and the receiving node acknowledges receipt of the data, wherein a congestion window specifies a maximum amount of unacknowledged data which the transmitting node may transmit before reception of a positive acknowledgement for all or part of that data, the method to be performed by the transmitting node and comprising:

measuring a flight size indicating an amount of data sent by the transmitting node and not yet acknowledged by the receiving node;

measuring a transmission rate, the transmission rate corresponding to a same time instant as the flight size;

determining a trend of the flight size;

determining a trend of the transmission rate, wherein the trend is derived from a transmission rate gradient calculation, in which either the transmission rate measurements or the transmission rate gradient calculations or both, are filtered to reduce their temporal variability;

detecting whether there is a congestion according to the determined trend of the transmission rate and the trend of the flight size;

upon positive detection of the congestion, modifying the congestion window; and

transmitting data while respecting the congestion window size, wherein;

the step of detecting whether there is a congestion includes detecting whether there is a congestion without unfair competition;

the congestion without unfair competition is positively detected when the trend of the flight size is increasing and the trend of the transmission rate is substantially stable, and negatively detected otherwise; and

the step of modifying the congestion window includes changing from a current congestion control state to a new congestion control state upon positively detecting the congestion without unfair competition, wherein the current and the new congestion control states specify respectively a current and a new rule for increasing the congestion window size upon receipt of data acknowledgements when neither congestion nor data losses have been detected, and

the new rule specifies a slower rate of increasing the congestion window size than the current rule.

9. The method according to claim 8, wherein the step of modifying the congestion window includes reducing the congestion window size upon positively detecting the congestion without unfair competition.

10. The method according to claim 9, wherein

the communication protocol is TCP, and

the reduction of the congestion window size upon positively detecting the congestion without unfair competition is performed if the transmitting node is in TCP congestion avoidance congestion control state and not performed otherwise.

11. The method according to claim 8, wherein

the communication protocol is TCP,

the change from a current congestion control state to a new congestion control state upon positively detecting the congestion without unfair competition is performed if the current congestion control state is TCP slow start and not performed otherwise, and

the new congestion control state is TCP congestion avoidance.

12. The method according to claim 8, wherein

in the steps of determining a trend of the flight size and a trend of the transmission rate, the trends of the flight size and the transmission rate are determined over a time period starting at an instant before and closest to a most recent change from a previous congestion control state to the current congestion control state, wherein the previous and the current congestion control states specify respectively a previous and a current rule for increasing the congestion window size upon receipt of data acknowledgements when neither congestion nor data losses have been detected, and the previous congestion control state specifies a faster rate of increasing the congestion window size than the current congestion control state.

13. The method according to claim 8, wherein

in the step of determining a trend of the flight size, the trend of the flight size is determined over a time period starting at an instant after and closest to a most recent reduction of the congestion window size due to a detected congestion;

and

in the step of determining a trend of the transmission rate, the trend of the transmission rate is determined over a time period starting at an instant before and closest to said most recent reduction of the congestion window size due to a detected congestion.

14. An apparatus for controlling, in a transmitting node, congestion in a data communication protocol employing acknowledged communication in which the transmitting node transmits data to a receiving node and the receiving node acknowledges receipt of the data, wherein a congestion window specifies a maximum amount of unacknowledged data which the transmitting node may transmit before reception of a positive acknowledgement for all or part of that data, the apparatus comprising:

a flight size measuring unit for measuring a flight size indicating an amount of data sent by the transmitting node and not yet acknowledged by the receiving node;

a transmission rate measuring unit for measuring a transmission rate, the transmission rate corresponding to a same time instant as the flight size;

a flight size trend calculation unit for determining a trend of the flight size;

a transmission rate trend calculation unit for determining a trend of the transmission rate, wherein the trend is derived from a transmission rate gradient calculation, in which either the transmission rate measurements or the transmission rate gradient calculations or both, are filtered to reduce their temporal variability;

a congestion detection unit for detecting whether there is a congestion according to the determined trend of the transmission rate and the trend of the flight size;

a congestion handling unit for, upon positive detection of the congestion by the congestion detection unit, modifying the congestion window; and

a transmission unit for transmitting data while respecting the congestion window size, wherein the congestion detection unit is configured to;

detect whether there is a congestion including detecting whether there is any of a congestion with unfair competition and a congestion without unfair competition,

to positively detect the congestion with unfair competition when the trend of the flight size is either increasing or substantially stable and the trend of the transmission rate is decreasing, and to negatively detect it otherwise, and

to positively detect the congestion without unfair competition when the trend of the flight size is increasing and the trend of the transmission rate is substantially stable, and to negatively detect it otherwise.

15. The apparatus according to claim 14, wherein the congestion handling unit is configured to modify the congestion window including increasing the congestion window size upon positively detecting the congestion with unfair competition by the congestion detection unit.

16. The apparatus according to claim 15, wherein

the communication protocol is TCP, and

the congestion handling unit is configured to increase the congestion window size upon positively detecting the congestion with unfair competition if the transmitting node is in TCP congestion avoidance congestion control state and not to reduce the congestion window size otherwise.

17. An apparatus for controlling, in a transmitting node, congestion in a data communication protocol employing acknowledged communication in which the transmitting node transmits data to a receiving node and the receiving node acknowledges receipt of the data, wherein a congestion window specifies a maximum amount of unacknowledged data which the transmitting node may transmit before reception of a positive acknowledgement for all or part of that data, the apparatus comprising:

a flight size measuring unit for measuring a flight size indicating an amount of data sent by the transmitting node and not yet acknowledged by the receiving node;

a transmission rate measuring unit for measuring a transmission rate, the transmission rate corresponding to a same time instant as the flight size;

a flight size trend calculation unit for determining a trend of the flight size;

a transmission rate trend calculation unit for determining a trend of the transmission rate, wherein the trend is derived from a transmission rate gradient calculation, in which either the transmission rate measurements or the transmission rate gradient calculations or both, are filtered to reduce their temporal variability;

a congestion detection unit for detecting whether there is a congestion according to the determined trend of the transmission rate and the trend of the flight size;

a congestion handling unit for, upon positive detection of the congestion by the congestion detection unit, modifying the congestion window; and

a transmission unit for transmitting data while respecting the congestion window size,

wherein the congestion detection unit is configured to;

detect whether there is a congestion including detecting whether there is a congestion with unfair competition; and

to positively detect the congestion with unfair competition when the trend of the flight size is either increasing or substantially stable and the trend of the transmission rate is decreasing, and to negatively detect it otherwise,

wherein the congestion handling unit is configured to modify the congestion window including changing from a current congestion control state to a new congestion control state upon positively detecting the congestion with unfair competition by the congestion detection unit, wherein the current and the new congestion control states specify respectively a current and a new rule for increasing the congestion window size upon receipt of data acknowledgements when neither congestion nor data losses have been detected by the congestion detection unit, and

wherein the new rule specifies a faster rate of increasing the congestion window size than the current rule.

18. The apparatus according to claim 17, wherein

the communication protocol is TCP,

the congestion handling unit is configured to change from a current congestion control state to a new congestion control state upon positively detecting the congestion with unfair competition is performed if the current congestion control state is TCP congestion avoidance and not to change the current congestion control state otherwise, and

the new congestion control state is TCP slow start.

19. The apparatus according to claim 17, wherein

the flight size trend calculation unit and the transmission rate trend calculation unit are configured to calculate the trend of the flight size and the trend of the transmission rate, respectively, over a time period starting at an instant before and closest to a most recent change from a previous congestion control state to the current congestion control state, wherein the previous and the current congestion control states specify respectively a previous and a current rule for increasing the congestion window size upon receipt of data acknowledgements when neither congestion nor data losses have been detected by the congestion detection unit, and the previous congestion control state specifies a faster rate of increasing the congestion window size than the current congestion control state.

20. The apparatus according to claim 17, wherein

the flight size trend calculation unit is configured to calculate the trend of the flight size over a time period starting at an instant after and closest to a most recent reduction of the congestion window size due to a congestion detected by the congestion detecting;

and

the transmission rate trend calculation unit is configured to calculate the trend of the transmission rate over a time period starting at an instant before and closest to the most recent reduction of the congestion window size due to a congestion detected by the congestion detecting.

21. An apparatus for controlling, in a transmitting node, congestion in a data communication protocol employing acknowledged communication in which the transmitting node transmits data to a receiving node and the receiving node acknowledges receipt of the data, wherein a congestion window specifies a maximum amount of unacknowledged data which the transmitting node may transmit before reception of a positive acknowledgement for all or part of that data, the apparatus comprising:

a flight size measuring unit for measuring a flight size indicating an amount of data sent by the transmitting node and not yet acknowledged by the receiving node;

a transmission rate measuring unit for measuring a transmission rate, the transmission rate corresponding to a same time instant as the flight size;

a flight size trend calculation unit for determining a trend of the flight size;

a transmission rate trend calculation unit for determining a trend of the transmission rate, wherein the trend is derived from a transmission rate gradient calculation, in which either the transmission rate measurements or the transmission rate gradient calculations or both, are filtered to reduce their temporal variability;

a congestion detection unit for detecting whether there is a congestion according to the determined trend of the transmission rate and the trend of the flight size;

a congestion handling unit for, upon positive detection of the congestion by the congestion detection unit, modifying the congestion window; and

a transmission unit for transmitting data while respecting the congestion window size,

wherein the congestion detection unit is configured to;

detect whether there is a congestion including detecting whether there is a congestion without unfair competition; and

to positively detect the congestion without unfair competition when the trend of the flight size is increasing and the trend of the transmission rate is substantially stable, and to negatively detect it otherwise,

wherein the congestion handling unit is configured to modify the congestion window including changing from a current congestion control state to a new congestion control state upon positively detecting the congestion without unfair competition by the congestion detection unit, wherein the current and the new congestion control states specify respectively a current and a new rule for increasing the congestion window size upon receipt of data acknowledgements when neither congestion nor data losses have been detected by the congestion detection unit, and

wherein the new rule specifies a slower rate of increasing the congestion window size than the current rule.

22. The apparatus according to claim 21, wherein the congestion handling unit is configured to modify the congestion window including reducing the congestion window size upon positively detecting the congestion without unfair competition by the congestion detection unit.

23. The apparatus according to claim 22, wherein

the communication protocol is TCP, and

the congestion handling unit is configured to reduce the congestion window size upon positively detecting the congestion without unfair competition if the transmitting node is in TCP congestion avoidance congestion control state and not to reduce the congestion window size otherwise.

24. The apparatus according to claim 21, wherein

the communication protocol is TCP,

the congestion handling unit is configured to change from a current congestion control state to a new congestion control state upon positively detecting the congestion with unfair competition is performed if the current congestion control state is TCP slow start and not to change the current congestion control state otherwise, and

the new congestion control state is TCP congestion avoidance.

25. The apparatus according to claim 21, wherein

the flight size trend calculation unit and the transmission rate trend calculation unit are configured to calculate the trend of the flight size and the trend of the transmission rate, respectively, over a time period starting at an instant before and closest to a most recent change from a previous congestion control state to the current congestion control state, wherein the previous and the current congestion control states specify respectively a previous and a current rule for increasing the congestion window size upon receipt of data acknowledgements when neither congestion nor data losses have been detected by the congestion detection unit, and the previous congestion control state specifies a faster rate of increasing the congestion window size than the current congestion control state.

26. The apparatus according to claim 21, wherein

the flight size trend calculation unit is configured to calculate the trend of the flight size over a time period starting at an instant after and closest to a most recent reduction of the congestion window size due to a congestion detected by the congestion detecting;

and

the transmission rate trend calculation unit is configured to calculate the trend of the transmission rate over a time period starting at an instant before and closest to the most recent reduction of the congestion window size due to a congestion detected by the congestion detecting.