Review: Random Early Detection

Paper: Random Early detection Gateways for Congestion Avoidance

Name: Robert Danek.
Course: CS2209, Fall '06.

    This paper describes a mechanism for congestion avoidance in
gateways. The mechanism, called Random Early Detection (RED), works as
follows: Two threshold values are maintained, a minimum threshold and a
maximum threshold. Congestion is detected in the gateway by measuring
the average queue length, and notification of congestion to sources is
done by either dropping packets or marking them. When the average queue
size in the gateway is below the minimum threshold, all packets pass
through the gateway unchanged. When the average queue size is greater
than the maximum threshold, all arriving packets are marked. Finally, if
the average queue size is between the minimum and maximum threshold,
packets are randomly marked based on a probability function.

    This mechanism has some desirable properties, including not being
biased against bursty traffic, and being able to avoid global
synchronization. A system is said to be biased against bursty traffic if
bursty traffic (such as the traffic on the Internet) is likely to cause
gateway queue's to overflow. Global synchronization is a problem that
occurs when all hosts in a network are notified of congestion at the
same time, which causes all hosts to simultaneously reduce their window
size and output to the network.

    The key way that RED can achieve the above properties is through its
randomization mechanism. When packets are marked randomly, the
probability that a particular packet is marked is proportional to the
bandwidth that the connection it is on is consuming.

    This was a good paper. It examined the behaviour of the algorithm
through a number of simulations. In particular, it ran simulations to
verify its lack of bias against bursty traffic, and the lack of global
synchronization.
Received on Thu Sep 28 2006 - 01:52:34 EDT