skip to main content
research-article

TCP ex machina: computer-generated congestion control

Published: 27 August 2013 Publication History

Abstract

This paper describes a new approach to end-to-end congestion control on a multi-user network. Rather than manually formulate each endpoint's reaction to congestion signals, as in traditional protocols, we developed a program called Remy that generates congestion-control algorithms to run at the endpoints.
In this approach, the protocol designer specifies their prior knowledge or assumptions about the network and an objective that the algorithm will try to achieve, e.g., high throughput and low queueing delay. Remy then produces a distributed algorithm---the control rules for the independent endpoints---that tries to achieve this objective.
In simulations with ns-2, Remy-generated algorithms outperformed human-designed end-to-end techniques, including TCP Cubic, Compound, and Vegas. In many cases, Remy's algorithms also outperformed methods that require intrusive in-network changes, including XCP and Cubic-over-sfqCoDel (stochastic fair queueing with CoDel for active queue management).
Remy can generate algorithms both for networks where some parameters are known tightly a priori, e.g. datacenters, and for networks where prior knowledge is less precise, such as cellular networks. We characterize the sensitivity of the resulting performance to the specificity of the prior knowledge, and the consequences when real-world conditions contradict the assumptions supplied at design-time.

References

[1]
A. Akella, S. Seshan, R. Karp, S. Shenker, and C. Papadimitriou. Selfish Behavior and Stability of the Internet: A Game-Theoretic Analysis of TCP. In SIGCOMM, 2002.
[2]
M. Alizadeh, A. Greenberg, D. A. Maltz, J. Padhye, P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan. Data Center TCP (DCTCP). In SIGCOMM, 2010.
[3]
M. Allman. Initial Congestion Window Specification. http://tools.ietf.org/html/draft-allman-tcpm-bump-initcwnd-00, 2010.
[4]
M. Allman. Comments on Bufferbloat. ACM SIGCOMM Computer Communication Review, 43(1), Jan. 2013.
[5]
H. Balakrishnan, H. S. Rahul, and S. Seshan. An Integrated Congestion Management Architecture for Internet Hosts. In SIGCOMM, 1999.
[6]
D. Bansal and H. Balakrishnan. Binomial Congestion Control Algorithms. In INFOCOM, 2001.
[7]
D. Bansal, H. Balakrishnan, S. Floyd, and S. Shenker. Dynamic Behavior of Slowly-Responsive Congestion Control Algorithms. In SIGCOMM, 2001.
[8]
D. S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein. The Complexity of Decentralized Control of Markov Decision Processes. Mathematics of Operations Research, 27(4):819--840, Nov. 2002.
[9]
L. S. Brakmo, S. W. O'Malley, and L. L. Peterson. TCP Vegas: New Techniques for Congestion Detection and Avoidance. In SIGCOMM, 1994.
[10]
D.-M. Chiu and R. Jain. Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks. Computer Networks and ISDN Systems, 17:1--14, 1989.
[11]
J. Chu, N. Dukkipati, Y. Cheng, and M. Mathis. Increasing TCP's Initial Window. http://tools.ietf.org/html/draft-ietf-tcpm-initcwnd-08, 2013.
[12]
D. Clark. The Design Philosophy of the DARPA Internet Protocols. In SIGCOMM, 1988.
[13]
N. Dukkipati, T. Refice, Y. Cheng, J. Chu, T. Herbert, A. Agarwal, A. Jain, and N. Sutin. An Argument for Increasing TCP's Initial Congestion Window. ACM SIGCOMM Computer Communication Review, 40(3):27--33, 2010.
[14]
W. Feng, K. Shin, D. Kandlur, and D. Saha. The BLUE Active Queue Management Algorithms. IEEE/ACM Trans. on Networking, Aug. 2002.
[15]
S. Floyd. TCP and Explicit Congestion Notification. CCR, 24(5), Oct. 1994.
[16]
S. Floyd, M. Handley, J. Padhye, and J. Widmer. Equation-Based Congestion Control for Unicast Applications. In SIGCOMM, 2000.
[17]
S. Floyd and V. Jacobson. Random Early Detection Gateways for Congestion Avoidance. IEEE/ACM Trans. on Networking, 1(4), Aug. 1993.
[18]
S. Ha, I. Rhee, and L. Xu. CUBIC: A New TCP-Friendly High-Speed TCP Variant. ACM SIGOPS Operating System Review, 42(5):64--74, July 2008.
[19]
J. C. Hoe. Improving the Start-up Behavior of a Congestion Control Scheme for TCP. In SIGCOMM, 1996.
[20]
D. Hofstadter. Metamagical Themas: Questing for the Essence of Mind and Pattern. Basic books, 1985.
[21]
V. Jacobson. Congestion Avoidance and Control. In SIGCOMM, 1988.
[22]
R. Jain. A Delay-based Approach for Congestion Avoidance in Interconnected Heterogeneous Computer Networks. In SIGCOMM, 1989.
[23]
P. Karn, C. Bormann, G. Fairhurst, D. Grossman, R. Ludwig, J. Mahdavi, G. Montenegro, J. Touch, and L. Wood. Advice for Internet Subnetwork Designers, 2004. RFC 3819, IETF.
[24]
D. Katabi, M. Handley, and C. Rohrs. Congestion Control for High Bandwidth-Delay Product Networks. In SIGCOMM, 2002.
[25]
F. P. 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.
[26]
E. Kohler, M. Handley, and S. Floyd. Designing DCCP: Congestion control Without Reliability. In SIGCOMM, 2006.
[27]
S. Kunniyur and R. Srikant. Analysis and Design of an Adaptive Virtual Queue (AVQ) Algorithm for Active Queue Management. In SIGCOMM, 2001.
[28]
T. Lan, D. Kao, M. Chiang, and A. Sabharwal. An Axiomatic Theory of Fairness. In INFOCOM, 2010.
[29]
D. Leith and R. Shorten. H-TCP Protocol for High-Speed Long Distance Networks. In PFLDNet, 2004.
[30]
S. Mascolo, C. Casetti, M. Gerla, M. Sanadidi, and R. Wang. TCP Westwood: Bandwidth Estimation for Enhanced Transport over Wireless Links. In MobiCom, 2001.
[31]
P. E. McKenney. Stochastic Fairness Queueing. In INFOCOM, 1990.
[32]
D. Meagher. Geometric Modeling Using Octree Encoding. Computer Graphics and Image Processing, 19(2):129--147, 1982.
[33]
K. Nichols and V. Jacobson. Controlling Queue Delay. ACM Queue, 10(5), May 2012.
[34]
F. A. Oliehoek. Decentralized POMDPs. In In Reinforcement Learning: State of the Art, Adaptation, Learning, and Optimization, pages 471--503, 2012.
[35]
R. Pan, B. Prabhakar, and K. Psounis. CHOKe--A Stateless Active Queue Management Scheme for Approximating Fair Bandwidth Allocation. In INFOCOM, 2000.
[36]
R. Srikant. The Mathematics of Internet Congestion Control. Birkhauser, 2004.
[37]
C. Tai, J. Zhu, and N. Dukkipati. Making Large Scale Deployment of RCP Practical for Real Networks. In INFOCOM, 2008.
[38]
K. Tan, J. Song, Q. Zhang, and M. Sridharan. A Compound TCP Approach for High-speed and Long Distance Networks. In INFOCOM, 2006.
[39]
J. Touch. Automating the Initial Window in TCP. http://tools.ietf.org/html/draft-touch-tcpm-automatic-iw-03, 2012.
[40]
Z. Wang and J. Crowcroft. A New Congestion Control Scheme: Slow Start and Search (Tri-S). In SIGCOMM, 1991.
[41]
D. Wei, C. Jin, S. Low, and S. Hegde. FAST TCP: Motivation, Architecture, Algorithms, Performance. IEEE/ACM Trans. on Networking, 14(6):1246--1259, 2006.
[42]
K. Winstein and H. Balakrishnan. End-to-End Transmission Control by Modeling Uncertainty about the Network State . In HotNets-X, 2011.
[43]
Y. Xia, L. Subramanian, I. Stoica, and S. Kalyanaraman. One More Bit is Enough. IEEE/ACM Trans. on Networking, 16(6):1281--1294, 2008.
[44]
L. Xu, K. Harfoush, and I. Rhee. Binary Increase Congestion Control (BIC) for Fast Long-Distance Networks. In INFOCOM, 2004.
[45]
Y. Yi and M. Chiang. Stochastic Network Utility Maximisation. European Transactions on Telecommunications, 19(4):421--442, 2008.
[46]
K. K. Ramakrishnan and R. Jain. A Binary Feedback Scheme for Congestion Avoidance in Computer Networks. ACM Trans. on Comp. Sys., 8(2):158--181, May 1990.

Cited By

View all
  • (2024)PudicaProceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation10.5555/3691825.3691832(113-129)Online publication date: 16-Apr-2024
  • (2024)Large Language Models Meet Next-Generation Networking Technologies: A ReviewFuture Internet10.3390/fi1610036516:10(365)Online publication date: 7-Oct-2024
  • (2024)On the Fairness of Internet Congestion Control over WiFi with Deep Reinforcement LearningFuture Internet10.3390/fi1609033016:9(330)Online publication date: 10-Sep-2024
  • Show More Cited By

Index Terms

  1. TCP ex machina: computer-generated congestion control

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM SIGCOMM Computer Communication Review
    ACM SIGCOMM Computer Communication Review  Volume 43, Issue 4
    October 2013
    595 pages
    ISSN:0146-4833
    DOI:10.1145/2534169
    Issue’s Table of Contents
    • cover image ACM Conferences
      SIGCOMM '13: Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM
      August 2013
      580 pages
      ISBN:9781450320566
      DOI:10.1145/2486001
    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 the author(s) 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: 27 August 2013
    Published in SIGCOMM-CCR Volume 43, Issue 4

    Check for updates

    Author Tags

    1. computer-designed algorithms
    2. congestion control

    Qualifiers

    • Research-article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)407
    • Downloads (Last 6 weeks)59
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)PudicaProceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation10.5555/3691825.3691832(113-129)Online publication date: 16-Apr-2024
    • (2024)Large Language Models Meet Next-Generation Networking Technologies: A ReviewFuture Internet10.3390/fi1610036516:10(365)Online publication date: 7-Oct-2024
    • (2024)On the Fairness of Internet Congestion Control over WiFi with Deep Reinforcement LearningFuture Internet10.3390/fi1609033016:9(330)Online publication date: 10-Sep-2024
    • (2024)TCP Stratos for stratosphere based computing platformsJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-024-00620-013:1Online publication date: 14-Mar-2024
    • (2024)RayNet: A Simulation Platform for Developing Reinforcement Learning-Driven Network ProtocolsACM Transactions on Modeling and Computer Simulation10.1145/365397534:3(1-25)Online publication date: 30-Mar-2024
    • (2024)Lightweight Automatic ECN Tuning Based on Deep Reinforcement Learning With Ultra-Low Overhead in Datacenter NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2024.345059621:6(6398-6408)Online publication date: 1-Dec-2024
    • (2024)Breaking the Inertial Thinking: Non-Blocking Multipath Congestion Control Based on the Single-Subflow Reinforcement Learning ModelIEEE Transactions on Network and Service Management10.1109/TNSM.2024.338004921:3(2876-2887)Online publication date: 1-Jun-2024
    • (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
    • (2024)Device-Based Cellular Throughput Prediction for Video Streaming: Lessons From a Real-World EvaluationIEEE Transactions on Machine Learning in Communications and Networking10.1109/TMLCN.2024.33525412(318-334)Online publication date: 2024
    • (2024)Deep Reinforcement Learning-Based Congestion Control for File Transfer over QUIC2024 IEEE International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON)10.1109/SIBIRCON63777.2024.10758499(25-30)Online publication date: 30-Sep-2024
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media