Constant gain controller for active queue management

• US 7,336,672 B1
• Filed: 04/25/2003
• Issued: 02/26/2008
• Est. Priority Date: 12/06/1999
• Status: Expired due to Term

• Current Assignee: Avaya Management L.P. (Avaya Incorporated)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Aweya, James, Montuno, Delfin Y., Ouellette, Michel, Yao, Zhonghui, Firoiu, Victor
• Primary Examiner(s): Duong, Frank
• Application Number:
  US10/422,796
• Time in Patent Office: 1,768 Days
• Field of Search: None
• US Class Current: 370/412
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• 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/32 by discarding or delaying data units, e.g. packets or frames

Abstract

Various techniques for queue management based on random early detection (RED) are disclosed herein. In particular, a method for generating a drop probability for an incoming packet in a device having a queue to buffer packets between segments of a network is provided. The method comprises determining, upon receipt of an incoming packet, a size of the queue and determining an error based at least in part on a difference between the queue size and a threshold. The method further comprises determining a drop probability for the incoming packet based at least in part on the error and a constant gain factor. The constant gain factor may be based at least in part on a linearized second order dynamic model of the network.

Claims

1. In a device having a queue to buffer packets between segments of a network, a method for generating a drop probability for an incoming packet comprising:

receiving an incoming packet;

determining, upon receipt of the incoming packet, a size of the queue;

determining an error based at least in part on a difference between the queue size and a threshold; and

generating a drop probability for the incoming packet based at least in part on the error and a constant gain factor.

2. The method as in claim 1, further comprising filtering the queue size using an exponentially weighted moving average (EWMA) filter to generate a filtered queue size and wherein the error is determined based on a difference between the filtered queue size and the threshold.

3. The method as in claim 2, wherein the queue size is filtered based on the equation:

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

β

){circumflex over (q)}(n−

1)+β

q(n)

where q(n) represents the queue size, {circumflex over (q)}(n) represents the filtered queue size at a current time instant, {circumflex over (q)}(n−

1) represents a filtered queue size of a previous time instant and β

represents a filter gain value between 0 and 1.

4. The method as in claim 1, wherein the drop probability is determined based on an equation:

P_d(n)=min[max(−

k_ce(n),0),θ

]

where P_d(n) represents the drop probability for the incoming packet, e(n) represents the error, k_c represents the constant gain factor and θ

represents a value between 0 and 1.

5. The method as in claim 1, wherein the constant gain factor is selected from a range of values:

$-\frac{2<br><br>N<br><br>\left(R_0<br><br>C+2<br><br>N\right)<br><br>z_1}{{\left(R_0<br><br>C\right)}^3<br><br>\sin <br><br>\left(z_1\right)}<<br><br>k_c<<br><br>\frac{4<br><br>N^2}{{\left(R_0<br><br>C\right)}^3}$

where N represents a number of connections to the network device, C represents a link capacity of the network, R₀ represents a round trip time of a packet in the network, and z₁ represents a solution to

$\cot <br><br>\left(z_1\right)=\frac{z_1^2-2<br><br>N/R_0<br><br>C}{z_1<br><br>\left(R_0<br><br>C+2<br><br>N\right)/R_0<br><br>C}$

such that z₁ε

(0,π

).

6. The method as in claim 1, wherein the constant gain factor is selected from a range of values:

$\underset{j=\mathrm{od},\mathrm{od}+2}{\max }<br><br>\left\{-\frac{2<br><br>N<br><br>\left(R_0<br><br>C+2<br><br>N\right)<br><br>z_j}{{\left(R_0<br><br>C\right)}^3<br><br>\sin <br><br>\left(z_j\right)}\right\}<<br><br><br><br>k_c<<br><br>\underset{j=\mathrm{ev},\mathrm{ev}+2}{\min }<br><br>\left\{-\frac{2<br><br>N<br><br>\left(R_0<br><br>C+2<br><br>N\right)<br><br>z_j}{{\left(R_0<br><br>C\right)}^3<br><br>\sin <br><br>\left(z_j\right)}\right\}$

where N represents a number of connections to the network device, C represents a link capacity of the network, R₀ represents a round trip time of a packet in the network, z_j is a solution of the equation

$\cot <br><br>\left(z\right)=\frac{z^2-2<br><br>N/R_0<br><br>C}{z<br><br>\left(R_0<br><br>C+2<br><br>N\right)/R_0<br><br>C}$

in the interval ((j−

1)π

,jπ

);

od is an odd natural number defined as

$\mathrm{od}=\arg <br><br><br><br>\underset{j<br><br><br><br>\mathrm{odd}<br><br>}{\min }<br><br>\left\{z_{\min }-z_j\right\}$

subject to z_min−

z_j≧

0, and ev is an even natural number or zero defined as

$\mathrm{ev}=\arg <br><br><br><br>\underset{j<br><br><br><br>\mathrm{even}}{\min }<br><br>\left\{z_{\min }-z_j\right\}$

subject to z_min−

z_j≧

0 and

$z_{\min }=R_0<br><br>\sqrt{\frac{2<br><br>N}{R_0^3<br><br>C}-\frac{{\left(\frac{\mathrm{R0C}+2<br><br>N}{R_0^2<br><br>C}\right)}^2}{2}}.$

7. The method as in claim 1, wherein the drop probability is implemented in an active queue management (AQM) mechanism to manage the queue.

8. The method as in claim 1, wherein the network includes a Transport Control protocol (TCP)-based network.

9. The method as in claim 1, wherein the constant gain factor is based at least in part on a linearized second order dynamic model of the network.

10. At least one processor readable medium for storing a computer program of instructions configured to be readable by at least one processor for instructing the at least one processor to execute a computer process for performing the method as in claim 1.

11. In a device having a queue to buffer packets between segments of a network, a method for managing the queue comprising:

generating, for an incoming packet, a drop probability based at least in part on a linearized second order dynamic model of the network;

comparing the drop probability with a random probability; and

dropping the incoming packet when the drop probability is less than or equal to the random probability.

12. The method as in claim 11, wherein the drop probability is determined based on an equation:

P_d(n)=min[max(−

k_ce(n),0),θ

]

where P_d(n) represents the drop probability for the incoming packet, e(n) represents an error between a size of the queue and a threshold, θ

represents a value between 0 and 1, and k_c represents a constant gain factor based at least in part on the linearized second order dynamic model.

13. The method as in claim 12, wherein the constant gain factor is selected from a range of values:

$-\frac{2<br><br>N<br><br>\left(R_0<br><br>C+2<br><br>N\right)<br><br>z_1}{{\left(R_0<br><br>C\right)}^3<br><br>\sin <br><br>\left(z_1\right)}<<br><br>k_c<<br><br>\frac{4<br><br>N^2}{{\left(R_0<br><br>C\right)}^3}$

where N represents a number of connections to the network device, C represents a link capacity of the network, R₀ represents a round trip time of a packet in the network, and z₁ represents a solution to

$\cot <br><br>\left(z_1\right)=\frac{z_1^2-2<br><br>N/R_0<br><br>C}{z_1<br><br>\left(R_0<br><br>C+2<br><br>N\right)/R_0<br><br>C}$

such that z₁ε

(0,π

).

14. The method as in claim 12, wherein the constant gain factor is selected from a range of values:

$\underset{j=\mathrm{od},\mathrm{od}+2}{\max }<br><br>\left\{-\frac{2<br><br>N<br><br>\left(R_0<br><br>C+2<br><br>N\right)<br><br>z_j}{{\left(R_0<br><br>C\right)}^3<br><br>\sin <br><br>\left(z_j\right)}\right\}<<br><br><br><br>k_c<<br><br>\underset{j=\mathrm{ev},\mathrm{ev}+2}{\min }<br><br>\left\{-\frac{2<br><br>N<br><br>\left(R_0<br><br>C+2<br><br>N\right)<br><br>z_j}{{\left(R_0<br><br>C\right)}^3<br><br>\sin <br><br>\left(z_j\right)}\right\}$

where N represents a number of connections to the network device, C represents a link capacity of the network, R₀ represents a round trip time of a packet in the network, z_j is a solution of the equation

$\cot <br><br>\left(z\right)=\frac{z^2-2<br><br>N/R_0<br><br>C}{z<br><br>\left(R_0<br><br>C+2<br><br>N\right)/R_0<br><br>C}$

in the interval ((j−

1)π

,jπ

);

od is an odd natural number defined as

$\mathrm{od}=\arg <br><br><br><br>\underset{j<br><br><br><br>\mathrm{odd}}{\min }<br><br>\left\{z_{\min }-z_j\right\}$

subject to z_min−

z_j≧

0, and ev is an even natural number or zero defined as

$\mathrm{ev}=\arg <br><br><br><br>\underset{j<br><br><br><br>\mathrm{even}}{\min }<br><br>\left\{z_{\min }-z_j\right\}$

subject to z_min−

z_j≧

0 and

$z_{\min }=R_0<br><br>\sqrt{\frac{2<br><br>N}{R_0^3<br><br>C}-\frac{{\left(\frac{\mathrm{R0C}+2<br><br>N}{R_0^2<br><br>C}\right)}^2}{2}}.$

15. The method as in claim 11, wherein the network includes a Transport Control Protocol (TCP)-based network.

16. At least one processor readable medium for storing a computer program of instructions configured to be readable by at least one processor for instructing the at least one processor to execute a computer process for performing the method as in claim 11.

17. In a device having a queue to buffer packets between segments of a network, a queue management apparatus comprising:

a packet drop controller configured to determine a drop probability for an incoming packet based at least in part on an error between a size of the queue and a threshold and a constant gain factor; and

an add/drop module operably connected to the queue controller and is configured to drop the incoming packet when the drop probability is less than or equal to a random probability.

18. The queue management apparatus as in claim 17, wherein the drop probability is determined based on an equation:

P_d(n)=min[max(−

k_ce(n),0),θ

]

where P_d(n) represents the drop probability for the incoming packet, e(n) represents the error between a size of the queue and a threshold, θ

represents a value between 0 and 1, and k_c represents the constant gain factor.

19. The queue management apparatus as in claim 17, wherein the constant gain factor is selected from a range of values:

$-\frac{2<br><br>N<br><br>\left(R_0<br><br>C+2<br><br>N\right)<br><br>z_1}{{\left(R_0<br><br>C\right)}^3<br><br>\sin <br><br>\left(z_1\right)}<<br><br>k_c<<br><br>\frac{4<br><br>N^2}{{\left(R_0<br><br>C\right)}^3}$

where N represents a number of connections to the network device, C represents a link capacity of the network, R₀ represents a round trip time of a packet in the network, and z₁ represents a solution to

$\cot <br><br>\left(z_1\right)=\frac{z_1^2-2<br><br>N/R_0<br><br>C}{z_1<br><br>\left(R_0<br><br>C+2<br><br>N\right)/R_0<br><br>C}$

such that z₁ε

(0,π

).

20. The queue management apparatus as in claim 17, wherein the constant gain factor is selected from a range of values:

$\underset{j=\mathrm{od},\mathrm{od}+2}{\max }<br><br>\left\{-\frac{2<br><br>N<br><br>\left(R_0<br><br>C+2<br><br>N\right)<br><br>z_j}{{\left(R_0<br><br>C\right)}^3<br><br>\sin <br><br>\left(z_j\right)}\right\}<<br><br><br><br>k_c<<br><br>\underset{j=\mathrm{ev},\mathrm{ev}+2}{\min }<br><br>\left\{-\frac{2<br><br>N<br><br>\left(R_0<br><br>C+2<br><br>N\right)<br><br>z_j}{{\left(R_0<br><br>C\right)}^3<br><br>\sin <br><br>\left(z_j\right)}\right\}$

where N represents a number of connections to the network device, C represents a link capacity of the network, R₀ represents a round trip time of a packet in the network, z_j is a solution of the equation

$\cot <br><br>\left(z\right)=\frac{z^2-2<br><br>N/R_0<br><br>C}{z<br><br>\left(R_0<br><br>C+2<br><br>N\right)/R_0<br><br>C}$

in the interval ((j−

1)π

,jπ

);

od is an odd natural number defined as

$\mathrm{od}=\arg <br><br><br><br>\underset{j<br><br><br><br>\mathrm{odd}}{\min }<br><br>\left\{z_{\min }-z_j\right\}$

subject to z_min−

z_j≧

0, and ev is an even natural number or zero defined as

$\mathrm{ev}=\arg <br><br><br><br>\underset{j<br><br><br><br>\mathrm{even}}{\min }<br><br>\left\{z_{\min }-z_j\right\}$

subject to z_min−

z_j≧

0 and

$z_{\min }=R_0<br><br>\sqrt{\frac{2<br><br>N}{R_0^3<br><br>C}-\frac{{\left(\frac{\mathrm{R0C}+2<br><br>N}{R_0^2<br><br>C}\right)}^2}{2}}.$

21. The queue management apparatus as in claim 17, wherein the network includes a Transport Control protocol (TCP)-based network.

22. The queue management apparatus as in claim 17, wherein the constant gain factor is based at least in part on a linearized second order dynamic model of the network.