Review - RED

Review of the paper "Random Early Detection Gateways for Congestion Avoidance"
by Ivan Hernandez

This paper presents a congestion avoidance mechanism at the gateway,
Random Early Detection (RED). The RED gateways are designed for a
network where a single dropped packet is sufficient to signal the
presence of congestion to the transport layer protocol, in our case
TCP. The RED gateway monitors the average queue size for each output
queue, and, using randomization, choose connections to notify of that
congestion. The probability that a connection is notified of
congestion is proportional to that connection's share of the
throughput through the gateway.

The RED algorithm is simple. For each packet arrival, the RED gateway
calculates the average queue size (AQS) using a low-pass filter (such
that transient congestion will not result in a significant increase in
the average queue size), then the AQS is compared with the minimum and
maximum threshold: if AQS is less than the minimum, the gateway does
not mark/drop the packet; if the AQS is in [minimum, maximum), then
the packet is marked/dropped with probability p (p is adjusted
dynamically and is a function of AQS); if AQS is greater than the
maximum, every packet is marked/dropped.

The results of the simulations show RED as a good congestion avoidance
algorithm. Additionally, RED does not overreact in the presence of
bursty traffic and transient congestion, avoids global synchronization
--because it marks packets at as low a rate as possible--, and shows a
good link utilization. On the other hand, it does not ensure
fairness. The paper also show how RED could be used to identify
misbehaving users, and with the use of higher policy layers to punish
them.

This paper is interesting, I liked its minimum/maximum approach in
order to early detect congestion problems. On the other hand, I felt
that the layout of the paper, just after section 5, is twisted. And
the format in which the authors presented their results, in some
cases, is unclear.
Received on Wed Sep 27 2006 - 23:43:18 EDT