One more bit is enough | Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications (original) (raw)
Published: 22 August 2005 Publication History
Abstract
Achieving efficient and fair bandwidth allocation while minimizing packet loss in high bandwidth-delay product networks has long been a daunting challenge. Existing end-to-end congestion control (eg TCP) and traditional congestion notification schemes (eg TCP+AQM/ECN) have significant limitations in achieving this goal. While the recently proposed XCP protocol addresses this challenge, XCP requires multiple bits to encode the congestion-related information exchanged between routers and end-hosts. Unfortunately, there is no space in the IP header for these bits, and solving this problem involves a non-trivial and time-consuming standardization process.In this paper, we design and implement a simple, low-complexity protocol, called Variable-structure congestion Control Protocol (VCP), that leverages only the existing two ECN bits for network congestion feedback, and yet achieves comparable performance to XCP, ie high utilization, low persistent queue length, negligible packet loss rate, and reasonable fairness. On the downside, VCP converges significantly slower to a fair allocation than XCP. We evaluate the performance of VCP using extensive ns2 simulations over a wide range of network scenarios. To gain insight into the behavior of VCP, we analyze a simple fluid model, and prove a global stability result for the case of a single bottleneck link shared by flows with identical round-trip times.
References
[1]
M. Allman, V. Paxson, and W. Stevens. TCP Congestion Control. IETF RFC 2581, April 1999.
[2]
S. Athuraliya, V. Li, S. Low, and Q. Yin. REM: Active Queue Management. IEEE Network, 15(3):48--53, May 2001.
[3]
D. Bansal and H. Balakrishnan. Binomial Congestion Control Algorithms. INFOCOM'01, April 2001.
[4]
D. Bertsekas and R. Gallager. Data Networks. 2nd Ed., Simon & Schuster, December 1991.
[5]
S. Bhandarkar, S. Jain, and A. Reddy. Improving TCP Performance in High Bandwidth High RTT Links Using Layered Congestion Control. PFLDNet'05, February 2005.
[6]
L. Brakmo and L. Peterson. TCP Vegas: End to End Congestion Avoidance on a Global Internet. IEEE J. Selected Areas in Communications, 13(8):1465--1480, October 1995.
[7]
H. Bullot and R. Les Cottrell. Evaluation of Advanced TCP Stacks on Fast Long-Distance Production Networks. Available at http://www.slac.stanford.edu/grp/scs/net/talk03/tcp-slac-nov03.pdf.
[8]
C. Casetti, M. Gerla, S. Mascolo, M. Sansadidi, and R. Wang. TCP Westwood: End-to-End Congestion Control for Wired/Wireless Networks. Wireless Networks Journal, 8(5):467--479, September 2002.
[9]
A. Charny, D. Clark, and R. Jain. Congestion Control with Explicit Rate Indication. IEEE ICC'95, June 1995.
[10]
D. Chiu and R. Jain. Analysis of the Increase/Decrease Algorithms for Congestion Avoidance in Computer Networks. J. of Computer Networks and ISDN, 17(1):1--14, June 1989.
[11]
M. Crovella and A. Bestavros. Self-Similarity in World Wide Web Traffic: Evidence and Possible Causes. IEEE/ACM Trans. Networking, 5(6):835--846, December 1997.
[12]
S. Deb and R. Srikant. Global Stability of Congestion Controllers for the Internet. IEEE Trans. Automatic Control, 48(6):1055--1060, June 2003.
[13]
A. Durresi, M. Sridharan, C. Liu, M. Goyal, and R. Jain. Multilevel Explicit Congestion Notification. SCI'01, July 2001.
[14]
W. Feng, K. Shin, D. Kandlur, and D. Saha. The BLUE active queue management algorithms. IEEE/ACM Trans. Networking, 10(4):513--528, August 2002.
[15]
S. Floyd. HighSpeed TCP for Large Congestion Windows. IETF RFC 3649, December 2003.
[16]
S. Floyd, M. Handley, J. Padhye, and J. Widmer. Equation-Based Congestion Control for Unicast Applications. SIGCOMM'00, August 2000.
[17]
S. Floyd and T. Henderson. The NewReno Modification to TCP's Fast Recovery Algorithm. IETF RFC 2582, April 1999.
[18]
S. Floyd and V. Jacobson. Random Early Detection Gateways for Congestion Avoidance. IEEE/ACM Trans. Networking, 1(4):397--413, August 1993.
[19]
S. Floyd and V. Paxson. Difficulties in Simulating the Internet. IEEE/ACM Trans. Networking, 9(4):392--403, August 2001.
[20]
E. Gafni and D. Bertsekas. Dynamic Control of Session Input Rates in Communication Networks. IEEE Trans. Automatic Control, 29(11):1009--1016, November 1984.
[21]
R. Gibbens and F. Kelly. Resource Pricing and the Evolution of Congestion Control. Automatica, 35:1969--1985, 1999.
[22]
K. Gopalsamy. Stability and Oscillations in Delay Differential Equations of Population Dynamics. Kluwer Academic Publishers, 1992.
[23]
C. Hollot, V. Misra, D. Towlsey, and W. Gong. On Designing Improved Controllers for AQM Routers Supporting TCP Flows. INFOCOM'01, April 2001.
[24]
C. Hollot, V. Misra, D. Towsley, and W. Gong. Analysis and Design of Controllers for AQM Routers Supporting TCP Flows. IEEE Trans. Automatic Control, 47(6):945--959, June 2002.
[25]
V. Jacobson. Congestion Avoidance and Control. SIGCOMM'88, August 1988.
[26]
A. Jain and S. Floyd. Quick-Start for TCP and IP. IETF Internet Draft draft-amit-quick-start-02.txt, October 2002.
[27]
R. Jain, S. Kalyanaraman, and R. Viswanathan. The OSU Scheme for Congestion Avoidance in ATM Networks: Lessons Learnt and Extensions. Performance Evaluation, 31(1):67--88, November 1997.
[28]
R. Jain and K. K. Ramakrishnan. Congestion Avoidance in Computer Networks with A Connectionless Network Layer: Concepts, Goals, and Methodology. Proc. IEEE Computer Networking Symposium, April 1988.
[29]
R. Jain, K. K. Ramakrishnan, and D. Chiu. Congestion Avoidance in Computer Networks with a Connectionless Network Layer. DEC-TR-506, August 1987.
[30]
H. Jiang and C. Dovrolis. Passive Estimation of TCP Round-Trip Times. ACM Computer Communications Review, 32(3):75--88, July 2002.
[31]
C. Jin, D. Wei, and S. Low. FAST TCP: Motivation, Architecture, Algorithms, Performance. INFOCOM'04, March 2004.
[32]
R. Johari and D. Tan. End-to-End Congestion Control for the Internet: Delays and Stability. IEEE/ACM Trans. Networking, 9(6):818--832, December 2001.
[33]
L. Kalampoukas, A. Varma, and K. K. Ramakrishnan. Dynamics of an Explicit Rate Allocation Algorithm for Available Bit-Rate (ABR) Service in ATM Networks. Proceedings of the IFIP/IEEE Conference on Broadband Communications, April 1996.
[34]
S. Kalyanaraman, R. Jain, S. Fahmy, R. Goyal, and B. Vandalore. The ERICA Switch Algorithm for ABR Traffic Management in ATM Networks. IEEE/ACM Trans. Networking, 8(1), February 2000.
[35]
D. Katabi, M. Handley, and C. Rohrs. Congestion Control for High Bandwidth-Delay Product Networks. SIGCOMM'02, August 2002.
[36]
T. Kelly. Scalable TCP: Improving Performance in Highspeed Wide Area Networks. Submitted, December 2002.
[37]
F. Kelly, A. Maulloo, and D. Tan. Rate Control in Communication Networks: Shadow Prices, Proportional Fairness and Stability. Journal of the Operational Research Society, 49:237--252, 1998.
[38]
A. Kesselman and Y. Mansour. Adaptive TCP Flow Control. PODC'03, July 2003.
[39]
Y. Kuang. Delay Differential Equations with Applications in Population Dynamics. Academic Press, 1993.
[40]
H. Kung, T. Blackwell, and A. Chapman. Credit-Based Flow Control for ATM Networks: Credit Update Protocol, Adaptive Credit Allocation, and Statistical Multiplexing. SIGCOMM'94, August 1994.
[41]
S. Kunniyur and R. Srikant. End-To-End Congestion Control: Utility Functions, Random Losses and ECN Marks. INFOCOM'00, March 2000.
[42]
S. Kunniyur and R. Srikant. Analysis and Design of an Adaptive Virtual Queue (AVQ) Algorithm for Active Queue Management. SIGCOMM'01, August 2001.
[43]
C. Lagoa, H. Che and B. Movsichoff. Adaptive Control Algorithms for Decentralized Optimal Traffic Engineering in the Internet. IEEE/ACM Trans. Networking, 12(3):415--428, June 2004.
[44]
T. Lakshman and U. Madhow. The Performance of TCP/IP for Networks with High Bandwidth-delay Products and Random Loss. IEEE/ACM Trans. Networking, 5(3):336--350, June 1997.
[45]
D. Leith and R. Shorten. H-TCP: TCP for High-speed and Long-distance Networks. PFLDnet'04, February 2004.
[46]
W. Leland, M. Taqqu, W. Willinger, and D. Wilson. On the Self-Similar Nature of Ethernet Traffic. SIGCOMM'93, August 1993.
[47]
D. Lin and R. Morris. Dynamics of Random Early Detection. SIGCOMM'97, August 1997.
[48]
S. Low and D. Lapsley. Optimization Flow Control, I: Basic Algorithm and Convergence. IEEE/ACM Trans. Networking, 7(6):861--875, December 1999.
[49]
S. Low, F. Paganini, J. Wang, and J. Doyle. Linear Stability of TCP/RED and a Scalable Control. Computer Networks Journal, 43(5):633--647, December 2003.
[50]
L. Massoule. Stability of Distributed Congestion Control with Heterogeneous Feedback Delays. IEEE Trans. Automatic Control, 47(6):895--902, June 2002.
[51]
M. Mathis, J. Mahdavi, S. Floyd, and A. Romanow. TCP Selective Acknowledgement Options. IETF RFC 2018, October 1996.
[52]
Network Simulator ns-2. Http://www.isi.edu/nsnam/ns/.
[53]
J. Padhye, V. Firoiu, D. Towsley, and J. Kurose. Modeling TCP Throughput: A Simple Model and its Empirical Validation. SIGCOMM'98, September 1998.
[54]
R. Pan, K. Psounis, and B. Prabhakar. CHOKe, A Stateless Active Queue Management Scheme for Approximating Fair Bandwidth Allocation. INFOCOM'00, March 2000.
[55]
V. Paxson. End-to-End Internet Packet Dynamics. SIGCOMM'97, September 1997.
[56]
V. Paxson and S. Flyod. Wide-Area Traffic: The Failure of Poisson Modeling. SIGCOMM'94, August 1994.
[57]
K. K. Ramakrishnan and S. Floyd. The Addition of Explicit Congestion Notification (ECN) to IP. IETF RFC 3168, September 2001.
[58]
K. K. Ramakrishnan and R. Jain. A Binary Feedback Scheme for Congestion Avoidance in Computer Networks. SIGCOMM'88, August 1988.
[59]
I. Rhee and L. Xu. CUBIC: A New TCP-Friendly High-Speed TCP Variant. PFLDNet'05, February 2005.
[60]
I. Stoica, S. Shenker, and H. Zhang. Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks. SIGCOMM'98, September 1998.
[61]
V. Utkin. Variable Structure Systems with Sliding Modes. IEEE Trans. Automatic Control, 22(2):212--222, April 1977.
[62]
G. Vinnicombe. On the Stability of End-to-end Congestion Control for the Internet. Univ. of Cambridge Tech Report CUED/F-INFENG/TR.398, December 2000.
[63]
J. Wen and M. Arcak. A Unifying Passivity Framework for Network Flow Control. INFOCOM'03, March, 2003.
[64]
E. Wright. A Non-linear Difference-Differential Equation. J. Reine Angew. Math., 494:66--87, 1955.
[65]
B. Wydrowski and M. Zukerman. MaxNet: A Congestion Control Architecture for Maxmin Fairness. IEEE Comm. Letters, 6(11):512--514, November 2002.
[66]
Y. Xia, L. Subramanian, I. Stoica, and S. Kalyanaraman. One More Bit is Enough. UC Berkeley Tech Report, June 2005.
[67]
L. Xu, K. Harfoush, and I. Rhee. Binary Increase Congestion Control (BIC) for Fast Long-Distance Networks. INFOCOM'04, March 2004.
[68]
Y. Yang and S. Lam. General AIMD Congestion Control. ICNP'00, November 2000.
[69]
L. Ying, G. Dullerud, and R. Srikant. Global Stability of Internet Congestion Controllers with Heterogeneous Delays. Proc. American Control Conference, June 2004.
[70]
Y. Zhang, S. Kang, and D. Loguinov. Delayed Stability and Performance of Distributed Congestion Control. SIGCOMM'04, September 2004.
Information & Contributors
Information
Published In
SIGCOMM '05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications
August 2005
350 pages
ACM SIGCOMM Computer Communication Review Volume 35, Issue 4
Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications
October 2005
324 pages
Copyright © 2005 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: 22 August 2005
Permissions
Request permissions for this article.
Check for updates
Author Tags
Qualifiers
- Article
Conference
Acceptance Rates
Overall Acceptance Rate 462 of 3,389 submissions, 14%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations
- Downloads (Last 12 months)112
- Downloads (Last 6 weeks)19
Reflects downloads up to 15 Oct 2024
Other Metrics
Citations
- Hu JHuang JLi ZWang JHe T(2023)A Receiver-Driven Transport Protocol With High Link Utilization Using Anti-ECN Marking in Data Center NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2022.321834320:2(1898-1912)Online publication date: Jun-2023
- Huang JLiu JJiang NLiu SHu JWang J(2022)Achieving Fast Convergence and High Efficiency Using Differential Explicit Feedback in Data CenterIEEE Transactions on Cloud Computing10.1109/TCC.2022.3199779(1-13)Online publication date: 2022
- Li LLi ZChen YZhang JLi L(2022)Upload Your Data Faster: Driver-Queue based Congestion Control for Wireless Networks2022 IEEE 30th International Conference on Network Protocols (ICNP)10.1109/ICNP55882.2022.9940357(1-11)Online publication date: 30-Oct-2022
- Huang XDong JYang WTian CZhou JKai YCai MXia NDou WChen G(2021)Clean: Minimize Switch Queue Length via Transparent ECN-proxy in Campus Networks2021 IEEE/ACM 29th International Symposium on Quality of Service (IWQOS)10.1109/IWQOS52092.2021.9521295(1-6)Online publication date: 25-Jun-2021
- Goyal PAgarwal ANetravali RAlizadeh MBalakrishnan HBhagwan RPorter G(2020)ABCProceedings of the 17th Usenix Conference on Networked Systems Design and Implementation10.5555/3388242.3388268(353-372)Online publication date: 25-Feb-2020
- Hu JHuang JLi ZWang JHe T(2020)AMRT: Anti-ECN Marking to Improve Utilization of Receiver-driven Transmission in Data CenterProceedings of the 49th International Conference on Parallel Processing10.1145/3404397.3404412(1-10)Online publication date: 17-Aug-2020
- Jiang NHuang JLiu SHu JWang J(2020)Achieving Fast Convergence and High Efficiency using Differential Explicit Feedback in Data CenterICC 2020 - 2020 IEEE International Conference on Communications (ICC)10.1109/ICC40277.2020.9149390(1-6)Online publication date: Jun-2020
- Lovewell RYin QZhang TKaur JSmith F(2017)Packet-Scale Congestion Control ParadigmIEEE/ACM Transactions on Networking10.1109/TNET.2016.259101825:1(306-319)Online publication date: 1-Feb-2017
- He LZhou H(2017)Robust Lyapunov---Krasovskii based design for explicit control protocol against heterogeneous delaysTelecommunications Systems10.1007/s11235-017-0290-766:3(377-392)Online publication date: 1-Nov-2017
- Xue LKumar SCui CKondikoppa PChiu CPark S(2016)Towards fair and low latency next generation high speed networksJournal of Network and Computer Applications10.1016/j.jnca.2016.03.02170:C(183-193)Online publication date: 1-Jul-2016
- Show More Cited By
View Options
View options
View or Download as a PDF file.
eReader
View online with eReader.
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Full Access
Media
Figures
Other
Tables
Affiliations
Yong Xia
Rensselaer Polytechnic Institute
Lakshminarayanan Subramanian
University of California, Berkeley
Ion Stoica
University of California, Berkeley
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute