Efficient congestion control in a tunneled network

Abstract

A method of congestion control implemented by a sender over a network link that includes a router having a queue. During a first state, information is received from a receiver. The information comprises an estimated maximum bandwidth for the link, a one-way transit time for traffic over the link, and an indication whether the network link is congested. In response to the link being congested, the sender transitions to a second state. While in the second state, a sending rate of packets in reduced, in part to attempt to drain the queue of data packets contributed by the sender. The sender transitions to a third state when the sender estimates that the queue has been drained of the data packets contributed. During the third state, the sending rate is increased until either the sender transitions back to the first state, or receives a new indication that the link is congested.

What is claimed is as follows: 
     
       1. A method of congestion control over network links that include a router having a queue used by a set of sending entities, comprising:
 as a particular sending entity is transmitting data over multiple paths, and for at least one path of the multiple paths:
 during a first state, receiving information from a receiving entity, the information comprising an estimated maximum bandwidth for a network link, a one-way transit time for traffic over the network link, a receive rate, and an indication whether the network link is congested; 
 responsive to the indication that the network link is congested, transitioning the sending entity from the first state to a second state; 
 while in the second state, estimating an amount of data the particular sending entity has contributed to the queue; 
 reducing a sending rate of packets at least in part to attempt to drain the queue of data estimated to have been contributed by the particular sending entity; and 
 transitioning the sending entity from the second state to a third state when the particular sending entity estimates that the queue has been drained of the data contributed by the particular sending entity. 
 
 
     
     
       2. The method as described in  claim 1  wherein estimating the amount of data the particular sending entity has contributed to the queue compares an amount of data that is currently outstanding in the queue and subtracts from that value an amount of data that the particular sending entity estimates should have been read from the queue given the receive rate reported by the receiving entity. 
     
     
       3. The method as described in  claim 1  wherein in the third state the sending rate is increased until either the particular sending entity transitions back to the first state, or a new indication that the network link is congested is received. 
     
     
       4. The method as described in  claim 1  wherein the first state is an unconstrained state, the second state is a draining state, and the third state is a probing state. 
     
     
       5. The method as described in  claim 1  wherein the indication that the network link is congested is based on relative sending and receiving rates as measured by the particular sending entity and the receiving entity. 
     
     
       6. The method as described in  claim 1  wherein the information also includes a sequence number of a highest packet received by the receiving entity. 
     
     
       7. The method as described in  claim 1  wherein the particular sending entity keeps track of a number of data packets in flight over the network link. 
     
     
       8. The method as described in  claim 7  wherein the number of data packets in flight is determined by observing a difference between a last packet sent and a last packet acknowledged by the receiving entity. 
     
     
       9. The method as described in  claim 8  wherein a sending rate is based on a desired number of data packets in flight that is equal to an observed round trip time, including queueing delay, and a speed of the network link. 
     
     
       10. The method as described in in  claim 1  wherein an estimate of the data contributed by the particular sending entity is based at least in part on a number of bytes sent but not acknowledged by the receiving entity.