Random early detection

Random Early Detection (RED) is a queue management algorithm.

In traditional Tail Drop algorithm router or other network component buffers as many packets as it can, and simply drops the ones it can't buffer. If buffers are constantly full, network is congested. Tail Drop distributes buffer space unfairly among traffic flows. Tail Drop can also lead to global synchronization as all TCP connections "hold back" simultaneously. Networks becomes under-utilized.

RED addresses these issues. It monitores the average queue size and drops packets based on statistical propabilities. If buffer is almost empty, all incoming packets are accepted. As the queue grows, the propability for dropping an incoming packets grows too. When buffer is full, the propability has reached 1 and all incoming packets are dropped.

RED is considered more fair that Tail Drop. The more a host transmits, the more likely it is that it's packets are dropped. Early detection helps avoid global syncronization.

RED makes Quality of Service (QoS differentiation impossible. Weighted RED (WRED) and RED In/Out (RIO) provide early detection with some QoS considerations.