Reverse-Engineering Congestion Control Algorithm Behavior
Authors: 
Margarida Ferreira, Ranysha Ware, Yash Kothari, Inês Lynce, Ruben Martins, Akshay Narayan, 
Justine SherryAuthors Info & Claims
Pages 401 - 414
Abstract
The rise of proprietary and novel congestion control algorithms (CCAs) opens questions about the future of Internet utilization, latency, and fairness. However, fully analyzing how novel CCAs impact these properties requires understanding the inner workings of these algorithms. We thus aim to reverse-engineer deployed CCAs' behavior from collected packet traces to facilitate analyzing them. We present Abagnale, a program synthesis pipeline that helps users automate the reverse-engineering task. Using Abagnale, we discover simple expressions capturing the behavior of 9 of the 16 CCAs distributed with the Linux kernel and analyze 7 CCAs from a graduate networking course.
References
[1]
Anup Agarwal, Venkat Arun, Devdeep Ray, Ruben Martins, and Srinivasan Seshan. Automating Network Heuristic Design and Analysis. In HotNets, 2022. Cited on page 13.
[2]
Anup Agarwal, Venkat Arun, Devdeep Ray, Ruben Martins, and Srinivasan Seshan. Towards Provably Performant Congestion Control. In NSDI, 2024. Cited on page 13.
[3]
Venkat Arun, Mina Tahmasbi Arashloo, Ahmed Saeed, Mohammad Alizadeh, and Hari Balakrishnan. Toward Formally Verifying Congestion Control Behavior. In SIGCOMM, 2021. Cited on pages 1 and 3.
[4]
Rukshani Athapathu, Ranysha Ware, Aditya Abraham Philip, Srinivasan Seshan, and Justine Sherry. Prudentia: Measuring Congestion Control Harm on the Internet. In SIGCOMM N2Women Workshop, 2020. Cited on page 3.
[5]
Andrea Baiocchi, Angelo P Castellani, Francesco Vacirca, et al. YeAH-TCP: Yet Another Highspeed TCP. In Proc. PFLDnet, volume 7, 2007. Cited on page 7.
[6]
Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. DeepCoder: Learning to Write Programs. In ICLR (Poster), 2017. Cited on page 3.
[7]
Donald J. Berndt and James Clifford. Using Dynamic Time Warping to Find Patterns in Time Series. In KDD Workshop, 1994. Cited on page 6.
[8]
L. Brakmo. TCP-NV: Congestion Avoidance for Data Centers. Linux Plumbers Conference, 2010. Cited on pages 7 and 10.
[9]
Lawrence S. Brakmo, Sean W. O'Malley, and Larry L. Peterson. TCP Vegas: New Techniques for Congestion Detection and Avoidance. In SIGCOMM, 1994. Cited on pages 5, 7, and 10.
[10]
Ricardo Brancas, Miguel Terra-Neves, Miguel Ventura, Vasco M. Manquinho, and Ruben Martins. Towards Reliable SQL Synthesis: Fuzzing-Based Evaluation and Disambiguation. In FASE, 2024. Cited on pages 2 and 7.
[11]
Deklin Caban, Devdeep Ray, and Srinivasan Seshan. Understanding Congestion Control for Cloud Game Streaming. 2020. Cited on page 1.
[12]
Carlo Caini and Rosario Firrincieli. TCP Hybla: a TCP Enhancement for Hetero- geneous Networks. Int. J. Satell. Commun. Netw., 22(5), 2004. Cited on pages 7 and 9.
[13]
Neal Cardwell, Yuchung Cheng, C. Stephen Gunn, Soheil Hassas Yeganeh, and Van Jacobson. BBR: Congestion-Based Congestion Control. ACM Queue, 14, 2016. Cited on pages 5, 7, and 8.
[14]
Nicolas Chan, Elizabeth Polgreen, and Sanjit A. Seshia. Gradient Descent over Metagrammars for Syntax-Guided Synthesis. CoRR, abs/2007.06677, 2020. Cited on page 12.
[15]
Haoxian Chen, Anduo Wang, and Boon Thau Loo. Towards Example-Guided Network Synthesis. In APNet, 2018. Cited on page 3.
[16]
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Pondé de Oliveira Pinto, Jared Kaplan, Harrison Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. Evaluating large language models trained on code. CoRR, abs/2107.03374, 2021. Cited on page 3.
[17]
Qiaochu Chen, Xinyu Wang, Xi Ye, Greg Durrett, and Isil Dillig. Multi-Modal Synthesis of Regular Expressions. In PLDI, 2020. Cited on page 3.
[18]
Dah-Ming Chiu and Raj Jain. Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks. Comput. Networks, 17, 1989. Cited on page 1.
[19]
Leonardo Mendonça de Moura and Nikolaj S. Bjørner. Z3: An Efficient SMT Solver. In TACAS, 2008. Cited on page 7.
[20]
Amogh Dhamdhere, David D. Clark, Alexander Gamero-Garrido, Matthew J. Luckie, Ricky K. P. Mok, Gautam Akiwate, Kabir Gogia, Vaibhav Bajpai, Alex C. Snoeren, and kc claffy. Inferring Persistent Interdomain Congestion. In SIGCOMM, 2018. Cited on page 3.
[21]
Yu Feng, Ruben Martins, Osbert Bastani, and Isil Dillig. Program Synthesis Using Conflict-Driven Learning. In PLDI, 2018. Cited on page 3.
[22]
Yu Feng, Ruben Martins, Jacob Van Geffen, Isil Dillig, and Swarat Chaudhuri. Component-Based Synthesis of Table Consolidation and Transformation Tasks From Examples. In PLDI, 2017. Cited on pages 3 and 12.
[23]
Yu Feng, Ruben Martins, Yuepeng Wang, Isil Dillig, and Thomas W. Reps. Component-Based Synthesis for Complex APIs. In POPL, 2017. Cited on page 6.
[24]
Margarida Ferreira, Akshay Narayan, Inês Lynce, Ruben Martins, and Justine Sherry. Counterfeiting Congestion Control Algorithms. In HotNets, 2021. Cited on pages 2, 3, 4, and 13.
[25]
John K. Feser, Swarat Chaudhuri, and Isil Dillig. Synthesizing Data Structure Transformations from Input-Output Examples. In PLDI, 2015. Cited on pages 3 and 12.
[26]
Sally Floyd. HighSpeed TCP for Large Congestion Windows. https://www.ietf. org/rfc/rfc3649.txt, 2003. Cited on page 11.
[27]
Sadjad Fouladi, John Emmons, Emre Orbay, Catherine Wu, Riad S. Wahby, and Keith Winstein. Salsify: Low-Latency Network Video through Tighter Integration between a Video Codec and a Transport Protocol. In NSDI, 2018. Cited on page 3.
[28]
Cheng Peng Fu and Soung C. Liew. TCP Veno: TCP Enhancement for Transmission over Wireless Access Networks. IEEE J. Sel. Areas Commun., 21(2), 2003. Cited on page 7.
[29]
Sishuai Gong, Usama Naseer, and Theophilus Benson. Inspector Gadget: A Framework for Inferring TCP Congestion Control Algorithms and Protocol Configurations. In TMA. IFIP, 2020. Cited on pages 3 and 4.
[30]
Sumit Gulwani. Programming by Examples - and its applications in Data Wrangling. In Javier Esparza, Orna Grumberg, and Salomon Sickert, editors, Dependable Software Systems Engineering, volume 45. 2016. Cited on page 12.
[31]
Sumit Gulwani, William R. Harris, and Rishabh Singh. Spreadsheet Data Manipulation Using Examples. CACM, 55, 2012. Cited on pages 1, 3, and 12.
[32]
Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program synthesis. Foundations and Trends in Programming Languages, 4, 2017. Cited on page 1.
[33]
Zheng Guo, David Cao, Davin Tjong, Jean Yang, Cole Schlesinger, and Nadia Polikarpova. Type-Directed Program Synthesis for RESTful APIs. In PLDI, 2022. Cited on page 6.
[34]
Sangtae Ha, Injong Rhee, and Lisong Xu. CUBIC: a New TCP-Friendly High-Speed TCP Variant. ACM SIGOPS Oper. Syst. Rev., 42(5), 2008. Cited on page 7.
[35]
Shivam Handa and Martin C. Rinard. Inductive Program Synthesis Over Noisy Data. In ESEC/SIGSOFT FSE, 2020. Cited on page 12.
[36]
David A. Hayes and Grenville J. Armitage. Revisiting TCP Congestion Control Using Delay Gradients. In Networking (2). Springer, 2011. Cited on pages 7 and 10.
[37]
Janey C. Hoe. Improving the Start-Up Behavior of a Congestion Control Scheme for TCP. In SIGCOMM, 1996. Cited on page 7.
[38]
Van Jacobson, Neal Cardwell, Yuchung Cheng, and Soheil Hassas Yeganeh. Bottleneck Bandwidth and RTT (BBR) Congestion Control. https://elixir.bootlin. com/linux/v4.14/source/net/ipv4/tcp_bbr.c. Cited on page 7.
[39]
Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. Oracle-Guided Component-Based Program Synthesis. In ICSE. ACM, 2010. Cited on page 3.
[40]
Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples. In ICLR (Poster), 2018. Cited on page 3.
[41]
Tom Kelly. Scalable TCP: Improving Performance in Highspeed Wide Area Networks. SIGCOMM CCR, 33, 2003. Cited on page 7.
[42]
Aleksandar Kuzmanovic and Edward W. Knightly. TCP-LP: Low-Priority Service via Endpoint Congestion Control. IEEE/ACM Trans. Netw., 14(4), 2006. Cited on page 7.
[43]
Adam Langley, Alistair Riddoch, Alyssa Wilk, Antonio Vicente, Charles Krasic, Dan Zhang, Fan Yang, Fedor Kouranov, Ian Swett, Janardhan R. Iyengar, Jeff Bailey, Jeremy Dorfman, Jim Roskind, Joanna Kulik, Patrik Westin, Raman Tenneti, Robbie Shade, Ryan Hamilton, Victor Vasiliev, Wan-Teh Chang, and Zhongyi Shi. The QUIC Transport Protocol: Design and Internet-Scale Deployment. In SIGCOMM, 2017. Cited on page 1.
[44]
Woosuk Lee, Kihong Heo, Rajeev Alur, and Mayur Naik. Accelerating Search- Based Program Synthesis Using Learned Probabilistic Models. In PLDI, 2018. Cited on page 3.
[45]
DJ Leith and R. Shorten. H-TCP Protocol for High-Speed Long Distance Networks. In PFLDNet, 2004. Cited on pages 5, 7, and 9.
[46]
Shao Liu, Tamer Basar, and R. Srikant. TCP-Illinois: A Loss- and Delay-Based Congestion Control Algorithm for High-Speed Networks. Perform. Evaluation, 65, 2008. Cited on pages 7 and 9.
[47]
Xavier Marchal, Philippe Graff, Joël Roman Ky, Thibault Cholez, Stéphane Tuffin, Bertrand Mathieu, and Olivier Festor. An Analysis of Cloud Gaming Platforms Behaviour Under Synthetic Network Constraints and Real Cellular Networks Conditions. J. Netw. Syst. Manag., 31(2), 2023. Cited on page 2.
[48]
Ruben Martins, Jia Chen, Yanju Chen, Yu Feng, and Isil Dillig. Trinity: An Extensible Synthesis Framework for Data Science. VLDB, 12(12), 2019. Cited on pages 3 and 6.
[49]
S. Mascolo, C. Casetti, M. Gerla, M.Y. Sanadidi, and R. Wang. TCP Westwood: Bandwidth Estimation for Enhanced Transport over Wireless Links. In MobiCom, 2001. Cited on page 7.
[50]
Aaron Meurer, Christopher P. Smith, Mateusz Paprocki, Ondrej Certík, Sergey B. Kirpichev, Matthew Rocklin, Amit Kumar, Sergiu Ivanov, Jason Keith Moore, Sartaj Singh, Thilina Rathnayake, Sean Vig, Brian E. Granger, Richard P. Muller, Francesco Bonazzi, Harsh Gupta, Shivam Vats, Fredrik Johansson, Fabian Pe- dregosa, Matthew J. Curry, Andy R. Terrel, Stepán Roucka, Ashutosh Saboo, Isuru Fernando, Sumith Kulal, Robert Cimrman, and Anthony M. Scopatz. SymPy: symbolic computing in Python. PeerJ Comput. Sci., 3, 2017. Cited on page 6.
[51]
Ayush Mishra, Xiangpeng Sun, Atishya Jain, Sameer Pande, Raj Joshi, and Ben Leong. The Great Internet TCP Congestion Control Census. In SIGMETRICS, 2020. Cited on pages 1, 2, 3, 4, 8, and 10.
[52]
Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I. Jordan, and Ion Stoica. Ray: A Distributed Framework for Emerging AI Applications. In OSDI, 2018. Cited on page 7.
[53]
Akshay Narayan, Frank Cangialosi, Deepti Raghavan, Prateesh Goyal, Srinivas Narayana, Radhika Mittal, Mohammad Alizadeh, and Hari Balakrishnan. Restructuring Endpoint Congestion Control. In SIGCOMM, 2018. Cited on pages 1 and 4.
[54]
Vikram Nathan, Vibhaalakshmi Sivaraman, Ravichandra Addanki, Mehrdad Khani Shirkoohi, Prateesh Goyal, and Mohammad Alizadeh. End-to-End Transport for Video QoE Fairness. In SIGCOMM, 2019. Cited on page 3.
[55]
Jitendra Padhye and Sally Floyd. On Inferring TCP Behavior. In SIGCOMM, 2001. Cited on page 3.
[56]
Adithya Abraham Philip, Rukshani Athapathu, Ranysha Ware, Fabian Francis Mkocheko, Alexis Schlomer, Mengrou Shou, Zili Meng, Srinivasan Seshan, and Justine Sherry. Prudentia: Findings of an Internet Fairness Watchdog. In SIG- COMM, 2024. Cited on page 3.
[57]
Devdeep Ray. Integrating Video Codec Design and Network Transport for Emerging Internet Video Streaming Applications. PhD thesis, Carnegie Mellon University, 2022. Cited on page 3.
[58]
Devdeep Ray and Srinivasan Seshan. CC-fuzz: Genetic Algorithm-Based Fuzzing for Stress Testing Congestion Control Algorithms. In HotNets, 2022. Cited on page 4.
[59]
Jan Rüth, Ike Kunze, and Oliver Hohlfeld. An Empirical View on Content Provider Fairness. In TMA, 2019. Cited on page 3.
[60]
Constantin Sander, Jan Rüth, Oliver Hohlfeld, and Klaus Wehrle. DeePCCI: Deep Learning-based Passive Congestion Control Identification. In NetAI@SIGCOMM, 2019. Cited on page 3.
[61]
Lei Shi, Yahui Li, Boon Thau Loo, and Rajeev Alur. Network Traffic Classification by Program Synthesis. In TACAS, 2021. Cited on page 3.
[62]
Armando Solar-Lezama, Rodric M. Rabbah, Rastislav Bodík, and Kemal Ebcioglu. Programming by Sketching for Bit-Streaming Programs. In PLDI, 2005. Cited on page 3.
[63]
Ranysha Ware, Matthew K. Mukerjee, Srinivasan Seshan, and Justine Sherry. Modeling BBR's Interactions with Loss-Based Congestion Control. In IMC, 2019. Cited on pages 1, 4, and 8.
[64]
Ranysha Ware, Adithya Abraham Philip, Nicholas Hungria, Yash Kothari, Justine Sherry, and Srinivasan Seshan. CCAnalyzer: An Efficient and Nearly-Passive Congestion Control Classifier. In SIGCOMM, 2024. Cited on pages 3, 4, 8, 10, and 12.
[65]
D.X. Wei, C. Jin, S.H. Low, and S. Hegde. FAST TCP: Motivation, Architecture, Algorithms, Performance. IEEE/ACM Trans. on Networking, 14(6), 2006. Cited on page 1.
[66]
Keith Winstein and Hari Balakrishnan. TCP ex Machina: Computer-Generated Congestion Control. In SIGCOMM, 2013. Cited on page 4.
[67]
Lisong Xu, Khaled Harfoush, and Injong Rhee. Binary Increase Congestion Control (BIC) for Fast Long-Distance Networks. In INFOCOM, 2004. Cited on pages 7 and 10.
[68]
Yifei Yuan, Dong Lin, Rajeev Alur, and Boon Thau Loo. Scenario-Based Programming for SDN Policies. In CoNEXT, 2015. Cited on page 3.
Index Terms
- Reverse-Engineering Congestion Control Algorithm Behavior
Recommendations
Configurable active multicast congestion control
A multicast congestion control and avoidance scheme is indispensable for group-based applications to fairly share and efficiently use network resources with unicast applications and maintain the stability of the Internet. It is difficult for the ...
Performance evaluation of Westwood+ TCP congestion control
Internet performance symposium (IPS 2002)Westwood+ TCP is a sender-side only modification of the classic Tahoe/Reno TCP that has been recently proposed to improve fairness and efficiency of TCP. The key idea of Westwood+ TCP is to perform an end-to-end estimate of the bandwidth available for a ...
TCP-friendly Congestion Control for HighSpeed Network
SAINT '07: Proceedings of the 2007 International Symposium on Applications and the InternetThe currently used TCP congestion control, TCP Reno, has two weaknesses. To solve this TCP Reno drawback, HighSpeed TCP and Scalable TCP were proposed. However, the fairness between these proposed TCP and TCP Reno is not considered, when both ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2024
812 pages
ISBN:9798400705922
DOI:10.1145/3646547
- General Chairs:
- Narseo Vallina-Rodríguez,
- Guillermo Suarez-Tángil,
- Program Chairs:
- Dave Levin,
- Cristel Pelsser
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 November 2024
Check for updates
Qualifiers
- Research-article
Funding Sources
- Portuguese Foundation for Science and Technology FCT
- Carnegie Mellon Portugal
- NSF (National Science Foundation)
Conference
IMC '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 277 of 1,083 submissions, 26%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 140Total Downloads
- Downloads (Last 12 months)140
- Downloads (Last 6 weeks)116
Reflects downloads up to 22 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in