RED Gateways for Congestion Avoidance
Dax Hawkins (daxh@microsoft.com)
Tue, 27 Apr 1999 23:47:33 -0700
Random Early Detection gateways are interesting because they control
congestion by attempting to avoid it rather than by dealing with it after it
happens. The goal is to keep queue sizes low to reduce the average delay in
the network. This paper starts off with a survey of other congestion
control techniques and but don't really directly come out and say that they
are inferior to RED algorithms. One of the more interesting observations to
me was that the congestion control mechanism should not cause
synchronization in the network. That is, connections should not all be
signaled at the same time to reduce their windows as this will cause cycles
of low network usage followed by high network useage. Goals of the
congestion avoidance scheme are clearly stated: control the average queue
size, avoid global synchronization and a bias towards bursty traffic, and
keep an upper bound on the average queue size in the face of ill-behaved
sources (those that don't respond to congestion control hints). The random
portion of the RED gateways is the key to avoiding global synchronization.
The probability that a certain connection's packet will be dropped is
proportional to the amount of bandwidth utilized by that connection. This
probability calculation can be done without any state being held by the
gateway. I find the RED algorithm appealing for its simplicity and its
immediate usefulness. One could reasonably plug in this algorithm at the
gateway and immediately start working in the current internet
infrastructure. In general the gateway keeps a min and max threshold for
the average queue size. Below the min, the gateway doesn't drop (or mark)
the packet. Above the max, the gateway drops every packet. Between min and
max, the gateway calculates a probability and with that probability drops an
arriving packet. Note that by dropping packets when the average queue size
is greater than max, RED gateways can still manage their queue lengths in
spite of misbehaving sources. Even though the algorithm itself is
straightforward, the calculation of the average queue length and threshold
values must be chosen carefully. In general, max should be twice the min
value and the average queue lenght calculation should be resistant to
transient effects caused by bursty traffic. The authors mention that RED
gateways do work best in a TCP environemnt whose connections have large
windows. My only complaint about this paper was that the evolution of
Early Random drop algorithms and current RED gateways was not clearly
explained.