One more bit is enough

ABSTRACT

Achieving efficient and fair bandwidth allocation while minimizing packet loss and bottleneck queue in high bandwidth-delay product networks has long been a daunting challenge. Existing end-to-end congestion control (e.g., TCP) and traditional congestion notification schemes (e.g., TCP+AQM/ECN) have significant limitations in achieving this goal. While the XCP protocol addresses this challenge, it requires multiple bits to encode the congestion-related information exchanged between routers and end-hosts. Unfortunately, there is no space in the IP header for these bits, and solving this problem involves a non-trivial and time-consuming standardization process.

In this paper, we design and implement a simple, low-complexity protocol, called Variable-structure congestion Control Protocol (VCP), that leverages only the existing two ECN bits for network congestion feedback, and yet achieves comparable performance to XCP, i.e., high utilization, negligible packet loss rate, low persistent queue length, and reasonable fairness. On the downside, VCP converges significantly slower to a fair allocation than XCP. We evaluate the performance of VCP using extensive ns2 simulations over a wide range of network scenarios and find that it significantly outperforms many recently-proposed TCP variants, such as HSTCP, FAST, CUBIC, etc. To gain insight into the behavior of VCP, we analyze a simplified fluid model and prove its global stability for the case of a single bottleneck shared by synchronous flows with identical round-trip times.

REFERENCES

• 1: M. Allman , V. Paxson , W. Stevens, TCP Congestion Control, RFC Editor, 1999
• 2: S. Athuraliya, V. Li, S. Low, and Q. Yin, "REM: Active queue management," IEEE Network, vol. 15, no. 3, pp. 48-53, May 2001.
• 3: D. Bansal and H. Balakrishnan, "Binomial Congestion Control Algorithms," Proc. INFOCOM'01, Apr. 2001.
• 4: Dimitri Bertsekas , Robert Gallager, Data networks (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 5: S. Bhandarkar, S. Jain, and A. Reddy, "Improving TCP performance in high bandwidth high RTT links using layered congestion control," Proc. PFLDNet'05, Feb. 2005.
• 6: L. Brakmo and L. Peterson, "TCP Vegas: End to end congestion avoidance on a global Internet," IEEE J. Sel. Areas Communications, vol. 13, no. 8, pp. 1465-1480, Oct. 1995.
• 7: Claudio Casetti , Mario Gerla , Saverio Mascolo , M. Y. Sanadidi , Ren Wang, TCP westwood: end-to-end congestion control for wired/wireless networks, Wireless Networks, v.8 n.5, p.467-479, September 2002 [doi>10.1023/A:1016590112381]
• 8: Dah-Ming Chiu , Raj Jain, Analysis of the increase and decrease algorithms for congestion avoidance in computer networks, Computer Networks and ISDN Systems, v.17 n.1, p.1-14, June 10, 1989 [doi>10.1016/0169-7552(89)90019-6]
• 9: S. Deb and R. Srikant, "Global stability of congestion controllers for the Internet," IEEE Trans. Autom. Control, vol. 48, no. 6, pp. 1055-1060, Jun. 2003.
• 10: A. Durresi, M. Sridharan, C. Liu, M. Goyal, and R. Jain, "Multilevel explicit congestion notification," Proc. SCI'01, Jul. 2001.
• 11: C. Edwards and S. Spurgeon, Sliding Mode Control: Theory and Applications . New York: Taylor and Francis, Aug. 1998.
• 12: Wu-chang Feng , Kang G. Shin , Dilip D. Kandlur , Debanjan Saha, The BLUE active queue management algorithms, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.513-528, August 2002 [doi>10.1109/TNET.2002.801399]
• 13: S. Floyd, HighSpeed TCP for Large Congestion Windows, RFC Editor, 2003
• 14: S. Floyd , T. Henderson, The NewReno Modification to TCP's Fast Recovery Algorithm, RFC Editor, 1999
• 15: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 16: C. Hollot, V. Misra, D. Towlsey, and W. Gong, "On designing improved controllers for AQM routers supporting TCP flows," Proc. INFOCOM' 01, Apr. 2001.
• 17: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 18: A. Jain and S. Floyd, "Quick-start for TCP and IP," IETF Internet Draft Draft-Amit-Quick-Start-02.txt, Oct. 2002.
• 19: Raj Jain , Shiv Kalyanaraman , Ram Viswanathan, The OSU scheme for congestion avoidance in ATM networks: lessons learnt and extensions, Performance Evaluation, v.31 n.1-2, p.67-88, Nov. 1997 [doi>10.1016/S0166-5316(97)00009-6]
• 20: R. Jain and K. K. Ramakrishnan, "Congestion avoidance in computer networks with a connectionless network layer: Concepts, goals, and methodology," in Proc. IEEE Computer Netw. Symp., Apr. 1988.
• 21: R. Jain, K. K. Ramakrishnan, and D. Chiu, "Congestion avoidance in computer networks with a connectionless network layer," DEC-TR-506, Aug. 1987.
• 22: C. Jin, D. Wei, and S. Low, "FAST TCP: Motivation, architecture, algorithms, performance," in Proc. INFOCOM, Mar. 2004.
• 23: Ramesh Johari , David Kim Hong Tan, End-to-end congestion control for the internet: delays and stability, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.818-832, December 2001 [doi>10.1109/90.974534]
• 24: Shivkumar Kalyanaraman , Raj Jain , Sonia Fahmy , Rohit Goyal , Bobby Vandalore, The ERICA switch algorithm for ABR traffic management in ATM networks, IEEE/ACM Transactions on Networking (TON), v.8 n.1, p.87-98, Feb. 2000 [doi>10.1109/90.836480]
• 25: Dina Katabi , Mark Handley , Charlie Rohrs, Congestion control for high bandwidth-delay product networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 26: Tom Kelly, Scalable TCP: improving performance in highspeed wide area networks, ACM SIGCOMM Computer Communication Review, v.33 n.2, April 2003 [doi>10.1145/956981.956989]
• 27: F. Kelly, A. Maulloo, and D. Tan, "Rate control in communication networks: Shadow prices, proportional fairness and stability," J. Oper. Res. Soc., vol. 49, pp. 237-252, 1998.
• 28: Alex Kesselman , Yishay Mansour, Adaptive AIMD congestion control, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.352-359, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872089]
• 29: Srisankar Kunniyur , R. Srikant, Analysis and design of an adaptive virtual queue (AVQ) algorithm for active queue management, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.123-134, August 2001, San Diego, California, United States
• 30: T. V. Lakshman , Upamanyu Madhow, The performance of TCP/IP for networks with high bandwidth-delay products and random loss, IEEE/ACM Transactions on Networking (TON), v.5 n.3, p.336-350, June 1997 [doi>10.1109/90.611099]
• 31: D. Leith and R. Shorten, "H-TCP: TCP for high-speed and long-distance networks," Proc. PFLDnet'04, Feb. 2004.
• 32: Dong Lin , Robert Morris, Dynamics of random early detection, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.127-137, September 14-18, 1997, Cannes, France
• 33: L. Massoule, "Stability of distributed congestion control with heterogeneous feedback delays," IEEE Trans. Autom. Control, vol. 47, no. 6, pp. 895-902, Jun. 2002.
• 34: M. Mathis , J. Mahdavi , S. Floyd , A. Romanow, TCP Selective Acknowledgement Options, RFC Editor, 1996
• 35: Network Simulator ns-2 [Online]. Available: Http://www.isi.edu/ nsnam/ns/
• 36: Jitendra Padhye , Victor Firoiu , Don Towsley , Jim Kurose, Modeling TCP throughput: a simple model and its empirical validation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.303-314, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 37: R. Pan, K. Psounis, and B. Prabhakar, "CHOKe, a stateless active queue management scheme for approximating fair bandwidth allocation," Proc. INFOCOM'00, Mar. 2000.
• 38: Vern Paxson, End-to-end Internet packet dynamics, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.139-152, September 14-18, 1997, Cannes, France
• 39: K. Ramakrishnan , S. Floyd , D. Black, The Addition of Explicit Congestion Notification (ECN) to IP, RFC Editor, 2001
• 40: K. K. Ramakrishnan , Raj Jain, A binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer, Symposium proceedings on Communications architectures and protocols, p.303-313, August 16-18, 1988, Stanford, California, United States
• 41: I. Rhee and L. Xu, "CUBIC: A new TCP-friendly high-speed TCP variant," Proc. PFLDNet'05, Feb. 2005.
• 42: Ion Stoica , Scott Shenker , Hui Zhang, Core-stateless fair queueing: achieving approximately fair bandwidth allocations in high speed networks, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.118-130, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 43: V. Utkin, "Variable structure systems with sliding modes," IEEE Trans. Autom. Control, vol. 22, no. 2, pp. 212-222, Apr. 1977.
• 44: G. Vinnicombe, "On the stability of end-to-end congestion control for the Internet," Univ. Cambridge, Cambridge, U.K., Tech. Rep. CUED/F-INFENG/TR.398, 2000.
• 45: J. Wen and M. Arcak, "A unifying passivity framework for network flow control," IEEE Trans. Autom. Control, vol. 49, no. 2, pp. 162-174, Feb. 2004.
• 46: B. Wydrowski and M. Zukerman, "MaxNet: A congestion control architecture for maxmin fairness," IEEE Commun. Lett., vol. 6, no. 11, pp. 512-514, Nov. 2002.
• 47: Y. Xia, L. Subramanian, I. Stoica, and S. Kalyanaraman, "One more bit is enough," Jun. 2005, U.C. Berkeley, Tech Report, [Online]. Available: http://networks.ecse.rpi.edu/~xiay/pub/vcp_tr.pdf.
• 48: L. Xu, K. Harfoush, and I. Rhee, "Binary increase congestion control (BIC) for fast long-distance networks," Proc. INFOCOM'04, Mar. 2004.
• 49: Y. R. Yang , S. S. Lam, General AIMD congestion control, Proceedings of the 2000 International Conference on Network Protocols, p.187, November 14-17, 2000
• 50: L. Ying, G. Dullerud, and R. Srikant, "Global stability of Internet congestion controllers with heterogeneous delays," in Proc. Amer. Control Conf., Jun. 2004.
• 51: Yueping Zhang , Seong-Ryong Kang , Dmitri Loguinov, Delayed stability and performance of distributed congestion control, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Management, Performance

Keywords:
AQM, ECN, TCP, congestion control, stability