Random Early Detection Gateways for Congestion Avoidance

Motivation: This paper presents Random Early Detection gateways which
can mark and notify congestion in the networks using a probability
function approximately proportional to connection's share of bandwidth.
RED gateway has no bias against bursty traffic and avoids global
synchronization.
 Key Points:

1) RED tries to address the congestion avoidance problem as well as the
synchronization and bursty bias associated with it without introducing
per-flow state into gateways.

2) A gateway is the "point" which seems to have access to all the
information and thus, seems reasonable to have congestion indication bit
be set at them as they have a good sense of the overall health of the
network.
3) The packets are marked with a probability which is proportional
(approx.) to their share of the bandwidth when within a specified range
and with probability 1 above the specified range of average queue
length. Also, the time since last packet was dropped is taken into
account while calculating the probability.

4) Detection of congestion - This is done by calculating the average
queue size at the gateway. The response time to the feedback is atleast
a round trip time to notice changes.

5) Since focus is on marking fewer packets than conventional approaches,
it avoids global synchronization to a certain extent.
6) Fairness is protected by marking packets proportional to the
connection's share of bandwidth. However, the argument seems weak in the
sense that the ill-behaved source would lose packets proportional to its
usage of bandwidth. This doesn't sound reason enough to not be able to
get unfair usage of the network.
7) This paper seems to have overlooked the problem of promptness in the
network. It would be interesting to see their results for Telnet like
applications. Specially, since queue sizes are measured in packets, it
seems that TELNET like applications would suffer in terms of response time.

Lesson Learnt: Randomness is beautiful.
Received on Thu Sep 28 2006 - 07:28:43 EDT