4.4.1 The Convergence Problem: Global Synchronization

When a standard FIFO buffer overflows, all TCP senders time out and re-enter Slow Start at the same time. This leads to severe oscillations in link utilization.

4.4.2 The RED Algorithmic Solution

RED (Random Early Detection) drops packets randomly before the buffer is full.

Step 1: Average Queue Weighting ($avg$)

Using EWMA (Exponential Weighted Moving Average): $$avg = (1 - w_q) imes avg_{old} + w_q imes q$$

• $w_q = 0.002$ is typical.

Step 2: Probability Calculation ($P_b$)

• If $avg < min_{th}$: $P = 0$.
• If $avg > max_{th}$: $P = 1$ (Forced drop).
• If $min < avg < max$:

$$P_b = max_p imes rac{avg - min_{th}}{max_{th} - min_{th}}$$

Step 3: Spread Probability ($P_a$)

To avoid dropping packets in bursts: $$P_a = rac{P_b}{1 - count imes P_b}$$ $count$ tracks packets accepted since the last drop.

4.4.3 Advantages of RED:

1. Bursty Traffic Tolerance: Short bursts pass through due to the EWMA filter.
2. Fairness: High-bandwidth flows are "statistically" more likely to have a packet dropped than low-bandwidth flows.