Approximation of the weighted random early detection buffer admittance algorithm
View Patent ↗An apparatus for storing a packet including a buffer in which packets are stored. The apparatus includes a mechanism for determining an average buffer fill of the buffer, where the average buffer fill is an average fill state of the buffer. The determining mechanism is connected to the buffer. The apparatus includes a mechanism for calculating a drop probability associated with the packet which identify is the probability the packet will be dropped from a the buffer. The apparatus includes a mechanism for generating a random number. The apparatus includes a mechanism for discarding the packet from the elements if the drop probability is greater in than the random number. A method for access control.
1. A method for access control comprising the steps of:
receiving a packet at an element having a buffer;
determining if an average buffer fill of the buffer in which the packet is to be stored is greater than a minimum threshold and less than a maximum threshold, where the average buffer fill is an average fill state of the buffer;
calculating a drop probability associated with the packet which identifies a probability the packet will be dropped from the element in regard to whether the average buffer fill is greater than the minimum threshold and less than the maximum threshold;
comparing the drop probability to a random number; and
discarding the packet from the element if the drop probability is greater than the random number, wherein the calculating step includes the step of retrieving the drop probability from a probability memory having precomputed drop probabilities.
2. A method as described in claim 1 wherein the calculating step includes before the retrieving step the step of identifying an address in the probability memory of the drop probability.
3. A method as described in claim 2 wherein the identifying the address step includes the step of mapping values of variables into at least two regions.
4. A method as described in claim 3 wherein the identifying the address step includes after the mapping step the step of determining the address from the variables.
5. A method as described in claim 4 wherein the mapping step includes the step of mapping of variables into at least two regions by comparing them with a programmable thresholds.
6. A method as described in claim 5 wherein the comparing step includes the step of comparing the drop probability to the random number generated by a linear feedback shift register which approximates a random number generator.
7. A method as described in claim 6 wherein the variables includes count since last drop, packet size, average buffer fill, color and queue, respectively.
8. A method as described in claim 7 wherein the regions include count_region, pktsize_region, abf_region, color and queue derived from the variables count since last drop, packet size, average buffer fill, color and queue, respectively.
9. A method as described in claim 8 wherein the discarding step includes the step of discarding a packet every 2 clock cycles.
10. A method as described in claim 9 wherein the element includes a reassembler for sending packets to a network.
11. A method as described in claim 9 wherein the probability is defined as
P
a
(
abf
marking
)
=
p
b
(
abf
marking
)
1
-
count
*
p
b
(
abf
marking
)
where
p
b
(
abf
marking
)
=
(
max_
p
marking
·
(
abf
marking
-
minth
marking
)
maxth
marking
-
minth
marking
)
(
pktsize
maxPacket
)
·
queue_weight
queue
and max_p marking , maxth marking , minth marking , maxPacket, and queue_weight queue are constants.
12. A method as described in claim 11 wherein the
abf
marking
,
new
=
(
k
1
·
abf
marking
,
old
+
k
2
·
iqf
marking
)
X
where k 1 and k 2 are integers whose sum=X.
13. A method as described in claim 12 wherein X=64.
14. An apparatus for storing a packet comprising:
a buffer in which packets are stored;
a mechanism for determining an average buffer fill of the buffer, where the average buffer fill is an average fill state of the buffer, the determining mechanism is connected to the buffer;
a mechanism for calculating a drop probability associated with the packet which identifies the probability the packet will be dropped from the buffer in regard to whether the average buffer fill is greater than the minimum threshold and less than the maximum threshold; and
a mechanism for generating a random number; and
a mechanism for discarding the packet from the elements if the drop probability is greater in than the random number, wherein the calculating mechanism includes a probability mechanism having predetermined drop probabilities from which the drop probability is obtained.
15. An apparatus as described in claim 14 wherein the probability mechanism has a probability memory having addresses and the calculating mechanism includes a mechanism for identifying an address in the probability memory having the drop probability.
16. An apparatus as described in claim 15 wherein the calculating mechanism includes a mechanism for mapping values of variables into regions.
17. An apparatus as described in claim 16 wherein the random number generating mechanism includes a linear feedback shift register which approximates a random number generator.
18. An apparatus as described in claim 17 wherein the probability is defined as
P
a
(
abf
marking
)
=
p
b
(
abf
marking
)
1
-
count
*
p
b
(
abf
marking
)
where
p
b
(
abf
marking
)
=
(
max_
p
marking
·
(
abf
marking
-
minth
marking
)
maxth
marking
-
minth
marking
)
(
pktsize
maxPacket
)
·
queue_weight
queue
and max_p marking , maxth marking , minth marking , maxPacket, and queue_weight queue are constants.
19. An apparatus as described in claim 18 wherein the
abf
marking
,
new
=
(
k
1
·
abf
marking
,
old
+
k
2
·
iqf
marking
)
64
where k 1 and k 2 are integers whose sum=64.
20. An apparatus as described in claim 18 wherein the determining mechanism includes a mechanism for determining the instantaneous queue fill.