RED (Random Early Detection) Queue Management

Topics below include:
Setting Parameters,
Evaluations of RED,
Other Proposals for Active Queue Management,
RED with Drop Preference,
Active Queue Management with Per-Flow Behaviors,
Queue Management for 3G Links,
The RED implementation in the NS simulator,
RED Implementations,
Deployment,
Notes from Sally,
Papers with Recommendations for RED,
Related Papers,
Email discussions regarding RED.

References on RED (Random Early Detection) Queue Management

Floyd, S., and Jacobson, V., Random Early Detection gateways for Congestion Avoidance V.1 N.4, August 1993, p. 397-413. Abstract.
This is the basic paper that describes RED queue management.
B. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin, S. Floyd, V. Jacobson, G. Minshall, C. Partridge, L. Peterson, K. Ramakrishnan, S. Shenker, J. Wroclawski, L. Zhang, RFC 2309: Recommendations on Queue Management and Congestion Avoidance in the Internet, April 1998. Informational.
Sally Floyd, Ramakrishna Gummadi, and Scott Shenker, Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management (postscript, PDF), August 2001. Simulation scripts.
Floyd, S., Recommendation on using the "gentle_" variant of RED, March 2000.
This note recommends implementing RED, and running simulations, with the "gentle_" modification to RED.
A variant of Adaptive RED has also been implemented in NS, and is illustrated in "./test-all-adaptive-red" in "tcl/test". In Adaptive RED, max_p is adjusted to better control the average queue size.
Floyd, S., and Fall, K., papers about Promoting the Use of End-to-End Congestion Control in the Internet.
Bug-fix for pseudocode in [FJ93]:
Stefann De Cnodder, Omar Elloumi, and Kenny Pauwels, Effect of Different Packet Sizes on RED Performance, 1999.
This paper points out a bug in the pseudocode given in [FJ93] for RED in byte mode (RED_2), where the packet dropping probability depends on the packet size in bytes, and gives a fix (RED_4). RED_4 corresponds to the byte-mode mechanism that has been implemented in NS since 4/30/97.

Setting Parameters:

In the "gentle_" modification to RED in NS, the packet-dropping probability varies from "max_p" to 1 as the average queue size varies from "maxthresh" to twice "maxthresh". This option makes RED much more robust to the setting of the parameters "maxthresh" and "max_p", and was added to NS on 6/12/99. My recommendation is to implement RED, and to run simulations, with "gentle_" set to 1.
Floyd, S., RED: Discussions of Setting Parameters, November 1997.
My current advice is to use the new default parameters of "Queue/RED set q_weight_ -1", "Queue/RED set thresh_ 0", and "Queue/RED set maxthresh_ 0", for automatic configuration. In this case, "thresh_" and "maxthresh_" are set as determined by the target average delay in seconds, "targetdelay_". The current default is "Queue/RED set targetdelay_ 0.005".
I [Sally] have been intending to write a note on "Preventing Oscillations Considered Harmful", explaining why preventing oscillations in the queue size is not one of RED's overriding goals, but I haven't quite gotten to it yet. Please don't set RED parameters with the overriding goal of preventing oscillations in the queue size in an environment of long-lived flows all with the same round-trip time!

Evaluations of RED

Elloumi, O., and Afifi, H., RED Algorithm in ATM Networks. Tech report, June 1997.
"We demonstrate ... how queue monitoring using an enhanced RED algorithm can further provide higher throughput, lower delay and fairness. We show that maintaining a low average buffer queue size benefits to connections sending small amounts of data."
May, M., Bolot, J., Diot, C., and Lyles, B., Reasons not to deploy RED, technical report, June 1999.
"The main results we found were, first, that RED with small buffers does not improve significantly the performance of the network... Second, parameter tuning in RED remains an inexact science, but has no big impact on end-to-end performance."
Note from Sally: It is not a big surprise that RED with small buffers doesn't improve performance significantly. This doesn't strike me as a relevant reason not to deploy RED.
The UNC articles:
- M. Christiansen, K. Jeffay, D. Ott, and F.D. Smith, Tuning RED for Web Traffic, ACM SIGCOMM, August 2000. Or the June 2001 version in IEEE/ACM Transactions on Networking.
  "We conclude that for links carrying only web traffic, RED queue management appears to provide no clear advantage over tail-drop FIFO for end-user response times... There are some limitations of this study that should be considered... Congestion on both paths on a full-duplex link and over multiple router hops should also be considered."
  Note from Sally: This paper uses as its metric the response time for HTTP request-response pairs. While the use of RED often improves average queueing delay and packet drop rates, it doesn't necessarily affect throughput; throughput is often just fine in Drop-Tail environments, particularly in realistic environments such as those used in this paper. The benefits of RED are shown in metrics that are more directly related to queueing delay and drop rates.
- L. Le, J. Aikat, K. Jeffay, and F.D. Smith, The Effects of Active Queue Management on Web Performance, ACM SIGCOMM, 2003.
  "We conclude that without ECN there is little end-user performance gain to be realized by employing the AQM designs studied here. However, with ECN, response times can be significantly improved."
- L. Le, J. Aikat, K. Jeffay, and F.D. Smith, The Effects of Active Queue Management and Explicit Congestion Notification on Web Performance, IEEE/ACM Transactions on Networking, 2005.
  "We conclude that AQM can improve application and network performance for Web or Web-like workloads. In particular, it appears likely that with AQM and ECN, provider links may be operated at near saturation levels without significant degradation in userperceived performance."
A Report on Some Recent Developments in TCP Congestion Control (postscript, PDF), Floyd, S., In submission, June 2000.
Section 3.1 of this paper includes a discussion of the impact of RED for TCP traffic.
Yin Zhang and Lili Qiu, Understanding the End-to-End Performance Impact of RED in a Heterogeneous Environment, Cornell CS Technical Report 2000-1802, July 2000.
"Our results show that overall RED improves performance at least for the types of heterogeneity we have considered."
C. Hollot, V. Misra, D. Towsley and W. Gong. A Control Theoretic Analysis of RED, INFOCOMM 2001.
"We present guidelines for designing linearly stable systems subject to network parameters like propogation delay and load level."
Wesley Eddy and Mark Allman. A Comparison of RED's Byte and Packet Modes. Computer Networks, 42(2), June 2003.
P. Ranjan, E. H. Abed, and R. J. La, Nonlinear Instabilities in TCP-RED IEEE/ACM Transactions on Networking, December 2004.
"This work develops a discrete-time dynamical feed-back system model for a simplified TCP network with RED control and provides a nonlinear analysis that can help in understanding observed parametric sensitivities."
Note from Sally: The simulations show oscillations in the average queue size, using scenarios with one-way traffic and with very low RED averaging weights of 0.000004 and 0.000005.
P. Tinnakornsrisuphap and R. J. La, Asymptotic Behavior of Heterogeneous TCP Flows and RED Gateway, IEEE/ACM Transactions on Networking, February 2006.
"We introduce a stochastic model of a bottleneck ECN/RED gateway under a large number of heterogeneous TCP flows, i.e., flows with diverse round-trip delays and session dynamics."
Discussion: "First, ... the arrivals and departures of connections (or simply session dynamics) are a major contributor to the random queue fluctuations. Second, the magnitude of the random queue fluctuations is not sensitive to the slope of the marking function. However, the stability of a system with TCP flows and RED gateway(s) is shown to be relatively sensitive to the slope of the system. Third, oscillations caused by [the binary nature and uncertainty of RED feedback and the structure of TCP] are also significant."

Proposed Modifications to RED, and Other Proposals for Active Queue Management

M. Shin, S. Chong, and I. Rhee, Dual-Resource TCP/AQM for Processing-Constrained Networks, IEEE/ACM ToN. April 2008.
"Both bandwidth and CPU resources can be a bottleneck and thus congestion control must deal with `congestion' on both of these resources."
- S. Chong, M. Shin, J. Mo, and H. Lee, Flow Control with Processing Constraint", IEEE Communications Letters, October 2005.
"We re-examine ﬂow control issues for a network environment where transmission links and CPUs on a data path can be jointly bottlenecked."
Shao Liu, Tamer Basar, and R. Srikant, Exponential RED: A Stabilizing AQM Scheme for Low- and High-speed TCP Protocols, IEEE/ACM ToN, October 2005.
"Our modification to RED sets the packet marking probability as an exponential function of the length of a virtual queue whose capacity is slightly smaller than the link capacity.... E-RED is the first router algorithm which can be proved to stabilize TCP-Reno for a general topology network with heterogeneous delays."
-- A related idea was proposed in an unpublished thesis in 2003 by Somak Halder in "EXPRED - A New Active Queue Management Algorithm". From that document: "The drop probability becomes an exponential function instead of a linear function of the average queue size."
Ashvin Lakshmikantha, C. L. Beck and R. Srikant, Robustness of Real and Virtual Queue-Based Active Queue Management Schemes (2002 version), IEEE/ACM ToN, February 2005.
"Using fluid flow models, we show via analysis and simulations that Virtual Queue (VQ)-based marking schemes outperform Real Queue (RQ)-based marking schemes in terms of robustness to disturbances and the ability to maintain low queueing delays."
S. Athuraliya, V. H. Li, S. H. Low and Q. Yin, REM: Active Queue Management, IEEE Network, May 2001.
"We describe a new active queue management scheme, Random Exponential Marking (REM), that aims to achieve both high utilization and negligible loss and delay in a simple and scalable manner." REM's goal is to stabilize the input rate around the link capacity, and to stabilize the queue around a small target.
J. Aweya, M. Ouellette, D. Y. Montuno and A. Chapman, A Control Theoretic Approach to Active Queue Management, Computer Networks 36, 2001, and An Optimization-oriented View of Random Early Detection, Computer Communications, 2001, to appear.
These two papers propose Dynamic-RED (DRED), which has the goal of maintaining the queue size close to a threshold value, and uses a controller that adapts the packet-dropping probability as a function of the average distance of the queue from the threshold value.
W. Feng, D. Kandlur, D. Saha, K. Shin, Techniques for Eliminating Packet Loss in Congested TCP/IP Networks, U. Michigan CSE-TR-349-97, November 1997.
This paper proposes Adaptive RED, which adjusts the packet dropping probability "max_p" based on the past history of the average queue size.
See also W. Feng, D. Kandlur, D. Saha, K. Shin, A Self-Configuring RED Gateway, INFOCOM '99, March 1999, for a subset of the work in [FKSS97].
W. Feng, D. Kandlur, D. Saha, K. Shin, Blue: A New Class of Active Queue Management Algorithms, UM CSE-TR-387-99, 1999.
This paper proposes a mechanism for active queue management that is based not on the queue size, but only on buffer overflow and link idle events. In Stochastic Fair Blue (SFB), a variant of Blue, flows are hashed into accounting bins, and each bin has its own packet-marking probability.
C. Hollot, V. Misra, D. Towsley and W. Gong. On Designing Improved Controllers for AQM Routers Supporting TCP Flows, INFOCOMM 2001.
"The second of our designs, the Proportional Integral (PI) controller is shown to outperform RED significantly."
Van Jacobson, Notes on using RED for Queue Management and Congestion Avoidance, viewgraphs (PDF, compressed Postscript), talk at NANOG 13, June 1998.
S. Kunniyur and R. Srikant, A time-scale decomposition approach to adaptive ECN marking. U. Illinois, CSL Technical Report. Earlier versions of this paper are to appear in Globecom2000 and Infocom2001.
Related paper: S. Kunniyur and R. Srikant, Analysis and Design of an Adaptive Virtual Queue Algorithm for Active Queue Management, Sigcomm 2001. (Later appeared in IEEE/ACM Transactions on Networking, April 2004.)
T. J. Ott, T. V. Lakshman, and L. H. Wong, SRED: Stabilized RED, Proceedings IEEE INFOCOM '99, New York, March 1999.
This paper proposes a mechanism for statistically estimating the number of active flows at a link; this mechanism could also be used for identifying misbehaving flows. The paper also describes Stabilized RED (SRED), which uses a packet-dropping probability based on the estimated number of active flows and the instantaneous queue size.
V. Rosolen, Bonaventure, O., and G. Leduc, A RED discard strategy for ATM networks and its performance evaluation with TCP/IP traffic, ACM Computer Communication Review, July 1999, and Impact of cell discard strategies on TCP/IP in ATM UBR networks, Proc. of the 6th Workshop on Performance Modelling and Evaluation of ATM Networks (IFIP ATM'98) Ilkley, UK, July 98.
These papers investigate a modified version of RED with a smoothed packet-dropping probability that varies from "max_p" to 1 as the average queue size varies from "maxthresh" to twice "maxthresh". This variant of RED is then modified for an ATM switch. Simulation results compare plain UBR with UBR with Early Packet Discard (EPD), Fair Buffer Allocation (FBA), and with RED.
[This modification to RED has been added to NS, via the `gentle_' parameter.]
Bing Zheng and Mohammed Atiquzzaman, Low Pass Filter/Over Drop Avoidance (LPF/ODA): An algorithm to improve the performance of RED gateways , CS-TR-01-001, technical report, University of Oklahoma, February 2001.
This paper proposes a new algorithm for computing the average queue length with a quicker response to long-term changes in the queue size.

RED with Drop Preference

David D. Clark and Wenjia Fang, Explicit Allocation of Best Effort Packet Delivery Service (PDF), ACM Transactions on Networking, August, 1998.
This paper describes RIO, or RED with In/Out bit. RIO "discriminates against Out packets in times of congestion."
U. Bodin, O. Schelen, and S. Pink, Load-tolerant Differentiation with Active Queue Management, CCR, July, 2000.
This paper evaluates RIO and WRED (Weighted RED), and proposes a modification, WRT (WRED With Thresholds), that calculates a separate average queue length for the higher-priority packets, preventing starvation for the lower-priority traffic.

Stability and Oscillations

This is a small sampling of a rather large literature in this area...

K. B. Kim and S. H. Low, Analysis and Design of AQM for Stabilizing TCP, Caltech Technical Report caltechCSTR:2002.009, March, 2002.
"We interpret existing AQMs such as RED (Random Early Detection), REM (Random Exponential Marking), PI (Proportional-Integral) and AVQ as different approximations of the unified AQM structure."

Active Queue Management with Per-Flow Behaviors

Dong Lin and Robert Morris, Dynamics of Random Early Detection. SIGCOMM 97.
This paper proposes FRED, a variant of RED, that uses per-active-connection accounting to make different dropping decisions for connections with different bandwidth usages.
Core-Stateless Fair Queueing, 1998.
Farooq M. Anjum, Leandros Tassiulas, Balanced-RED: An Algorithm to Achieve Fairness in the Internet, Infocom 1999, March 1999.
This paper proposes Balanced-RED (BRED), which drops packets based on the buffer occupancy of the flow, to achieve a more balanced bandwidth allocation in the presence of non-adaptive traffic.
Anurag Acharya and Anand Rangarajan, Early Regulation of Unresponsive Flows, July 1999.
This paper proposes that RED-based core routers generate rate-limited source quenches, and that edge routers use the source quenches to control per-flow regulators. The goal is to drop undeliverable packets as close to the periphery of the network as possible.
Ratul Mahajan and Sally Floyd, RED with Preferential Dropping (RED-PD), 2001.
"This paper investigates RED-PD, a mechanism that uses the packet drop history at the router to detect high-bandwidth flows in times of congestion, and preferentially drops packets from these high-bandwidth flows to control the bandwidth received by these flows at the congested queue."
Smitha and A. Reddy, LRU-RED: An Active Queue Management Scheme to Contain High Bandwidth Flows at Congested Routers, Global Telecommunicaations Conference, 2001.
LRU-RED "maintains an LRU cache at the routers to record information about the high-bandwidth ﬂows... In addition, it lowers the drop rates of short-lived ﬂows and also of responsive high bandwidth ﬂows."

Active Queue Management with Per-Flow Scheduling

Bernhard Suter, T. V. Lakshman, Dimitrios Stiliadis, and Abhijit Choudhury, Efficient Active Queue Management for Internet Routers, November 1997, Interop '98.
"Per-flow service disciplines are only effective when supported by an appropriate per-flow buffer management strategy, and in particular the shared buffer with soft-partitioning, drop-from-front and longest queue drop."

Queue Management for 3G Links

M. Sagfors, R. Ludwig, M. Meyer, and J. Peisa, Queue management for TCP Traffic over 3G Links, Wireless Communications and Networking, 2003. WCNC 2003.
"We propose a novel active queue management scheme tailored to the specific characteristics of third generation (3G) cellular networks."
H. Ekstrom and Reiner Ludwig, Queue Management for TFRC-Based Traffic in 3G Networks Distributed Computing Systems Workshop, 2003.
"We show that drop-on-full queuing is absolutely inappropriate for TFRC traffic running over 3G links."

The RED implementation in the NS simulator

Floyd, S, Ns Simulator Tests for Random Early Detection (RED) Gateways, Technical report, October 1996, contains simulator validation tests for the NS simulator.

RED Implementations

The red-impl mailing list has been closed, as it is no longer active. It was created for discussions of issues related to software or hardware implementations of RED. Archives up to June 2001. Discussions of active queue management currently take place on the end2end-interest mailing list.
Linux: The RED implementation in Linux was written by Alexey Kuznetsov. RED has been supported in Linux since the 2.2.* kernel.
Jamal Hadi Salim has written a multi-level RED variant, GRED, for Linux. GRED can run up to 16 virtual queues on a single physical queue. This is described further in the web page on "Differentiated Services on Linux". GRED can operate in "RIO mode", with coupled average queue estimates from the virtual queues, or in "standard mode" where each virtual queue has its own independent average queue estimate.
FreeBSD: RED and gentle RED (GRED) are supported in the IPFW2 code in FreeBSD, as of July 2002, from Luigi Rizzo. The parameters for a given queue are: red or gred, w_q, min_th, max_th, and max_p.
Cisco: Cisco's RED implementations include Distributed Weighted Random Early Detection. More information about Cisco's RED implementations can be found on Cisco's web pages by doing a search for "Random Early Detection" on their search engine. RED is implemented for the Cisco AS5200, 4000, 4500, and 4700. Cisco's Weighted RED preferentially drops lower-priority packets by setting different drop-probability functions for each priority level.
ATLQ: Cho, K., an release of RED for BSD Unix. This is a release of Alternate Queueing (ALTQ) for BSD Unix, with CBQ, WFQ, RED, and RSVP stubs for CBQ. ALTQ runs on FreeBSD/NetBSD/OpenBSD. Test results, 1997.
Juniper: The RED implementation for Juniper routers.
Solaris: Michel, Scott, Distant Early Warning (UCLAdew). Distant Early Warning was an implementation of RED for Solaris 2.5 and Solaris 2.5.1. 1997.
Gaynor, M., Proactive Packet Dropping Methods for IP Gateways. November 1996. Abstract, Comments from Sally.

Deployment

My impression from talking with people (e.g., from Cisco, Juniper, British Telecom) is that there is a reasonable deployment of RED in the Internet on access links, but I don't know of any data except for what is cited below.
Possible tests to infer the presence or absence of active queue management along a congested path include the following: (1) Measurements of how frequently multiple packets are dropped from a single window of data; (2) Measurements of the correlation between the loss rate and short-term burstiness.

Marcel Dischinger, Andreas Haeberlen, Krishna P. Gummadi, and Stefan Saroiu. Characterizing Residential Broadband Networks, IMC 2007.
"To quantify the extent of RED deployment in broadband networks, we tested whether the increases in RTT and loss rates are strongly correlated... We found that 26.2% of the DSL hosts show a RED-style drop policy on their upstream queues."
Simon Leinen, Use of RED in practice?, End2end-interest mailing list, March 2006.
"We used to use RED when we had overloaded (transatlantic) links, very successfully I might add - RED brought down peak-hour delays considerably, despite the relatively high base delay, without increasing loss rates or reducing link utilization."
Cisco's documentation on WRED and Why Use WRED?, January 2003.
Chuck Semeria, Supporting Differentiated Service Classes: Active Queue Memory Management, Juniper Networks white paper on WRED, RED, and ECN. February 2002 (registration required for free downloading).
"Active queue memory management plays a vital role in your network because it allows you to control service class depth, manage end-to-end delay, and avoid global TCP synchronization."
WRED and RED are supported in many Juniter routers.
Jun Liu and Mark Crovella, Using Loss Pairs to Discover Network Properties, ACM SIGCOMM Internet Measurement Workshop, 2001.
"Using loss pairs, we show that it is possible to characterize the packet dropping behavior of drop-tail and AQM routers internal to the network... One way to characterize the behavior of an AQM scheme is to plot a curve of its drop rate as a function of queue occupancy."
John Kristoff has data from enabling RED on March 22, 2001 on a border router for an 18 Mbps WAN link. Before RED, packet drop rates were regularly above 400/second. After RED, daily peaks were rarely over 100/second.
WRED is enabled on Cisco GSRs on overloaded links at AS1 (Genuity), to reduce queueing delay (October, 2000). Experience has been positive. (Reported by Derek Fonda of Genuity.)
Doran, S., 1998 data from a deployment of Cisco's (DW) RED implementation by Ebone Inc. is discussed on a thread on "RED on a busy ISP-facing line" on the end2end-interest mailing list.
Villamizar, C., and Song, C., High Performance TCP in ANSNET. Computer Communications Review, V. 24 N. 5, October 1994, p. 45-60.
More reports on actual implementation experiences would be greatly appreciated.

Notes from Sally

Floyd, S., Notes on Implementing RED with ATM, October 1995.
The first paragraph is also about computing the average queue size in hardware.
Floyd, S., Notes on Testing RED Implementations, October 1996.
Floyd, S., RED: Discussions of Byte and Packet Modes, March 1997. With additional comments from January 1998 and October 2000.
Floyd, S., RED: Optimum functions for computing the drop probability? , October 1997.
Floyd, S., RED: Distributions for intervals between marked packets. , February 1998.
Floyd, S., RED: Average queue length vs. instantaneous queue length, November 1997.
Floyd, S., RED with Drop From Front, March 1998.
Floyd, S., Notes on the Holt-Winters Procedure, October 1993.
This note describes a variant of the Exponential-Weighted Moving Average procedure for estimating the average queue size that takes into account the average slope of the average queue size, as well as the queue size itself.

Papers with Recommendations for RED

Firoiu, V., and Borden, M., A Study of Active Queue Management for Congestion Control.
This paper observes the oscillatory behavior with RED when the average packet drop rate exceeds max_p, in the absence of RED's "gentle_" modification, and strongly recommends against the discontinuity in the packet drop rate that occurs in the original, non-"gentle_" variant of RED. This paper also recommends that the ideal rate for sampling the average queue size is "once every RTT"; it seems to me that with such an infrequent sampling of the average queue size, RED could be overly slow to respond to sharp increases in the queue size.