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 gateways.
  
  
• 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, Recommendations on Queue Management and Congestion Avoidance in the Internet, April 1998. Available as RFC 2309 ( text) as an Informational RFC.
  
  
• Floyd, S., and Fall, K., papers about Promoting the Use of End-to-End Congestion Control in the Internet.
  
  
• Elloumi, O., and Afifi, H., RED Algorithm in ATM Networks. Tech report, June 1997.
  
  
• Other papers related to RED can be found by searching for "Random Early Detection" on Henning Schulzrinne's Bibliography of Networking Research.

Proposed Modifications to RED

• 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.

• 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.

• Van Jacobson, Notes on using RED for Queue Management and Congestion Avoidance, viewgraphs (PDF, compressed Postscript), talk at NANOG 13, June 1998.

• V. Rosolen, O. Bonaventure, and G. Leduc, A RED discard strategy for ATM networks and its performance evaluation with TCP/IP traffic, under submission, 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.

Implementation Experiences

• I have created a mailing list for discussions of issues related to software or hardware implementations of RED. To join the list, send email to "red-impl-request@lbl.gov" with subject "subscribe". To unsubscribe, send email to "red-impl-request@lbl.gov" with subject "unsubscribe". Retrieving archived mail might be limited to list members.

  The initial "welcome" message was for the wrong mailing list. This has been fixed...

• 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. More information is available on Fred Baker's web page on Random Early Detection Commands. Cisco's Weighted RED ( WRED) preferentially drops lower-priority packets by setting different drop-probability functions for each priority level.
  
  
• Cho, K., an beta release of RED for BSD Unix. This is a beta release of Alternate Queueing for BSD Unix, with CBQ, WFQ, RED, and RSVP stubs for CBQ. Freliminary test results.
  
  
• Doran, S., Data from a deployment of Cisco's (DW) RED implementation by Ebone Inc. For a discussion of this data, see the thread on "RED on a busy ISP-facing line" on the end2end-interest mailing list.

• Gaynor, M., Proactive Packet Dropping Methods for IP Gateways. November 1996. Abstract, Comments from Sally.
  
  
• Michel, Scott, Distant Early Warning (UCLAdew). Distant Early Warning is an implementation of RED for Solaris 2.5 and Solaris 2.5.1. This distribution includes the source code to the STREAMS device driver which implements the RED algorithm.
  
  
• Villamizar, C., and Song, C., High Performance TCP in ANSNET. Computer Communications Review, V. 24 N. 5, October 1994, p. 45-60. Abstract.
  
  
• Floyd, S., Notes on Implementing RED with ATM, October 1995.
  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.
  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: Discussions of Setting Parameters, November 1997.
  Floyd, S., RED: Average queue length vs. instantaneous queue length, November 1997.
  Floyd, S., RED with Drop From Front, March 1998.
  
  

Related Papers

• Floyd, S., TCP and Explicit Congestion Notification. ACM Computer Communication Review, V. 24 N. 5, October 1994, p. 10-23. [This issue of CCR incorrectly has "1995" on the cover instead of "1994".] Abstract.
  
  
• Floyd, S., and Jacobson, V., On Traffic Phase Effects in Packet-Switched Gateways. Internetworking: Research and Experience, V.3 N.3, September 1992, p.115-156. Abstract. An earlier version of this paper appeared in Computer Communication Review, V.21 N.2, April 1991.
  
  
• Floyd, S., Connections with Multiple Congested Gateways in Packet-Switched Networks Part 1: One-way Traffic. Computer Communications Review, Vol.21, No.5, October 1991, p. 30-47. Abstract.
  
  

Our simulator

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

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, to appear in Interop '98.
• Core-Stateless Fair Queueing.

Email discussions regarding RED

• the DiffServ mailing list archives (including a thread on AF: To RED or not to RED), the end2end-interest mailing list archives.

Return to the [ Network Research Group].