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