Axiomatizing Congestion Control

Abstract

The overwhelmingly large design space of congestion control protocols, along with the increasingly diverse range of application environments, makes evaluating such protocols a daunting task. Simulation and experiments are very helpful in evaluating the performance of designs in specific contexts, but give limited insight into the more general properties of these schemes and provide no information about the inherent limits of congestion control designs (such as, which properties are simultaneously achievable and which are mutually exclusive). In contrast, traditional theoretical approaches are typically focused on the design of protocols that achieve to specific, predetermined objectives (e.g., network utility maximization), or the analysis of specific protocols (e.g., from control-theoretic perspectives), as opposed to the inherent tensions/derivations between desired properties. To complement today's prevalent experimental and theoretical approaches, we put forth a novel principled framework for reasoning about congestion control protocols, which is inspired by the axiomatic approach from social choice theory and game theory. We consider several natural requirements ("axioms'') from congestion control protocols -- e.g., efficient resource-utilization, loss-avoidance, fairness, stability, and TCP-friendliness -- and investigate which combinations of these can be achieved within a single design. Thus, our framework allows us to investigate the fundamental tradeoffs between desiderata, and to identify where existing and new congestion control architectures fit within the space of possible outcomes.

References

1. M. Alizadeh, A. Kabbani, B. Atikoglu, and B. Prabhakar. Stability analysis of QCN: the averaging principle. In SIGMETRICS, 2011.
2. A. Altman and M. Tennenholtz. Axiomatic foundations for ranking systems. Journal of Artificial Intelligence Research, 2008.
3. A. Altman and M. Tennenholtz. An axiomatic approach to personalized ranking systems. Journal of the ACM (JACM), 2010.
4. E. Altman, K. Avrachenkov, and B. Prabhu. Fairness in MIMD congestion control algorithms. In INFOCOM 2005, 2005.
5. E. Altman, R. El-Azouzi, Y. Hayel, and H. Tembine. The evolution of transport protocols: An evolutionary game perspective. Computer Networks, 2009.
6. R. Andersen, C. Borgs, J. Chayes, U. Feige, A. Flaxman, A. Kalai, V. Mirrokni, and M. Tennenholtz. Trust-based recommendation systems: an axiomatic approach. In World Wide Web, 2008.
7. K. J. Arrow. A difficulty in the concept of social welfare. Journal of political economy, 1950.
8. V. Arun and H. Balakrishnan. Copa: Practical delay-based congestion control for the internet. In 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18), pages 329--342, Renton, WA, 2018.
9. D. Bansal and H. Balakrishnan. Binomial congestion control algorithms. In INFOCOM, 2001.
10. B. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin, S. Floyd, V. Jacobson, G. Minshall, C. Partridge, et al. Recommendations on queue management and congestion avoidance in the internet. Technical report, 1998.
11. L. S. Brakmo and L. L. Peterson. TCP vegas: End to end congestion avoidance on a global internet. IEEE Journal on selected Areas in communications, 1995.
12. Briat, Hjalmarsson, Johansson, Jonsson, Karlsson, Sandberg, and Yavuz. An axiomatic fluid-flow model for congestion control analysis. In Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on, pages 3122--3129. IEEE, 2011.
13. L. Cai, X. Shen, J. Pan, and J. W. Mark. Performance analysis of TCP-friendly AIMD algorithms for multimedia applications. Transactions on Multimedia, 2005.
14. N. Cardwell, Y. Cheng, C. S. Gunn, S. H. Yeganeh, and V. Jacobson. BBR: Congestion-based congestion control. Queue, 2016.
15. G. Chichilnisky. An axiomatic approach to sustainable development. Social choice and welfare, 1996.
16. D.-M. Chiu and R. Jain. Analysis of the increase and decrease algorithms for congestion avoidance in computer networks. Computer Networks and ISDN systems, 1989.
17. S. Cohen and A. Zohar. An axiomatic approach to link prediction. In AAAI. Citeseer, 2015.
18. M. Dong, Q. Li, D. Zarchy, P. B. Godfrey, and M. Schapira. PCC: Re-architecting congestion control for consistent high performance. In NSDI 15, 2015.
19. M. Dong, T. Meng, D. Zarchy, E. Arslan, Y. Gilad, B. Godfrey, and M. Schapira. Vivace: Online-learning congestion control. In 15th USENIX Symposium on NSDI 18. USENIX Association, 2018.
20. S. Floyd. Metrics for the Evaluation of Congestion Control Mechanisms. RFC 5166, Mar. 2008.
21. S. Floyd, M. Handley, and J. Padhye. A comparison of equation-based and AIMD congestion control. 2000.
22. A. Gibbard et al. Manipulation of voting schemes: a general result. Econometrica, 1973.
23. P. Godfrey, M. Schapira, A. Zohar, and S. Shenker. Incentive compatibility and dynamics of congestion control. In SIGMETRICS, 2010.
24. S. Ha, I. Rhee, and L. Xu. CUBIC: a new TCP-friendly high-speed TCP variant. ACM SIGOPS Operating Systems Review, 2008.
25. C. V. Hollot, V. Misra, D. Towsley, and W.-B. Gong. On designing improved controllers for aqm routers supporting tcp flows. In INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 3, pages 1726--1734. IEEE, 2001.
26. F. P. Kelly, L. Massoulié, and N. S. Walton. Resource pooling in congested networks: proportional fairness and product form. Queueing Systems, 63(1):165, 2009.
27. T. Lakshman and U. Madhow. The performance of TCP/IP for networks with high bandwidth-delay products and random loss. Transactions on Networking (ToN), 1997.
28. O. Lev, M. Tennenholtz, and A. Zohar. An axiomatic approach to routing. In INFOCOM 2015, 2015.
29. Y. Liu and W. Gong. On fluid queueing systems with strict priority. IEEE Transactions on Automatic Control, 2003.
30. M. Mathis, J. Semke, J. Mahdavi, and T. Ott. The macroscopic behavior of the TCP congestion avoidance algorithm. SIGCOMM, 1997.
31. R. Mittal, N. Dukkipati, E. Blem, H. Wassel, M. Ghobadi, A. Vahdat, Y. Wang, D. Wetherall, D. Zats, et al. TIMELY: RTT-based congestion control for the datacenter. In SIGCOMM, 2015.
32. J. Mo, R. J. La, V. Anantharam, and J. Walrand. Analysis and comparison of TCP reno and vegas. In INFOCOM'99, 1999.
33. J. Mo and J. Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking (ToN), 2000.
34. R. Netravali, A. Sivaraman, S. Das, A. Goyal, K. Winstein, J. Mickens, and H. Balakrishnan. Mahimahi: Accurate record-and-replay for HTTP. In 2015 USENIX Annual Technical Conference (USENIX ATC 15), 2015.
35. T. Ott, J. Kemperman, and M. Mathis. The stationary behavior of ideal TCP congestion avoidance. 1996.
36. J. Padhye, V. Firoiu, D. Towsley, and J. Kurose. Modeling TCP throughput: A simple model and its empirical validation. SIGCOMM, 1998.
37. F. Paganini, J. Doyle, and S. H. Low. A control theoretical look at internet congestion control. Lecture notes in control and information sciences, 2003.
38. P.-F. Quet and H. Ozbay. On the design of aqm supporting tcp flows using robust control theory. IEEE transactions on automatic control, 49(6):1031--1036, 2004.
39. G. Raina, D. Towsley, and D. Wischik. Part ii: Control theory for buffer sizing. ACM SIGCOMM Computer Communication Review, 35(3):79--82, 2005.
40. R. Rejaie, M. Handley, and D. Estrin. RAP: An end-to-end rate-based congestion control mechanism for realtime streams in the internet. In INFOCOM'99, 1999.
41. M. A. Satterthwaite. Strategy-proofness and arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of economic theory, 1975.
42. S. Shenker. A theoretical analysis of feedback flow control. In SIGCOMM, 1990.
43. R. Shorten, F. Wirth, and D. Leith. A positive systems model of TCP-like congestion control: asymptotic results. Transactions on Networking (TON), 2006.
44. M. Shreedhar and G. Varghese. Efficient fair queuing using deficit round-robin. Transactions on networking, 1996.
45. A. Sivaraman, K. Winstein, S. Subramanian, and H. Balakrishnan. No Silver Bullet: Extending SDN to the Data Plane. In Twelfth ACM Workshop on Hot Topics in Networks (HotNets-XII), College Park, MD, November 2013.
46. R. Srikant. The mathematics of Internet congestion control. 2012.
47. M. Tennenholtz. Reputation systems: An axiomatic approach. In Uncertainty in artificial intelligence, 2004.
48. B. White, J. Lepreau, L. Stoller, R. Ricci, S. Guruprasad, M. Newbold, M. Hibler, C. Barb, and A. Joglekar. An integrated experimental environment for distributed systems and networks. In USENIX OSDI, 2002.
49. K. Winstein and H. Balakrishnan. TCP ex machina: Computer-generated congestion control. In SIGCOMM, 2013.
50. K. Winstein, A. Sivaraman, H. Balakrishnan, et al. Stochastic forecasts achieve high throughput and low delay over cellular networks. In NSDI, 2013.
51. F. Wirth, R. Stanojevi´c, R. Shorten, and D. Leith. Stochastic equilibria of AIMD communication networks. SIAM Journal on Matrix Analysis and Applications, 2006.
52. Y. R. Yang and S. S. Lam. General AIMD congestion control. In Network Protocols, 2000, 2000.
53. L. Zhang, S. Shenker, and D. D. Clark. Observations on the dynamics of a congestion control algorithm: The effects of two-way traffic. SIGCOMM, 1991.

Index Terms

• Networks

  • Network performance evaluation

    • Network performance modeling

  • Network protocols

    • Transport protocols