Rate-based proportional-integral control scheme for active queue management
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-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 gain settings 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 gain combination of a proportional controller gain k p and an integral controller gain k i ;
measuring a data arrival rate R(n) at time n;
calculating an 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 (x≧1) is a parameter representing a nominal packet size used in the computation of k p and k i ;
computing a mark/drop probability p(n) according to the relation
p p ( n )=min{max[ k p ·e ( n ),0], p max }
p 1 ( n )=min{max[ p 1 ( n− 1)+ k i ·Δt·e ( n ),0],p max }
p ( n )=min{max[ p p ( n )+ p i ( 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
executing a packet mark/drop routine, thereby producing at least one marked packed or at least one dropped packet, based upon the calculated mark/drop probability p(n).
2. The method of claim 1 wherein the step of selecting a stable gain combination of a proportional controller gain k p and an integral controller gain k i is preceded by the step of;
pre-calculating a range within which all gain pairs k i and k p result in a stable gain combination.
3. The method of claim 2 wherein the step of pre-calculating a range within which all gain pairs k i and k p result in a stable gain combination for a data network, is determined according to the method of:
(1) 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;
(2) choosing a k p in the range
-
1
k
[
τ
d
0
α
1
sin
(
α
1
)
-
cos
(
α
1
)
]
<
k
p
<
1
k
where α 1 is a solution of
tan
(
α
)
=
-
τ
τ
+
d
0
α
in the interval (0,π)
(3) Initializing a counter j for tracking odd number roots to an initial value of 1;
(4) determining the root z j of
-
kk
p
+
cos
(
z
j
)
-
τ
d
0
z
j
sin
(
z
j
)
=
0
;
(5) computing the parameter a j associated with z j using
a
j
=
-
z
j
kd
0
[
sin
(
z
j
)
+
τ
d
0
z
j
cos
(
z
j
)
]
;
(6) testing the root z j to see if a search condition has been reached by determining if cos(z j )>0;
and if not, incrementing the counter j by 2 and returning to step (4);
(7) if so, choosing the maximum of all calculated a j 's as the lower bound of k i for the k p specified in step (2);
(8) repeating steps (2) through (7) for all desired values of k p .
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 filterrd 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, said apparatus configured according to the method of any of claims 1 - 6 .
8. An apparatus for controlling a data flow in a data network, the apparatus comprising:
a proportional-integral controller having a proportional controller gain k p setting and an integral controller gain k i setting;
a specific stable gain setting combination set for said proportional controller gain k p setting and an integral controller gain k i setting pair;
a data arrival rate measurer for measuring data arrival rate R(n) at time n;
an error signal calculator for calculating an 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(x≧1) is a parameter representing a nominal packet size used in the computation of k p and k i ;
a mark/drop probability processor for computing a mark/drop probability p(n), according to the relation
p p ( n )=min{max[ k p ·e ( n ),0 ],p max }
p i ( n )=min{max[ p i ( n− 1)+ k i ·Δt·e ( n ),0 ],p max }
p ( n )=min{max [ p p ( n )+ p i ( 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, thereby producing at least one marked packed or at least one dropped packet, based upon the calculated mark/drop probability p(n).
9. The apparatus of claim 8 wherein the stable gain combination of a proportional controller gain k p setting and an integral controller gain k i setting is chosen from a pre-calculated range within which all gain pairs k i and k p result in a stable gain combination.
10. The apparatus of claim 9 wherein the pre-calculated range within which all gain pairs k i and k p result in a stable gain combination for said data network, is determined according to the method of:
(1) 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;
(2) choosing a k p in the range
-
1
k
[
τ
d
0
α
1
sin
(
α
1
)
-
cos
(
α
1
)
]
<
k
p
<
1
k
where α 1 is a solution of
tan
(
α
)
=
-
τ
τ
+
d
0
τ
in the interval (0,π)
(3) initializing a counter j for tracking odd number roots to an initial value of
(4) determining the root z j of
-
kk
p
+
cos
(
z
j
)
-
τ
d
0
z
j
sin
(
z
j
)
=
0
;
(5) computing the parameter a j associated with z j using
a
j
=
-
z
j
kd
0
[
sin
(
z
j
)
+
τ
d
0
z
j
cos
(
z
j
)
]
;
(6) testing the root z j to see if a search condition has been reached by determining if cos(z j )>0;
and if not, incrementing the counter j by 2 and returning to step (4);
and if so, choosing the maximum of all calculated a j 's as the lower bound of k i for the k p specified in step (2);
(7) repeating steps (2) through (6) for all desired values of k p .
11. The apparatus of claim 8 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.
12. The apparatus of claim 8 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.
13. The apparatus of claim 8 wherein the packet mark/drop module further comprises:
a random number generator drop scheme module.
14. A computer program product, comprising a computer readable medium having stored thereon computer executable instructions, which, when executed by at least one processor, cause the at least one processor to control a data flow by performing the steps of:
selecting a stable gain combination of a proportional controller gain k p and an integral controller gain k i ;
measuring a data arrival rate R(n) at time n;
calculating an 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 (x≧1) is a parameter representing a nominal packet size used in the computation of k p and k i ;
computing a mark/drop probability p(n) according to the relation
p p ( n )=min{max[ k p ·e ( n ),0 ],p max }
p i ( n )=min{max[ p i ( n− 1)+ k i ·Δt·e ( n ),0 ],p max }
p ( n )=min{max[p p ( n )+ p i ( 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
executing a packet mark/drop routine, thereby producing at least one marked packed or at least one dropped packet, based upon the calculated mark/drop probability p(n).