The New AIMD Congestion Control Algorithm

Authors: Hayder Natiq Jasem, Zuriati Ahmad Zukarnain, Mohamed Othman, Shamala Subramaniam

Abstract:

Congestion control is one of the fundamental issues in computer networks. Without proper congestion control mechanisms there is the possibility of inefficient utilization of resources, ultimately leading to network collapse. Hence congestion control is an effort to adapt the performance of a network to changes in the traffic load without adversely affecting users perceived utilities. AIMD (Additive Increase Multiplicative Decrease) is the best algorithm among the set of liner algorithms because it reflects good efficiency as well as good fairness. Our control model is based on the assumption of the original AIMD algorithm; we show that both efficiency and fairness of AIMD can be improved. We call our approach is New AIMD. We present experimental results with TCP that match the expectation of our theoretical analysis.

Keywords: Congestion control, Efficiency, Fairness, TCP, AIMD.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329823

References:

[1] D. Chiu and R. Jain. Analysis of the Increase/Decrease Algorithms for Congestion Avoidance in Computer Networks. Journal of Computer Networks and ISDN, 17(1), June 1989.
[2] A. Lahanas and V. Tsaoussidis. Additive Increase Multiplicative Decrease - Fast Convergence (AIMD-FC). In Proc. Networks 2002, Atlanta, Georgia.
[3] A. Lahanas and V. Tsaoussidis. Exploiting the Efficiency and Fairness Potential of AIMD-based Congestion Avoidance and Control. Journal of Computer Networks, 2003.
[4] Nader F. Mir, computer and communication networks, Prentice Hall, 2007.
[5] James F. Kurose, Keith W. Ross, computer networking, third edition, Addison Wesley, 2004.
[6] William Stallings, Data and computer communications, Prentice Hall, 2004.
[7] John Nagle. Congestion control in ip/tcp internetworks. SIGCOMM Comput. Commune. Rev., 14(4):11-17, October 1984.
[8] Van Jacobson. Congestion avoidance and control. In ACM SIGCOMM -88, pages 314-329, Stanford, CA, August 1988.
[9] Saverio Mascolo, Claudio Casetti, Mario Gerla, M. Y. Sanadidi, and Ren Wang. Tcp westwood: Bandwidth estimation for enhanced transport over wireless links. In Mobi-Com -01: Proceedings of the 7th annual international conference on Mobile computing and networking, pages 287-297, New York, NY, USA, 2001. ACM Press.
[10] Lisong Xu, Khaled Harfoush, and Injong Rhee. Binary increase congestion control (bic) for fast long-distance networks. In IEEE Infocom 2004, 2004.
[11] Fernando Paganini, Zhikui Wang, John C. Doyle, and Steven H. Low. Congestion control for high performance, stability, and fairness in general networks. IEEE/ACM Trans. Netw., 13(1):43-56, February 2005.
[12] Sally Floyd and Kevin Fall. Promoting the use of end-to-end congestion control in the internet. IEEE ACM Transactions on Networking, 7(4):458-472, 1999.
[13] D. Katabi, M. Handley, and C. Rohrs. Internet congestion control for future high bandwidth-delay product environments, 2002.
[14] R. Stewart, Q. Xie, K. Morneault, C. Sharp, H. Schwarzbauer, T. Taylor, T. Rytina, M. Kalla, L. Zhang, and V. Paxson. Stream control transmission protocol, 2000.
[15] Jean-Yves Le Boudec (EPFL Lausanne) "Rate adaptation, Congestion Control and Fairness: A Tutorial" Nov 2005.
[16] Comer, Douglas E. Internetworking with TCP/IP, 5E, Prentice Hall: Upper Saddle River, NJ. (2006).
[17] K. Ramakrishnan and R. Jain. A Binary Feedback Scheme for Congestion Avoidance in Computer Networks with a Connectionless Network Layer. ACM Transactions on Computer Systems, 8(2):158- 181,May 1990.
[18] V. Jacobson. Congestion Avoidance and Control. In Proceedings of the ACM SIGCOMM -88, pages 314-329, August 1988.
[19] S. Shenker. A Theoretical Analysis of Feedback Flow Control. In ACM SIGCOM Symposium, September 1990.
[20] A. Tang, J. Wang, S. Hedge and S. H. Low. Equilibrium and fairness of networks shared by TCP Reno and Vegas/FAST. Telecommunication Systems, 30(4):417-439, December 2005.
[21] L. Wang, L. Cai, X. Liu and X. Shen. AIMD Congestion Control: Stability, TCP-friendliness, Delay Performance, Tech. Rep., Mar. 2006.
[22] Sally Floyd, Mark Handley, Jitendra Padhye. A Comparison of Equation-Based and AIMD Congestion Control; ACIRI; May 2000.
[23] Lawrence S. Brakmo and Larry L. Peterson. Tcp Vegas: End to end congestion avoidance on a global internet. IEEE Journal on Selected Areas in Communications, 13(8):1465-1480, 1995.
[24] S. Y. Wang, C. L. Chou, C. C. Lin. The design and implementation of the NCTUns network simulation engine. Science Direct, Simulation Modeling Practice and Theory, 2007, 57-81.