Active queue management using proportional control and rate-based information
View Patent ↗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.
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 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 root z 1 in the interval
(
π
2
,
π
)
satisfying
tan
(
z
1
)
=
-
τ
d
0
z
1
;
and
computing a range of stable gains k p for said data network according to
-
τ
kd
0
z
1
2
+
d
0
2
τ
2
<
k
p
<
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 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 root z 1 in the interval
(
π
2
,
π
)
satisfying
tan
(
z
1
)
=
-
τ
d
0
z
1
;
and
computing a range of stable gains k p for said data network according to
-
τ
kd
0
z
1
2
+
d
0
2
τ
2
<
k
p
<
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.