--- 1/draft-ietf-tcpm-proportional-rate-reduction-03.txt 2013-02-06 06:41:19.123707316 +0100 +++ 2/draft-ietf-tcpm-proportional-rate-reduction-04.txt 2013-02-06 06:41:19.159710037 +0100 @@ -1,19 +1,19 @@ TCP Maintenance Working Group M. Mathis Internet-Draft N. Dukkipati Intended status: Experimental Y. Cheng -Expires: April 25, 2013 Google, Inc - Oct 22, 2012 +Expires: August 10, 2013 Google, Inc + Feb 6, 2013 Proportional Rate Reduction for TCP - draft-ietf-tcpm-proportional-rate-reduction-03.txt + draft-ietf-tcpm-proportional-rate-reduction-04.txt Abstract This document describes an experimental algorithm, Proportional Rate Reduction (PPR) to improve the accuracy of the amount of data sent by TCP during loss recovery. Standard Congestion Control requires that TCP and other protocols reduce their congestion window in response to losses. This window reduction naturally occurs in the same round trip as the data retransmissions to repair the losses, and is implemented by choosing not to transmit any data in response to some @@ -37,80 +37,80 @@ Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. 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." - This Internet-Draft will expire on April 25, 2013. + This Internet-Draft will expire on August 10, 2013. Copyright Notice - Copyright (c) 2012 IETF Trust and the persons identified as the + Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 5 - 3. Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 5 + 3. Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.1. Examples . . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Properties . . . . . . . . . . . . . . . . . . . . . . . . . . 9 5. Measurements . . . . . . . . . . . . . . . . . . . . . . . . . 11 6. Conclusion and Recommendations . . . . . . . . . . . . . . . . 12 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 13 8. Security Considerations . . . . . . . . . . . . . . . . . . . 13 - 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 - 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 - 10.1. Normative References . . . . . . . . . . . . . . . . . . . 13 + 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 + 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 14 + 10.1. Normative References . . . . . . . . . . . . . . . . . . . 14 10.2. Informative References . . . . . . . . . . . . . . . . . . 14 Appendix A. Strong Packet Conservation Bound . . . . . . . . . . 15 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 16 1. Introduction This document describes an experimental algorithm, Proportional Rate Reduction (PPR) to improve the accuracy of the amount of data sent by TCP during loss recovery. Standard Congestion Control [RFC5681] requires that TCP (and other protocols) reduce their congestion window in response to losses. Fast Recovery, described in the same document, is the reference algorithm for making this adjustment. Its stated goal is to recover TCP's self clock by relying on returning ACKs during recovery to clock more data into the network. Fast Recovery typically adjusts the window by waiting for one half RTT of ACKs to pass before sending any data. It is fragile because it can not compensate for the implicit window reduction caused by the losses themselves. - RFC 3517 [RFC3517] makes Fast Recovery with SACK [RFC2018] more + RFC 6675 [RFC6675] makes Fast Recovery with SACK [RFC2018] more accurate by computing "pipe", a sender side estimate of the number of - bytes still outstanding in the network. With RFC 3517, Fast Recovery + bytes still outstanding in the network. With RFC 6675, Fast Recovery is implemented by sending data as necessary on each ACK to prevent pipe from falling below ssthresh, the window size as determined by the congestion control algorithm. This protects Fast Recovery from timeouts in many cases where there are heavy losses, although not if the entire second half of the window of data or ACKs are lost. - However, a single ACK carrying a SACK option that reports of large + However, a single ACK carrying a SACK option that implies a large quantity of missing data can cause a step discontinuity in the pipe estimator, which can cause Fast Retransmit to send a burst of data. The rate-halving algorithm sends data on alternate ACKs during recovery, such that after one RTT the window has been halved. Rate- halving is implemented in Linux after only being informally published [RHweb], including an uncompleted Internet-Draft [RHID]. Rate- halving also does not adequately compensate for the implicit window reduction caused by the losses and assumes a net 50% window reduction, which was completely standard at the time it was written, @@ -129,72 +129,82 @@ two additional reduction bound algorithms limits the total window reduction due to all mechanisms, including transient application stalls and the losses themselves. We describe two slightly different reduction bound algorithms: conservative reduction bound (CRB), which is strictly packet conserving; and a slow start reduction bound (SSRB), which is more aggressive than CRB by at most one segment per ACK. PRR-CRB meets the Strong Packet Conservation Bound described in Appendix A, however in real networks it does not perform as well as the algorithms - described in RFC 3517, which prove to be more aggressive in a + described in RFC 6675, which prove to be more aggressive in a significant number of cases. SSRB offers a compromise by allowing TCP to send one additional segment per ACK relative to CRB in some - situations. Although SSRB is less aggressive than RFC 3517 + situations. Although SSRB is less aggressive than RFC 6675 (transmitting fewer segments or taking more time to transmit them) it outperforms it, due to the lower probability of additional losses during recovery. The Strong Packet Conservation Bound on which PRR and both reduction bounds are based is patterned after Van Jacobson's packet conservation principle: segments delivered to the receiver are used as the clock to trigger sending the same number of segments back into the network. As much as possible Proportional Rate Reduction and the reduction bound algorithms rely on this self clock process, and are only slightly affected by the accuracy of other estimators, such as - pipe [RFC3517] and cwnd. This is what gives the algorithms their + pipe [RFC6675] and cwnd. This is what gives the algorithms their precision in the presence of events that cause uncertainty in other estimators. The original definition of the packet conservation principle [Jacobson88] treated packets that are presumed to be lost (e.g. marked as candidates for retransmission) as having left the network. - This idea is reflected in the pipe estimator defined in RFC 3517 and + This idea is reflected in the pipe estimator defined in RFC 6675 and used here, but it is distinct from Strong Packet Conservation Bound described in Appendix A, which is defined solely on the basis of data arriving at the receiver. We evaluated these and other algorithms in a large scale measurement - study presented in an companion paper [IMC11] and summarized in - Section 5. For authentic network traffic PRR+SSRB outperforms both + study presented in a companion paper [IMC11] and summarized in + Section 5. This measurement study was based on RFC 3517 [RFC3517], + which has since been superseded by RFC 6675. Since there are slight + difference between the two specifications, and we were meticulous + about our implementation of RFC 3517 we are not comfortable + unconditionally asserting that our measurement results apply to RFC + 6675, although we believe this to be the case. We have instead + chosen to be pedantic about describing measurement results relative + to RFC 3517, on which they were actually based. General discussions + algorithms and their properties have been updated to refer to RFC + 6675. + + We found that for authentic network traffic PRR+SSRB outperforms both RFC 3517 and Linux Rate Halving even though it is less aggressive - than RFC 3517. + than RFC 3517. We believe that these results apply to RFC 6675 as + well. The algorithms are described as modifications to RFC 5681 [RFC5681], TCP Congestion Control, using concepts drawn from the pipe algorithm - [RFC3517]. They are most accurate and more easily implemented with - SACK [RFC2018], but do not require SACK. The analysis and - measurement study presented here predates [RFC6675], which updates - RFC 3517. + [RFC6675]. They are most accurate and more easily implemented with + SACK [RFC2018], but do not require SACK. 2. Definitions The following terms, parameters and state variables are used as they are defined in earlier documents: RFC 793: snd.una - RFC 3517: covered (as in "covered sequence numbers") - RFC 5681: duplicate ACK, FlightSize, Sender Maximum Segment Size (SMSS) + RFC 6675: covered (as in "covered sequence numbers") + Voluntary window reductions: choosing not to send data in response to some ACKs, for the purpose of reducing the sending window size and data rate. We define some additional variables: SACKd: The total number of bytes that the scoreboard indicates have been delivered to the receiver. This can be computed by scanning the scoreboard and counting the total number of bytes covered by all sack blocks. If SACK is not in use, SACKd is not defined. @@ -228,21 +238,21 @@ ssthresh = CongCtrlAlg() // Target cwnd after recovery prr_delivered = 0 // Total bytes delivered during recovery prr_out = 0 // Total bytes sent during recovery RecoverFS = snd.nxt-snd.una // FlightSize at the start of recovery On every ACK during recovery compute: DeliveredData = change_in(snd.una) + change_in(SACKd) prr_delivered += DeliveredData - pipe = (RFC 3517 pipe algorithm) + pipe = (RFC 6675 pipe algorithm) if (pipe > ssthresh) { // Proportional Rate Reduction sndcnt = CEIL(prr_delivered * ssthresh / RecoverFS) - prr_out } else { // Two version of the reduction bound if (conservative) { // PRR+CRB limit = prr_delivered - prr_out } else { // PRR+SSRB limit = MAX(prr_delivered - prr_out, DeliveredData) + MSS } @@ -275,21 +285,21 @@ 'R'etransmitted data would be sent. Note that the algorithms for deciding which data to send are out of scope of this document. When there is a single loss, PRR with either of the reduction bound algorithms has the same behavior. We show "RB", a flag indicating which reduction bound subexpression ultimately determined the value of sndcnt. When there is minimal losses "limit" (both algorithms) will always be larger than ssthresh - pipe, so the sndcnt will be ssthresh - pipe indicated by "s" in the "RB" row. - RFC 3517 + RFC 6675 ack# X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 cwnd: 20 20 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 pipe: 19 19 18 18 17 16 15 14 13 12 11 10 10 10 10 10 10 10 10 sent: N N R N N N N N N N N Rate Halving (Linux) ack# X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 cwnd: 20 20 19 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 11 pipe: 19 19 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 11 10 sent: N N R N N N N N N N N @@ -301,30 +311,30 @@ RB: s s Cwnd is not shown because PRR does not use it. Key for RB s: sndcnt = ssthresh - pipe // from ssthresh b: sndcnt = prr_delivered - prr_out + SMSS // from banked d: sndcnt = DeliveredData + SMSS // from DeliveredData (Sometimes more than one applies) Note that all three algorithms send the same total amount of data. - RFC 3517 experiences a "half-window of silence", while the Rate + RFC 6675 experiences a "half-window of silence", while the Rate Halving and PRR spread the voluntary window reduction across an entire RTT. Next we consider the same initial conditions when the first 15 packets (0-14) are lost. During the remainder of the lossy RTT, only 5 ACKs are returned to the sender. We examine each of these algorithms in succession. - RFC 3517 + RFC 6675 ack# X X X X X X X X X X X X X X X 15 16 17 18 19 cwnd: 20 20 11 11 11 pipe: 19 19 4 10 10 sent: N N 7R R R Rate Halving (Linux) ack# X X X X X X X X X X X X X X X 15 16 17 18 19 cwnd: 20 20 5 5 5 pipe: 19 19 4 4 4 sent: N N R R R @@ -334,24 +344,24 @@ pipe: 19 19 4 4 4 sent: N N R R R RB: b b b PRR-SSRB ack# X X X X X X X X X X X X X X X 15 16 17 18 19 pipe: 19 19 4 5 6 sent: N N 2R 2R 2R RB: bd d d - In this specific situation, RFC 3517 is more aggressive, because once + In this specific situation, RFC 6675 is more aggressive, because once fast retransmit is triggered (on the ACK for segment 17) TCP immediately retransmits sufficient data to bring pipe up to cwnd. - Our measurement data (see Section 5) indicates that RFC 3517 + Our measurement data (see Section 5) indicates that RFC 6675 significantly outperforms Rate Halving, PRR-CRB and some other similarly conservative algorithms that we tested, showing that it is significantly common for the actual losses to exceed the window reduction determined by the congestion control algorithm. The Linux implementation of Rate Halving includes an early version of the conservative reduction bound [RHweb]. In this situation the five ACKs trigger exactly one transmission each (2 new data, 3 old data), and cwnd is set to 5. At a window size of 5, it takes three round trips to retransmit all 15 lost segments. Rate Halving does not @@ -384,21 +394,21 @@ For less extreme events, where the total losses are smaller than the difference between Flight Size and ssthresh, PRR-CRB and PRR-SSRB have identical behaviours. 4. Properties The following properties are common to both PRR-CRB and PRR-SSRB except as noted: Proportional Rate Reduction maintains TCPs ACK clocking across most - recovery events, including burst losses. RFC 3517 can send large + recovery events, including burst losses. RFC 6675 can send large unclocked bursts following burst losses. Normally Proportional Rate Reduction will spread voluntary window reductions out evenly across a full RTT. This has the potential to generally reduce the burstiness of Internet traffic, and could be considered to be a type of soft pacing. Hypothetically, any pacing increases the probability that different flows are interleaved, reducing the opportunity for ACK compression and other phenomena that increase traffic burstiness. However these effects have not been quantified. @@ -438,21 +448,21 @@ out of scope for this document. Proportional Rate Reduction with Reduction Bound is less sensitive to errors in the pipe estimator. While in recovery, pipe is intrinsically an estimator, using incomplete information to estimate if un-SACKed segments are actually lost or merely out-of-order in the network. Under some conditions pipe can have significant errors, for example pipe is underestimated when when a burst of reordered data is prematurely assumed to be lost and marked for retransmission. If the transmissions are regulated directly by pipe as they are with RFC - 3517, such as step discontinuity in the pipe estimator causes a burst + 6675, such as step discontinuity in the pipe estimator causes a burst of data, which can not be retracted once the pipe estimator is corrected a few ACKs later. For PRR, pipe merely determines which algorithm, Proportional Rate Reduction or the reduction bound, is used to compute sndcnt from DeliveredData. While pipe is underestimated the algorithms are different by at most one segment per ACK. Once pipe is updated they converge to the same final window at the end of recovery. Under all conditions and sequences of events during recovery, PRR-CRB strictly bounds the data transmitted to be equal to or less than the @@ -461,47 +471,48 @@ not lead to additional forced losses in some environments. It has the property that if there is a standing queue at a bottleneck with no cross traffic, the queue will maintain exactly constant length for the duration of the recovery, except for +1/-1 fluctuation due to differences in packet arrival and exit times. See Appendix A for a detailed discussion of this property. Although the Strong Packet Conserving Bound in very appealing for a number of reasons, our measurements summarized in Section 5 demonstrate that it is less aggressive and does not perform as well - as RFC3517, which permits large bursts of data when there are bursts + as RFC 6675, which permits large bursts of data when there are bursts of losses. PRR-SSRB is a compromise that permits TCP to send one extra segment per ACK as compared to the packet conserving bound. From the perspective of a strict packet conserving bound, PRR-SSRB does indeed open the window during recovery, however it is - significantly less aggressive than RFC3517 in the presence of burst + significantly less aggressive than RFC6675 in the presence of burst losses. 5. Measurements In a companion IMC11 paper [IMC11] we describe some measurements comparing the various strategies for reducing the window during recovery. The experiments were performed on servers carrying Google production traffic and are briefly summarized here. The various window reduction algorithms and extensive instrumentation were all implemented in Linux 2.6. We used the uniform set of algorithms present in the base Linux implementation, including CUBIC [CUBIC], limited transmit [RFC3042], threshold transmit from [FACK] - (a similar algorithm appears in [RFC6675]) and lost retransmission - detection algorithms. We confirmed that the behaviors of Rate - Halving (the Linux default), RFC 3517 and PRR were authentic to their - respective specifications and that performance and features were - comparable to the kernels in production use. All of the different - window reduction algorithms were all present in a common kernel and - could be selected with a sysctl, such that we had an absolutely - uniform baseline for comparing them. + (this algorithm was not present in RFC 3517, but a similar algorithm + has been added to RFC 6675) and lost retransmission detection + algorithms. We confirmed that the behaviors of Rate Halving (the + Linux default), RFC 3517 and PRR were authentic to their respective + specifications and that performance and features were comparable to + the kernels in production use. All of the different window reduction + algorithms were all present in a common kernel and could be selected + with a sysctl, such that we had an absolutely uniform baseline for + comparing them. Our experiments included an additional algorithm, PRR with an unlimited bound (PRR-UB), which sends ssthresh-pipe bursts when pipe falls below ssthresh. This behavior parallels RFC 3517. An important detail of this configuration is that CUBIC only reduces the window by 30%, as opposed to the 50% reduction used by traditional congestion control algorithms. This accentuates the tendency for RFC 3517 and PRR-UB to send a burst at the point when Fast Retransmit gets triggered because pipe is likely to already be @@ -523,42 +534,46 @@ Rate Halving experiences 5% more timeouts and significantly smaller final cwnd values at the end of recovery. The smaller cwnd sometimes causes the recovery itself to take extra round trips. These results are representative of PRR-CRB and other algorithms that implement strict packet conservation during recovery. 6. Conclusion and Recommendations Although the Strong Packet Conserving Bound used in PRR-CRB is very appealing for a number of reasons, our measurements show that it is - less aggressive and does not perform as well as RFC 3517, which - permits bursts of data when there are bursts of losses. RFC 3517 is - conservative in the original sense of Van Jacobson's packet - conservation principle, which included the assumption that presumed - lost segments have indeed left the network. PRR-CRB makes no such - assumption, following instead a Strong Packet Conserving Bound, in - which only packets that have arrived at the receiver are considered - to have left the network. PRR-SSRB is a compromise that permits TCP - to send one extra segment per ACK relative to the Strong Packet - Conserving Bound, to partially compensate for excess losses. + less aggressive and does not perform as well as RFC 3517, (and by + implication RFC 6675), which permit bursts of data when there are + bursts of losses. RFC 3517 and RFC 6675 are conservative in the + original sense of Van Jacobson's packet conservation principle, which + included the assumption that presumed lost segments have indeed left + the network. PRR-CRB makes no such assumption, following instead a + Strong Packet Conserving Bound, in which only packets that have + actually arrived at the receiver are considered to have left the + network. PRR-SSRB is a compromise that permits TCP to send one extra + segment per ACK relative to the Strong Packet Conserving Bound, to + partially compensate for excess losses. From the perspective of the Strong Packet Conserving Bound, PRR-SSRB does indeed open the window during recovery, however it is - significantly less aggressive than RFC 3517 in the presence of burst - losses. Even so, it often outperforms RFC 3517, because it avoids - some of the self inflicted losses caused by bursts. + significantly less aggressive than RFC 3517 (and RFC 6675) in the + presence of burst losses. Even so, it often outperforms RFC 3517, + (and presumably RFC 6675) because it avoids some of the self + inflicted losses caused by bursts. At this time we see no reason not to test and deploy PRR-SSRB on a large scale. Implementers worried about any potential impact of raising the window during recovery may want to optionally support PRR-CRB (which is actually simpler to implement) for comparison - studies. + studies. Furthermore, there is one minor detail of PRR that can be + improved by replacing pipe by total_pipe as defined by Laminar TCP + [Laminar]. One final comment about terminology: we expect that common usage will drop "slow start reduction bound" from the algorithm name. This document needed to be pedantic about having distinct names for proportional rate reduction and every variant of the reduction bound. However, we do not anticipate any future exploration of the alternative reduction bounds. 7. Acknowledgements @@ -635,20 +650,24 @@ [Jacobson88] Jacobson, V., "Congestion Avoidance and Control", SIGCOMM Comput. Commun. Rev. 18(4), Aug 1988. [Savage99] Savage, S., Cardwell, N., Wetherall, D., and T. Anderson, "TCP congestion control with a misbehaving receiver", SIGCOMM Comput. Commun. Rev. 29(5), October 1999. + [Laminar] Mathis, M., "Laminar TCP and the case for refactoring TCP + congestion control", draft-mathis-tcpm-tcp-laminar-01 + (work in progress), July 2012. + Appendix A. Strong Packet Conservation Bound PRR-CRB is based on a conservative, philosophically pure and aesthetically appealing Strong Packet Conservation Bound, described here. Although inspired by Van Jacobson's packet conservation principle [Jacobson88], it differs in how it treats segments that are missing and presumed lost. Under all conditions and sequences of events during recovery, PRR-CRB strictly bounds the data transmitted to be equal to or less than the amount of data delivered to the receiver. Note that the effects of presumed losses are included in