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
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.

  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.