article

Free access

Dynamics of random early detection

Authors:

Robert MorrisAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 27, Issue 4

Pages 127 - 137

https://doi.org/10.1145/263109.263154

Published: 01 October 1997 Publication History

Abstract

In this paper we evaluate the effectiveness of Random Early Detection (RED) over traffic types categorized as non-adaptive, fragile and robust, according to their responses to congestion. We point out that RED allows unfair bandwidth sharing when a mixture of the three traffic types shares a link. This unfairness is caused by the fact that at any given time RED imposes the same loss rate on all flows, regardless of their bandwidths.We propose Fair Random Early Drop (FRED), a modified version of RED. FRED uses per-active-flow accounting to impose on each flow a loss rate that depends on the flow's buffer use.We show that FRED provides better protection than RED for adaptive (fragile and robust) flows. In addition, FRED is able to isolate non-adaptive greedy traffic more effectively. Finally, we present a "two-packet-buffer" gateway mechanism to support a large number of flows without incurring additional queueing delays inside the network. These improvements are demonstrated by simulations of TCP and UDP traffic.FRED does not make any assumptions about queueing architecture; it will work with a FIFO gateway. FRED's per-active-flow accounting uses memory in proportion to the total number of buffers used: a FRED gateway maintains state only for flows for which it has packets buffered, not for all flows that traverse the gateway.

References

[1]

Brakmo, L, O'Malley, S., Peterson, L., '~TCP Vegas: New Techniques for Congestion Detection and Avoidance" SIG- COMM'94

Digital Library

[2]

Claffy, K., Braun, H-W., Polyzos, G., "A Parameterizable Methodology for Internet Traffic Flow Profiling" IEEE Journal on Selected Areas in Communications, March 1995.

Digital Library

[3]

Eldridge, C., "Rate Controls in Standard Transport Protocols;' ACM Computer Communication Review, July 1992.

Digital Library

[4]

Fall, K., Floyd S., "Simulation-based Comparisons of Tahoe, Reno, and SACK TCP,' Computer Communication Review, July 1996

Digital Library

[5]

Floyd, S, Jacobson V., "Random Early Detection for Congestion Avoidance" IEEE/ACM Transactions on Networking. August 1993

Digital Library

[6]

Floyd, S., Jacobson, V., "On Traffic Phase Effects in Packet- Switched Gateways,' Computer Communication Review, April 1991

Digital Library

[7]

Floyd, S., "TCP and Explicit Congestion Notification" Computer Communication Review, October 1994

Digital Library

[8]

Floyd, S., "Connections with Multiple Congested Gateways in Packet-Switched Networks Part 1' One-way Traffic,' Computer Communications Review, October 1991

Digital Library

[9]

Hahne, E, Gallager, R., "Round Robin Scheduling for Fair Flow Control in Data Communications Networks" IEEE International Conference on Communications, June 1986

[10]

Hashem, E, "Analysis of Random Drop for Gateway Congestion control;' MIT-LCS-TR-465

[11]

Hoe, J, "Improving the Start-up Behavior of a Congestion Control Scheme for TCP,' SIGCOMM'96

Digital Library

[12]

Jaeobson, V., "Congestion Avoidance and Control" SiG- COMM'88

Digital Library

[13]

Jaeobson, V., "Modified TCP congestion avoidance algorithm;' April 30, 1990, end2end-interest mailing list

[14]

Jain, R, Ramakrishnan, K.K., Chiu, D., "Congestion Avoidance in Computer Networks With a Connectionless Network Layer,' DEC-TR-506

[15]

Kung, H. T., Blackwell, T., Chapman, A., "Credit-Based Flow Control for ATM Networks: Credit Update Protocol, Adaptive Credit Allocation, and Statistical Multiplexing" SIGCOMM '94

Digital Library

[16]

Kung, H.T., Chapman, A., The CreditNet Project, http:// www. eecs.harvard.edu/cn.html

[17]

Lin, D., "TCP Fast Retransmission and Fast Recovery Strategies: Analysis and Improvements;' work in progress

[18]

Mankin, A., Ramakrishnan, K., "Gateway Congestion Control Survey" RFC 1254

Digital Library

[19]

Mankin, A., "Random Drop Congestion Control" SiG- COMM'90

Digital Library

[20]

Morris, R., "TCP Behavior with Many Flows;' work in progress

[21]

Nagle, J., "On Packet Switches with Infinite Storage" IEEE Transactions on Communications, Vol. 35, pp 435438, 1987

[22]

Rizzo, L., "RED and non-responsive flows" end2end-interest mailing list, June, 1997

[23]

Tanenbaum, A., Computer Networks, Prentice Hall, 2nd Edition, 1989

Digital Library

[24]

Turner, J.S, "Maintaining High Throughput during overload in ATM Switches,' INFOCOM'96

Digital Library

[25]

Villamizar, C., Song, C., "High Performance TCP in ANS- NET," Computer Communications Review, October 1994

Digital Library

[26]

Zhang, L., "A New Architecture for Packet Switching Network Protocols" MIT-LCS-TR-455

Cited By

Hamad Mahmud S(2024)Simulation Modeling and Performance Comparison of RED and ERED Algorithms using Congestion Indicatorsمجلة العلوم والدراسات الإنسانية - كلية الآداب والعلوم – المرج10.37376/1571-000-063-008(1-11)Online publication date: 6-May-2024
https://doi.org/10.37376/1571-000-063-008
Shan DPeng GRen SMa JLong STang Y(2024)Adaptive Approximate Fair Queueing for Shared-Memory Programmable SwitchesIEEE Transactions on Network Science and Engineering10.1109/TNSE.2024.337781411:4(3563-3576)Online publication date: Jul-2024
https://doi.org/10.1109/TNSE.2024.3377814
Zaryadov IViana HKorolkova AMilovanova T(2023)Chronology of the development of Active Queue Management algorithms of RED family. Part 1: from 1993 up to 2005Discrete and Continuous Models and Applied Computational Science10.22363/2658-4670-2023-31-4-305-33131:4(305-331)Online publication date: 15-Dec-2023
https://doi.org/10.22363/2658-4670-2023-31-4-305-331
Show More Cited By

Index Terms

Dynamics of random early detection
1. Networks
  1. Network architectures
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Communications management

Recommendations

Dynamics of random early detection
SIGCOMM '97: Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication

In this paper we evaluate the effectiveness of Random Early Detection (RED) over traffic types categorized as non-adaptive, fragile and robust, according to their responses to congestion. We point out that RED allows unfair bandwidth sharing when a ...
Delay-based early congestion detection and adaptation in TCP: impact on web performance

Concerns over the scalability of TCP's end-to-end approach to congestion control and its AIMD congestion adaptation have led to proposals for router-based congestion control, specifically, active queue management (AQM). In this paper we present an end-...
Random Early Detection Assisted Layered Multicast
MMNS '02: Proceedings of the 5th IFIP/IEEE International Conference on Management of Multimedia Networks and Services: Management of Multimedia on the Internet

The deployment of the Random Early Detection (RED) algorithm in multicast routers can improve the performance of layered multicast congestion control schemes. In this paper, a new layered multicast protocol called RED Assisted Layered Multicast (RALM) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 27, Issue 4

Oct. 1997

291 pages

ISSN:0146-4833

DOI:10.1145/263109

Chairmen:
Christophe Diot
INRIA Sophia Antipolis, France
,
Christian Huitema
Bellcore
,
Scott Shenker
Xerox Corp.,
,
Editor:
Martha Steenstrup
BBN Corp., Cambridge, MA

Issue’s Table of Contents

SIGCOMM '97: Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication
October 1997
311 pages
ISBN:089791905X
DOI:10.1145/263105
Chairmen:
Christophe Diot
INRIA Sophia Antipolis, France
,
Christian Huitema
Bellcore
,
Scott Shenker
Xerox Corp.
,
Editor:
Martha Steenstrup
BBN Corp., Cambridge, MA

Copyright © 1997 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1997

Published in SIGCOMM-CCR Volume 27, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

457
Total Citations
View Citations
2,828
Total Downloads

Downloads (Last 12 months)267
Downloads (Last 6 weeks)39

Reflects downloads up to 07 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hamad Mahmud S(2024)Simulation Modeling and Performance Comparison of RED and ERED Algorithms using Congestion Indicatorsمجلة العلوم والدراسات الإنسانية - كلية الآداب والعلوم – المرج10.37376/1571-000-063-008(1-11)Online publication date: 6-May-2024
https://doi.org/10.37376/1571-000-063-008
Shan DPeng GRen SMa JLong STang Y(2024)Adaptive Approximate Fair Queueing for Shared-Memory Programmable SwitchesIEEE Transactions on Network Science and Engineering10.1109/TNSE.2024.337781411:4(3563-3576)Online publication date: Jul-2024
https://doi.org/10.1109/TNSE.2024.3377814
Zaryadov IViana HKorolkova AMilovanova T(2023)Chronology of the development of Active Queue Management algorithms of RED family. Part 1: from 1993 up to 2005Discrete and Continuous Models and Applied Computational Science10.22363/2658-4670-2023-31-4-305-33131:4(305-331)Online publication date: 15-Dec-2023
https://doi.org/10.22363/2658-4670-2023-31-4-305-331
Deng XMa LLiu X(2022)CCAIB: Congestion Control Based on Adaptive Integral Backstepping for Wireless Multi-Router NetworkSensors10.3390/s2205181822:5(1818)Online publication date: 25-Feb-2022
https://doi.org/10.3390/s22051818
Jafri SAhmed IAli S(2022)Queue-Buffer Optimization Based on Aggressive Random Early Detection in Massive NB-IoT MANET for 5G ApplicationsElectronics10.3390/electronics1118295511:18(2955)Online publication date: 18-Sep-2022
https://doi.org/10.3390/electronics11182955
Ma LLiu XWang HZhou YDeng X(2022)Congestion Control for Internet of Things Based on PriorityInternational Journal of Control, Automation and Systems10.1007/s12555-021-0076-220:4(1154-1165)Online publication date: 2-Apr-2022
https://doi.org/10.1007/s12555-021-0076-2
Hilquias VZaryadov IMatyushenko SMilovanova T(2022)The Queueing System with Threshold-Based Direct and Inverse General Renovation MechanismDistributed Computer and Communication Networks: Control, Computation, Communications10.1007/978-3-031-23207-7_24(309-323)Online publication date: 26-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-23207-7_24
Abualhaj MAl-Tahrawi MHussein AAl-Khatib S(2021)Fuzzy-Logic Based Active Queue Management Using Performance Metrics Mapping into Multi-Congestion IndicatorsCybernetics and Information Technologies10.2478/cait-2021-001721:2(29-44)Online publication date: 1-Jul-2021
https://doi.org/10.2478/cait-2021-0017
Khurshid KUllah IShah ZHassan NAhanger T(2021)Protocols for Transferring Bulk Data Over Internet: Current Solutions and Future ChallengesIEEE Access10.1109/ACCESS.2021.30946569(95228-95249)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3094656
Kurniawan IAsyhari AHe FLiu Y(2021)Mobile computing and communications-driven fog-assisted disaster evacuation techniques for context-aware guidance supportComputer Communications10.1016/j.comcom.2021.07.020179:C(195-216)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.comcom.2021.07.020
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents