Rate-based multi-level active queue management with drop precedence differentiation
View Patent ↗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.
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 0 , and τ,
where k is a steady-state gain of said network,
d 0 is a time delay of said network, and
τ is a time constant of said network;
determining a z 1 in the interval
(
0
,
π
2
)
satisfying
cot
(
z
1
)
=
τ
d
0
z
1
;
and
computing a range of stable gains k i for said data network according to
-
τ
kd
0
2
z
1
z
1
2
+
d
0
2
τ
2
<
k
i
<
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 0 , and τ,
where k is a steady-state gin of said network,
d 0 is a time delay of said network, and
τ is a time constant of said network;
determining a zZ i in the interval
(
0
,
π
2
)
satisfying
cot
(
z
1
)
=
τ
d
0
z
1
;
and
computing a range of stable gains k i for said data network according to
-
τ
kd
0
2
z
1
z
1
2
+
d
0
2
τ
2
<
k
i
<
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).