TCP rate control with adaptive thresholds

• US 7,047,312 B1
• Filed: 12/18/2000
• Issued: 05/16/2006
• Est. Priority Date: 07/26/2000
• Status: Expired due to Term

• Current Assignee: Avaya Management L.P. (Avaya Incorporated)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Ouellette, Michel, Montuno, Delfin Y., Aweya, James
• Primary Examiner(s): Caldwell, Andrew
• Assistant Examiner(s): WILLETT, STEPHAN F
• Application Number:
  US09/739,309
• Time in Patent Office: 1,975 Days
• Field of Search: 709/235, 709/238, 709/233, 709/215, 370/236, 371/231
• US Class Current: 709/235
• CPC Class Codes: H04L 1/1832 Details of sliding window management
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/25 with rate being modified by the source upon detecting a change of network conditions
• 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 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/35 by embedding flow control information in regular packets, e.g. piggybacking
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures

Abstract

The TCP receiver'"'"'s advertised window (i.e., the receive buffer of a TCP connection) limits the maximum window and consequently the throughput that can be achieved by the sender. Thus, the idea behind TCP rate control is to match the offered network load to the available resources by modifying at an intermediate network device, the receiver'"'"'s advertised window in TCP acknowledgments returning to the sources. In this disclosure, we propose a new TCP rate control scheme for a shared buffer where the buffer is logically organized into multiple queues. In the scheme, dynamic buffer thresholds are used to ensure efficient and fair usage of buffer memory among the queues. Conventional schemes allocate buffer space to each queue through the use of static buffer thresholds. This can result in unnecessary packet drops which leads to poor network performance since congested or heavily loaded queues cannot gain access to buffers not utilized by lightly loaded queues.

Claims

1. A method for controlling the transmission of data packets through a network by controlling a Transmission Control Protocol (TCP) rate in a network device having a shared buffer with shared buffer space, the method comprising:

organizing a forward data buffer into one or more queues that store at least one forward data packet;

calculating the network device'"'"'s advertised window size by;

(1) initializing a timer to a predetermined time interval Δ

t, and an iteration counter to a predetermined initial value n;

(2) sampling a current queue size q_i(n) during the predetermined time interval Δ

t;

(3) calculating a current error signal e_i(n) based, at least in part, upon the current queue size q_i(n);

(4) calculating the network device'"'"'s advertised window size W_i(n), based, at least in part, upon the current error signal e_i(n) according to the equation;

W_i(n)=[W_i(n−

1)+α

e_i(n)]_Wmin^Wmax, where α

, W_max, and W_min, are predetermined parameters;

(5) resetting the timer, upon expiration of the predetermined interval Δ

t; and

(6) iterating the iteration counter, upon expiration of the predetermined time interval Δ

t;

providing the network device'"'"'s advertised window size to a TCP source; and

calculating a dynamic buffer threshold based, at least in part, upon the sum of the queue sizes and the shared buffer space.

2. The method of claim 1 wherein the step of organizing a forward data buffer further comprises:

organizing the forward data buffer into one or more queues with one queue per service class.

3. The method of claim 1 wherein the at least one forward data packet is stored according to its service class.

4. The method of claim 1 wherein the steps of calculating a current error signal e_i(n) and calculating the network device'"'"'s advertised window size further comprise:

filtering the current error signal e_i(n) according to the relation;

ê

_i(n)=(1−

β

)ê

_i(n−

1)+β

e_i(n), where β

is a predetermined parameter; and

calculating the network device'"'"'s advertised window size W_i(n), based, at least in part, upon the filtered current error signal ê

_i(n) according to the equation;

W_i(n)=[W_i(n−

1)+α

ê

_i(n)]_Wmin^Wmax, where α

, W_max, and W_min, are predetermined parameters.

5. The method of claim 1 wherein the step of providing the network device'"'"'s advertised window size to a TCP source further comprises:

carrying information relating to the network device'"'"'s advertised window size by returning TCP acknowledgements in a receiver'"'"'s advertised window field.

6. The method of claim 1 wherein the step of providing the network device'"'"'s advertised window size to a TCP source further comprises:

updating a TCP receiver'"'"'s advertised window size.

7. The method of claim 6 wherein the step of updating a TCP receiver'"'"'s advertised window size further comprises:

identifying whether a packet is an ACK packet, and, if not, putting the non-ACK packet in a reverse data buffer;

determining a service class for the identified ACK packet;

reading the TCP receiver'"'"'s advertised window size (RW_rec) and a checksum (RCHKSUM) from the identified ACK packet;

determining whether the TCP receiver'"'"'s advertised window size RW_REC, is less than or equal to the calculated network device'"'"'s advertised window size W_i(n) and, if not setting a advertised window field in the identified ACK packet equal to the network device'"'"'s advertised window size W_i(n) and updating the checksum field for the identified ACK packet.

8. The method of claim 1 wherein the step of calculating a dynamic buffer threshold further comprises:

initializing a timer to a predetermined time interval Δ

s and an iteration counter to a predetermined initial value n;

setting an initial dynamic buffer threshold T(0) equal to a gain constant γ

multiplied by a buffer size B and divided by a number of service classes K;

sampling a current queue size q_i(n) during the predetermined time interval Δ

s;

calculating a sum of the sampled current queue size according to the equation;

$Q<br><br>\left(n\right)=\underset{i=1}{\overset{K}{\sum <br><br>}}<br><br>q_i<br><br>\left(n\right);<br><br>$

determining whether the sum of the sampled current queue size is less than the product of the gain constant and the buffer size γ

B;

if so, updating the dynamic buffer threshold according to min{T(n−

1)+Δ

T, γ

B}, where Δ

T is a step size that controls the rate at which the dynamic buffer threshold changes;

if not, updating the dynamic buffer threshold according to max{T(n−

1)−

Δ

T, T_min}, where T_min is a predetermined minimum size for the dynamic buffer threshold;

resetting the timer, upon expiration of the predetermined interval Δ

s; and

iterating the iteration counter, upon expiration of the predetermined time interval Δ

s.

9. The method of claim 8 wherein the step of calculating a sum of the sampled current queue size further comprises:

filtering the sum of the sampled current queue size Q(n) according to the relation;

{circumflex over (Q)}(n)=(1−

φ

){circumflex over (Q)}(n−

1)+φ

Q(n), wherein φ

is a predetermined parameter.

10. An apparatus for controlling the transmission of data packets through a network by controlling a Transmission Control Protocol (TCP) rate in a network device having a shared buffer with shared buffer space, the apparatus comprising:

a forward data buffer, organized into one or more queues that store at least one forward data packet;

a network device'"'"'s advertised window size calculation module further comprising;

(1) a timer, initially set to a predetermined time interval Δ

t, and an iteration counter initially set to a predetermined initial value n;

(2) a current queue size sampler that samples a current queue size q_i(n) during the predetermined time interval Δ

t;

(3) a current error signal calculation module that calculates a current error signal e_i(n) based, at least in part, upon the current queue size q_i(n); and

(4) a window size calculation module that calculates the network device'"'"'s advertised window size W_i(n), based, at least in part, upon the current error signal e_i(n) according to the equation;

W_i(n)=[W_i(n−

1)+α

e_i(n)]_Wmin^Wmax, where α

, W_max, and W_min, are predetermined parameters;

a feed back module that provides the network device'"'"'s advertised window size to a TCP source; and

a dynamic buffer threshold module that calculates a dynamic buffer threshold based, at least in part, upon the sum of the queue sizes and the shared buffer space.

11. The apparatus of claim 10 wherein the current error signal calculation module further comprises:

a filter module that filters the current error signal e_i(n) according to the relation;

ê

_i(n)=(1−

β

)ê

_i(n−

1)+β

e_i(n), where β

is a predetermined parameter; and

wherein the window size calculation module calculates the network device'"'"'s advertised window size W_i(n), based, at least in part, upon the filtered current error signal ê

_i(n) according to the equation;

W_i(n)=[W_i(n−

1)+α

ê

_i(n)]_Wmin^Wmax, where α

, W_max, and W_min, are predetermined parameters.

12. The apparatus of claim 10 wherein the feed back module further comprises:

an advertised window size updating module that updates a TCP receiver'"'"'s advertised window size.

13. The apparatus of claim 12 wherein the advertised window size updating module further comprises:

an ACK packet identification module that identifies whether a packet is an ACK packet, and, if not, puts the non-ACK packet in a reverse data buffer;

an ACK packet classifier that determines a service class for the identified ACK packet;

an advertised window size reader that reads a TCP receiver'"'"'s advertised window size (RW_rec) and a checksum (RCHKSUM) from the identified ACK packet;

a window size comparison module that determines whether the TCP receiver'"'"'s advertised window size RW_REC, is less than or equal to the calculated network device'"'"'s advertised window size W_i(n) and, if not sets an advertised window field in the identified ACK packet equal to the calculated network device'"'"'s advertised window size W_i(n) and updates the checksum field for the identified ACK packet.

14. The apparatus of claim 10 wherein the dynamic buffer threshold module further comprises:

a timer initially set to a predetermined time interval Δ

s and an iteration counter initially set to a predetermined initial value n;

a current queue size sampler that samples a current queue size q_i(n) during the predetermined time interval Δ

s;

a current queue size calculation module that calculates a sum of the sampled current queue size according to the equation;

$Q<br><br>\left(n\right)=\underset{i=1}{\overset{K}{\sum <br><br>}}<br><br>q_i<br><br>\left(n\right),$

where K is a number of service classes;

a dynamic buffer threshold determiner that determines whether the sum of the sampled current queue size is less than the product of a gain constant γ and

a buffer size B;

and an updating module that updates the dynamic buffer threshold if the sum of the sampled current queue size is less than the product of the gain constant γ and

the buffer size B, according to min{T(n−

1)+Δ

T, γ

B}, where Δ

T is a step size that controls the rate at which the dynamic buffer threshold changes and if the sum of the sampled current queue size is not less than the product of a gain constant γ and

a buffer size B, updates the dynamic buffer threshold according to max{T(n−

1)−

Δ

T, T_min}, where T_min is a predetermined minimum size for the dynamic buffer threshold.

15. The apparatus of claim 14 wherein the current queue size calculation module further comprises:

a filter that filters the sum of the sampled current queue size Q(n) according to the relation;

{circumflex over (Q)}(n)=(1−

φ

){circumflex over (Q)}(n−

1)+φ

Q(n), wherein φ

is a predetermined parameter.

16. An article of manufacture for controlling the transmission of data packets through a network by controlling a Transmission Control Protocol (TCP) rate in a network device having a shared buffer with shared buffer space, the article of manufacture comprising:

at least one processor readable carrier; and

instructions carried on the at least one carrier;

wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to;

organize a forward data buffer into one or more queues that store at least one forward data packet;

calculate a network device'"'"'s advertised window size by;

(1) initializing a timer to a predetermined time interval Δ

t, and an iteration counter to a predetermined initial value n;

(2) sampling a current queue size q_i(n) during the predetermined time interval Δ

t;

(3) calculating a current error signal e_i(n) based, at least in part, upon the current queue size q_i(n);

(4) calculating the network device'"'"'s advertised window size W_i(n), based, at least in part, upon the current error signal e_i(n) according to the equation;

W_i(n)=[W_i(n−

1)+α

e_i(n)]_Wmin^Wmax, where α

, W_max, and W_min, are predetermined parameters;

(5) resetting the timer, upon expiration of the predetermined interval Δ

t; and

(6) iterating the iteration counter, upon expiration of the predetermined time interval Δ

t;

provide the network device'"'"'s advertised window size to a TCP source; and

calculate a dynamic buffer threshold based, at least in part, upon the sum of the queue sizes and the shared buffer space.

17. The article of manufacture of claim 16 wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to:

organize the forward data buffer into one or more queues with one queue per service class.

18. The article of manufacture of claim 16 wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to:

store the at least one forward data packet according to its service class.

19. The article of manufacture of claim 16 wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to:

filter the current error signal e_i(n) according to the relation;

ê

_i(n)=(1−

β

)ê

_i(n−

1)+β

e_i(n), where β

is a predetermined parameter; and

calculate the network device'"'"'s advertised window size W_i(n), based, at least in part, upon the filtered current error signal ê

_i(n) according to the equation;

W_i(n)=[W_i(n−

1)+α

ê

_i(n)]_Wmin^Wmax, where α

, W_max, and W_min, are predetermined parameters.

20. The article of manufacture of claim 16 wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to:

carry information relating to the network device'"'"'s advertised window size by returning TCP acknowledgements in a receiver'"'"'s advertised window field.

21. The article of manufacture of claim 16 wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to:

update a TCP receiver'"'"'s advertised window size.

22. The article of manufacture of claim 21 wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to:

identify whether a packet is an ACK packet, and, if not, put the non-ACK packet in a reverse data buffer;

determine a service class for the identified ACK packet;

read a TCP receiver'"'"'s advertised window size (RW_rec) and a checksum (RCHKSUM) from the identified ACK packet;

determine whether the TCP receiver'"'"'s advertised window size RW_REC, is less than or equal to the calculated network device'"'"'s advertised window size W_i(n) and, if not setting an advertised window field in the identified ACK packet equal to the calculated network device'"'"'s advertised window size W_i(n) and updating the checksum field for the identified ACK packet.

23. The article of manufacture of claim 16 wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to:

initialize a timer to a predetermined time interval Δ

s and an iteration counter to a predetermined initial value n;

set an initial dynamic buffer threshold T(0) equal to a gain constant γ

multiplied by a buffer size B and divided by a number of service classes K;

sample a current queue size q_i(n) during the predetermined time interval Δ

s;

calculate a sum of the sampled current queue size according to the equation;

$Q<br><br>\left(n\right)=\underset{i=1}{\overset{K}{\sum <br><br>}}<br><br>q_i<br><br>\left(n\right);<br><br>$

determine whether the sum of the sampled current queue size is less than the product of the gain constant and the buffer size γ

B;

if so, updating the dynamic buffer threshold according to min{T(n−

1)+Δ

T, γ

B}, where Δ

T is a step size that controls the rate at which the dynamic buffer threshold changes;

if not, updating the dynamic buffer threshold according to max{T(n−

1)−

Δ

T, T_min}, where T_min is a predetermined minimum size for the dynamic buffer threshold;

reset the timer, upon expiration of the predetermined interval Δ

s; and

iterate the iteration counter, upon expiration of the predetermined time interval Δ

s.

24. The article of manufacture of claim 23 wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to:

filter the sum of the sampled current queue size Q(n) according to the relation;

{circumflex over (Q)}(n)=(1−

φ

){circumflex over (Q)}(n−

1)+φ

Q(n), wherein φ

is a predetermined parameter.