article

CYRF: a theory of window-based unicast congestion control

Authors:

Nishanth R. Sastry,

Simon S. LamAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 13, Issue 2

Pages 330 - 342

https://doi.org/10.1109/TNET.2005.845545

Published: 01 April 2005 Publication History

Abstract

This work presents a comprehensive theoretical framework for memoryless window-based congestion control protocols that are designed to converge to fairness and efficiency. We first derive a necessary and sufficient condition for stepwise convergence to fairness. Using this, we show how fair window increase/decrease policies can be constructed from suitable pairs of monotonically nondecreasing functions. We generalize this to smooth protocols that converge over each congestion epoch. The framework also includes a simple method for incorporating TCP-friendliness.Well-studied congestion control protocols such as TCP, GAIMD, and Binomial congestion control can be constructed using this method. Thus, we provide a common framework for the analysis of such window-based protocols. We also present two new congestion control protocols for streaming media-like applications as examples of protocol design in this framework: The first protocol, LOG, has the objective of reconciling the smoothness requirement of an application with the need for a fast dynamic response to congestion.The second protocol, SIGMOID, guarantees a minimum bandwidth for an application but behaves exactly like TCP for large windows.

References

[1]

{1} M. Allman, V. Paxson, and W. Stevens, "TCP congestion control," Internet Engineering Task Force, RFC 2581 (Standards Track), Apr. 1999.]]

[2]

{2} D. Bansal and H. Balakrishnan, "Binomial congestion control algorithms," in Proc. IEEE INFOCOM, Apr. 2001, pp. 631-640.]]

[3]

{3} D. Bansal, H. Balakrishnan, S. Floyd, and S. Shenker, "Dynamic behavior of slowly responsive congestion control algorithms," in Proc. ACM SIGCOMM, San Diego, CA, Aug. 2001, pp. 263-273.]]

[4]

{4} B. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin, and S. Floyd, "Recommendations on queue management and congestion avoidance in the Internet," Internet Engineering Task Force, RFC 2309 (Informational), Apr. 1998.]]

[5]

{5} D.-M. Chiu and R. Jain, "Analysis of the increase and decrease algorithms for congestion avoidance in computer networks," Comput. Netw. ISDN Syst., vol. 17, pp. 1-14, 1989.]]

[6]

{6} J. Crowcroft and P. Oechslin, "Differentiated end-to-end Internet services using a weighted proportional fair sharing TCP," ACM Comput. Commun. Rev., vol. 28, no. 3, pp. 53-67, Jul. 1998.]]

[7]

{7} S. Floyd, M. Handley, and J. Padhye. (2000, May) A comparison of equation-based and AIMD congestion control. {Online}. Available: http://www.aciri.org/tfrc]]

[8]

{8} S. Floyd, M. Handley, J. Padhye, and J. Widmer, "Equation-based congestion control for unicast applications," in Proc. ACM SIGCOMM, Aug. 2000, pp. 43-56. Extended version available as International Computer Science Institute Tech. Report TR-00-03, Mar. 2000.]]

[9]

{9} V. Jacobson and M. Karels, "Congestion avoidance and control," ACM Comput. Commun. Rev., vol. 18, no. 4, pp. 314-329, Aug. 1990. Revised version of an ACM Sigcomm'88 paper.]]

[10]

{10} R. Jain, D.-M. Chiu, and W. Hawe, "A quantitative measure of fairness and discrimination for resource allocation in shared computer systems," Digital Equipment Corporation, DEC Research Report, Tech. Rep. TR-301, Sep. 1984.]]

[11]

{11} R. Jain, K. K. Ramakrishnan, and D.-M. Chiu, "Congestion avoidance in computer networks with a connectionless network layer," Digital Equipment Corporation, Tech. Rep. DEC-TR-506, 1988. Reprinted in Innovations in Internetworking, C. Partridge, Ed. Norwood, MA: Artech House, 1988.]]

[12]

{12} S. Jin, L. Guo, I. Matta, and A. Bestavros, "TCP-friendly SIMD congestion control and its convergence behavior," in Proc. 9th IEEE Int. Conf. Network Protocols (ICNP), Nov. 2001, pp. 156-164.]]

[13]

{13} L. Kalampoukas, A. Varma, and K. K. Ramakrishnan, "Explicit window adaptation: a method to enhance TCP performance," in Proc. IEEE INFOCOM, San Francisco, CA, Mar./Apr. 1998, pp. 242-251.]]

[14]

{14} R. Mahajan and S. Floyd, "Controlling high-bandwidth flows at the congested router," in Proc. 9th IEEE Int. Conf. Network Protocols (ICNP), Nov. 2001, pp. 192-201.]]

[15]

{15} J. Mahdavi and S. Floyd. (1997, Jan.) TCP-friendly unicast rate-based flow control. {Online}. Available: http://www.psc.edu/networking/papers/tcp_friendly.html]]

[16]

{16} J. Mahdavi and S. Floyd. (1999, Jun.) The TCP-friendly web-site. {On-line}. Available: http://www.psc.edu/networking/tcp_ friendly.html]]

[17]

{17} K. K. Ramakrishnan, S. Floyd, and D. Black, "The addition of Explicit Congestion Notification (ECN) to IP," Internet Engineering Task Force, RFC 3168 (Standards Track), Sep. 2001.]]

[18]

{18} K. K. Ramakrishnan and R. Jain, "A binary feedback scheme for congestion avoidance in computer networks," ACM Trans. Comput. Syst., vol. 8, no. 2, pp. 158-181, May 1990.]]

[19]

{19} R. Rejaie, M. Handley, and D. Estrin, "Quality adaptation for unicast audio and video," in Proc. ACM SIGCOMM, Sep. 1999, pp. 189-200.]]

[20]

{20} R. Rejaie, M. Handley, and D. Estrin, "RAP: an end-to-end rate-based congestion control mechanism for realtime streams in the Internet," in Proc. IEEE INFOCOM, Mar. 1999, pp. 1337-1345.]]

[21]

{21} I. Rhee, V. Ozdemir, and Y. Yi, "TEAR: TCP Emulation at Receivers--Flow Control for Multimedia Streaming," North Carolina State Univ., Raleigh, NC, Technical Report, Apr. 2000.]]

[22]

{22} D. Sisalem and H. Schulzrinne, "The loss-delay based adjustment algorithm: a TCP-friendly adaptation scheme," presented at the 8th Int. Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV), Cambridge, U.K., 1998.]]

[23]

{23} G. Wright and W. R. Stevens, TCP/IP Illustrated, Volume 2: The Implementation. Reading, MA: Addison Wesley, 1995.]]

[24]

{24} Y. R. Yang, M. S. Kim, and S. S. Lam, "Transient behaviors of TCP-friendly congestion control protocols," in Proc. IEEE INFOCOM, Anchorage,AK, Apr. 2001, pp. 1716-1725.]]

[25]

{25} Y. R. Yang and S. S. Lam, "General AIMD congestion control," in Proc. 8th IEEE Int. Conf. Network Protocols, Osaka, Japan, Nov. 2000, pp. 187-198.]]

Cited By

Barbera MLombardo APanarello CSchembra G(2010)Queue stability analysis and performance evaluation of a TCP-compliant window management mechanismIEEE/ACM Transactions on Networking10.1109/TNET.2010.204062818:4(1275-1288)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1109/TNET.2010.2040628
Tayel MTaha A(2008)Effect of TCP and UDP parameters on the quality of video streaming delivery over the internetWSEAS TRANSACTIONS on COMMUNICATIONS10.5555/1456091.14561047:6(653-662)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.5555/1456091.1456104
Zhu PZeng WLi C(2007)Cross-layer design of source rate control and congestion control for wireless video streamingAdvances in Multimedia10.1155/2007/685022007:1(3-3)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.1155/2007/68502
Show More Cited By

Index Terms

CYRF: a theory of window-based unicast congestion control
1. Networks
  1. Network protocols
    1. Network protocol design
    2. Transport protocols
  2. Network types
    1. Public Internet

Recommendations

Fair multicast congestion control (M2C)
INFOCOM'09: Proceedings of the 28th IEEE international conference on Computer Communications Workshops

We propose a new TCP-friendly multicast congestion control for very large groups of receivers. This protocol named M2C is layered and receiver-driven. Like TCP, M2C is composed of a Congestion Avoidance and a Slow Start state. However, M2C can re-...
A spectrum of TCP-friendly window-based congestion control algorithms

The increasing diversity of Internet application requirements has spurred recent interest in transport protocols with flexible transmission controls. In window-based congestion control schemes, increase rules determine how to probe available bandwidth, ...
ECN-capable TCP-friendly Layered Multicast Multimedia Delivery
UKSIM '09: Proceedings of the UKSim 2009: 11th International Conference on Computer Modelling and Simulation

ECN-capable TCP-friendly layered multicast mul-timedia delivery combines explicit congestion notifica-tion (ECN) with the TCP-friendly layered multicast scheme. TCP-Friendliness denotes that receiver–driven architecture behaves under congestion like the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 13, Issue 2

April 2005

238 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 April 2005

Published in TON Volume 13, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
357
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Barbera MLombardo APanarello CSchembra G(2010)Queue stability analysis and performance evaluation of a TCP-compliant window management mechanismIEEE/ACM Transactions on Networking10.1109/TNET.2010.204062818:4(1275-1288)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1109/TNET.2010.2040628
Tayel MTaha A(2008)Effect of TCP and UDP parameters on the quality of video streaming delivery over the internetWSEAS TRANSACTIONS on COMMUNICATIONS10.5555/1456091.14561047:6(653-662)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.5555/1456091.1456104
Zhu PZeng WLi C(2007)Cross-layer design of source rate control and congestion control for wireless video streamingAdvances in Multimedia10.1155/2007/685022007:1(3-3)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.1155/2007/68502
Chen CLi ZSoh Y(2007)MRFIEEE/ACM Transactions on Networking10.1109/TNET.2007.89323115:3(697-708)Online publication date: 1-Jun-2007
https://dl.acm.org/doi/10.1109/TNET.2007.893231
Chen CLi ZSoh Y(2007)Analysis of monotonic responsive functions for congestion controlProceedings of the 13th International conference on Multimedia Modeling - Volume Part II10.1007/978-3-540-69429-8_39(383-392)Online publication date: 9-Jan-2007
https://dl.acm.org/doi/10.1007/978-3-540-69429-8_39
Peng MJagannathan SSubramanya S(2006)Rate-based end-to-end congestion control of multimedia traffic in packet switched networksJournal of High Speed Networks10.5555/2692151.269215415:4(357-378)Online publication date: 1-Oct-2006
https://dl.acm.org/doi/10.5555/2692151.2692154

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents