# How is probabilistic marking performed with Random Early Detection?

I am currently studying for my Computer Networks exam.

I cannot wrap my head around the following.

When the current Average Queue Length is in between a min_threshold and a max_threshold, the Random Early Detection algorithm marks every packet it receives with a probability (for dropping or Explicit Congestion Notification) .

I understand every packet is marked when the AQL is greater than max_threshold (i.e. p is 1), but I cannot undestand in the former case how is the calculated probability is used to decide whether a packet will be marked or not.

For instance, if p_b is calculated to be 0.7 for a packet, does it mean that the packet will not be marked at all?

For reference, here is the RED algorithm in pseudocode, as first proposed at http://www.cs.princeton.edu/courses/archive/fall06/cos561/papers/red.pdf:

``````Initialization:
avg ← 0
count ← −1

for each packet arrival calculate the new average queue size avg:
if the queue is nonempty
avg ← (1 − w_q)*avg + w_q*q
else
m← f(time−q time)
avg←(1−w )^m*avg￼q

if min_th ≤ avg < max_th
increment count

calculate probability pa:
pb ← maxp(avg − minth)/(maxth − minth) pa ←pb/(1−count·pb)
with probability pa:
mark the arriving packet count ← 0

else if maxth ≤ avg
mark the arriving packet count ← 0
else count ← −1

when queue becomes empty
q_time ← time
``````

Think of RED as an arbitrary curve in a coordinate system.

Y is probability of drop X is how congested you are (for example how full egress buffers are)

Operator could add 5 points there

1. X=40%, Y=0%
2. X=50%, Y=5%
3. X=60%, Y=20%
4. X=70%, Y=40%
5. X=90%, Y=100%

Then you'd draw lines to the points to form the curve, to get exact Y (drop probability) for every X (demand/congestion).

The exact implementation how to produce random number to the percentage is not very interesting, it could be that you do random number from 1-100 and if Y==5, then for random numbers 1-5 you drop, for 6-100 you don't drop.

WRED is exactly the same, there is just different curves for different QoS classes.

This may not be as academic answer as you'd hope, and I can't recommend very academic book for QoS either. QoS is very very implementation specific. TM (Traffic Manager) are single most complex pieces of modern router.

• It needed not be academic at all, I got all the details in the professor's book but, as much as uninteresting, I was missing that piece to visualise comprehensively how the whole thing works. Thank you very much. Jun 17 '13 at 21:08