Summary: Random Early Detection Gateways for Congestion Avoidance

This paper points out that network congestion can most accurately be
understood at the gateway, since it can distinguish high propagation delay
from high delay brought on by increasing queue lengths. Therefore, the
authors suggest that congestion detection should be done at the gateway.

The proposed system monitors the lengths of queues, and sends congestion
feedback to transmitters if the long-term queue length average becomes too
high. This is preferable to simply using short queue lengths, since it
allows the network to more efficiently handle bursty flows. Feedback-based
congestion control is also preferable to the conventional solution of
allowing queues to fill to capacity and then rejecting new traffic. This is
because rejecting packets in this way tends to cause many flows to detect the
congestion and back off (termed "global synchronization" in the paper). As a
result, the gateway's outbound link rapidly goes from being over-utilized to
under-utilized.

Congestion feedback is sent to a random selection of flows. The described
algorithm chooses incoming packets at random to be "marked" for congestion
control, with the fraction of packets marked being determined by the average
queue length. Randomly selecting incoming packets implies that the
probability of a given flow receiving a congestion notification is
proportional to the number of packets it is submitting to the gateway. The
authors claim that this is roughly the same saying that flows are notified
with a probability in proportion to the bandwidth they consume, although this
would seem to assume that all packets are of the same size (a variation on
the algorithm presented later in the paper measures queue lengths in bytes).
Flows with marked packets receive some sort of congestion notification
(dependant on the network protocol in use). For TCP/IP, this would be done
by dropping the marked packet.

If the average queue lengths exceed a maximum, the described algorithm enters
a mode where all packets are simply dropped on arrival. This allows the
gateway to make strong performance guarantees, even in the face of malicious
clients.

The paper seems to present a pretty useful idea. Furthermore, the algorithm
is pretty straightforward and would likely be easy to implement. The authors
also explicitly point out that this system provides benefits even if it is
not simultaneously deployed on many other gateways.
Received on Thu Sep 28 2006 - 01:31:24 EDT