Posted by dcoetzee on March 9th, 2009
Citation: Floyd, S. and Jacobson, V. Random early detection gateways for congestion avoidance. IEEE/ACM Trans. Netw. 1, 4 (Aug. 1993), 397-413. (PDF)
Abstract: This paper presents Random Early Detection (RED) gateways for congestion avoidance in packet-switched networks. The gateway detects incipient congestion by computing the average queue size. The gateway could notify connections of congestion either by dropping packets arriving at the gateway or by setting a bit in packet headers. When the average queue size exceeds a preset threshold, the gateway drops or marks each arriving packet with a certain probability, where the exact probability is a function of the average queue size.
RED gateways keep the average queue size low while allowing occasional bursts of packets in the queue. During congestion, the probability that the gateway notifies a particular connection to reduce its window is roughly proportional to that connection’s share of the bandwidth through the gateway. RED gateways are designed to accompany a transport-layer congestion control protocol such as TCP. The RED gateway has no bias against bursty traffic and avoids the global synchronization of many connections decreasing their window at the same time. Simulations of a TCP/IP network are used to illustrate the performance
of RED gateways.
Discussion: This 1993 paper introduced the first widely-used active queue management (AQM) algorithm, known as random early detection (RED); this algorithm is deployed today in many commercial routers in order to manage network congestion.
First some background. A router connects two or more networks together; it receives network packets, examines them to determine which network they should be sent to, and then sends them to that network. Because it handles traffic from many clients, sometimes packets will arrive more quickly than they can be processed. In this case they are temporarily placed in a fixed-size queue. Network congestion occurs when packets arrive so quickly that this queue fills completely; in this case the router is forced to drop, or discard, packets. Transport protocols like TCP are constructed with this possibility in mind; they detect dropped packets and retransmit them later. Moreover, because dropped packets are a good signal of network congestion, a well-behaved TCP client will decrease its sending rate when it notices a packet has been dropped.
The simplest method of queue management, known as tail drop or Drop Tail, is to drop any packet received while the queue is full. TCP clients respond to the drops by throttling their sending rate and soon the queue begins to empty and new packets can be handled. However, tail drop has three main problems:
- Global synchronization: If many clients are sending data through the router simultaneously, it is likely that by dropping many consecutive packets, all clients will get some dropped packets. Consequently, they all reduce their sending rate simultaneously, leading to underutilization. The router responds by dropping no packets, leading to a cycle of underutilization and congestion.
- Bias against bursty traffic: Some clients send large numbers of packets in short bursts; they may use only a small percentage of the bandwidth, but are disproportionately likely to have packets dropped by tail drop, since the average queue size is high and inserting many packets into a mostly-full buffer at once will cause many of them to be dropped. The result is less throughput for these clients.
- High latency: because of tail drop’s high average queue size, each packet must wait in line to be processed for a relatively long time, leading to increased latency, a serious problem in real-time network applications like audio/video calls and interactive remote applications.
Random early detection is one solution to these problems. It operates by keeping a running estimate of the average queue size; if it’s too small, no packets will be dropped. If it’s too large, all packets will be dropped. Between these two thresholds, it smoothly increases the probability that each incoming packet will be dropped, from zero up to a fixed maximum probability maxp.
Although it seems strange at first to be dropping packets while there’s still perfectly good space in the queue, the point is to send an implicit signal to the sender that they need to cut their sending rate. By only dropping a small percentage of packets, only some connections will be affected, avoiding global synchronization, but still effectively limiting growth of the queue. By keeping the average queue size small, average latency is kept small, and there’s room for bursts of traffic, avoiding a bias against bursty senders. Because the average queue size is a running average taken over a period of time, it’s not significantly distorted by these bursts. Global synchronization may still occur if the average queue length exceeds the maximum threshold, but this is a last-resort measure expected to occur only in the face of severe congestion.
One important optimization that RED uses is that the probability that it will drop a packet depends not only on the average queue size but also on the number of packets count processed since the last dropped packet according to the formula p = pb/(1 – count ⋅ pb). The result is that the dropped packets will be spread out more evenly with less clustering, which further decreases the risk of bias against bursty traffic and global synchronization.
A difficult problem in any networking publication is empirical studies: constructing a real large-scale network is far too expensive, and the delays introduced by measurement can affect results. The RED paper relied on simulations of small, simple networks (up to about 10 nodes). One experiment used clients performing full-speed file transfer to measure utilization in this best-case scenario; another featured more mixed traffic. It would be years before limitations of RED in large-scale networks would begin to emerge (discussed below).
Although the most well-known, RED was not the first active queue management algorithm; at least two similar schemes predated it. The Early Random Drop (ERD) algorithm, proposed by Hashem in 1989, was already well-studied by 1993 (Hashem, E., Analysis of random drop for gateway congestion control. Report LCS TR-465, Laboratory for Computer Science, MIT, Cambridge, MA). In this simple scheme, there is no tracking of average queue length; instead, whenever the queue exceeds a certain size, the gateway begins to drop packets with a fixed drop probability. Although this preliminary scheme was effective in reducing global synchronization, it still allowed misbehaving users who do not obey standard protocols to achieve higher throughput.
More similar to RED was DECbit, a 1988 scheme deployed with a custom transport protocol (Raj Jain and K. K. Ramakrishnan. Congestion Avoidance in Computer Networks with a Connectionless Network Layer: Concepts, Goals and Methodology. Proceedings of the IEEE Computer Networking Symposium, pp. 134-143). This scheme kept an estimate of average queue length and marked (set a bit in) packets that arrived when the queue length is high. If clients began to receive many marked packets, they would reduce their sending rate. In TCP, if a client observes even a single dropped packet, it will dramatically reduce its sending rate, exacerbating issues of global synchronization (see slow-start). With its custom protocol DECbit was less severely affected by this problem. However, the RED paper demonstrates that DECbit still demonstrates a bias against bursty traffic. These problems, together with the inability to deploy DECbit in existing TCP networks, have made it unpopular in industry.
One of the main practical problems with RED is that it has a variety of parameters that need to be tuned by a designer depending on specific network conditions:
- minth: The minimum average queue size below which all packets are kept.
- maxth: The maximum average queue size above which all packets are dropped (recommended to be at least twice minth).
- maxp: The maximum value for the probability that each incoming packet will be dropped. If this probability is not sufficient to control traffic, the maximum threshold will be reached and all packets will be dropped. A typical value is 0.02.
- wq: This factor controls how long a period the running average queue length is taken over. If it’s too large, the period will be short and the running average will be too strongly influenced by short bursts of traffic. If it’s too small, the period will be too long and the running average will respond too slowly to actual long-term congestion.
To allow RED to work in a more general setting with less tweaking, a technique known as Adaptive RED or Active RED was developed in 2001 that adjusts parameters in response to the average queue size (Floyd S, Gummadi R, Shenker S. Adaptive RED: an algorithm for increasing the robustness of RED’s active queue management. PDF). A number of other modern schemes for active queue management have been developed that are also more “automatic,” notably Blue (1999) and its variants (W. Feng, D. Kandlur, D. Saha, K. Shin. Blue: A New Class of Active Queue Management Algorithms. U. Michigan CSE-TR-387-99. PDF).
Another issue with RED is that it has trouble scaling to wide area networks (WANs) such as the Internet: in 2003 Low et al showed that large propagation delays could cause RED to update its estimate of the average queue length too slowly (Low, S. H., Paganini, F., Wang, J., and Doyle, J. C. 2003. Linear stability of TCP/RED and a scalable control. Comput. Netw. 43, 5, 633-647. PDF). New variants such as Ohsaki et al’s SPRED were designed to cope with WANs (Ohsaki, H., Yamamoto, H., and Imase, M. SPRED: Active Queue Management Mechanism for Wide-Area Networks. In Proceedings of the 2007 international Symposium on Applications and the internet, January 15 – 19, 2007).
The author releases all rights to all content herein and grants this work into the public domain, with the exception of works owned by others such as abstracts, quotations, and WordPress theme content.