Congestion window modification

• US 9,391,911 B1
• Filed: 07/15/2011
• Issued: 07/12/2016
• Est. Priority Date: 07/15/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Anderson, Glen, Radhakrishnan, Sivasankar
• Primary Examiner(s): Kading, Joshua A
• Application Number:
  US13/184,375
• Time in Patent Office: 1,824 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 1/1621 Group acknowledgement, i.e. the acknowledgement message defining a range of identifiers, e.g. of sequence numbers
• CPC Class Codes: H04L 1/1628 List acknowledgements, i.e. the acknowledgement message consisting of a list of identifiers, e.g. of sequence numbers H04L1/1614 takes precedence
• CPC Class Codes: H04L 1/1635 Cumulative acknowledgement, i.e. the acknowledgement message applying to all previous messages
• CPC Class Codes: H04L 1/1671 the supervisory signal being transmitted together with control information
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures

Abstract

Techniques and mechanisms for evaluating a transmission outcome indicium to determine a state of data traffic congestion in a network. In an embodiment, congestion information for a packet of a transmission group is evaluated at a computer device to determine a congestion state, where a size of the transmission group is determined based on a congestion window parameter. In another embodiment, the evaluation to determine the congestion state is performed prior to the computer device detecting a transmission outcome indicium for some other packet of the transmission group.

Claims

1. A method performed by a source agent of a computer device, the method comprising:

transmitting, by the computer device, a plurality of packets as a transmission group to a destination for the transmission group, where a size of the transmission group is defined by a congestion window parameter having a first value, the transmission group including at least two packets;

receiving, by the computer device, from the destination, an acknowledge message associated with a number of packets of the transmission group, wherein the acknowledge message is associated with more than one packet in the transmission group and less than all packets sent in the transmission group;

identifying, in the acknowledge message, an explicit indicator that the associated packets of the transmission group experienced data traffic congestion;

determining a number of packets of the transmission group that have experienced data traffic congestion based on explicit indicators identified in respective acknowledge messages;

performing an evaluation based on a comparison of the determined number of packets to a threshold number of packets;

determining a congestion state based on the evaluation;

prior to receiving any subsequent acknowledge messages associated with other packets of the transmission group, changing the congestion window parameter from the first value to a second value based on the determined congestion state; and

transmitting, by the computer device, at least one additional packet of the transmission group with the congestion window parameter having the second value.

2. The method of claim 1, the congestion window parameter indicating a threshold number of transmitted packets that are pending in a network at a given time.

3. The method of claim 1, wherein the transmission group is a first transmission group, the method further comprising:

transmitting packets of a second transmission group subsequent to the first transmission group, the second transmission group size is based on the congestion window parameter having the second value, prior to receiving respective transmission outcome indicia for each packet of the first transmission group.

4. The method of claim 1, wherein the transmission group is a first transmission group, the method further comprising:

initiating a sending of packets of a second transmission group subsequent to the first transmission group, based on the congestion window parameter having the second value;

detecting a transmission outcome indicium associated with a second packet of the first transmission group;

performing an evaluation of the transmission outcome indicium associated with the second packet of the first transmission group to determine a second congestion state; and

based on the determining the second congestion state, generating a signal indicating that the congestion window parameter is to be changed from the second value to a third value, wherein, after the initiating the sending of packets of the second transmission group, the sending of packets of the second transmission group is modified based on the congestion window parameter having the third value.

5. The method of claim 1, further comprising changing a packet transmission rate.

6. The method of claim 1, further comprising:

detecting second congestion information from a second acknowledge message associated with a second packet;

performing a second evaluation to determine a second congestion state, the second evaluation based on the second congestion information; and

modifying a congestion mitigation measure based on the second evaluation.

7. The method of claim 1, wherein the performing the evaluation is prior to any determination of a failure to receive, by the computer device, an acknowledge message associated with another packet transmitted in the transmission group.

8. The method of claim 1, wherein the evaluation is based on at least one of the following:

a threshold number of packets of the transmission group which have been identified as being associated with data traffic congestion; and

a threshold rate of change of a number of packets of the transmission group which have been identified as being associated with data traffic congestion.

9. A computer device comprising:

a transmission outcome repository to store congestion information;

a communication interface configured to;

transmit a plurality of packets as a transmission group to a destination for the transmission group, where a size of the transmission group is defined by a congestion window parameter having a first value, the transmission group including at least two packets, and

receive, from the destination, an acknowledge message associated with a number of packets of the transmission group, wherein the acknowledge message is associated with more than one packet in the transmission group and less than all packets sent in the transmission group;

congestion evaluation logic coupled to the transmission outcome repository configured to;

identify, in the acknowledge message, an explicit indicator that the associated packets of the transmission group experienced data traffic congestion;

determine a number of packets of the transmission group that have experienced data traffic congestion based on explicit indicators identified in respective acknowledge messages, and

perform an evaluation based on a comparison of the determined number of packets to a threshold number of packets;

the congestion evaluation logic further configured to determine a congestion state based on the evaluation; and

congestion response logic, wherein the congestion evaluation logic is configured to send a signal to the congestion response logic prior to receiving any subsequent acknowledge messages associated with other packets of the transmission group, the congestion response logic configured to change, responsive to the signal, the congestion window parameter from the first value to a second value based on the determined congestion state, after which the communication interface transmits at least one additional packet of the transmission group with the congestion window parameter having the second value.

10. The computer device of claim 9, wherein:

the transmission group is a first transmission group, and

the congestion response logic is further configured to transmit packets of a second transmission group subsequent to the first transmission group, the second transmission group size is based on the congestion window parameter having the second value, prior to the communication interface receiving respective transmission outcome indicium for each packet of the first transmission group.

11. The computer device of claim 10, wherein the transmission group is a first transmission group and wherein:

the congestion response logic is further configured to initiate a sending of packets of the second transmission group subsequent to the first transmission group based on the congestion window parameter having the second value;

the congestion evaluation logic is further configured to detect the transmission outcome indicium associated with a second packet of the first transmission group;

the congestion evaluation logic is further configured to perform an evaluation of the transmission outcome indicium associated with the second packet of the first transmission group to determine a second congestion state;

based on the determining the second congestion state, the congestion evaluation logic is further configured to signal that the congestion window parameter is to be changed from the second value to a third value; and

wherein after the initiating the sending of packets of the second transmission group, the congestion response logic is further configured to modify the sending of packets of the second transmission group based on the congestion window parameter having the third value.

12. The computer device of claim 9, wherein the congestion evaluation logic is further configured to detect second congestion information from a second acknowledge message associated with a second packet, and the congestion evaluation logic further to perform a second evaluation to determine a second congestion state, the second evaluation based on the second congestion information.

13. The computer device of claim 12, wherein the congestion response logic is further configured to modify a congestion mitigation measure based on the second evaluation.

14. The computer device of claim 9, wherein the congestion evaluation logic is configured to perform the evaluation based on at least one of the following:

a threshold number of packets of the transmission group which have been identified as being associated with data traffic congestion; and

a threshold rate of change of a number of packets of the transmission group which have been identified as being associated with data traffic congestion.

15. A non-transitory computer-readable storage medium having stored thereon instructions which, when executed by one or more processing units, cause the one or more processing units to:

transmit a plurality of packets as a transmission group to a destination for the transmission group, where a size of the transmission group is defined by a congestion window parameter having a first value, the transmission group including at least two packets;

receive, from the destination, an acknowledge message associated with a number of packets of the transmission group, wherein the acknowledge message is associated with more than one packet in the transmission group and less than all packets sent in the transmission group;

identify, in the acknowledge message, an explicit indicator that the associated packets of the transmission group experienced data traffic congestion;

determine a number of packets of the transmission group that have experienced data traffic congestion based on explicit indicators identified in respective acknowledge messages;

perform an evaluation based on a comparison of the determined number of packets to a threshold number of packets;

determine a congestion state based on the evaluation;

change, prior to receiving any subsequent acknowledge messages associated with other packets of the transmission group, the congestion window parameter from the first value to a second value based on the determined congestion state; and

transmit at least one additional packet of the transmission group with the congestion window parameter having the second value.

16. The computer-readable storage medium of claim 15, the congestion window parameter indicating a threshold number of transmitted packets to be pending in a network at a given time.

17. The computer-readable storage medium of claim 15, wherein the transmission group is a first transmission group, and the instructions further cause the one or more processing units to:

transmit packets of a second transmission group subsequent to the first transmission group, the second transmission group sized based on the congestion window parameter having the second value, prior to receiving respective transmission outcome indicia for each packet of the first transmission group.

18. The computer-readable storage medium of claim 15, wherein the transmission group is a first transmission group, and the instructions further cause the one or more processing units to:

initiate sending of packets of a second transmission group subsequent to the first transmission group based on the congestion window parameter having the second value;

detect the transmission outcome indicium associated with a second packet of the first transmission group;

perform an evaluation of a transmission outcome indicium associated with the second packet of the first transmission group to determine a second congestion state;

change, based on the second congestion state, the congestion window parameter from the second value to a third value after initiating the sending of packets of the second transmission group; and

modify the sending of packets of the second transmission group based on the congestion window parameter having the third value.

19. The computer-readable storage medium of claim 15, wherein the instructions further cause the one or more processing units to change a packet transmission rate.

20. The computer-readable storage medium of claim 15, wherein the instructions further cause the one or more processing units to:

detect second congestion information from a second acknowledge message associated with a second packet;

perform a second evaluation to determine a second congestion state, the second evaluation based on the second congestion information; and

modify a congestion mitigation measure based on the second evaluation.

21. The computer-readable storage medium of claim 15, wherein the performing the evaluation is prior to any determination of a failure to acknowledge the second packet.

22. The computer-readable storage medium of claim 15, wherein the evaluation is based on at least one of the following:

a threshold number of packets of the transmission group which have been identified as being associated with data traffic congestion; and

a threshold rate of change of a number of packets of the transmission group which have been identified as being associated with data traffic congestion.