TCP ex machina: computer-generated congestion control

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.

Index Terms

• Networks

  • Network protocols