Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/1080091.1080098acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
Article
Free access

One more bit is enough

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.

Cited By

View all
  • (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
  • (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
  • (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
  • Show More Cited By

Index Terms

  1. One more bit is enough

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SIGCOMM '05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications
    August 2005
    350 pages
    ISBN:1595930094
    DOI:10.1145/1080091
    • cover image ACM SIGCOMM Computer Communication Review
      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
      ISSN:0146-4833
      DOI:10.1145/1090191
      Issue’s Table of Contents
    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]

    Sponsors

    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

    1. AQM
    2. ECN
    3. TCP
    4. XCP
    5. congestion control
    6. protocol

    Qualifiers

    • Article

    Conference

    SIGCOMM05
    Sponsor:
    SIGCOMM05: ACM SIGCOMM 2005 Conference
    August 22 - 26, 2005
    Pennsylvania, Philadelphia, USA

    Acceptance Rates

    Overall Acceptance Rate 462 of 3,389 submissions, 14%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)115
    • Downloads (Last 6 weeks)14
    Reflects downloads up to 21 Nov 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (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
    • (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
    • (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
    • (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
    • (2020)ABCProceedings of the 17th Usenix Conference on Networked Systems Design and Implementation10.5555/3388242.3388268(353-372)Online publication date: 25-Feb-2020
    • (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
    • (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
    • (2017)Packet-Scale Congestion Control ParadigmIEEE/ACM Transactions on Networking10.1109/TNET.2016.259101825:1(306-319)Online publication date: 1-Feb-2017
    • (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
    • (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

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media