Congestion control for high bandwidth-delay product networks

ABSTRACT

Theory and experiments show that as the per-flow product of bandwidth and latency increases, TCP becomes inefficient and prone to instability, regardless of the queuing scheme. This failing becomes increasingly important as the Internet evolves to incorporate very high-bandwidth optical links and more large-delay satellite links.To address this problem, we develop a novel approach to Internet congestion control that outperforms TCP in conventional environments, and remains efficient, fair, scalable, and stable as the bandwidth-delay product increases. This new eXplicit Control Protocol, XCP, generalizes the Explicit Congestion Notification proposal (ECN). In addition, XCP introduces the new concept of decoupling utilization control from fairness control. This allows a more flexible and analytically tractable protocol design and opens new avenues for service differentiation.Using a control theory framework, we model XCP and demonstrate it is stable and efficient regardless of the link capacity, the round trip delay, and the number of sources. Extensive packet-level simulations show that XCP outperforms TCP in both conventional and high bandwidth-delay environments. Further, XCP achieves fair bandwidth allocation, high utilization, small standing queue size, and near-zero packet drops, with both steady and highly varying traffic. Additionally, the new protocol does not maintain any per-flow state in routers and requires few CPU cycles per packet, which makes it implementable in high-speed routers.

REFERENCES

• 1: The network simulator ns-2. http://www.isi.edu/nsnam/ns.
• 2: Red parameters. http://www.icir.org/floyd/red.html#parameters.
• 3: Yehuda Afek , Yishay Mansour , Zvi Ostfeld, Phantom: a simple and effective flow control scheme, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.169-182, August 28-30, 1996, Palo Alto, California, United States
• 4: M. Allman, D. Glover, and L. Sanchez. Enhancing tcp over satellite channels using standard mechanisms, Jan. 1999.
• 5: S. Athuraliya, V. H. Li, S. H. Low, and Q. Yin. Rem: Active queue management. IEEE Network, 2001.
• 6: D. Bansal and H. Balakrishnan. Binomial congestion control algorithms. In Proc. of IEEE INFOCOM '01, Apr. 2001.
• 7: Deepak Bansal , Hari Balakrishnan , Sally Floyd , Scott Shenker, Dynamic behavior of slowly-responsive congestion control algorithms, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.263-274, August 2001, San Diego, California, United States
• 8: J. Border, M. Kojo, J. Griner, and G. Montenegro. Performance enhancing proxies, Nov. 2000.
• 9: A. Charny. An algorithm for rate allocation in a packet-switching network with feedback, 1994.
• 10: D.-M. Chiu , R. 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]
• 11: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 12: Sally Floyd , Mark Handley , Jitendra Padhye , Jörg Widmer, Equation-based congestion control for unicast applications, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.43-56, August 28-September 01, 2000, Stockholm, Sweden
• 13: 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]
• 14: R. Gibbens and F. Kelly. Distributed connection acceptance control for a connectionless network. In Proc. of the 16th Intl. Telegraffic Congress, June 1999.
• 15: C. Hollot, V. Misra, D. Towsley, , and W. Gong. On designing improved controllers for aqm routers supporting tcp flows. In Proc. of IEEE INFOCOM, Apr. 2001.
• 16: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 17: R. Jain, S. Fahmy, S. Kalyanaraman, and R. Goyal. The erica switch algorithm for abr traffic management in atm networks: Part ii: Requirements and performance evaluation. In The Ohio State University, Department of CIS, Jan. 1997.
• 18: 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]
• 19: D. Katabi and C. Blake. A note on the stability requirements of adaptive virtual queue. MIT Technichal Memo, 2002.
• 20: D. Katabi and M. Handley. Precise feedback for congestion control in the internet. MIT Technical Report, 2001.
• 21: F. Kelly, A. Maulloo, and D. Tan. Rate control for communication networks: shadow prices, proportional fairness and stability.
• 22: 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
• 23: S. H. Low, F. Paganini, J. Wang, S. Adlakha, and J. C. Doyle. Dynamics of tcp/aqm and a scalable control. In Proc. of IEEE INFOCOM, June 2002.
• 24: V. Misra, W. Gong, and D. Towsley. A fluid-based analysis of a network of aqm routers supporting tcp flows with an application to red. Aug. 2000.
• 25: G. Montenegro, S. Dawkins, M. Kojo, V. Magret, and N. Vaidya. Long thin networks, Jan. 2000.
• 26: F. Paganini, J. C. Doyle, and S. H. Low. Scalable laws for stable network congestion control. In IEEE CDC, 2001.
• 27: K. K. Ramakrishnan and S. Floyd. Proposal to add explicit congestion notification (ecn) to ip. RFC 2481, Jan. 1999.
• 28: 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

INDEX TERMS

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

General Terms:
Design, Performance

Keywords:
congestion control, high-speed networks, large bandwidth-delay product