Dong Lin
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.
- 1 Brakmo, L,, O'Malley, S., Peterson, L., '~TCP Vegas: New Techniques for Congestion Detection and Avoidance" SIG- COMM'94 Google Scholar
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. Google ScholarDigital Library
- 3 Eldridge, C., "Rate Controls in Standard Transport Protocols;' ACM Computer Communication Review, July 1992. Google ScholarDigital Library
- 4 Fall, K., Floyd S., "Simulation-based Comparisons of Tahoe, Reno, and SACK TCP,' Computer Communication Review, July 1996 Google ScholarDigital Library
- 5 Floyd, S,, Jacobson V., "Random Early Detection for Congestion Avoidance" IEEE/ACM Transactions on Networking. August 1993 Google ScholarDigital Library
- 6 Floyd, S., Jacobson, V., "On Traffic Phase Effects in Packet- Switched Gateways,' Computer Communication Review, April 1991 Google ScholarDigital Library
- 7 Floyd, S., "TCP and Explicit Congestion Notification" Computer Communication Review, October 1994 Google ScholarDigital Library
- 8 Floyd, S., "Connections with Multiple Congested Gateways in Packet-Switched Networks Part 1' One-way Traffic,' Computer Communications Review, October 1991 Google ScholarDigital Library
- 9 Hahne, E,, Gallager, R., "Round Robin Scheduling for Fair Flow Control in Data Communications Networks" IEEE International Conference on Communications, June 1986Google Scholar
- 10 Hashem, E,, "Analysis of Random Drop for Gateway Congestion control;' MIT-LCS-TR-465Google Scholar
- 11 Hoe, J,, "Improving the Start-up Behavior of a Congestion Control Scheme for TCP,' SIGCOMM'96 Google ScholarDigital Library
- 12 Jaeobson, V., "Congestion Avoidance and Control" SiG- COMM'88 Google ScholarDigital Library
- 13 Jaeobson, V., "Modified TCP congestion avoidance algorithm;' April 30, 1990, end2end-interest mailing listGoogle Scholar
- 14 Jain, R,, Ramakrishnan, K.K., Chiu, D., "Congestion Avoidance in Computer Networks With a Connectionless Network Layer,' DEC-TR-506Google Scholar
- 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 Google ScholarDigital Library
- 16 Kung, H.T., Chapman, A., The CreditNet Project, http:// www. eecs.harvard.edu/cn.htmlGoogle Scholar
- 17 Lin, D., "TCP Fast Retransmission and Fast Recovery Strategies: Analysis and Improvements;' work in progressGoogle Scholar
- 18 Mankin, A., Ramakrishnan, K., "Gateway Congestion Control Survey" RFC 1254 Google ScholarDigital Library
- 19 Mankin, A., "Random Drop Congestion Control" SiG- COMM'90 Google ScholarDigital Library
- 20 Morris, R., "TCP Behavior with Many Flows;' work in progressGoogle Scholar
- 21 Nagle, J., "On Packet Switches with Infinite Storage" IEEE Transactions on Communications, Vol. 35, pp 435438, 1987Google ScholarCross Ref
- 22 Rizzo, L., "RED and non-responsive flows" end2end-interest mailing list, June, 1997Google Scholar
- 23 Tanenbaum, A., Computer Networks, Prentice Hall, 2nd Edition, 1989 Google ScholarDigital Library
- 24 Turner, J.S,, "Maintaining High Throughput during overload in ATM Switches,' INFOCOM'96 Google ScholarDigital Library
- 25 Villamizar, C., Song, C., "High Performance TCP in ANS- NET," Computer Communications Review, October 1994 Google ScholarDigital Library
- 26 Zhang, L., "A New Architecture for Packet Switching Network Protocols" MIT-LCS-TR-455Google Scholar
Index Terms
- Dynamics of random early detection
Recommendations
Dynamics of random early detection
SIGCOMM '97: Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communicationIn 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 InternetThe 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