Random early detection

Random early detection (RED), also known as random early discard or random early drop is an active queue management algorithm. It is also a congestion avoidance algorithm. In the traditional tail drop algorithm, a router or other network component buffers as many packets as it can, and simply drops the ones it cannot buffer. If buffers are constantly full, the network is congested. Tail drop distributes buffer space unfairly among traffic flows. Tail drop can also lead to TCP global synchronization as all TCP connections "hold back" simultaneously, and then step forward simultaneously. Networks become under-utilized and flooded by turns. RED addresses these issues. It monitors the average queue size and drops (or marks when used in conjunction with ECN) packets based on statistical probabilities. If the buffer is almost empty, all incoming packets are accepted. As the queue grows, the probability for dropping an incoming packet grows too. When the buffer is full, the probability has reached 1 and all incoming packets are dropped. RED is considered more fair than tail drop. The more a host transmits, the more likely it is that its packets are dropped. Early detection helps avoid global synchronization. RED makes Quality of Service (QoS) differentiation impossible. Weighted RED (WRED) and RED In/Out (RIO) provide early detection with some QoS considerations.

Other Variants

Weighted RED (WRED) - In Weighted RED, you can have different probabilities for different priorities (ip prec, dscp) and/or queues. See more in Weighted RED Adaptive / Active RED ( ARED ) - ARED algorithm infers whether to make RED more/less aggressive based on the observation of the average queue length. If the average queue length oscillates around min threshold then Early Detection is too aggressive. On the other hand if the average queue length oscillates around max threshold then Early Detection is being too conservative. The algorithm changes the probability according to how aggressive it senses it has been discarding traffic. See Srikant 2004^[1] for an in-depth account on these techniques and their analysis.

Notes and references

External links

• The RED web page
• [1], a diagram demonstrating the operation of RED.
• Guduz Project