Active queue management process

• US 7,272,111 B2
• Filed: 08/09/2002
• Issued: 09/18/2007
• Est. Priority Date: 08/09/2001
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Australia Pty Ltd (Hewlett-Packard Enterprise Company), University of Melbourne
• Original Assignee: Hewlett-Packard Australia Pty Ltd (Hewlett-Packard Enterprise Company), University of Melbourne
• Inventors: Zukerman, Moshe, Wydrowski, Bartek Peter
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): TRAN, PHUC H
• Application Number:
  US10/215,182
• Publication Number:
  US 20030088690A1
• Time in Patent Office: 1,866 Days
• Field of Search: None
• US Class Current: 370/230
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• 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

An active queue management (AQM) process for network communications equipment. The AQM process is rate based and involves applying at a rate congestion notification to communications packets in a queue of a link, and adjusting the rate of congestion notification on the basis of the difference between an arrival rate for the packets and a target capacity of the link. Network communications equipment includes a switch component for switching communications packets between input ports and output ports, packet queues for at least the output ports, and an active queue manager for applying congestion notification to communications packets in the queues for the output ports. The congestion notification is applied at respective rates for the queues, and the rates of congestion notification adjusted on the basis of the respective arrival rates of the packets for the queues of the output ports. The AQM process can be applied to a class based DiffServ architecture.

Claims

1. An active queue management process, including:

applying at a rate P congestion notification to communications packets in a queue of a link; and

adjusting said rate P of congestion notification on the basis of the difference between an arrival rate for said packets and a target capacity of said link;

wherein said rate P of congestion notification is incremented by an amount Δ

P at an update rate when said arrival rate is above said capacity, and P is decremented by Δ

P at said update rate when said arrival rate is less than said capacity.

2. A process as in claim 1, wherein P=P+Δ

P·

U(X_est−

c_t), where X_est is the estimated arrival rate, c_t is the target capacity of the link, and

$U<br><br>\left(x\right)=\{\begin{array}{cc}+1& x\ge <br><br>0\\ -1& x<<br><br>0\end{array}.$

3. A process as in claim 2, wherein Δ

P=max(abs(α

(x_est−

c_t), k), where α

is a constant to control gain, and k is a constant to limit minimum adjustment to P.

4. A process as in claim 2, wherein X_est=(1−

exp(−

Del/K))*(B/Del)+exp(−

Del/K)*X_est, where Del is the time between received packets, B the packet size and K is a time constant.

5. A process as in claim 1, wherein said link has a plurality of said queue allocated respectively to priority classes i of said packets and for each queue, said rate of congestion Pi(t) at a given time t is:

P_i(t)=P_i(t)+Δ

P_i(t)·

U(x_i(t)−

u<sub>i·

ci</sub>(t))

where

$U<br><br>\left(x\right)=\{\begin{array}{cc}+1& x\ge <br><br>0\\ -1& x<<br><br>0\end{array}<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{\Delta <br><br>}<br><br><br><br>P_i<br><br>\left(t\right)=\max <br><br>\left(\mathrm{abs}<br><br>\left({\mathrm{\alpha <br><br>}}_l<br><br>\left(x_i<br><br>\left(t\right)-u_i·<br><br>c_i<br><br>\left(t\right)\right)\right),k_l\right)<br><br><br><br>\mathrm{and}$

x_i(t) is said arrival rate for said queue, c_i(t) is a capacity of said link allocated to said queue, α

_l is a constant for said queue, u_i is a constant for said queue such that u_i·

c_i(t) is said target capacity for said queue, k_l is a constant for said queue, and said update rate is when a class i packet arrives at said queue.

6. A process as in claim 1 including inducing a predetermined delay in said packets of said queue.

7. A process as in claim 6, wherein explicit congestion notification (ECN) packets have no induced delay in said queue and other packets in said queue have said predetermined delay.

8. A process as in claim 7, including having two queues for said link, one for said ECN packets and one for said other packets.

9. A process as in claim 1 including setting a limit for the congestion notification rate.

16. Network communications equipment having an active queue manager for executing the steps of claim 1.

17. Computer readable medium comprising software for executing the steps of an active queue management process as claimed in claim 1.

10. An active queue management process, including:

applying congestion notification to communications packets in a plurality of queues of a link, said congestion notification being applied at respective rates for said queues; and

adjusting said rates of notification on the basis of the respective arrival rates for said packets in said queues; and

scheduling said packets of said queues for said link;

wherein the respective capacities of said queues is estimated, and the rate of congestion notification is adjusted on the basis of the difference between said arrival rate and the estimated capacity for each of said queues; and

wherein said queues are for respective classes of packets and the estimated class capacity, S_i(t), for a queue is determined on the basis of time allocated to class i by a scheduling process for the past H packets by

$S_i<br><br>\left(t\right)=\frac{\underset{j=0}{\overset{H}{\sum <br><br>}}<br><br><br><br>B_j<br><br>\left(t\right)·<br><br>I<br><br>\left(j,i\right)}{\underset{j=0}{\overset{H}{\sum <br><br>}}<br><br><br><br>B_j}<br><br>S<br><br>\left(t\right)<br><br><br><br>\mathrm{where}<br><br><br><br>I<br><br>\left(j,i\right)=\{\begin{array}{cc}1& <br><br>\mathrm{if}<br><br><br><br>C_j=i\\ 0& \mathrm{otherwise}\end{array},$

B is a vector representing the size of the H packets that have been served most recently, C is a vector of H elements such that C_i is the class (Cj∈

{1,2,3, . . . N} of the packet represented by B_ij=1, 2, 3, . . . H.

11. Network communications equipment, including:

a switch component for switching communications packets between input ports and output ports;

packet queues for at least said output ports; and

an active queue manager for applying congestion notification to communications packets in the queues for said output ports, said congestion notification being applied at respective rates for said queues, and adjusting said rates of congestion notification on the basis of the respective arrival rates of the packets for said queues of said output ports;

wherein said rate P of congestion notification is incremented by an amount Δ

P at an update rate when said arrival rate is above a target capacity for the link associated with each of said queues, and P is decremented by Δ

P at said update rate when said arrival rate is less than said capacity.

12. Network communications equipment as in claim 11, wherein the respective capacities of said queues is estimated, and the rate of congestion notification is adjusted on the basis of the difference between the arrival rate and the estimated capacity for each of said queues.

13. Network communications equipment as in claim 11, wherein P=P+Δ

P·

U(X_est−

c_t), where X_est is the estimated arrival rate, c_t is the target capacity of the link, and

$U<br><br>\left(x\right)=\{\begin{array}{cc}+1& x\ge <br><br>0\\ -1& x<<br><br>0.\end{array}$

14. Network communications equipment as in claim 11, wherein said queues are for respective classes of packets and the estimated class capacity, S_i(t), for a queue is determined on the basis of time allocated to class i by a scheduling process for the past H packets by

$S_i$

( t ) = ∑

j = 0 H ⁢

⁢

B j ⁡

( t ) ·

I ⁡

( j , i ) ∑

j = 0 H ⁢

⁢

B j ⁢

S ⁡

( t ) ⁢

⁢

where ⁢

⁢

I ⁡

( j , i ) = { 1 ⁢

if ⁢

⁢

C j = i 0 otherwise ,

B is a vector representing the size of the H packets that have been served most recently, C is a vector of H elements such that C_j is the class (Cj∈

{1, 2, 3, . . . N}) of the packet represented by B_j,j=1, 2, 3, . . . H.

15. Network communications equipment as in claim 11, wherein said queues are allocated respectively to priority classes i of said packets and for each queue, said rate of congestion Pi(t) at a given time t is:

P_i(t)=P_i(t)+Δ

P_i(t)·

U(x_i(t)−

u<sub>i·

ci</sub>(t))

where

$U<br><br>\left(x\right)=\{\begin{array}{cc}+1& x\ge <br><br>0\\ -1& x<<br><br>0\end{array}<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{\Delta <br><br>}<br><br><br><br>P_i<br><br>\left(t\right)=\max <br><br>\left(\mathrm{abs}<br><br>\left({\mathrm{\alpha <br><br>}}_l<br><br>\left(x_i<br><br>\left(t\right)-u_i·<br><br>c_i<br><br>\left(t\right)\right)\right),k_l\right)<br><br><br><br>\mathrm{and}$

x_i,(t) is said arrival rate for said queue, c_i(t) is a capacity of said link allocated to said queue, α

_l is a constant for said queue, u_i is a constant for said queue such that u_i·

c_i(t) is said target capacity for said queue, k_l is a constant for said queue, and said update rate is when a class I packet arrives at said queue.