Rate-based multi-level active queue management with drop precedence differentiation

• US 7,336,611 B1
• Filed: 08/01/2003
• Issued: 02/26/2008
• Est. Priority Date: 04/30/2003
• Status: Active Grant

• Current Assignee: Avaya Management L.P. (Avaya Incorporated)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Aweya, James, Ouellette, Michel, Montuno, Delfin, Felske, Kent
• Primary Examiner(s): Ngo, Ricky Q.
• Assistant Examiner(s): Yuen, Kan
• Application Number:
  US10/633,459
• Time in Patent Office: 1,670 Days
• Field of Search: 370/229, 370/230, 370/231
• US Class Current: 370/235
• 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/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

Disclosed is a rate-based multi-level Active Queue Management with drop precedence differentiation method and apparatus which uses traffic rate information for congestion control. Using a nonlinear fluid-flow model of Traffic Control Protocol, an integral controller in a closed-loop configuration with gain settings characterized for stable operation allows a matching of the aggregate rate of the active TCP connections to the available capacity. Further disclosed is a method for calculation of the regime of gains over which stable operation of a given network obtains. An enhancement of the basic algorithm provides the ability to drop low-precedence packets in preference to higher precedence packets. This approach allows for a rate-based AQM approach for application in a differentiated service environment.

Claims

1. A method for controlling a data flow in a data network, the method comprising:

setting a stable integral controller gain k_i for said data network;

specifying a plurality of precedence grades, each of said precedence grades having a priority associated thereto;

for each precedence grade, calculating a cumulative data arrival rate R(n) where R(n) is the sum of the data arrival rates for a particular precedence grade under consideration plus the data arrival rates of all precedence grades with a higher priority than said particular precedence grade under consideration;

for each precedence grade calculating a normalized error signal e(n), according to the relation

e(n)=(T(n)−

R(n))/x,

 

where T(n) is an assigned precedence grade capacity at time n, and x is a nominal packet size;

for each precedence grade computing a mark/drop probability p(n) according to the relation

p(n)=min {max [p(n−

1)+k_i·

Δ

t·

e(n), 0], p_max}

 

where Δ

t is the time interval between a (n−

1)^th and the n^th computation, and 0<

p_max≦

1; and

for each precedence grade executing a packet mark/drop routine based upon the calculated mark/drop probability p(n).

2. The method of claim 1 wherein the number of precedence grades is three.

3. The method of claim 1 wherein the step of setting the stable integral controller gain k_i for said data network is preceded by the step of pre-calculating a range within which all gains k_i result in a stable gain.

4. The method of claim 3 wherein the step of pre-calculating the range within which all gains k_i result in the stable gain for said data network is determined according to the method of:

obtaining for said network a value for said network a set of parameters k, d₀, and τ

,

where k is a steady-state gain of said network,

d₀ is a time delay of said network, and

τ

is a time constant of said network;

determining a z₁ in the interval

$\left(0,\frac{\mathrm{\pi <br><br>}}{2}\right)$

satisfying

$\cot <br><br>\left(z_1\right)=\frac{\mathrm{\tau <br><br>}}{d_0}<br><br>z_1;<br><br>$

and

computing a range of stable gains k_i for said data network according to

$-\frac{\mathrm{\tau <br><br>}}{{\mathrm{kd}}_0^2}<br><br>z_1<br><br>\sqrt{z_1^2+\frac{d_0^2}{{\mathrm{\tau <br><br>}}^2}}<<br><br>k_i<<br><br>0.$

5. The method of claim 1 wherein the step of for each precedence grade measuring the data arrival rate R(n) at time n further comprises:

filtering the data arrival rate R(n) according to the relation;

R′

(n)=(1−

β

)·

R′

(n−

1)+β

·

R(n)

where β

is a filter gain parameter such that 0<

β

<

1,

R′

(n−

1) is the filtered data arrival rate at time n−

1,

R′

(n) is the desired filtered data arrival rate at time n, and

R(n) is the cumulative data arrival rate at time n.

6. The method of claim 1 further comprising a step, preceding the step of for each precedence grade executing the packet mark/drop routine, of:

for each precedence grade testing the cumulative data arrival rate R(n) against a rate threshold T_L specific to that precedence grade; and

if the cumulative data arrival rate R(n) is below or equal to said rate threshold T_L then bypassing the step of executing a packet mark/drop routine for that precedence grade.

7. The method of claim 1 further comprising a step, preceding the step of for each precedence grade executing the packet mark/drop routine, of:

for each precedence grade testing the cumulative data arrival rate R(n) against a rate threshold T_L common to all precedence grades; and

if the cumulative data arrival rate R(n) is below or equal to said rate threshold T_L then bypassing the step of executing a packet mark/drop routine for that precedence grade.

8. The method of claim 1 wherein the step of executing the packet mark/drop routine further comprises marking/dropping packets according to a random number generator mark/drop scheme.

9. An apparatus for controlling a data flow in a data network, the apparatus comprising:

an integral controller having an integral controller gain k_i setting for which the said network is stable;

a cumulative data rate calculator for calculating a cumulative data arrival rate R(n) associated with each of said plurality of precedence grades, wherein R(n) is the sum of the data arrival rates for a particular precedence grade under consideration plus the data arrival rates of all precedence grades with a higher priority than said particular precedence grade under consideration;

an error signal calculator for calculating a normalized error signal e(n) for each of said plurality of precedence grades according to the relation

e(n)=(T(n)−

R(n))/x,

 

where T(n) is an assigned precedence grade capacity at time n, and x is a nominal packet size;

a mark/drop probability processor for computing a mark/drop probability p(n) for each of said plurality of precedence grades according to the relation

p(n)=min {max [p(n−

1)+k_i·

Δ

t·

e(n), 0], p_max}

 

where Δ

t is the time interval between a (n−

1)^th and the n^th computation, and 0<

p_max≦

1; and

a packet mark/drop module for executing a packet mark/drop routine based upon the calculated mark/drop probability p(n).

10. The apparatus of claim 9 wherein the number of precedence grades is three.

11. The apparatus of claim 9 wherein the integral controller gain k_i setting for which the said network is stable is chosen from a pre-calculated range within which all gains k_i are gains for which said network is stable.

12. The apparatus of claim 11 wherein the pre-calculated range within which all gains k_i are gains for which said network is stable is determined according to the method of:

obtaining for said network a value for said network of a set of parameters k, d₀, and τ

,

where k is a steady-state gin of said network,

d₀ is a time delay of said network, and

τ

is a time constant of said network;

determining a zZ_i in the interval

$\left(0,\frac{\mathrm{\pi <br><br>}}{2}\right)$

satisfying

$\cot <br><br>\left(z_1\right)=\frac{\mathrm{\tau <br><br>}}{d_0}<br><br>z_1;<br><br>$

and

computing a range of stable gains k_i for said data network according to

$-\frac{\mathrm{\tau <br><br>}}{{\mathrm{kd}}_0^2}<br><br>z_1<br><br>\sqrt{z_1^2+\frac{d_0^2}{{\mathrm{\tau <br><br>}}^2}}<<br><br>k_i<<br><br>0.$

13. The apparatus of claim 9 wherein the cumulative data rate calculator for measuring data arrival rate R(n) at time n further comprises:

a filter for filtering the data arrival rate R(n) according to the relation;

R′

(n)=(1−

β

)·

R′

(n−

1)+β

·

R(n)

where β

is a filter gain parameter such that 0<

β

<

1,

R′

(n−

1) is the filtered data arrival rate at time n−

1,

R′

(n) is the desired filtered data arrival rate at time n, and

R(n) is the cumulative data arrival rate at time n.

14. The apparatus of claim 9 further comprising:

a test module for testing the cumulative data arrival rate R(n) against a rate threshold T_L specific to that precedence grade;

configured such that

if the cumulative data arrival rate R(n) is below or equal to said rate threshold T_L then bypassing the packet mark/drop module for that precedence grade.

15. The apparatus of claim 9 further comprising:

a test module for testing the cumulative data arrival rate R(n) against a rate threshold T_L common to all precedence grades;

configured such that

if the cumulative data arrival rate R(n) is below or equal to said rate threshold T_L then bypassing the packet mark/drop module for that precedence grade.

16. The apparatus of claim 9 wherein the packet mark/drop module further comprises a random number generator drop scheme module.

17. A computer program product comprising a computer readable medium having stored thereon computer executable instructions for controlling a data flow in a data network, the computer executable instructions comprising:

instructions for setting a stable gain of a integral controller gain k_i for said data network;

instructions for specifying a plurality of precedence grades, each of said precedence grades having a priority associated thereto;

instructions for calculating, for each precedence grade, a cumulative data arrival rate R(n) where R(n) is the sum of the data arrival rates for a particular precedence garde under consideration and the data arrival rates of all precedence grades with a higher priority than said particular precedence grade under consideration;

instructions for calculating, for each precedence grade, a normalized error signal e(n), according to the relation

e(n)=(T(n)−

R(n))/x,

where T(n) is an assigned precedence grade capacity at time n, and x is a nominal packet size;

instructions for computing, for each precedence grade, a mark/drop probability p(n) according to the relation

p(n)=min {max [p(n−

1)+k_i·

Δ

t·

e(n), 0], p_max}

 

where Δ

t is the time interval between a (n−

1)^th and the n^th computation, and 0<

p_max≦

1; and

instructions for executing, for each precedence grade, a packet mark/drop routine based upon the calculated mark/drop probability p(n).