The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm Matthew Mathis, Jeffrey Semke, Jamshid Mahdavi * <[email protected]> <[email protected]> <[email protected]> Pittsburgh Supercomputing Center Teunis Ott <[email protected]> Bellcore Abstract In this paper, we analyze a performance model for the TCP Congestion Avoidance algorithm. The model pre- dicts the bandwidth of a sustained TCP connection sub- jected to light to moderate packet losses, such as loss caused by network congestion. It assumes that TCP avoids retransmission timeouts and always has suffi- cient receiver window and sender data. The model pre- dicts 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 sev- eral TCP implementations under a range of loss con- ditions and in environments with both drop-tail and RED queuing. The model is also compared to live In- ternet 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 con- gested gateways; this analysis shows strong agreement with prior work in this area. Finally, we present sev- eral important implications about the behavior of the Internet in the presence of high load from diverse user communities. 1 Introduction Traffic dynamics in the Internet are heavily influenced by the behavior of the TCP Congestion Avoidance al- gorithm [Jac88a, Ste97]. This paper investigates an analytical performance model for this algorithm. The model predicts end-to-end TCP performance from prop- erties of the underlying IP path. This paper is a first step at discovering the relationship between end-to-end application performance, as observed by an Internet user, and hop-by-hop IP performance, as might be mon- itored and marketed by an Internet Service Provider. *This work is supported in part by National Science Founda- tion Grant No. NCR-9415552. Our initial inspiration for this work was the "heuris- tic analysis" by Sally Floyd [Flo91]. This paper follows a first principles derivation of the stationary distribution of the congestion window of ideal TCP Congestion Avoidance subject to indepen- dent congestion signals with constant probability. The derivation, by Teunis Ott, was presented at DIMACS [OKM96b] and is available on line [OKM96a]. The full derivation and formal analysis is quite complex and is expected to appear in a future paper. We present a simple approximate derivation of the model, under the assumption that the congestion signal losses are periodic. This arrives at the same mathemat- ical form as the full derivation, although the constant of proportionality is slightly different. This paper is focused on evaluating the model's applicability and im- pact to the Internet. The model applies whenever TCP's performance is determined solely by the Congestion Avoidance algo- rithm (described below). We hypothesize that it ap- plies to nearly all implementations of SACK TCP (TCP with Selective Acknowledgements) [MMFR96] under most normal Internet conditions and to Reno TCP [Jac90, Ste94, Ste97] under more restrictive conditions. To test our hypothesis we examine the performance of the TCP Congestion Avoidance algorithm in three ways. First, we look at several TCP implementations in a simulator, exploring the performance effects of ran- dom packet loss, packet loss due to drop-tail queu- ing, phase effects IF J92], and Random Early Detection (RED) queuing [F J93]. Next, we compare the model to Internet measurements using results from the TReno ("tree-no") [Mat96] user mode performance diagnos- tic. Finally, we compare the model to measurements of packet traces of real TCP implementations. Many of our experiments are conducted with an up- dated version of the FACK TCP [MMg6a], designed for use with Selective Acknowledgements. We call this Forward Acknowledgments with Rate-Halving (FACK- RH) [MMg6b]. Except as noted, the differences between FACK-RH and other TCP implementations do not have significant effects on the results. See Appendix A for more information about FACK-RH. ACM SIGCOMM 67 Computer Communication Reviewcongestion window (packets) 2 I i I I 0 ~ // 0 w W 3_E 2W 2 2 Time ( RTT) Figure 1: TCP window evolution under periodic loss w 2 ZIW~2 Each cycle delivers (T) + ~-~--~j : lip packets and takes W/2 round trip times. 2 The Model The TCP Congestion Avoidance algorithm [Jac88a] drives the steady-state behavior of TCP under condi- tions of light to moderate packet losses. It calls for in- creasing the congestion window by a constant amount on each round trip and for decreasing it by a constant multiplicative factor on each congestion signal. 1 Al- though we assume that congestion is signaled by packet loss, we do not assume that every packet loss is a new congestion signal. For all SACK-based TCPs, multiple losses within one round trip are treated as a single con- gestion signal. This complicates our measurements of congestion signals. We can easily estimate TCP's performance by mak- ing some gross simplifications. Assume that TCP is running over a lossy path which has a constant round trip time (RTT) because it has sufficient bandwidth and low enough total load that it never sustains any queues. For ease of derivation, we approximate random packet loss at constant probability p by assuming that the link delivers approximately 1/p consecutive packets, fol- 1 The window is normally opened at the constant rate of one maximum segment size (MSS) per round trip time (RTT) and halved on each congestion signal. In actual implementations, there are a number of important details to this algorithm. Opening the congestion window at a constant rate is actu- ally implemented by opening the window by small increments on each acknowledgment, such that if every segment is acknowl- edged, the window is opened by one segment per round trip. Let W be the window size in packets. Each acknowledgment adjusts the
View Full Document
Unlocking...