I enjoyed the paper "Random Early Detection Gateways for Congestion Avoidance" (Floyd, Jacobson).
Although the paper was rather longish, I found it remarkably comprehensible and well written. This, of
course, says little of the content but it does go a long way in appreciating the paper.
The Random Early Detection (RED) method described in the paper differs somewhat from the RED
method described in our course book. The RED method in the book describes dropping packets with some
varying probability as the congestion scale slides up and down. The RED method in the paper uses a
congestion bit while the gateway is in the congestion zone (the area between minimum congestion and
maximum congestion). Packets are not dropped until the congestion exceeds the maximum congestion
I like this method because it allows the sender and receiver to dynamically adjust their window to
accommodate the current network congestion without purposeful packet losses. Anytime a congestion bit
is set the sender should immediately scale back their window. It also removes the dynamic calculation of
congestion bits received and resulting back scaling that is required by DECbit. A congestion bit received
via RED always means scale back.
The paper describes that the algorithm is fair in its congestion control. Their argument appears to be
persuasive in that the probability of frequent senders getting congestion bit set is greater than that of an
One area of omission is how to control misbehaved users. The paper describes a possible solution but no
implemented solution is tested. Misbehaved users are a problem for any gateway congestion avoidance
algorithm. RED, like some other methods, depend on the users responding to the congestion bit in the
packets. If a user chooses to ignore the bit then the gateway may give over an unfair amount of bandwidth
to the misbehaved user. The authors suggest keeping a list of the last N marked packets. If some user has a
large percentage of those packets then the user is probably misbehaved and corrective action could be
taken. Also, RED requires support at the TCP endpoints. The users must respond to the congestion bit or
RED simply fails over to dropping packets when some peak congestion is encountered.
All in all I liked the paper. It seems to present a good argument for the method and I would be interested in
seeing the results of actual implementation.