“Random Early Detection Gateways for Congestion Avoidance”

Like earlier work on fair queuing, Random Early Detection (RED) argues that the router must play an important role in achieving effective congestion control. However, the RED approach is markedly different from fair queuing. The basic idea in RED is to start taking corrective action as soon as approaching congestion is detected, rather than waiting until the queue buffers are completely full.

RED divides this task into two separate algorithms:

  • Imminent congestion is detected by calculating the average queue size. This is done with a low-pass filter with an exponential moving average; the idea being to distinguish between periods of transient buffering, caused by bursty traffic, and longer-term buffering caused by imminent congestion. RED defines two thresholds for queue size, a minimum size and a maximum size. In essence, the router can be in three states: “no congestion” (below minimum threshold), “severe congestion” (above maximum threshold), and “moderate congestion” (between minimum and maximum thresholds).
  • Once congestion has been detected, RED must then decide on corrective action. To reduce congestion, RED “marks” a packet to inform senders to reduce their transmission rate. Marking can be implemented either by dropping the packet (as in traditional TCP), or by setting a bit in the packet header to inform the sender that congestion is occurring. When the queue size is below the minimum threshold, no packets need to be marked. When the queue size is above the maximum, every incoming packet is marked (or dropped if necessary). When the queue size is between these two thresholds, each incoming packet is marked with a probability that is a function of the current queue size (that is, as the queue size increases, the probability that packets will be marked increases).

This scheme has several important properties. First, it responds to approaching congestion more promptly than a traditional “Tail Drop” policy, which gives senders more time to moderate their transmission rates. While it seems counter-intuitive to mark or drop packets when there is buffer space available, it makes avoiding catastrophic congestion collapse more likely because senders require time to reduce their transmission rates. Second, high-bandwidth senders are more likely to have their packets dropped than low-bandwidth senders, which contributes to fair usage of the link capacity.

Finally, RED does not have a bias against “bursty” traffic, unlike Tail Drop or Random Drop. Tail Drop is biased against bursty traffic, because queue overflows are likely when a cluster of packets from the same connection arrive at about the same time. While the paper confirms their claims about bursty traffic with simulation results, I didn’t get a good intuition for why RED does better than Random Drop on bursty flows — hopefully we can discuss this in class.


The assumptions behind this paper are interesting, and quite different from the assumptions made by the fair queueing work. For example, the papers on fair queueing assume that controlling misbehaving users ought to be a responsibility of the network infrastructure. In this paper, handling misbehaving users is basically an afterthought: RED gives administrators the tools to identify misbehaving users, and vaguely suggests that this information might be used by “higher policy layers” to modify those user’s bandwidth allocations.

In a similar vein, I thought it was remarkable that the paper suggests that FIFO scheduling is “useful for sharing delay among connections, reducing delay for a particular connection during its periods of burstiness.” This seems to be describing exactly the same behavior that the fair queuing papers talk about: FIFO scheduling yields increased latency for low-bandwidth interactive flows like Telnet that share a link with a high-bandwidth latency-tolerant flow like file transfer. The FQ papers view this as undesirable (in fact, they go further and give low-bandwidth sessions an extra “promptness” bonus), whereas this paper views this behavior as desirable. It would be interesting to discuss what gives rise to this difference of opinion.

Another difference in assumptions is the importance of ensuring fair behavior for bursty traffic. I didn’t think this was very well-motivated by the paper: is bursty traffic actually a problem in practice, and why can’t the client space out their traffic more effectively? The example of file transfer with a small window on a connection with a high bandwidth-delay product seems like it could be resolved by better sender-side algorithms, for example (i.e. why is the window small if the bandwidth is large?). Perhaps this points toward the well-known problems with TCP’s additive increase for connections with a high RTT, but I didn’t see a convincing argument in the paper.

It seems like this scheme would be much more effective when marking is implemented with explicit sender notification rather than packet drops. Packet drops are both more severe (sender responds by drastically curtailing transmission rate), and take longer to detect: the sender might need to wait for the full RTO to expire, for example.

Leave a comment

Filed under Paper Summaries

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s