7

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*avgq 

    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
ytti
  • 9,776
  • 42
  • 53
Riccardo Angius
  • 73
  • 4

1 Answers1

6

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.

ytti
  • 9,776
  • 42
  • 53
  • 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. – Riccardo Angius Jun 17 '13 at 21:08