Matthew Mathis
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.
- {B+97} Robert Braden et al. Recommendations on Queue Management and Congestion Avoidance in the Internet, March 1997. Internet draft draft-irtf-e2e-queue-mgt-00.txt (Work in progress). Google Scholar
Digital Library
- {BOP94} Lawrence S. Brakmo, Sean W. O'Malley, and Larry L. Peterson. TCP Vegas: New Techniques for Congestion Detection and Avoidance. Proceedings of ACM SIGCOMM '94, August 1994. Google ScholarDigital Library
- {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.Google Scholar
- {CJ89} D. Chiu and R. Jain. Analysis of the Increase/Decrease Algorithms for Congestion Avoidance in Computer Networks. Journal of Computer Networks and ISDN, 17(1): 1- 14, June 1989. Google ScholarDigital Library
- {Cla96} Dave Clark. Private communication, December 1996. Derivation of Bandwidth vs. Loss.Google Scholar
- {DLY95} Peter B. Danzig, Zhen Liu, and Limim Yan. An Evaluation of TCP Vegas by Live Emulation. ACM SIGMetrics '95, 1995.Google Scholar
- {FF96} Kevin Fall and Sally Floyd. Simulations-Based Comparisons of Tahoe, Reno and SACK TCP. Computer Communications Review, 26(3), July 1996. Google ScholarDigital Library
- {FJ92} Sally Floyd and Van Jacobson. On Traffic Phase Effects in Packet-Switched Gateways. Internetworking: Research and Experience , 3(3): 115-156, September 1992.Google Scholar
- {FJ93} Sally Floyd and Van Jacobson. Random Early Detection Gateways for Congestion Avoidance. IEEE/ACM Transactions on Networking, August 1993. Google ScholarDigital Library
- {Flo91} Sally Floyd. Connections with Multiple Congested Gateways in Packet-Switched Networks, Part 1: One-way Traffic. Computer Communications Review, 21(5), October 1991. Google ScholarDigital Library
- {Flo95} Sally Floyd. TCP and Successive Fast Retransmits, February 1995. Obtain via ftp://ftp.ee.lbl.gov/papers/fastretrans.ps.Google Scholar
- {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.Google Scholar
- {Hoe95} Janey C. Hoe. Startup Dynamics of TCP's Congestion Control and Avoidance Schemes. Master's thesis, Massachusetts Institute of Technology, June 1995.Google Scholar
- {Hoe96} Janey C. Hoe. Improving the Start-up Behavior of a Congestion Control Scheme for TCP. Proceedings of ACM SIGCOMM '96, August 1996. Google ScholarDigital Library
- {Jac88a} Van Jacobson. Congestion Avoidance and Control. Proceedings of ACM SIGCOMM '88, August 1988. Google ScholarDigital Library
- {Jac88b} Van Jacobson. Traceroute Source Code, 1988. Obtain via ftp from ftp.ee.lbl.gov.Google Scholar
- {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.Google Scholar
- {JB88} Van Jacobson and Robert Braden. TCP Extensions for Long-Delay Paths, October 1988. Request for Comments 1072.Google Scholar
- {JBB92} Van Jacobson, Robert Braden, and Dave Borman. TCP Extensions for High Performance, May 1992. Request for Comments 1323.Google Scholar
- {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.Google Scholar
- {Mat94a} Matthew Mathis. Private communication, November 1994. Derivation of Bandwidth vs. Loss.Google Scholar
- {Mat94b} Matthew B. Mathis. Windowed Ping: An IP Layer Performance Diagnostic. Proceedings of INET'94/JENC5, 2, June 1994. Google ScholarDigital Library
- {Mat96} Matthew Mathis. Diagnosing Internet Congestion with a Transport Layer Performance Tool. Proceedings of INET'96, June 1996.Google Scholar
- {Mat97} Matthew Mathis. Internet Performance and IP Provider Metrics information page. Obtain via http://www.psc.edu/~mathis/ ippm/, 1997.Google Scholar
- {MF95} Steven McCanne and Sally Floyd. ns-LBL Network Simulator. Obtain via: http://www-nrg.ee.lbl.gov/ns/, 1995.Google Scholar
- {MM96a} Matthew Mathis and Jamshid Mahdavi. Forward Acknowledgment: Refining TCP Congestion Control. Proceedings of ACM SIGCOMM '96, August 1996. Google ScholarDigital Library
- {MM96b} Matthew Mathis and Jamshid Mahdavi. TCP Rate-Halving with Bounding Parameters, October 1996. Obtain via: http://www.psc.edu/networking/papers/FACKnotes/current/.Google Scholar
- {MMFR96} Matthew Mathis, Jamshid Mahdavi, Sally Floyd, and Allyn Romanow. TCP Selective Acknowledgement Options, October 1996. Request for Comments 2018.Google Scholar
- {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.Google Scholar
- {OKM96b} Teunis J. Ott, J. H. B. Kemperman, and Matt Mathis. Window Size Behavior in TCP/IP with Constant Loss Probability, November 1996.Google Scholar
- {Ost96} Shawn Ostermann. tcptrace TCP dump-file analysis tool. Obtain via http://jarok.cs.ohiou.edu/software/tcptrace/tcptrace.html, 1996.Google Scholar
- {Pax97a} Vern Paxson. Automated Packet Trace Analysis of TCP Implementations. Proceedings of ACM SIGCOMM '97, August 1997. Google ScholarDigital Library
- {Pax97b} Vern Paxson. Measurements and Analysis of End-to-End Internet Dynamics. PhD thesis, University of California, Berkeley, April 1997.Google ScholarDigital Library
- {Ste94} W. Richard Stevens. TCP/IP Illustrated, volume 1. Addison-Wesley, Reading MA, 1994.Google Scholar
- {Ste97} W. Richard Stevens. TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms, January 1997. Request for Comments 2001.Google Scholar
Index Terms
- The macroscopic behavior of the TCP congestion avoidance algorithm
Recommendations
Delay-based congestion avoidance for TCP
The set of TCP congestion control algorithms associated with TCP/Reno (e.g., slow-start and congestion avoidance) have been crucial to ensuring the stability of the Internet. Algorithms such as TCP/NewReno (which has been deployed) and TCP/Vegas (which ...
Delay-based TCP congestion avoidance: A network calculus interpretation and performance improvements
In delay-based TCP congestion avoidance mechanisms, a source adjusts its window size to adapt to changes in network conditions as measured through changing queueing delays. Although network calculus (NC) has been used to study window flow control and ...
Comments