diff options
Diffstat (limited to 'doc/rfc/rfc6937.txt')
| -rw-r--r-- | doc/rfc/rfc6937.txt | 899 |
1 files changed, 899 insertions, 0 deletions
diff --git a/doc/rfc/rfc6937.txt b/doc/rfc/rfc6937.txt new file mode 100644 index 0000000..06b8ab8 --- /dev/null +++ b/doc/rfc/rfc6937.txt @@ -0,0 +1,899 @@ + + + + + + +Internet Engineering Task Force (IETF) M. Mathis +Request for Comments: 6937 N. Dukkipati +Category: Experimental Y. Cheng +ISSN: 2070-1721 Google, Inc. + May 2013 + + + Proportional Rate Reduction for TCP + +Abstract + + This document describes an experimental Proportional Rate Reduction + (PRR) algorithm as an alternative to the widely deployed Fast + Recovery and Rate-Halving algorithms. These algorithms determine the + amount of data sent by TCP during loss recovery. PRR minimizes + excess window adjustments, and the actual window size at the end of + recovery will be as close as possible to the ssthresh, as determined + by the congestion control algorithm. + +Status of This Memo + + This document is not an Internet Standards Track specification; it is + published for examination, experimental implementation, and + evaluation. + + This document defines an Experimental Protocol for the Internet + community. This document is a product of the Internet Engineering + Task Force (IETF). It represents the consensus of the IETF + community. It has received public review and has been approved for + publication by the Internet Engineering Steering Group (IESG). Not + all documents approved by the IESG are a candidate for any level of + Internet Standard; see Section 2 of RFC 5741. + + Information about the current status of this document, any errata, + and how to provide feedback on it may be obtained at + http://www.rfc-editor.org/info/rfc6937. + + + + + + + + + + + + + + + +Mathis, et al. Experimental [Page 1] + +RFC 6937 Proportional Rate Reduction May 2013 + + +Copyright Notice + + 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 ....................................................2 + 2. Definitions .....................................................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. References .....................................................13 + 9.1. Normative References ......................................13 + 9.2. Informative References ....................................14 + Appendix A. Strong Packet Conservation Bound ......................15 + +1. Introduction + + This document describes an experimental algorithm, PRR, 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 (cwnd) 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 round-trip time + (RTT) of ACKs to pass before sending any data. It is fragile because + it cannot compensate for the implicit window reduction caused by the + losses themselves. + + + + + +Mathis, et al. Experimental [Page 2] + +RFC 6937 Proportional Rate Reduction May 2013 + + + RFC 6675 [RFC6675] makes Fast Recovery with Selective Acknowledgement + (SACK) [RFC2018] more accurate by computing "pipe", a sender side + estimate of the number of 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 slow-start + threshold (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 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 1 RTT the window has been halved. Rate- + Halving is implemented in Linux after only being informally published + [RHweb], including an uncompleted document [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 but not + appropriate for modern congestion control algorithms, such as CUBIC + [CUBIC], which reduce the window by less than 50%. As a consequence, + Rate-Halving often allows the window to fall further than necessary, + reducing performance and increasing the risk of timeouts if there are + additional losses. + + PRR avoids these excess window adjustments such that at the end of + recovery the actual window size will be as close as possible to + ssthresh, the window size as determined by the congestion control + algorithm. It is patterned after Rate-Halving, but using the + fraction that is appropriate for the target window chosen by the + congestion control algorithm. During PRR, one of 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, 1 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 6675, which prove to be more aggressive + in a significant number of cases. SSRB offers a compromise by + allowing TCP to send 1 additional segment per ACK relative to CRB in + some situations. Although SSRB is less aggressive than RFC 6675 + + + + + +Mathis, et al. Experimental [Page 3] + +RFC 6937 Proportional Rate Reduction May 2013 + + + (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, PRR 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 [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 6675 and + used here, but it is distinct from the Strong Packet Conservation + Bound as 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 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 + differences 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 + of 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. 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 [RFC6675]. They are most accurate and more easily + implemented with SACK [RFC2018], but do not require SACK. + + + + + + + +Mathis, et al. Experimental [Page 4] + +RFC 6937 Proportional Rate Reduction May 2013 + + +2. Definitions + + The following terms, parameters, and state variables are used as they + are defined in earlier documents: + + RFC 793: snd.una (send unacknowledged) + + 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. + + DeliveredData: The total number of bytes that the current ACK + indicates have been delivered to the receiver. When not in + recovery, DeliveredData is the change in snd.una. With SACK, + DeliveredData can be computed precisely as the change in snd.una, + plus the (signed) change in SACKd. In recovery without SACK, + DeliveredData is estimated to be 1 SMSS on duplicate + acknowledgements, and on a subsequent partial or full ACK, + DeliveredData is estimated to be the change in snd.una, minus 1 + SMSS for each preceding duplicate ACK. + + Note that DeliveredData is robust; for TCP using SACK, DeliveredData + can be precisely computed anywhere in the network just by inspecting + the returning ACKs. The consequence of missing ACKs is that later + ACKs will show a larger DeliveredData. Furthermore, for any TCP + (with or without SACK), the sum of DeliveredData must agree with the + forward progress over the same time interval. + + We introduce a local variable "sndcnt", which indicates exactly how + many bytes should be sent in response to each ACK. Note that the + decision of which data to send (e.g., retransmit missing data or send + more new data) is out of scope for this document. + + + + + + + +Mathis, et al. Experimental [Page 5] + +RFC 6937 Proportional Rate Reduction May 2013 + + +3. Algorithms + + At the beginning of recovery, initialize PRR state. This assumes a + modern congestion control algorithm, CongCtrlAlg(), that might set + ssthresh to something other than FlightSize/2: + + 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 6675 pipe algorithm) + if (pipe > ssthresh) { + // Proportional Rate Reduction + sndcnt = CEIL(prr_delivered * ssthresh / RecoverFS) - prr_out + } else { + // Two versions of the Reduction Bound + if (conservative) { // PRR-CRB + limit = prr_delivered - prr_out + } else { // PRR-SSRB + limit = MAX(prr_delivered - prr_out, DeliveredData) + MSS + } + // Attempt to catch up, as permitted by limit + sndcnt = MIN(ssthresh - pipe, limit) + } + + On any data transmission or retransmission: + + prr_out += (data sent) // strictly less than or equal to sndcnt + +3.1. Examples + + We illustrate these algorithms by showing their different behaviors + for two scenarios: TCP experiencing either a single loss or a burst + of 15 consecutive losses. In all cases we assume bulk data (no + application pauses), standard Additive Increase Multiplicative + Decrease (AIMD) congestion control, and cwnd = FlightSize = pipe = 20 + segments, so ssthresh will be set to 10 at the beginning of recovery. + We also assume standard Fast Retransmit and Limited Transmit + [RFC3042], so TCP will send 2 new segments followed by 1 retransmit + in response to the first 3 duplicate ACKs following the losses. + + + + + + +Mathis, et al. Experimental [Page 6] + +RFC 6937 Proportional Rate Reduction May 2013 + + + Each of the diagrams below shows the per ACK response to the first + round trip for the various recovery algorithms when the zeroth + segment is lost. The top line indicates the transmitted segment + number triggering the ACKs, with an X for the lost segment. "cwnd" + and "pipe" indicate the values of these algorithms after processing + each returning ACK. "Sent" indicates how much 'N'ew or + '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 are 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 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 + + + PRR + ack# X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 + pipe: 19 19 18 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 10 + sent: N N R N N N N N N N N + 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 3 algorithms send the same total amount of data. + RFC 6675 experiences a "half window of silence", while the + Rate-Halving and PRR spread the voluntary window reduction across an + entire RTT. + + + +Mathis, et al. Experimental [Page 7] + +RFC 6937 Proportional Rate Reduction May 2013 + + + 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 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 + + PRR-CRB + 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 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 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 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 5 + ACKs trigger exactly 1 transmission each (2 new data, 3 old data), + and cwnd is set to 5. At a window size of 5, it takes 3 round trips + to retransmit all 15 lost segments. Rate-Halving does not raise the + window at all during recovery, so when recovery finally completes, + TCP will slow start cwnd from 5 up to 10. In this example, TCP + operates at half of the window chosen by the congestion control for + more than 3 RTTs, increasing the elapsed time and exposing it to + timeouts in the event that there are additional losses. + + + +Mathis, et al. Experimental [Page 8] + +RFC 6937 Proportional Rate Reduction May 2013 + + + PRR-CRB implements a Conservative Reduction Bound. Since the total + losses bring pipe below ssthresh, data is sent such that the total + data transmitted, prr_out, follows the total data delivered to the + receiver as reported by returning ACKs. Transmission is controlled + by the sending limit, which is set to prr_delivered - prr_out. This + is indicated by the RB:b tagging in the figure. In this case, + PRR-CRB is exposed to exactly the same problems as Rate-Halving; the + excess window reduction causes it to take excessively long to recover + the losses and exposes it to additional timeouts. + + PRR-SSRB increases the window by exactly 1 segment per ACK until pipe + rises to ssthresh during recovery. This is accomplished by setting + limit to one greater than the data reported to have been delivered to + the receiver on this ACK, implementing slow start during recovery, + and indicated by RB:d tagging in the figure. Although increasing the + window during recovery seems to be ill advised, it is important to + remember that this is actually less aggressive than permitted by RFC + 5681, which sends the same quantity of additional data as a single + burst in response to the ACK that triggered Fast Retransmit. + + For less extreme events, where the total losses are smaller than the + difference between FlightSize and ssthresh, PRR-CRB and PRR-SSRB have + identical behaviors. + +4. Properties + + The following properties are common to both PRR-CRB and PRR-SSRB, + except as noted: + + PRR maintains TCP's ACK clocking across most recovery events, + including burst losses. RFC 6675 can send large unclocked bursts + following burst losses. + + Normally, PRR 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. + + If there are minimal losses, PRR will converge to exactly the target + window chosen by the congestion control algorithm. Note that as TCP + approaches the end of recovery, prr_delivered will approach RecoverFS + and sndcnt will be computed such that prr_out approaches ssthresh. + + + + + + +Mathis, et al. Experimental [Page 9] + +RFC 6937 Proportional Rate Reduction May 2013 + + + Implicit window reductions, due to multiple isolated losses during + recovery, cause later voluntary reductions to be skipped. For small + numbers of losses, the window size ends at exactly the window chosen + by the congestion control algorithm. + + For burst losses, earlier voluntary window reductions can be undone + by sending extra segments in response to ACKs arriving later during + recovery. Note that as long as some voluntary window reductions are + not undone, the final value for pipe will be the same as ssthresh, + the target cwnd value chosen by the congestion control algorithm. + + PRR with either Reduction Bound improves the situation when there are + application stalls, e.g., when the sending application does not queue + data for transmission quickly enough or the receiver stops advancing + rwnd (receiver window). When there is an application stall early + during recovery, prr_out will fall behind the sum of the + transmissions permitted by sndcnt. The missed opportunities to send + due to stalls are treated like banked voluntary window reductions; + specifically, they cause prr_delivered - prr_out to be significantly + positive. If the application catches up while TCP is still in + recovery, TCP will send a partial window burst to catch up to exactly + where it would have been had the application never stalled. Although + this burst might be viewed as being hard on the network, this is + exactly what happens every time there is a partial RTT application + stall while not in recovery. We have made the partial RTT stall + behavior uniform in all states. Changing this behavior is out of + scope for this document. + + PRR 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 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 6675, a step + discontinuity in the pipe estimator causes a burst of data, which + cannot be retracted once the pipe estimator is corrected a few ACKs + later. For PRR, pipe merely determines which algorithm, PRR or the + Reduction Bound, is used to compute sndcnt from DeliveredData. While + pipe is underestimated, the algorithms are different by at most 1 + 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 + amount of data delivered to the receiver. We claim that this Strong + Packet Conservation Bound is the most aggressive algorithm that does + + + +Mathis, et al. Experimental [Page 10] + +RFC 6937 Proportional Rate Reduction May 2013 + + + 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 Conservation Bound is 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 RFC 6675, which permits bursts of data when there are bursts of + losses. PRR-SSRB is a compromise that permits TCP to send 1 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 RFC 6675 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 (Section 3.1 + in [FACK]) (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 + below ssthresh. Precisely this condition was observed for 32% of the + + + +Mathis, et al. Experimental [Page 11] + +RFC 6937 Proportional Rate Reduction May 2013 + + + recovery events: pipe fell below ssthresh before Fast Retransmit was + triggered, thus the various PRR algorithms started in the Reduction + Bound phase, and RFC 3517 sent bursts of segments with the Fast + Retransmit. + + In the companion paper, we observe that PRR-SSRB spends the least + time in recovery of all the algorithms tested, largely because it + experiences fewer timeouts once it is already in recovery. + + RFC 3517 experiences 29% more detected lost retransmissions and 2.6% + more timeouts (presumably due to undetected lost retransmissions) + than PRR-SSRB. These results are representative of PRR-UB and other + algorithms that send bursts when pipe falls below ssthresh. + + 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 Conservation 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 (and by + implication RFC 6675), which permits 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 Conservation 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 1 extra + segment per ACK relative to the Strong Packet Conservation Bound, to + partially compensate for excess losses. + + From the perspective of the Strong Packet Conservation Bound, + PRR-SSRB does indeed open the window during recovery; however, it is + 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 + + + + +Mathis, et al. Experimental [Page 12] + +RFC 6937 Proportional Rate Reduction May 2013 + + + 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 PRR + and every variant of the Reduction Bound. However, we do not + anticipate any future exploration of the alternative Reduction + Bounds. + +7. Acknowledgements + + This document is based in part on previous incomplete work by Matt + Mathis, Jeff Semke, and Jamshid Mahdavi [RHID] and influenced by + several discussions with John Heffner. + + Monia Ghobadi and Sivasankar Radhakrishnan helped analyze the + experiments. + + Ilpo Jarvinen reviewed the code. + + Mark Allman improved the document through his insightful review. + +8. Security Considerations + + PRR does not change the risk profile for TCP. + + Implementers that change PRR from counting bytes to segments have to + be cautious about the effects of ACK splitting attacks [Savage99], + where the receiver acknowledges partial segments for the purpose of + confusing the sender's congestion accounting. + +9. References + +9.1. Normative References + + [RFC0793] Postel, J., "Transmission Control Protocol", STD 7, + RFC 793, September 1981. + + [RFC2018] Mathis, M., Mahdavi, J., Floyd, S., and A. Romanow, "TCP + Selective Acknowledgment Options", RFC 2018, October + 1996. + + [RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion + Control", RFC 5681, September 2009. + + + + + +Mathis, et al. Experimental [Page 13] + +RFC 6937 Proportional Rate Reduction May 2013 + + + [RFC6675] Blanton, E., Allman, M., Wang, L., Jarvinen, I., Kojo, + M., and Y. Nishida, "A Conservative Loss Recovery + Algorithm Based on Selective Acknowledgment (SACK) for + TCP", RFC 6675, August 2012. + +9.2. Informative References + + [RFC3042] Allman, M., Balakrishnan, H., and S. Floyd, "Enhancing + TCP's Loss Recovery Using Limited Transmit", RFC 3042, + January 2001. + + [RFC3517] Blanton, E., Allman, M., Fall, K., and L. Wang, "A + Conservative Selective Acknowledgment (SACK)-based Loss + Recovery Algorithm for TCP", RFC 3517, April 2003. + + [IMC11] Dukkipati, N., Mathis, M., Cheng, Y., and M. Ghobadi, + "Proportional Rate Reduction for TCP", Proceedings of + the 11th ACM SIGCOMM Conference on Internet Measurement + 2011, Berlin, Germany, November 2011. + + [FACK] Mathis, M. and J. Mahdavi, "Forward Acknowledgment: + Refining TCP Congestion Control", ACM SIGCOMM SIGCOMM96, + August 1996. + + [RHID] Mathis, M., Semke, J., and J. Mahdavi, "The Rate-Halving + Algorithm for TCP Congestion Control", Work in Progress, + August 1999. + + [RHweb] Mathis, M. and J. Mahdavi, "TCP Rate-Halving with + Bounding Parameters", Web publication, December 1997, + <http://www.psc.edu/networking/papers/FACKnotes/current/>. + + [CUBIC] Rhee, I. and L. Xu, "CUBIC: A new TCP-friendly high- + speed TCP variant", PFLDnet 2005, February 2005. + + [Jacobson88] Jacobson, V., "Congestion Avoidance and Control", + SIGCOMM Comput. Commun. Rev. 18(4), August 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", Work in Progress, July 2012. + + + + + + +Mathis, et al. Experimental [Page 14] + +RFC 6937 Proportional Rate Reduction May 2013 + + +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 + the pipe calculation, but do not affect the outcome of PRR-CRB, once + pipe has fallen below ssthresh. + + We claim that this Strong Packet Conservation Bound is the most + aggressive algorithm that does not lead to additional forced losses + in some environments. It has the property that if there is a + standing queue at a bottleneck that is carrying no other traffic, the + queue will maintain exactly constant length for the entire duration + of the recovery, except for +1/-1 fluctuation due to differences in + packet arrival and exit times. Any less aggressive algorithm will + result in a declining queue at the bottleneck. Any more aggressive + algorithm will result in an increasing queue or additional losses if + it is a full drop tail queue. + + We demonstrate this property with a little thought experiment: + + Imagine a network path that has insignificant delays in both + directions, except for the processing time and queue at a single + bottleneck in the forward path. By insignificant delay, we mean when + a packet is "served" at the head of the bottleneck queue, the + following events happen in much less than one bottleneck packet time: + the packet arrives at the receiver; the receiver sends an ACK that + arrives at the sender; the sender processes the ACK and sends some + data; the data is queued at the bottleneck. + + If sndcnt is set to DeliveredData and nothing else is inhibiting + sending data, then clearly the data arriving at the bottleneck queue + will exactly replace the data that was served at the head of the + queue, so the queue will have a constant length. If queue is drop + tail and full, then the queue will stay exactly full. Losses or + reordering on the ACK path only cause wider fluctuations in the queue + size, but do not raise its peak size, independent of whether the data + is in order or out of order (including loss recovery from an earlier + RTT). Any more aggressive algorithm that sends additional data will + overflow the drop tail queue and cause loss. Any less aggressive + algorithm will under-fill the queue. Therefore, setting sndcnt to + DeliveredData is the most aggressive algorithm that does not cause + forced losses in this simple network. Relaxing the assumptions + + + +Mathis, et al. Experimental [Page 15] + +RFC 6937 Proportional Rate Reduction May 2013 + + + (e.g., making delays more authentic and adding more flows, delayed + ACKs, etc.) is likely to increase the fine grained fluctuations in + queue size but does not change its basic behavior. + + Note that the congestion control algorithm implements a broader + notion of optimal that includes appropriately sharing the network. + Typical congestion control algorithms are likely to reduce the data + sent relative to the Packet Conserving Bound implemented by PRR, + bringing TCP's actual window down to ssthresh. + +Authors' Addresses + + Matt Mathis + Google, Inc. + 1600 Amphitheatre Parkway + Mountain View, California 94043 + USA + + EMail: mattmathis@google.com + + + Nandita Dukkipati + Google, Inc. + 1600 Amphitheatre Parkway + Mountain View, California 94043 + USA + + EMail: nanditad@google.com + + + Yuchung Cheng + Google, Inc. + 1600 Amphitheatre Parkway + Mountain View, California 94043 + USA + + EMail: ycheng@google.com + + + + + + + + + + + + + + +Mathis, et al. Experimental [Page 16] + |