Random Early Detection Gateways for Congestion Avoidance

This paper describes the Random Early Detection queue management strategy for routers, which provides feedback to TCP connections before congestion occurs to keep queue sizes small and avoid drops, thus improving both throughput and delay. RED works by marking packets for congestion with some probability when the queue size is between two thresholds, and then marking 100% of packets when it exceeds the max threshold. This "smooths out" the congestion notification, rather than going from allowing everything through to dropping everything. It also keeps queue sizes small, avoiding unnecessary delays. Finally, the use of marks reduces packet drops while still avoiding congestion (although RED can also be used with drops, and this would mean no changes to endpoints are necessary).

The paper is especially interesting for its detailed analysis of the problem and its comparison with similar proposed schemes. An especially interesting aspect is how RED is designed to avoid synchronization - many connections lowering their window together, than raising it together, etc, leading to oscillations. Synchronization is a rather scary aspect of end-to-end networking, and several of Sally Floyd's papers address it and have perhaps helped prevent it in many protocols in the global Internet. XCP is also designed to reduce oscillations, and this is how it gains in throughput over TCP even in some low-bandwidth-delay-product settings. In the XCP paper, it is mentioned that even RED can't manage oscillations perfectly at very high throughputs, but RED clearly works well in the experiments in the paper.

Finally, unlike some other QOS mechanisms, RED with drops is fairly easy to deploy incrementally and provides a benefit even to legacy protocol. Is it actually available today on any routers? RED with just marking, on the other hand, still has problems because the end-hosts would need to be able to understand the markings (in fact, un-upgraded hosts would have an advantage over upgraded ones).