Active queue management using proportional control and rate-based information

• US 7,277,391 B1
• Filed: 04/30/2003
• Issued: 10/02/2007
• 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): Hailu, Kibrom T
• Application Number:
  US10/426,763
• Time in Patent Office: 1,616 Days
• Field of Search: 370/229, 370/230, 370/235, 370/230.1, 370/235.1, 370/252, 370/253
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

Disclosed is an Active Queue Management method and apparatus which uses traffic rate information for congestion control. Using a nonlinear fluid-flow model of Traffic Control Protocol, a proportional 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 for which stable operation of a given network obtains. This approach allows for capacity matching while maintaining minimal queue size and high link utilization.

Claims

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

selecting a stable proportional controller gain k_p for said data network;

measuring a data arrival rate R(n) at time n;

calculating a normalized error signal e(n), according to the relation

e(n)=(T(n)−

R(n))/x,

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

computing a mark/drop probability p(n) according to the relation

p(n)=min { max [k_p·

e(n),0],p_max}

where p_max is a predefined maximum probability and 0<

p_max≦

1; and

executing a packet mark/drop routine based upon the calculated mark/drop probability p(n), thereby producing at least one marked packet or at least one dropped packet.

2. The method of claim 1 wherein the step of selecting a stable proportional controller gain k_p for said data network is preceded by the step of:

pre-calculating a range within which all gains k_p result in a stable gain.

3. The method of claim 2 wherein the step of pre-calculating a range within which all gains k_p result in a 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 root z₁ in the interval

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

satisfying

$\tan <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_p for said data network according to

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

4. The method of claim 1 wherein the step of measuring a 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, and

R′

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

5. The method of claim 1 further comprising a step, preceding the step of executing a packet mark/drop routine, of:

testing the data arrival rate R(n) against a rate threshold T_L; and

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

6. The method of claim 1 wherein the step of executing a packet mark/drop routine further comprises:

marking/dropping packets according to a random number generator mark/drop scheme.

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

a proportional controller having a proportional controller gain k_p setting for which the said network is stable;

a data arrival rate measurer for measuring data arrival rate R(n) at time n;

an error signal calculator for calculating a normalized error signal e(n), according to the relation

e(n)=(T(n)−

R(n))/x,

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

a mark/drop probability processor for computing a mark/drop probability p(n), according to the relation

p(n)=min { max [k_p·

e(n),0],p_max}

where p_max is a predefined maximum probability 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), thereby producing at least one marked packet or at least one dropped packet.

8. The apparatus of claim 7 wherein the proportional controller gain k_p setting for which the said network is stable is chosen from a pre-calculated range within which all gains k_p are gains for which said network is stable.

9. The apparatus of claim 8 wherein the pre-calculated range within which all gains k_p 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 gain of said network,

d₀ is a time delay of said network, and

τ

is a time constant of said network;

determining a root z₁ in the interval

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

satisfying

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

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

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

10. The apparatus of claim 7 wherein the data arrival rate measurer 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, and

R′

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

11. The apparatus of claim 7 further comprising:

a test module for testing the data arrival rate R(n) against a rate threshold T_L; and

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

12. The apparatus of claim 7 wherein the packet mark/drop module further comprises:

a random number generator drop scheme module.

13. 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 selecting a stable gain of a proportional controller gain k_p for said data network;

instructions for measuring a data arrival rate R(n) at time n;

instructions for calculating normalized error signal e(n), according to the relation

e(n)=(T(n)−

R(n))/x,

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

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

p(n)=min { max [k_p·

e(n),0],p_max}

where p_max is a predefined maximum probability and 0<

p_max≦

1; and

instructions for a packet mark/drop routine based upon the calculated mark/drop probability p(n), thereby producing at least one marked packet or at least one dropped packet.