Random Early Detection

Early drop probability

Prerequisites

graph TD
  TCP[TCP congestion control] --> RED[Random Early Detection]
  Queues[Queueing theory basics] --> RED
  Net[Routers and buffers] --> RED

When to use

Core router queues where many TCP flows share one bottleneck and you want early congestion signals without waiting for buffer overflow.
Avoiding global synchronization — random drops spread TCP backoff across flows instead of everyone halving at once.
Weighted RED (WRED) when traffic classes differ (VoIP vs bulk) and you need different drop curves per class.

When not to use

Shallow buffers or single-flow links — simple tail-drop or explicit ECN may suffice.
Non-TCP traffic that does not backoff on random loss — drops may not signal congestion usefully.
Ultra-low-latency switches with minimal buffering — RED’s EWMA may react too slowly.

Lab

On the interactive RED lab, drag min_th and max_th to see the RED Pb ramp vs the tail-drop cliff at 100% fill, move the avg fill marker, and run Calm link, RED gentle, or Tail-drop cliff presets. Toggle RED vs tail-drop on the packet timeline, predict whether RED avoids a full buffer under burst traffic, then reveal side-by-side drop counts and max queue depth.

Simple Fundamental Explanation

Imagine a popular highway exit ramp. It can only hold 50 cars. If 100 cars try to exit at once, the ramp fills completely. The 51st car hits a dead stop on the main highway, causing a massive, catastrophic pileup behind it. This is how basic internet routers work (“Tail Drop”): they accept data packets until their memory buffer is 100% full, and then they completely drop every subsequent packet, causing the sender’s connection to severe lag or timeout.

Now, imagine a traffic cop on the ramp.

When the ramp is mostly empty, the cop does nothing.
When the ramp is 50% full, the cop starts randomly forcing a few cars to keep driving on the main highway instead of exiting.
When the ramp is 80% full, the cop forces many random cars to keep driving.

By randomly dropping a few packets before the buffer is completely full, the sender notices the dropped packets and naturally slows down their transmission rate. The buffer never hits 100%, and the catastrophic pileup is avoided.

This is Random Early Detection (RED). It probabilistically drops network packets to implicitly signal to senders that congestion is occurring.

Deep Dive: How It Works Under the Hood

Internet traffic relies heavily on the TCP protocol. TCP has a built-in congestion control mechanism: if it detects that a packet was lost, it assumes the network is congested and halves its sending speed.

Standard routers use “Tail Drop.” They fill their queue, and then drop everything else. This causes two massive problems:

Global Synchronization: Because the router drops packets from everyone simultaneously, all TCP senders halve their speed at the exact same moment. The network goes from 100% congested to 10% utilized instantly, then builds back up and crashes again in a constant, inefficient sawtooth wave.
Lock-Out: A single greedy user streaming 4K video can fill the entire queue, meaning a tiny DNS request from a different user is dropped completely.

The RED Algorithm

RED continuously calculates the average queue size. It establishes a Minimum Threshold ( $mi n_{t h}$ ) and a Maximum Threshold ( $ma x_{t h}$ ).

If Average Queue < $mi n_{t h}$ : Accept all packets.
If Average Queue > $ma x_{t h}$ : Drop all packets (Buffer is functionally full).
If $mi n_{t h} < Average Queue < ma x_{t h}$ : Calculate a probability $P$ . Drop the arriving packet with probability $P$ .

Because RED drops packets randomly, the probability that a specific user’s packet is dropped is roughly proportional to how much bandwidth they are using. The 4K video streamer loses more packets than the DNS user, forcing the greedy streamer to slow down. Furthermore, because drops are random, different TCP streams slow down at different times, completely eliminating Global Synchronization.

Visual Diagram

Queue Size:
[ 0% ] ------------ [ min_th ] ------------ [ max_th ] ------------ [ 100% ]
      No Drops                Probabilistic Drops         100% Drops

Probability of Drop (P):
100% |                                          /-------------------
     |                                         /
     |                                        /
     |                                       /
     |                                      /
 0%  |-------------------------------------/
     0              min_th                max_th               100

Practical Example: Cisco Routers and the Core Internet

If you look at the configuration of enterprise core routers (like Cisco or Juniper hardware that route traffic between cities), you will rarely find simple “Tail Drop” enabled on major interfaces.

Instead, they use WRED (Weighted Random Early Detection). WRED is a variant of RED that applies different probabilities based on the priority of the traffic. For example, Voice-over-IP (VoIP) packets are highly sensitive to delay. Bulk file downloads are not. Using WRED, if the router queue reaches 60%, the router might start randomly dropping the file download packets with a 10% probability, but keep the probability of dropping VoIP packets at 0%.

This probabilistically ensures the file download slows down, clearing the queue and ensuring the phone call remains crystal clear, without requiring the router to maintain complex state tables for every single user.

The Mathematics: Equations and In-Depth Analysis

1. Calculating the Average Queue Size

If RED reacted to the instantaneous queue size, a momentary micro-burst of traffic would cause unnecessary packet drops. RED uses an Exponential Weighted Moving Average (EWMA) to smooth the measurement.

Let $q$ be the instantaneous queue size. Let $w_{q}$ be the weight parameter (e.g., 0.002). The average queue size $avg$ is calculated on every packet arrival:

avg \leftarrow (1 - w_{q}) \cdot avg + w_{q} \cdot q

This low-pass filter ensures RED only reacts to sustained, long-term congestion.

2. Calculating the Drop Probability

If $avg$ falls between $mi n_{t h}$ and $ma x_{t h}$ , the base probability $P_{b}$ grows linearly from 0 to a maximum probability $P_{ma x}$ (often 0.1, or 10%).

P_{b} = P_{ma x} \cdot \frac{avg - mi n _{t h}}{ma x _{t h} - mi n _{t h}}

3. The Count Variable Optimization

If we just drop packets with probability $P_{b}$ , we might accidentally drop two packets in a row, or go a long time without dropping any. To space out the drops evenly, RED keeps a variable count, which tracks how many packets have arrived since the last drop.

The actual drop probability $P_{a}$ applied to the packet is:

P_{a} = \frac{P _{b}}{1 - count \cdot P _{b}}

As count increases, the denominator gets smaller, causing $P_{a}$ to rapidly increase toward 1. This guarantees that a packet will be dropped soon, ensuring the congestion signal is sent promptly and uniformly, maximizing the efficiency of the TCP backoff algorithm.

Lab

Random Early Detection raises drop probability linearly between min and max thresholds on the EWMA average queue — before the buffer hits 100%. Tail-drop accepts until the queue is full, then drops everything (global synchronization). The chart compares both policies; the timeline is a deterministic packet run with the README’s Pb and Pa formulas.

Min threshold (min_th)20% fill

Max threshold (max_th)80% fill

P_max (base drop cap)10%

EWMA weight (w_q)0.008

Avg queue fill (chart marker)55%

Arrival burst (sim)3.5

RED Pb

Tail-drop

Marker = slider avg fill

Blue ramp: probabilistic drops between min_th and max_th. Red step: drops only at 100% fill. Marker shows Pb = 0.058 at 55% avg fill.

Bar height ≈ instant queue after each packet (last 80). Green = accepted, red = dropped.

With min_th 20%, max_th 80%, and burst arrival 3.5 over 120 packets, will RED keep the buffer below full while tail-drop hits 100% capacity?

RED at 3.5 burst: instant fill 74%, EWMA avg 84%, zone prob. Reveal above for side-by-side drop counts.