Queue based multi-level AQM with drop precedence differentiation
View Patent ↗Disclosed is a queue based multi-level Active Queue Management with drop precedence differentiation method and apparatus which uses queue size information for congestion control. The method provides for a lower complexity in parameter configuration and greater ease of configuration over a wide range of network conditions. A key advantage is a greater ability to maintain stabilized network queues, thereby minimizing the occurrences of queue overflows and underflows, and providing high system utilization.
1. A method for controlling a data flow in a data network at an element having a queue, the method comprising:
specifying a plurality of precedence grades, each of said precedence grades having a priority associated thereto;
for each precedence grade, calculating a cumulative queue size q(n) where q(n) is the sum of the queue size for a particular precedence grade under consideration plus the queue sizes of all precedence grades with a higher priority than said particular precedence grade under consideration;
for each precedence grade calculating an error signal e(n), according to the relation
e ( n )=( q ( n )− T ),
where T is an-assigned precedence grade queue capacity at time n;
for each precedence grade computing a mark/drop probability p(n) according to the relation
p ( n )=min{max [ p ( n− 1)+α· e ( n )/2 ·T, 0], θ}
where α is a control gain, and 0<θ≦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 for each precedence grade measuring a queue size q(n) at time n further comprises:
filtering the queue size q(n) according to the relation:
q ′( n )=(1−β)· q ′( n −1)+β· q ( n )
where β is a filter gain parameter such that 0<β<1,
q′(n−1) is the filtered queue size at time n−1,
q′(n) is the desired filtered queue size at time n, and
q(n) is the cumulative queue size at time n.
4. The method of claim 1 further comprising a step, preceding the step of for each precedence grade executing a packet mark/drop routine, of:
for each precedence grade testing the cumulative queue size q(n) against a queue threshold L specific to that precedence grade; and
if the cumulative queue size q(n) is below or equal to said queue threshold L then bypassing the step of executing a packet mark/drop routine for that precedence grade.
5. The method of claim 1 further comprising a step, preceding the step of for each precedence grade executing a packet mark/drop routine, of:
for each precedence grade testing the cumulative queue size q(n) against a queue threshold L common to all precedence grades; and
if the cumulative queue size q(n) is below or equal to said queue threshold L then bypassing the step of executing a packet mark/drop routine for that precedence grade.
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 having a plurality of precedence grades each of said precedence grades having a priority associated thereto, the apparatus comprising:
a cumulative queue size calculator for calculating a cumulative queue size q(n) associated with each of said plurality of precedence grades, wherein q(n) is the sum of the queue sizes for a particular precedence grade under consideration plus the queue sizes of all precedence grades with a higher priority than said particular precedence grade under consideration;
an error signal calculator for calculating a error signal e(n) for each of said plurality of precedence grades according to the relation
e ( n )=( q ( n )− T ),
where T is an assigned precedence grade capacity at time n;
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)+α· e ( n )/2 ·T, 0], θ}
where α is a control gain, and 0<θ≦1; and
a packet mark/drop module for executing a packet mark/drop routine based upon the calculated mark/drop probability p(n).
8. The apparatus of claim 7 wherein the number of precedence grades is three.
9. The apparatus of claim 7 wherein the queue size calculator for calculating queue size q(n) at time n further comprises:
a filter for filtering the queue size q(n) according to the relation:
q ′( n )=(1−β)· q ′( n− 1)+β· q ( n )
where β is a filter gain parameter such that 0<β<1,
q′(n−1) is the filtered data arrival rate at time n−1,
q′(n) is the desired filtered data arrival rate at time n, and
q(n) is the cumulative data arrival rate at time n.
10. The apparatus of claim 7 further comprising:
a test module for testing the cumulative queue size q(n) against a queue threshold L specific to that precedence grade; configured such that
if the cumulative queue size q(n) is below or equal to said queue threshold L then bypassing the packet mark/drop module for that precedence grade.
11. The apparatus of claim 7 further comprising:
a test module for testing the cumulative queue size q(n) against a threshold L common to all precedence grades; configured such that
if the cumulative queue size q(n) is below or equal to said threshold L then bypassing the packet mark/drop module for that precedence grade.
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 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 queue size q(n) where q(n) is the sum of the data arrival rates for a particular precedence grade 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, an error signal e(n), according to the relation
e ( n )=( q ( n )− T ),
where T is an assigned precedence grade capacity at time n;
instructions for computing, for each precedence grade, a mark/drop probability p(n) according to the relation
p ( n )=min{max [ p ( n− 1)+α· e ( n )/2 ·T, 0], θ}
where α is a control gain, and 0<0 ≦1; and
instructions for executing, for each precedence grade, a packet mark/drop routine based upon the calculated mark/drop probability p(n).