Random early detection gateways for congestion avoidance
Abstract
The authors present 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 present 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.>
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
RED is the earliest and most well known AQM scheme.
“Random Early Detection (RED) [148] is the earliest and most well known AQM scheme.”
From A comprehensive survey on machine learning for networking: Evolution, applications and research opportunities (2018) · cites this paper as [148]
Cites
Probability Inequalities for sums of Bounded Random Variables
Hoeffding, W. (1994) · Springer series in statistics · doi:10.1007/978-1-4612-0865-5_26 · Cited by 6,683 · see citing works
Congestion avoidance and control
Jacobson, V. L. (1995) · ACM SIGCOMM Computer Communication Review · doi:10.1145/205447.205462 · Cited by 5,306 · see citing works
Self-citationProbability Inequalities for Sums of Bounded Random Variables
Hoeffding, W. (1963) · Journal of the American Statistical Association · doi:10.1080/01621459.1963.10500830 · Cited by 4,869 · see citing works
Forecasting, Structural Time Series Models and the Kalman Filter
Fildes, R. A., Harvey, A. C., West, M., & Harrison, J. (1991) · Journal of the Operational Research Society · doi:10.2307/2583225 · Cited by 4,683 · see citing works
Congestion avoidance and control
Jacobson, V. (1988) · Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication · doi:10.1145/52324.52356 · Cited by 4,650 · see citing works
Self-citationForecasting, Structural Time Series Models and the Kalman Filter
Harvey, A. C. (1990) · doi:10.1017/cbo9781107049994 · Cited by 4,195 · see citing works
Internet Control Message Protocol
Postel, J. B. (1981) · doi:10.17487/rfc0777 · Cited by 868 · see citing works
Supporting real-time applications in an Integrated Services Packet Network
Clark, D. D., Shenker, S. J., & Zhang, L. (1992) · doi:10.1145/144179.144199 · Cited by 851 · see citing works
Recursive Estimation and Time-Series Analysis
Young, P. C. (2011) · Springer eBooks · doi:10.1007/978-3-642-21981-8 · Cited by 796 · see citing works
A control-theoretic approach to flow control
Keshav, S. (1991) · doi:10.1145/115992.115995 · Cited by 752 · see citing works
Recursive Estimation and Time-Series Analysis
Young, P. (1984) · Springer eBooks · doi:10.1007/978-3-642-82336-7 · Cited by 680 · see citing works
A Table of Series and Products
Hansen, E. R. (1975) · International Linear Collider · Cited by 581 · see citing works
Connections with multiple congested gateways in packet-switched networks part 1
Floyd, S. (1991) · ACM SIGCOMM Computer Communication Review · doi:10.1145/122431.122434 · Cited by 385 · see citing works
Self-citationObservations on the dynamics of a congestion control algorithm
Zhang, L., Shenker, S. J., & Clark, D. D. (1991) · doi:10.1145/115992.116006 · Cited by 377 · see citing works
A binary feedback scheme for congestion avoidance in computer networks
Ramakrishnan, K. K., & Jain, R. K. (1990) · ACM Transactions on Computer Systems · doi:10.1145/78952.78955 · Cited by 365 · see citing works
Traffic phase effects in packet-switched gateways
Floyd, S., & Jacobson, V. L. (1991) · ACM SIGCOMM Computer Communication Review · doi:10.1145/122419.122421 · Cited by 335 · see citing works
Self-citationA delay-based approach for congestion avoidance in interconnected heterogeneous computer networks
Jain, R. K. (1989) · ACM SIGCOMM Computer Communication Review · doi:10.1145/74681.74686 · Cited by 322 · see citing works
Recursive Estimation and Time-Series Analysis: An Introduction
Young, P. (1984) · Medical Entomology and Zoology · Cited by 261 · see citing works
Ramakrishnan, K. K., & Jain, R. K. (1995) · ACM SIGCOMM Computer Communication Review · doi:10.1145/205447.205461 · Cited by 255 · see citing works
The synchronization of periodic routing messages
Floyd, S., & Jacobson, V. L. (1994) · IEEE/ACM Transactions on Networking · doi:10.1109/90.298431 · Cited by 244 · see citing works
Self-citationCongestion control in computer networks: issues and trends
Jain, R. K. (1990) · IEEE Network · doi:10.1109/65.56532 · Cited by 239 · see citing works
Probabilistic Analysis of Algorithms
Hofri, M. (1987) · Springer eBooks · doi:10.1007/978-1-4612-4800-2 · Cited by 172 · see citing works
Congestion control for high speed packet switched networks
Bala, K., Cidon, I., & Sohraby, K. (2002) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.1990.91290 · Cited by 167 · see citing works
Congestion Avoidance in Computer Networks with a Connectionless Network LayerPreprint
Jain, R. K., Ramakrishnan, K. K., & Chiu, D. M. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/9809094 · Cited by 164 · see citing works
A new architecture for packet switching network protocols
Zhang, L. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 152 · see citing works
A hop by hop rate-based congestion control scheme
Mishra, P. P., & Kanakia, H. (1992) · doi:10.1145/144179.144254 · Cited by 148 · see citing works
Keshav, S. (1988) · UC Berkeley · Cited by 146 · see citing works
Jain, R. K., & Ramakrishnan, K. K. (2003) · doi:10.1109/cns.1988.4990 · Cited by 144 · see citing works
Analysis of Random Drop for Gateway Congestion Control
Hashem, E. S. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 130 · see citing works
Congestion control in computer networks
Keshav, S. (1991) · UC Berkeley · Cited by 124 · see citing works
A new congestion control scheme
Wang, Z., & Crowcroft, J. (1991) · ACM SIGCOMM Computer Communication Review · doi:10.1145/116030.116033 · Cited by 122 · see citing works
Eliminating periodic packet losses in the 4.3-Tahoe BSD TCP congestion control algorithm
Wang, Z., & Crowcroft, J. (1992) · ACM SIGCOMM Computer Communication Review · doi:10.1145/141800.141801 · Cited by 113 · see citing works
van Haeringen, H., & Kok, L. P. (1986) · Mathematics of Computation · doi:10.1090/s0025-5718-1986-0856718-0 · Cited by 107 · see citing works
Dynamic adaptive windows for high speed data networks: theory and simulations
Mitra, D., & Seery, J. B. (1990) · doi:10.1145/99508.99527 · Cited by 90 · see citing works
Gateway Congestion Control Survey
Mankin, A., & Ramakrishnan, K. (1991) · doi:10.17487/rfc1254 · Cited by 76 · see citing works
Myths about Congestion Management in High Speed NetworksPreprint
Jain, R. K. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/9809088 · Cited by 69 · see citing works
The synchronization of periodic routing messages
Floyd, S., & Jacobson, V. L. (1993) · doi:10.1145/166237.166241 · Cited by 60 · see citing works
Self-citationTwo fast implementations of the “minimal standard” random number generator
Carta, D. F. (1990) · Communications of the ACM · doi:10.1145/76372.76379 · Cited by 48 · see citing works
Something a Host Could Do with Source Quench: The Source Quench Introduced Delay (SQuID)
Prue, W., & Postel, J. B. (1987) · doi:10.17487/rfc1016 · Cited by 42 · see citing works
Dynamic adaptive windows for high speed data networks with multiple paths and propagation delays
Mitra, D., & Seery, J. B. (1993) · Computer Networks and ISDN Systems · doi:10.1016/0169-7552(93)90060-h · Cited by 30 · see citing works
Dynamic adaptive windows for high speed data networks with multiple paths and propagation delays
Mitra, D., & Seery, J. B. (1991) · doi:10.1109/infcom.1991.147482 · Cited by 30 · see citing works
Hofri, M. (2011) · Medical Entomology and Zoology · Cited by 14 · see citing works
The performance of adaptive window flow controls in a dynamic load environment
Pingali, S., Tipper, D., & Hammond, J. L. (2002) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.1990.91233 · Cited by 14 · see citing works
Nest: A Network Simulation and Prototyping Tool.
Bacon, D. F., Schwartz, J., & Yemini, Y. (1988) · Cited by 14 · see citing works
TCP over ATM with Congestion: Some Performance Results
Romanow, A. (2005) · doi:10.1109/lman.1993.665401 · Cited by 5 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Allman, M., Paxson, V., & Blanton, E. (2009) · doi:10.17487/rfc5681 · Cited by 2,523 · see citing works
Recommendations on Queue Management and Congestion Avoidance in the Internet
Braden, B., Clark, D., Crowcroft, J., Davie, B., Deering, S., Estrin, D., Floyd, S., Jacobson, V., Minshall, G., Partridge, C., et al. (1998) · doi:10.17487/rfc2309 · Cited by 1,318 · see citing works
Self-citationBoutaba, R., Salahuddin, M. A., Limam, N., Ayoubi, S., Shahriar, N., Estrada-Solano, F., & Caicedo, O. M. (2018) · Journal of Internet Services and Applications · doi:10.1186/s13174-018-0087-2 · Cited by 1,036 · see citing works
The BLUE active queue management algorithms
Feng, W.-C., Shin, K. G., Kandlur, D. D., & Saha, D. (2002) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2002.801399 · Cited by 576 · see citing works
A case for stateful forwarding plane
Yi, C., Afanasyev, A., Moiseenko, I., Wang, L., Zhang, B., & Zhang, L. (2013) · Computer Communications · doi:10.1016/j.comcom.2013.01.005 · Cited by 474 · see citing works
Analytic evaluation of RED performance
Bonald, T., May, M., & Bolot, J.-C. (2002) · Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064) · doi:10.1109/infcom.2000.832539 · Cited by 405 · see citing works
DENS: Data Center Energy-Efficient Network-Aware Scheduling
Kliazovich, D., Bouvry, P., & Khan, S. U. (2010) · 2010 IEEE/ACM Int'l Conference on Green Computing and Communications & Int'l Conference on Cyber, Physical and Social Computing · doi:10.1109/greencom-cpscom.2010.31 · Cited by 239 · see citing works
Li, F., Sun, J., Zukerman, M., Liu, Z., Xu, Q., Chan, S., Chen, G., & Ko, K.-T. (2014) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2014.01.005 · Cited by 33 · see citing works
NN-RED: an AQM mechanism based on neural networks
Hariri, B., & Sadati, N. (2007) · Electronics Letters · doi:10.1049/el:20071791 · Cited by 29 · see citing works
An Adaptive Neuron AQM for a Stable Internet
Sun, J., & Zukerman, M. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-72606-7_72 · Cited by 30 · see citing works
IAPI: An intelligent adaptive PI active queue management scheme
Sun, J., Chan, S., & Zukerman, M. (2012) · Computer Communications · doi:10.1016/j.comcom.2012.07.013 · Cited by 19 · see citing works
An adaptive AQM algorithm based on neuron reinforcement learning
Zhou, C., Di, D., Chen, Q., & Guo, J. (2009) · 2009 IEEE International Conference on Control and Automation · doi:10.1109/icca.2009.5410198 · Cited by 17 · see citing works
Improve throughput of TCP-Vegas in multihop ad hoc networks
Ding, L., Wang, X., Xu, Y., & Zhang, W. (2008) · Computer Communications · doi:10.1016/j.comcom.2008.03.026 · Cited by 13 · see citing works
α_ SNFAQM: an active queue management mechanism using neurofuzzy prediction
Zhani, M. F., Elbiaze, H., & Kamoun, F. (2007) · 2007 12th IEEE Symposium on Computers and Communications · doi:10.1109/iscc.2007.4381596 · Cited by 11 · see citing works
- Authors
- Floyd, S., & Jacobson, V.
- Affiliations
- Lawrence Berkeley National Laboratory (US)
- ORCID
- Jacobson, V.
- Venue
- IEEE/ACM Transactions on Networking
- Published
- 1993
- Volume
- 1
- Issue
- 4
- Pages
- 397-413
- ISSN
- 1063-6692 (ISSN-L)
- OpenAlex
- W2158733823
- Cited by
- 6,290
- References
- 45
- Citations by year
- 2026: 44 · 2025: 60 · 2024: 83 · 2023: 79 · 2022: 90 · 2021: 113 · 2020: 124 · 2019: 134 · 2018: 107 · 2017: 131 · 2016: 175 · 2015: 180 · 2014: 189 · 2013: 203 · 2012: 260
- FWCI
- 14.32
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE/ACM Transactions on Networking (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Network Traffic and Congestion Control
- Physical Sciences › Computer Science › Computer Networks and Communications › Software-Defined Networks and 5G
- Physical Sciences › Engineering › Control and Systems Engineering › Traffic control and management
- Keywords
- random early detection, congestion avoidance, packet-switched networks, packet dropping, packet marking, TCP congestion control, global synchronization, bursty traffic, bandwidth sharing
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review