The macroscopic behavior of the TCP congestion avoidance algorithm

ABSTRACT

In this paper, we analyze a performance model for the TCP Congestion Avoidance algorithm. The model predicts the bandwidth of a sustained TCP connection subjected to light to moderate packet losses, such as loss caused by network congestion. It assumes that TCP avoids retransmission timeouts and always has sufficient receiver window and sender data. The model predicts the Congestion Avoidance performance of nearly all TCP implementations under restricted conditions and of TCP with Selective Acknowledgements over a much wider range of Internet conditions.We verify the model through both simulation and live Internet measurements. The simulations test several TCP implementations under a range of loss conditions and in environments with both drop-tail and RED queuing. The model is also compared to live Internet measurements using the TReno diagnostic and real TCP implementations.We also present several applications of the model to problems of bandwidth allocation in the Internet. We use the model to analyze networks with multiple congested gateways; this analysis shows strong agreement with prior work in this area. Finally, we present several important implications about the behavior of the Internet in the presence of high load from diverse user communities.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	B. Braden , D. Clark , J. Crowcroft , B. Davie , S. Deering , D. Estrin , S. Floyd , V. Jacobson , G. Minshall , C. Partridge , L. Peterson , K. Ramakrishnan , S. Shenker , J. Wroclawski , L. Zhang, Recommendations on Queue Management and Congestion Avoidance in the Internet, RFC Editor, 1998
	2	Lawrence S. Brakmo , Sean W. O'Malley , Larry L. Peterson, TCP Vegas: new techniques for congestion detection and avoidance, Proceedings of the conference on Communications architectures, protocols and applications, p.24-35, August 31-September 02, 1994, London, United Kingdom
	3	[CH95] David D. Clark and Janey C. Hoe. Start-up Dynamics of TCP's Congestion Control and Avoidance Schemes. Technical report, Internet End-to-End Research Group, 1995. Presentation. Cited for acknowledgement purposes only.
	4	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]
	5	[Cla96] Dave Clark. Private communication, December 1996. Derivation of Bandwidth vs. Loss.
	6	[DLY95] Peter B. Danzig, Zhen Liu, and Limim Yan. An Evaluation of TCP Vegas by Live Emulation. ACM SIGMetrics '95, 1995.
	7	Kevin Fall , Sally Floyd, Simulation-based comparisons of Tahoe, Reno and SACK TCP, ACM SIGCOMM Computer Communication Review, v.26 n.3, p.5-21, July 1996 [doi>10.1145/235160.235162]
	8	[FJ92] Sally Floyd and Van Jacobson. On Traffic Phase Effects in Packet-Switched Gateways. Internetworking: Research and Experience , 3(3): 115-156, September 1992.
	9	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]
	10	Sally Floyd, Connections with multiple congested gateways in packet-switched networks part 1: one-way traffic, ACM SIGCOMM Computer Communication Review, v.21 n.5, p.30-47, Oct. 1991 [doi>10.1145/122431.122434]
	11	[Flo95] Sally Floyd. TCP and Successive Fast Retransmits, February 1995. Obtain via ftp://ftp.ee.lbl.gov/papers/fastretrans.ps.
	12	[Flo96] Sally Floyd. SACK TCP: The sender's congestion control algorithms for the implementation sackl in LBNL's ns simulator (viewgraphs). Technical report, TCP Large Windows Working Group of the IETF, March 1996. Obtain via ftp://ftp.ee.lbl.gov/talks/sacks.ps.
	13	[Hoe95] Janey C. Hoe. Startup Dynamics of TCP's Congestion Control and Avoidance Schemes. Master's thesis, Massachusetts Institute of Technology, June 1995.
	14	Janey C. Hoe, Improving the start-up behavior of a congestion control scheme for TCP, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.270-280, August 28-30, 1996, Palo Alto, California, United States
	15	V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
	16	[Jac88b] Van Jacobson. Traceroute Source Code, 1988. Obtain via ftp from ftp.ee.lbl.gov.
	17	[Jac90] Van Jacobson. Modified TCP Congestion Avoidance Algorithm. Email to end2end- interest Mailing List, April 1990. Obtain via ftp://ftp.ee.lbl.gov/email/ vanj.90apr30.txt.
	18	V. Jacobson , R. T. Braden, TCP extensions for long-delay paths, RFC Editor, 1988
	19	V. Jacobson , R. Braden , D. Borman, TCP Extensions for High Performance, RFC Editor, 1992
	20	[LM94] T. V. Lakshman and U. Madhow. The Performance of TCP/IP for Networks with High Bandwidth-Delay Products and Random Loss. IFIP Transactions C-26, High Performance Networking, pages 135-150, 1994.
	21	[Mat94a] Matthew Mathis. Private communication, November 1994. Derivation of Bandwidth vs. Loss.
	22	Matthew Mathis, Windowed ping: an IP layer performance diagnostic, Selected papers of the annual conference on Internet Society/5th joint European networking conference, p.449-459, December 1994, Prague, Czech Republic
	23	[Mat96] Matthew Mathis. Diagnosing Internet Congestion with a Transport Layer Performance Tool. Proceedings of INET'96, June 1996.
	24	[Mat97] Matthew Mathis. Internet Performance and IP Provider Metrics information page. Obtain via http://www.psc.edu/~mathis/ ippm/, 1997.
	25	[MF95] Steven McCanne and Sally Floyd. ns-LBL Network Simulator. Obtain via: http://www-nrg.ee.lbl.gov/ns/, 1995.
	26	Matthew Mathis , Jamshid Mahdavi, Forward acknowledgement: refining TCP congestion control, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.281-291, August 28-30, 1996, Palo Alto, California, United States
	27	[MM96b] Matthew Mathis and Jamshid Mahdavi. TCP Rate-Halving with Bounding Parameters, October 1996. Obtain via: http://www.psc.edu/networking/papers/FACKnotes/current/.
	28	[MMFR96] Matthew Mathis, Jamshid Mahdavi, Sally Floyd, and Allyn Romanow. TCP Selective Acknowledgement Options, October 1996. Request for Comments 2018.
	29	[OKM96a] Teunis Ott, J. H. B. Kemperman, and Matt Mathis. The Stationary Behavior of Ideal TCP Congestion Avoidance. In progress, August 1996. Obtain via pub/tjo/TCPwindow.ps using anonymous ftp to ftp.bellcore.com, See also [OKM96b]., August 1996.
	30	[OKM96b] Teunis J. Ott, J. H. B. Kemperman, and Matt Mathis. Window Size Behavior in TCP/IP with Constant Loss Probability, November 1996.
	31	[Ost96] Shawn Ostermann. tcptrace TCP dump-file analysis tool. Obtain via http://jarok.cs.ohiou.edu/software/tcptrace/tcptrace.html, 1996.
	32	Vern Paxson, Automated packet trace analysis of TCP implementations, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.167-179, September 14-18, 1997, Cannes, France
	33	[Pax97b] Vern Paxson. Measurements and Analysis of End-to-End Internet Dynamics. PhD thesis, University of California, Berkeley, April 1997.
	34	[Ste94] W. Richard Stevens. TCP/IP Illustrated, volume 1. Addison-Wesley, Reading MA, 1994.
	35	[Ste97] W. Richard Stevens. TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms, January 1997. Request for Comments 2001.