Random Early Detection Gateways for Congestion Avoidance

This paper explores the use of Random Early Detection (RED) gateways as a congestion control mechanism in cooperation with network transport protocols such as TCP. The primary goal of RED gateways is to maintain the network in a high throughput, low delay region by detecting incipient congestion and responding appropriately. Other crucial goals stem from the shortcomings of Random Drop and Drop Tail gateways. One is to avoid global synchronization due to many connections reduce their transport windows in response to congestion and lead to suboptimal network throughput. Another is to accommodate bursty traffic by allowing transient congestion. RED gateways use minimum and maximum thresholds for the average queue size to control packet dropping. If the average queue size is less than the minimum threshold, no packets are dropped; if the average queue size exceeds the maximum threshold, all packets are dropped. In the critical region between the two thresholds, RED gateways mark packets for dropping with a probability linearly related to the average queue size. This approach ensures that a particular connection is notified of congestion with a probability that is roughly proportional to the connection's share of the gateway bandwidth. Moreover, this definitely avoids the global synchronization problem. To determine the average queue size, RED gateways use an exponential weighted average low-pass filter, which effectively eliminates any bias against bursty network traffic. The authors assert that the optimum average queue size for maximizing throughput and minimizing delay is dependent on network characteristics.

This paper was an enjoyable read, especially because the explanations were very lucid and there was no unnecessary mathematical notation to explain a relatively simple concept. The discussion of using packet-based vs byte-based queue control was excellent, especially because that was a central issue in the previous papers on gateway FQ-based congestion control. The mention of using separate queues for separate classes of traffic was essential. Even though the authors accounted for the ambiguity in the optimal queue size, some examples of average queue sizes and min/max thresholds used for RED gateways would have been appropriate. The coverage of misbehaving hosts felt a little inadequate as well, but overall this is a must for the syllabus.