Random Early Detection Review

The paper discusses another gateway-based method of congestion
avoidance. It states that it is undesirable for modern high speed
networks to tolerate large queue-sizes and that gateways should attempt
to maintain high throughput by keeping queue sizes low, even in the
presence of un-co-operative hosts. It also claims that the gateway has
a unique vantage point for detecting congestion because it can
distinguish between propagation delay and persistent queuing delay.
Moreover, it claims that it is premature to suggest per-connection
mechanisms except in cases where there is an explicit need for them.

The main goal is to implement congestion avoidance by controlling the
average queue size. The other goals are:

* Avoiding global synchronization (all users adjust their window sizes
in sync resulting in oscillation)
* Avoiding biases against bursty traffic which causes temporary
fluctuations in queue size
* Maintaining an upper bound on the maximum queue size even without the
co-operation of transport-level protocols

The algorithm is implemented either by dropping packets or setting a bit
in packet headers after the average queue size exceeds a specified
threshold, similar to DEC. The connection to be notified is chosen
randomly. After a certain maximum threshold is passed, every packet is
marked with the congestion bit or further packets are discarded.
Fairness is achieved because the probability that a connection's packet
is dropped (i.e. that is notified of congestion) is proportional to the
connection's share of packets passing through the gateway. The queue
length averaging algorithm is responsible for tolerating bursty traffic
although it strives to maintain a low queue length.

A simulation is performed using a network simulator, with hosts based on
the Tahoe TCP stack running FTP servers. The results are very
encouraging and the paper includes a discussion of the goals that RED
has achieved: simplicity, congestion avoidance, timely notification of
sources of congestion and timely adjustment of flows, no global
synchronization, and it's appropriate for networks with varied
characteristics. However, fairness can not be guaranteed for each
connection without extending the algorithm and the algorithm is targeted
to protocols where a single dropped packet or congestion bit is
sufficient to notify the transport layer of congestion. This may
require changes on the host side.
Received on Thu Sep 28 2006 - 01:59:29 EDT