INTERNET-DRAFT Amy S. Hughes, Joe Touch, John Heidemann draft-hughes-restart-00.txt ISI Dec. 1, 2001 Expires: Jun. 1, 2002 Issues in TCP Slow-Start Restart After Idle Status of this Memo This document is an Internet-Draft and is NOT offered in accordance with Section 10 of RFC2026, and the author does not provide the IETF with any rights other than to publish as an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html The distribution of this document is unlimited. Abstract This draft discusses variations in the TCP 'slow-start restart' (SSR) algorithm, and the unintended failure of some variations to properly restart in some environments. SSR is intended to avoid line-rate bursts after idle periods, where TCP accumulates permission to send in the form of ACKs, but does not consume that permission immediately. SSR's original "restart after send is idle" is commonly implemented as "restart after receive is idle". The latter unintentionally fails to restart for bidirectional connections where the sender's burst is triggered by a reverse-path data packet, such as in persistent HTTP. Both the former and latter are shown to permit bursts in other circumstances. Several solutions are discussed, and their implementations evaluated. This document updates draft-ietf-tcpimpl-restart-01.txt. It is a product of the LSAM, X-Bone, and DynaBone projects at ISI. Comments are solicited and should be addressed to the authors. Expires Jun. 1, 2002 [Page 1]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 Introduction Slow-Start Restart (SSR) describes one TCP behavior to respond to long sending pauses in an open connection. When a sender becomes idle, the normal ACK-clocking mechanism which regulates traffic is no longer present and the sender may introduce a burst of packets into the network as large as the current congestion window (CWND). Such a burst may be too large for the intermediate routers to handle and may be too large for the receiver to handle at one time as well. A send timer was first proposed [JK92] to detect idle sending periods; the recommended response is to close the congestion window and perform a new slow-start. However, a footnote to this first proposed solution noted that send/receive symmetry on the channel meant that a receive timer could be used instead to achieve the same results. As this second solution takes advantage of a timer that is already required (to detect packet loss) it was implemented by Jacobson and Karels. This solution has been repeated in implementations which derive from their work. Bursty connections, such as the persistent connections required in HTTP/1.1 [FGMFB97] have been found to interact in meaningful ways with SSR [Hei97]. In fact, it was discovered that SSR never occurs with HTTP/1.1 [Poo97]. This is because a new request will reset the receive timer (as suggested in the footnote in [JK92]) and the sending pause will not be detected [Tou97]. Further, both timer solutions depend on the retransmit timeout (RTO) and cannot detect send pauses that are shorter than this duration. In such cases, the sender may transmit a burst as large as the full congestion window. Burst Detection. There are several ways of determining whether a connection is at risk of sending a burst of packets into the channel. We will discuss each method below, from the least radical to the most radical. Receive Timer: The use of a receive timer is the most common burst detection method. It is attractive because it is simple and makes use of an existing timer. However, a receive timer does not properly detect bursts in HTTP/1.1 because the timer is cancelled when the request packet is received. Further, when the connection is idle for less than a full RTO, a burst cannot be detected. Such a burst can happen when the connection is "nearly idle" or when ACKs are lost or reordered. Expires Jun. 1, 2002 [Page 2]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 Send Timer: A send timer is the reciprocal solution to using a receive timer. While it requires a new timestamp field to be maintained, it clearly detects send pauses and corrects the problem presented by HTTP/1.1. However, as with the receive timer, it cannot detect bursts that could happen before a full RTO. Packet Counting: An alternative method examines the unused portion of the congestion window to determine if the capacity to burst exists. This method is simple, it uses existing information to make its decision, and it solves both the HTTP/1.1. problem as well as the RTO problem. In addition, it addresses the problem that needs to be solved (bursts) instead of a specific circumstance where the problem could happen (send pauses). However, where timer detection avoids defining a burst (it defines idle periods instead), here a burst must be defined before it can be detected. One possible definition is the situation where the available portion of the sending window is some proportion of the entire congestion window, say 50%. Another definition places a numerical limit on the available portion of the congestion window, say 4 or CWND-1 packets. Burst Response Once a burst is detected, there are several different ways to take action. The different possibilities are listed below, again from least to most radical. Full Restart: Reducing the congestion window to one packet and re-entering slow- start, the original slow-start restart, is one response. This was the solution proposed by Jacobson and Karels. This is a very conservative response and it defeats most of the speedup that HTTP/1.1 provides [HOT97]. Current proposals [FAP97] have suggested increasing the initial window from 1 packet to 4 packets. Further, depending on the method of burst detection, Full Restart can be far more punitive than it should be. Coupled with a timer, full restart is most likely to respond to a completely empty congestion window. Coupled with Packet Counting, the response could close the window too far, even smaller than the amount of outstanding data. Window Limiting: This is a modified version of Full Restart which solves the problem created by using Packet Counting to detect bursts. With this type of Expires Jun. 1, 2002 [Page 3]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 response, the congestion window is reduced to the amount of outstanding data plus the slow-start initial window (1, 2, or 4). It works exactly like Full Restart in the idle case, but is successful at controlling bursts in an active connection. Further, in an active connection, it effectively implements a leaky bucket of the initial window size for the accumulation of send opportunity based on the receipt of ACKs. This solution is fairly conservative, especially as it defaults to Full Restart, but more importantly, sending opportunity is simply lost if not used, and is not available for paced output. Also, it forces negative congestion feedback on the congestion window. Burst Size Limitation: When a burst is detected, its effects are limited, the sender may not send any more than a preset number of packets into the network. This is less conservative than the first two responses in that it does not affect the size of the congestion window, and it is simple to implement, simply count up the number of packets you can send and stop when you reach the limit. The burst count is reset according to some policy, such as when ACKs are received, each time send is called, or when some timer triggers. The behavior is determined by how these parameters are combined to reset the count. Pacing: When a burst is detected, packets are periodically sent into the network until the sender starts receiving acks and normal maintenance can be resumed [VH97,PK98]. This solution is very easy on the network and scales well in cases of high bw/delay. However, it requires a new timer and additional research for parameter tuning. Implemented Solutions Now we will examine combinations of the different detection and response methods presented above. Each of the solutions below have been implemented in some form. BSD Implementation (Jacobson and Karels) The most common implementation uses a receive timer coupled with Full Restart. This is the implementation that causes the interaction problems with HTTP/1.1. The obvious alternative is to implement a send timer as originally intended and use Full Restart. There are several drawbacks to this solution. First, a send timer adds additional state and serves no purpose other than to correct the bursting behavior after send pauses. Second, forcing a slow-start in this situation is problematic for HTTP/1.1. A slow-start for each Expires Jun. 1, 2002 [Page 4]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 new user request adds a delay burden to characteristically small HTTP responses. Further, the HTTP user request pattern is unpredictable. It is possible for the user to make a new request before the send timer expires, triggering a burst that would defeat such a timer. Maximum Burst Limitation (Floyd) Floyd has proposed a coupling of Packet Counting with Burst Size Limitation. It was developed to avoid bursts caused by gaps in the ACK stream. Such gaps cause the send window to slide forward in jumps, rather than smoothly by 1-2 MTUs; subsequent send calls can thus generate bursts. This solution has been implemented in "ns" and it prevents the sender from transmitting a series of back-to-back packets larger than the user configured burst limit (suggested to be 5 packets) [NS97]. Maxburst defines a new function, send_much, with a parameter, maxburst, which is called every time an external event occurs, such as ACK is received or a timeout occurs. Each time send_much is called, at most maxburst packets are emitted. This forces interleaved processing of ACKs and sending of data. Sends initiated by the arrival of data in the buffer are not affected; as a result, if there is less than RTO of delay, and the send buffer is filled by the application, Maxburst can still send a burst the size of an entire window. Maxburst does not explicitly address the sending of bursts after an idle period; it relies on the existing mechanism to collapse CWND after an RTO, because send_much does not replace send as the application interface to transmitting data. The limit of 5 packets is designed to allow non-sequental ACK losses, and allow the CWND to grow normally under slow-start. Here is a list of the possible burst limits, and the need for each: 1 packet per ACK or nothing gets done 2 packets per ACK if ACKs are compressed 3 packets during window growth; 2 for the compressed ACK, 1 for the growth 4 packets per ACK received if ACKs are lost (not back-to-back), and ACKs are compressed 5 packets per ACK received if ACKs are lost (not back-to-back), ACKs are compressed, and the window is growing Expires Jun. 1, 2002 [Page 5]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 Use it or lose it (UI/LI) (Hughes, Touch, and Heidemann) One proposed solution combines Packet Counting with Window Limiting, and the IETF community refers to it as "Use-It-or-Lose-It" (it was originally called Congestion Window Monitoring, CWM, but we will use the acronym UI/LI, pronounced 'wee-lee', here). Whenever (CWND - outstanding data > 4), we reduce CWND to (outstanding data + 4). The choice of 4 packets is discussed in with the implementation details below. UI/LI allows the congestion window to grow normally but shrinks the congestion window as the sender becomes idle. It also prevents the sender from transmitting any bursts larger than 4 packets in response to a new request. Because UI/LI is not dependent on any timers, the loss of an ACK or a nearly idle connection cannot cause any bursts. UI/LI is similar to Maxburst, but avoids the burst by reducing CWND, rather than by inhibiting the sends directly. As a result, we avoid the potential problem of sequential calls to "tcp_output", which would cause bursts in Maxburst. UI/LI also causes TCP to use the feedback of 'not using the CWND fast enough', which results in a decrease in the CWND. UI/LI effectively imposes a leaky bucket type limitation on the congestion window. The window is allowed to grow and be managed normally but the sender is not allowed to save up any sending opportunities. Any opportunity that is not used is lost. This property of UI/LI forces interleaved reception of ACKs and processing of sends. Burst-or-lose (Touch, Floyd) We have considered a modified version of Maxburst, in which all sends, including those initiated by data arrival from the application, limit their burst size each time they are called, and reset their flag at that time. We call this burst-or-lose (BOL). The result is very similar to UI/LI, but the bucket reflects only the permission to send created as the result of an ACK receipt, rather than the overall limit of the congestion window. In this case, it is unncessary to collapse CWND after an RTO. The primary reason for the collapse is to avoid bursts; BOL avoids bursts completely, but recovers as quickly as the ACK clocking can be restored. In the case when there is no data to send, multiple ACK arrivals do not increase the bucket available for sending. This avoids the bursts after idle periods. In the case when ACKs are lost, the remaining ACK generates permission to send only a fixed amount of data. The application cannot defeat this bucket by calling send multiple times. Expires Jun. 1, 2002 [Page 6]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 Rate Based Pacing (Visweswaraiah and Heidemann) Rate Based Pacing (RBP) combines the Pacing response with either a Send Timer or Packet Counting. It avoids slow-start when resuming after sending pauses and allows the normal clocking of packets to be gracefully restarted. When a burst potential is detected, the algorithm meters a small burst of packets into the channel [VH97]. RBP is the least conservative solution to the bursting problem because it continues to make use of the pre-pause congestion window. If network conditions have changed significantly, maintaining the previous window could cause the paced connection to be overly aggressive as compared to other connections. (Although some work suggests congestion windows are stable over multi-minute timeframes [BSSK97].) More recently pacing has been suggested for use in wireless networking scenarios [BPK97], and for satellite connections. Solution Comparison Below we present a comparison of the solutions presented above, plus the original Send Timer solution. The Send Timer solution is not in use, but we implemented it in FreeBSD for comparison purposes. We contrast each solution on four criteria. A "yes" in the "HTTP Burst" column indicates that this solution will solve the bursting problem created by HTTP/1.1. A "yes" in the "Other Burst" column indicates that the solution will prevent bursts in other situations as well. A "yes" in the "Adj CWND" column indicates that the solution involves adjusting the value of CWND. The final column, "Code Size", gives the number of lines of code needed to correctly implement the solution. | | HTTP Burst Other Burst Adj CWND Code Size -----------+------------------------------------------------- Send Timer | yes no yes ~5 lines -----------+------------------------------------------------- Rcv Timer | no no yes 3 lines -----------+------------------------------------------------- Maxburst | yes yes no ~5 lines -----------+------------------------------------------------- UI/LI | yes yes yes 3 lines -----------+------------------------------------------------- BOL | yes yes no ~5 lines -----------+------------------------------------------------- RBP | yes yes no ~30 lines Expires Jun. 1, 2002 [Page 7]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 There are other conditions under which to compare these algorithms, including behavior after a single ACK loss, behavior after multiple ACK losses (sequential and non-sequential), and the window regrowth proper- ties. These are outside the scope of this document. | | Recovery rate -----------+------------------------------------------------- Send Timer | SS then CA -----------+------------------------------------------------- Rcv Timer | SS then CA -----------+------------------------------------------------- Maxburst | (not applicable) -----------+------------------------------------------------- UI/LI | SS and or CA, depending on SSTHRESH -----------+------------------------------------------------- BOL | (not applicable) -----------+------------------------------------------------- RBP | 1 RTT The only significant difference between UI/LI and BOL is whether CWND is affected, and thus the recovery period after the loss of an ACK. UI/LI interprets ACK loss as an event warranting traditional TCP window recov- ery, whereas BOL and Maxburst do not. Both UI/LI and BOL avoid the need for idle detection for the purpose of CWND adjustment, and implement a type of leaky bucket. Although UI/LI was intended as a type of leaky- bucket system, BOL is much more directly analogous. Experimental Comparisons Packet traces of the current FreeBSD implementation of SSR (using the receive timer), of a modified version of FreeBSD using a send timer, and of UI/LI with HTTP/1.1 support the above observations. The graphs below show traces of two HTTP/1.1 requests. The first request opens the CWND. How the server responds to the packet containing the second request reveals the differences between implementations. The first graph shows the trace with FreeBSD v2.2.6, but the relevant portions of the code have not been altered in more current releases. In response to the first request, the server performs slow-start normally. After 10 seconds, and after the retransmission timeout (RTO), the second request arrives. At this point, receipt of the second request resets the receive timer. The server, under the belief that communication has not gone idle, sends a CWND-sized burst of packets into the network. Expires Jun. 1, 2002 [Page 8]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 Idle trace with Receive Timer sequence number (in bytes) +------+-------+------+-------+------+-------+------+D-A---+ + + + + + + + DDAA | 100000 ++ Client_ACK A DDAA ++ | Client_SEG C D A A | | Server_SEG D D A | 80000 ++ D A ++ | D A | | D | 60000 ++ D AA D ++ | D A | | D A | | D ADDAA | 40000 ++ D A ++ | D A | | D AAD A | 20000 ++ D A ++ | D A A | + +D AAD A+ + + + + + | 0 ++A-D-A+-------+------+-------+------+-C-----+------+-----++ 0 2 4 6 8 10 12 14 time since first SYN (in seconds) The second graph shows the trace with FreeBSD v2.2.6 altered to use a send timer to detect idle communication. As expected, the server responds to the first request with normal slow-start. Now, the receipt of the second request comes in after the RTO and the idle period is cor- rectly detected. In response, the server re-enters slow-start for the second response. Expires Jun. 1, 2002 [Page 9]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 Idle trace with Send Timer sequence number (in bytes) +-------------+-------------+------------+-------------+DAAA + + + + D AAAA| 100000 ++ Client_ACK A DADA ++ | Client_SEG C DA A | | Server_SEG D D AAD | 80000 ++ DAAA ++ | D AAD | | D AAD | 60000 ++ D AA D AA AA ++ | D AA | | DAAA | | D AAAA | 40000 ++ D AA ++ | DADA | | D AAAA | 20000 ++ DADA ++ | DDAAD | + DAAAA A + + + | 0 ++----AADAA---+-------------+--------CC--+-------------+--++ 0 5 10 15 20 time since first SYN (in seconds) The third graph shows the trace with FreeBSD altered to use UI/LI to limit bursts. Again, the first request and response are normal. This shows that UI/LI allows the congestion window to grow normally. With the second request we see the main difference of UI/LI. Again, the sec- ond request comes after the RTO, and here we see the main difference with UI/LI. In response to the second request, the server does not send a burst the size of CWND or enter slow-start. Instead, it sends several small 4-packet bursts, with the CWND growing normally from this point. Expires Jun. 1, 2002 [Page 10]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 Idle trace with UI/LI sequence number (in bytes) +-------+------+-------+------+-------+------+------DD-A---+ + + + + + + + D+A | 100000 ++ Client_ACK A D A A ++ | Client_SEG C DDAA | | Server_SEG D D A | 80000 ++ DD AD ++ | D AD A | | D AD AA | 60000 ++ D A D ++ | DDA A | | D A | | D AD A | 40000 ++ DDAA ++ | D A | | DDAAA | 20000 ++ D AD A ++ | D A | + D A D AAA + + + + + | 0 ++A-D-A-D------+-------+------+---C---+------+-------+----++ 0 2 4 6 8 10 12 14 time since first SYN (in seconds) Note, RTO is the usual timer limit, but any value would have the same results, depending on when the second request was presented in relation to the timer. If the second request arrives after the timer expires, the reponse will behave as presented in these graphs. If the second request arrives before the timer expires and after all outstanding pack- ets have been acknowledged, systems with a send or receive timer will send a CWND-sized burst. If the second request arrives before the last ACK but after the last packet sent, the server has the potential to send a burst no larger than CWND. UI/LI will limit any burst to 4 packets regardless of the timing of the second request. Implementation of UI/LI UI/LI requires a simple modification to existing TCP output routines. The changes required replace the current idle detection code. Below is the suggested pseudocode from Appendix C of [JK92]: int idle = (snd_max == snd_una); if (idle && now - lastrcv >= rto) cwnd = 1; UI/LI would replace that code as below: Expires Jun. 1, 2002 [Page 11]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 int idle = (snd_max == snd_una); int maxwin = 4 + snd_nxt - snd_una; if (cwnd > maxwin) cwnd = maxwin; Packet counting is implemented by line 2. Lines 3 and 4 implement Window Limitation. Note that the comparison in line 1 (defining "idle" [JK92]) is required for later Silly Window Syndrome avoidance and could now be moved there. We have implemented UI/LI in FreeBSD. The affected code is in the file /sys/netinet/tcp_output.c. The lines: idle = (tp->snd_max == tp->snd_una); if (idle && tp->t_idle >= tp->t_rxtcur) tp->snd_cwnd = tp->t_maxseg; Are replaced with: idle = (tp->snd_max == tp->snd_una); maxwin = (4 * tp->t_maxseg) + tp->snd_nxt - tp->snd_una; if (tp->snd_cwnd > maxwin) tp->snd_cwnd = maxwin; The choice of limiting the available congestion window to 4 packets is based on the normal operation of TCP. An ACK received by the sender may be in response to the receipt of 2 packets, allowing another 2 to be sent. Further, normal window growth may require the sending of a third packet. Lastly, in slow-start with delayed ACKs, the receipt of an ACK can trigger the sending of 4 packets. Thus, 4 packets is a reasonable burst to send into the network. Increasing the initial window in slow-start to 4 packets has already been proposed [FAP97]. The effects of this change have been explored in simulation in [PN98] and in practice in [AHO98]. Such a modifica- tion to TCP would cause the same behavior as our solution in the cases where the pause timer has expired. It does not address the pre-timeout bursting situation we are concerned with. Implementation of BOL BOL can be implemented with a small amount of additional state, and a small number of lines in TCP's input, output, and timer routines. The state indicates the number of packets that can be emitted before the next timer or ACK receipt. The other lines increment the state when a notable event occurs, and decrement it when packets are sent. Our implementation uses two state variables: bucket - the number of Expires Jun. 1, 2002 [Page 12]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 packets that can be immediately sent, and ack_ratio - the number of packets per ACK (upper bound). ack_ratio is implied by RFC-2581, as at least one ACK "SHOULD" be sent for every 2 MSSs received, i.e., ACK compression [APS99]. This is our default; we parameterize it so that when others modify TCP to use less frequent ACKs, our portion of the code will operate correctly. It should be noted that less fre- quent ACKs will, by definition, increase the burstiness of the source as a result. We also assume 'initial_win' is defined, currently 2 MSS, but may be configurable as per Experimental RFC-2414 [FAP97]. There are two events that set the value of bucket. When an ACK is received, we set bucket to ack_ratio * 2 + 1. This is for the same reasons as Maxburst uses '5' - to allow for TCP to run at full rate in the presence of isolated ACK losses. On timeout events, the bucket is set to init_win. When packets are emitted in the existing tcp_output routine, the bucket is decremented. The bucket does not become negative; if it would, that data is not sent, and the routine returns. This 'refusal to send' behavior is identical to not having sufficient send window; the application will retry, typically due to some timer event. The code is as follows: /* define the state for BOL */ int ack_ratio, /* max number of packets per ack */ int bucket, /* max burst size */ #DEFINE init_win 2 /* set the bucket on ACK receipt */ bucket = ack_ratio * 2 + 1; /* set bucket on timeout */ bucket = init_win; /* decrement the bucket accordingly */ can_send = min(bucket - want_send, 0); bucket -= can_send; do_send(can_send); return can_send; Local connections We recently discovered cases where SSR adversely affected local con- nections, i.e., connections within the same subnet. There is already code in the current BSD-derived TCP implementation that disables ini- tializing the congestion window (CWND) to a small value, when both Expires Jun. 1, 2002 [Page 13]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 ends of a connection share a subnet. This code, from FreeBSD tcp_input.c, is outlined below, where inp = tp->t_inpcb. /* * Don't force slow-start on local network. */ if (!in_localaddr(inp->inp_faddr)) tp->snd_cwnd = mss; RFC-2414 observes that there are 3 types of window sizes used in BSD TCP: 1. intital window 2. restart after timeout 3. restart after loss Recent work indicates that these windows should be treated differ- ently; e.g., the restart-after-loss window should always be set to 1, and the initial window can be set to 4 or not used for local connec- tions [FAP97]. We proposed that it is consistent to extend this local exception to the restart-after-timeout window, as shown below as a FreeBSD code segment: idle = (tp->snd_max == tp->snd_una); maxwin = (4 * tp->t_maxseg) + tp->snd_nxt - tp->snd_una; if ((tp->snd_cwnd > maxwin) && !in_localaddr(tcp->t_inpcb->inp_faddr)) tp->snd_cwnd = maxwin; This modification is considered reasonable because it corresponds to the initial window determination. There are other cases where TCP uses "local" rules, such as MSS determination, and piggybacking. Performance Issues The purpose of these modifications is to avoid line-rate bursts, pri- marily as the result of the source being idle, but also due to ACK losses. A result of many of the proposed solutions is to limit the source, either by reducing the congestion window, or limiting the transmission of bursts. The performance effects of congestion window reduction are well-studied, and are not addressed here. BOL can limit the source without modifying the congestion window, and there are concerns that this may affect the performance of TCP. In particular, some implementations of TCP send ACKs in a bursty fashion, either by reducing the send/receive context switching, or by reducing the overall number of ACKs. These modifications are used to increase the performance of TCP, but can also increase the burstiness Expires Jun. 1, 2002 [Page 14]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 of the source. BOL, by reducing the burstiness of the source, is con- sidered to potentially limit the effectiveness of these enhancements. TCP currently recommends that an ACK "SHOULD" be sent for at least every two MSS's received. We assume that this recommendation implies an interleaving factor for the source as well. If this factor is encoded in a TCB variable (ack_ratio), then BOL can allow for corre- sponding bursts consistent with reasonable (non-adjacent) ACK losses. We assume that TCPs should not delay ACK processing to aggregate the receive-side timeslices, in order to reduce send/receive interleav- ing, unless this is also encoded in their ack_ratio variable. Our initial measurements indicate that even the recommended interleaving does not substantially affect the performance of TCP. In addition, we recommend that any burst-avoidance modification be disabled for direct LAN connections. For such connections, the con- gestion window mechanism is already disabled in several TCP implemen- tations. The resulting burstiness is handled by the link layer and receiver buffers. Conclusions At this time, we propose BOL as a simple, minimal and effective fix to the 'bug' in current TCP implementations that is exploited by HTTP/1.1. Modifications can be made to TCP to solve the slow-start restart problem that are consistent with the original congestion avoidance specifications (i.e. a send timer). However, we feel that the original intended behavior is not appropriate to some current applications, specifically HTTP. Thus, we recommend BOL to prevent bursts into the network. Not only does this solution solve the cur- rent problem in a simple way, it will prevent bursting in any other situation that might arise. The packet bursts which we allow are con- sistent with congestion window growth algorithms and with Floyd's conclusion about increasing the initial window size. BOL, as well as the other solutions listed, need to be re-evaluated within emerging TCP implementations, e.g., SACK [JB88]. In general, TCP has no rate pacing and uses congestion control to avoid bursts in current implementations. A more explicit mechanism, such as RBP or similar proposals may be desirable in the future. Security implications There are security risks associated with these algorithms that can result in denial of service attacks. Intermediate routers can delay data or ACKs in ways that can cause the restarting party to restart more conservatively. They also result in less probability of the Expires Jun. 1, 2002 [Page 15]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 restarting party generating a line-rate burst. In Send-Timer and Maxburst algorithms, as well as in a no-restart system, an attacker (either an intermediate router or data receiver) can clump the delivery of ACKs, which can result in line-rate bursts. The Receive-Timer, Rate-Based Pacing, UI/LI, and BOL algorithms use data or ACK arrival to moderate outgoing data and avoid bursts. If the attacker attempts to deliver data or ACKs so as to cause a burst, these algorithms successfully avoid creating a burst. In the process, their throughput is reduced. We believe the latter algorithms should be considered more robust than the former, because slow-start restart focuses on avoiding bursts, rather than maximizing throughput. In the recommended algo- rithms (BOL now, RBP for the future), the system succesfully avoids generating a burst as the result of an attacker. Acknowledgements We would like to acknowledge Kacheong Poon, Sally Floyd, members of the End-to-End-Interest Mailing List, and members of the IETF TCP Implementation Working Group for their feedback and discussions on this document. We would also like to thank Ruth Aydt, Steve Tuecke, and Carl Kesselman for their observation of the local connection issue. References [AHO98] Mark Allman, Chris Hayes, and Shawn Ostermann. An Evaluation of TCP with Larger Initial Windows. ACM Computer Communications Review, 28(3), 41-52 , July 1998. [APS99] M. Allman, V. Paxson, W. Stevens. TCP Congestion Control, April 1999. RFC-2581. [BPK97] Hari Balakrishnan, Venkata N. Padmanabhan, and Randy H. Katz. The Effects of Asymmetry on TCP Performance. In Proceedings of the ACM/IEEE Mobicom, Budapest, Hungary, ACM. September, 1997. [BSSK97] Hari Balakrishnan, Srinivasan Seshan, Mark Stemm, and Randy H. Katz. Analyzing Stability in Wide-Area Network Performance. In Proceedings of the ACM SIGMETRICS, Seattle WA, USA, ACM. June, 1997. [FGMFB97] R. Fielding, Jim Gettys, Jeffrey C. Mogul, H. Frystyk, and Tim Berners-Lee. Hypertext Transfer Protocol -- HTTP/1.1, Expires Jun. 1, 2002 [Page 16]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 January 1997. RFC-2068. [FAP97] Mark Allman, Sally Floyd, and Craig Partridge. Increasing TCP's Initial Window, September 1998. RFC-2414. [Hei97] John Heidemann. Performance Interactions Between P-HTTP and TCP Implementations. ACM Computer Communications Review, 27(2), 65-73, April 1997. [HOT97] John Heidemann, Katia Obraczka, and Joe Touch. Modeling the Performance of HTTP Over Several Transport Protocols. ACM/IEEE Transactions on Networking 5(5), 616-630, October, 1997. [JB88] Van Jacobson and R.T. Braden. TCP extensions for long-delay paths, October 1988. RFC 1072. [Jac88] Van Jacobson. Congestion Avoidance and Control. Proc. SIG- COMM '88, in ACM Computer Communication Review, 18(4):314-329, August 1988. NOTE: This paper lacks the appendix that describes slow-start restart, which appears only in the unpublished [JK92]. [JK92] Van Jacobson and Mike Karels. Congestion Avoidance and Con- trol. This is a revised version of [Jac88], which adds Karels as co-author and includes an additional appendix. The revised ver- sion has not been published, but is available at ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z [NS97] ns Network Simulator. http://www-mash.cs.berkeley.edu/ns/, 1997. [PK98] Venkata N. Padmanabhan and Randy H. Katz. TCP Fast Start: A Technique for Speeding Up Web Transfers. In Proceedings of the IEEE GLOBECOM Internet Mini-Conference, Sydney, Australia, Novem- ber, 1998. [PN98] K. Poduri and K. Nichols. Simulation Studies of Increased Ini- tial TCP Window Size, September 1998. RFC-2415. [Poo97] Kacheong Poon, Sun Microsystems, tcp-implementors mailing list, August, 1997. [Tou97] Joe Touch, ISI, tcp-implementors mailing list, August 12, 1997. [VH97] Vikram Visweswaraiah and John Heidemann. Improving Restart of Idle TCP Connections. Technical Report 97-661, University of Southern California, November 1997. Expires Jun. 1, 2002 [Page 17]
Hughes et al. Issues in TCP Slow-Start Restart Dec. 1, 2001 Authors/ Address Amy S. Hughes, Joe Touch, John Hiedemann University of Southern California/Information Sciences Institute 4676 Admiralty Way Marina del Rey, CA 90292-6695 USA Phone: +1 310-822-1511 Fax: +1 310-823-6714 URLs: http://www.isi.edu/~ahughes http://www.isi.edu/touch http://www.isi.edu/~johnh Email: ahughes@isi.edu touch@isi.edu johnh@isi.edu Expires Jun. 1, 2002 [Page 18]