Random Early Detection Gateways for Congestion Avoidance

Paper Review: Random Early Detection Gateways for Congestion Avoidance

With congestion becoming a major problem on the Internet, gateways are
being designed with large queue sizes leading to large delay values.
The paper introduces a mechanism to reduce average queue sizes in
gateways. It argues that the most reliable method of detecting
congestion occurs in the gateway rather than end systems.

Their proposed scheme requires gateways to monitor their queue sizes.
Once the queue sizes pass a certain threshold value, the scheme
randomly selects connections to notify of the state of congestion.
The congestion is indicated by either marking packets or simply
dropping them.

More specifically, the algorithm requires maintaining a minimum and
maximum threshold. When the queue size is less than the minimum, no
packets are marked. When the queue size is larger than the maximum,
all packets are marked. Finally, when the queue size is between the
two thresholds, each packet is marked with a probability which is a
function of the average queue size. Furthermore, queue sizes are
measured in bytes, rather than packets, and the probability that a
packet is marked is proportional to its size (larger packets more
likely to be marked).

In simulations, the RED gateways properly managed queue sizes while
providing high throughput and low delays. RED gateways were shown to
allow TCP connections to open their windows and did not exhibit the
problem of global synchronization.

One advantage of their scheme is that not all gateways must
immediately implement the algorithm. RED gateways could be gradually
introduced to alleviate congestion conditions. By randomly selecting
connections to notify of congestion, RED does not show bias against
bursty traffic. The randomization also removes the problem of global
synchronization where all end systems reduce their window sizes at the
same time. The scheme is highly tuneable through the control of
several parameters. RED gateways attempt to control ill-behaving
sources by monitoring the number of marked packets belonging to a
particular connection and can then be tuned to provide lower priority
to these connections.

Overall the paper is well-written. Some more analytical work could
improve the thoroughness of the study. Specifically, further work is
required in calculating the average queue sizes to optimize
performance. Also, the use of simulations was necessary as the
gateways were never implemented. They did, however, show the
simplicity of the algorithm and were convincing in their argument that
the RED gateways would be easy to deploy.

-- Nadeem Abji
Received on Thu Sep 28 2006 - 04:33:29 EDT