Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-05T09:44:53.989Z Has data issue: false hasContentIssue false
  • English
  • Français

Rate of convergence for the ‘square root formula’ in the Internet transmission control protocol

Part of: Limit theorems Special processes Stochastic processes

Published online by Cambridge University Press:  08 September 2016

Teunis J. Ott
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The ‘square root formula’ in the Internet transmission control protocol (TCP) states that if the probability p of packet loss becomes small and there is independence between packets, then the stationary distribution of the congestion window W is such that the distribution of W√p is almost independent of p and is completely characterizable. This paper gives an elementary proof of the convergence of the stationary distributions for a much wider class of processes that includes classical TCP as well as T. Kelly's ‘scalable TCP’. This paper also gives stochastic dominance results that translate to a rate of convergence.

Keywords

Computer networkingtransport protocolstochastic processsquare root lawstationary distributionstochastic dominancerate of convergencecoupled stochastic processes

MSC classification

Primary: 60F99: None of the above, but in this section 60G10: Stationary processes 60G99: None of the above, but in this section 60K30: Applications (congestion, allocation, storage, traffic, etc.) 60K99: None of the above, but in this section 68U99: None of the above, but in this section
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 38 , Issue 4 , December 2006 , pp. 1132 - 1154
Copyright
Copyright © Applied Probability Trust 2006 

References

Altman, E., Avrachenkov, K. and Barakat, C. (2005). A stochastic model of TCP/IP with stationary random losses. IEEE/ACM Trans. Networking 13, 356–369.Google Scholar
Altman, E., Avrachenkov, K., Barakat, C. and Nunez-Queija, R. (2001). State-dependent M/G/1 type queueing analysis for congestion control in data networks. In Proc. INFOCOM 2001 (Anchorage, AK, April 2001), Vol. 3, pp. 1350–1359.Google Scholar
Altman, E. et al. (2005). Analysis of MIMD congestion control algorithm for high speed networks. Comput. Networks 48, 972–989.CrossRefGoogle Scholar
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.Google Scholar
Dumas, V., Guillemin, F. and Robert, P. (2002). A Markovian analysis of additive-increase, multiplicative-decrease algorithms. Adv. Appl. Prob. 34, 85–111.CrossRefGoogle Scholar
Guillemin, F., Robert, P. and Zwart, B. (2004). AIMD algorithms and exponential functionals. Ann. Appl. Prob. 14, 90–117.CrossRefGoogle Scholar
Kelly, T. (2003). Scalable TCP: improving performance in highspeed wide area networks. Comput. Commun. Rev. 33, 83–91.CrossRefGoogle Scholar
Kelly, T. (2004). Engineering flow controls for the Internet. , University of Cambridge. Available at http://www.deneholme.net/tom/papers.Google Scholar
Lehmann, E. L. (1986). Testing Statistical Hypotheses, 2nd edn. John Wiley, New York.CrossRefGoogle Scholar
Loève, M. (1963). Probability Theory, 3rd edn. Van Nostrand, Princeton, NJ.Google Scholar
Ott, T. J. (2005). Transport protocols in the TCP paradigm and their performance. Telecommun. Systems 30, 351–385. Available at http://www.teunisott.com/Papers.Google Scholar
Ott, T. J. (2006). Rate of convergence for the ‘square root formula’, extended version. Unpublished manuscript. Available at http://www.teunisott.com/Papers.Google Scholar
Ott, T. J. and Swanson, J. (2006). Asymptotic behavior of a generalized TCP congestion avoidance algorithm. Submitted. Available at http://www.teunisott.com/Papers.Google Scholar
Ott, T. J. and Swanson, J. (2006). Stationarity of some processes in transport protocols. To appear in Performance Eval. Rev. Extended version available at http://www.teunisott.com/Papers.Google Scholar
Ott, T. J., Kemperman, J. H. B. and Mathis, M. (1996). The stationary behavior of ideal TCP congestion avoidance. Preprint. Available at http://www.teunisott.com/Papers.Google Scholar
Ott, T. J., Kemperman, J. H. B. and Mathis, M. (2004). The stationary behavior of ideal TCP congestion avoidance, revisited. Unpublished manuscript.Google Scholar
Ramakrishnan, K., Floyd, S. and Black, D. (2001). The addition of explicit congestion notification (ECN) to IP. Internet Engineering Task Force RFC 3168. Available at ftp://ftp.rfc-editor.org/in-notes/rfc3168.txt.Google Scholar