The paper defining RED queues. The property of RED is:

- Behavior determined by the average queue size
- Dropping packet is an option, but not the only action upon congestion
- Packet-marking probability is a function of the average queue size

The algorithm of RED is as follows.

Average queue length calculation is done every time upon packet arrival:

```
if the queue is non-empty:
avg = (1-Wq)*avg + Wq*Q
else the queue is empty:
m = f(time - qTime)
avg = (1-Wq)^m * avg
```

where `Q`

is the current queue size, `qTime`

is the time that the queue start to be idle, and `f`

is a linear function. So when the queue becomes empty, it set

```
qTime = time
```

The marking decision is also done per packet arrival:

```
if min_th ≤ avg < max_th:
count++
p_b = max_p * (avg - min_th)/(max_th - min_th)
p_a = p_b * (1 - count*p_b)
do in probability p_a:
mark the packet
count = 0
else if avg ≥ max_th:
mark the packet
count = 0
else avg < min_th:
count = -1
```

The count above counts the number of packets since last marked packet. So that the marking probability increases with time when it stays `min_th`

≤ `avg`

< `max_th`

. The above code assumes the queue is packet-based. If it is byte-based, we need to take in the packet size into account when computing `p_b`

, which the probability computation above becomes:

```
p_b = max_p * (avg - min_th)/(max_th - min_th)
p_b = p_b * (packet size)/(max packet size)
p_a = p_b * (1 - count*p_b)
```

The numbers used in the paper are as follows:

```
min_th = 3 to 50 packets
max_th = 3 * min_th
Wq = 0.002
max_p = 1/50
```

## Bibliographic data

```
@article{
title = "Random Early Detection Gateways for Congestion Avoidance",
author = "Sally Floyd and Van Jacobson",
journal = "IEEE/ACM Transactions on Networking",
volume = "1",
number = "4",
pages = "397--413",
month = "Aug",
year = "1993",
}
```