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

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/