Random Early Detection

The basic observation this paper makes is that, since dropping packets is interpreted by many transport protocols to be a sign of congestion, dropping packets can be used to request that endpoints communicating through the router reduce their traffic. The goals of RED are twofold; one is to maintain short queues in the router so as to minimize latency, and the other is to maintain a fair allocation of bandwidth between competing flows. The protocol uses relatively simple estimators to approximate the running average of the queue depth and to drop packets at a rate which increases with the queue length. As the length of the queue increases, RED will drop proportionally more of the incoming request stream to quench more senders. Since the drops are approximately uniformly distributed in time, flows using more of the router's capacity should experience more dropped packets.

RED different from FQ in several important respects. Clearly, RED is stateless with respect to individual conversations, a significant advantage. RED also explicitly extends the congestion feedback loop to include the senders by making the assumption that they will respond to dropped or marked packets by reducing their rate. As the authors mention, they are considering networks where most of the traffic is TCP streams (or DECbit). However, unlike the authors of FQ, they do not evaluate the effect of "firehose" senders being present on the network; it appears that this scheme would fail in those cases because although packets are dropped randomly, the altruistic senders would reduce their rate in response to this feedback, which would leave the greedy ones a greater share of the capacity. It is a useful result that cooperating senders eliminates the need for per-connection state in such as simple way.

This paper definitely has the feel of the journal paper that it is; a conference never would have allowed the authors to go on for so long about relatively basic math. Pedagogically speaking, though, I thought it was pretty interesting to see the problem mapped out in such detail; although the idea is very simple the authors did a good job of examining some of the premises underlying their work; in particular, it seems like you could really get in a hole with parameter selection where you have only rules of thumb about the actual values. They attempt to quantify the tradeoffs of each setting; with any dynamic system, I suspect the devil is in the details and so it is good to see it worked out. It strikes me that these past few papers we have read on queuing discipline have been a bit more rigorous then your run-of-the-mill cs paper; for me, this is a reason to keep them.