draft-ietf-tcpm-proportional-rate-reduction-04.txt   rfc6937.txt 
TCP Maintenance Working Group M. Mathis Internet Engineering Task Force (IETF) M. Mathis
Internet-Draft N. Dukkipati Request for Comments: 6937 N. Dukkipati
Intended status: Experimental Y. Cheng Category: Experimental Y. Cheng
Expires: August 10, 2013 Google, Inc ISSN: 2070-1721 Google, Inc.
Feb 6, 2013 May 2013
Proportional Rate Reduction for TCP Proportional Rate Reduction for TCP
draft-ietf-tcpm-proportional-rate-reduction-04.txt
Abstract Abstract
This document describes an experimental algorithm, Proportional Rate This document describes an experimental Proportional Rate Reduction
Reduction (PPR) to improve the accuracy of the amount of data sent by (PRR) algorithm as an alternative to the widely deployed Fast
TCP during loss recovery. Standard Congestion Control requires that Recovery and Rate-Halving algorithms. These algorithms determine the
TCP and other protocols reduce their congestion window in response to amount of data sent by TCP during loss recovery. PRR minimizes
losses. This window reduction naturally occurs in the same round excess window adjustments, and the actual window size at the end of
trip as the data retransmissions to repair the losses, and is recovery will be as close as possible to the ssthresh, as determined
implemented by choosing not to transmit any data in response to some by the congestion control algorithm.
ACKs arriving from the receiver. Two widely deployed algorithms are
used to implement this window reduction: Fast Recovery and Rate
Halving. Both algorithms are needlessly fragile under a number of
conditions, particularly when there is a burst of losses such that
the number of ACKs returning to the sender is small. Proportional
Rate Reduction minimizes 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 determined by the congestion
control algorithm. It is patterned after Rate Halving, but using the
fraction that is appropriate for target window chosen by the
congestion control algorithm.
Status of this Memo
This Internet-Draft is submitted in full conformance with the Status of This Memo
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering This document is not an Internet Standards Track specification; it is
Task Force (IETF). Note that other groups may also distribute published for examination, experimental implementation, and
working documents as Internet-Drafts. The list of current Internet- evaluation.
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months This document defines an Experimental Protocol for the Internet
and may be updated, replaced, or obsoleted by other documents at any community. This document is a product of the Internet Engineering
time. It is inappropriate to use Internet-Drafts as reference Task Force (IETF). It represents the consensus of the IETF
material or to cite them other than as "work in progress." 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.
This Internet-Draft will expire on August 10, 2013. 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.
Copyright Notice Copyright Notice
Copyright (c) 2013 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 ....................................................2
2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Definitions .....................................................5
3. Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 6 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 . . . . . . . . . . . . . . . . . . . . . 14 9. References .....................................................13
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 14 9.1. Normative References ......................................13
10.1. Normative References . . . . . . . . . . . . . . . . . . . 14 9.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
1. Introduction 1. Introduction
This document describes an experimental algorithm, Proportional Rate This document describes an experimental algorithm, PRR, to improve
Reduction (PPR) to improve the accuracy of the amount of data sent by 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 (cwnd) in response to
Fast Recovery, described in the same document, is the reference losses. Fast Recovery, described in the same document, is the
algorithm for making this adjustment. Its stated goal is to recover reference algorithm for making this adjustment. Its stated goal is
TCP's self clock by relying on returning ACKs during recovery to to recover TCP's self clock by relying on returning ACKs during
clock more data into the network. Fast Recovery typically adjusts recovery to clock more data into the network. Fast Recovery
the window by waiting for one half RTT of ACKs to pass before sending typically adjusts the window by waiting for one half round-trip time
any data. It is fragile because it can not compensate for the (RTT) of ACKs to pass before sending any data. It is fragile because
implicit window reduction caused by the losses themselves. it cannot compensate for the implicit window reduction caused by the
losses themselves.
RFC 6675 [RFC6675] makes Fast Recovery with SACK [RFC2018] more RFC 6675 [RFC6675] makes Fast Recovery with Selective Acknowledgement
accurate by computing "pipe", a sender side estimate of the number of (SACK) [RFC2018] more accurate by computing "pipe", a sender side
bytes still outstanding in the network. With RFC 6675, Fast Recovery estimate of the number of bytes still outstanding in the network.
is implemented by sending data as necessary on each ACK to prevent With RFC 6675, Fast Recovery is implemented by sending data as
pipe from falling below ssthresh, the window size as determined by necessary on each ACK to prevent pipe from falling below slow-start
the congestion control algorithm. This protects Fast Recovery from threshold (ssthresh), the window size as determined by the congestion
timeouts in many cases where there are heavy losses, although not if control algorithm. This protects Fast Recovery from timeouts in many
the entire second half of the window of data or ACKs are lost. cases where there are heavy losses, although not if the entire second
However, a single ACK carrying a SACK option that implies a large half of the window of data or ACKs are lost. However, a single ACK
quantity of missing data can cause a step discontinuity in the pipe carrying a SACK option that implies a large quantity of missing data
estimator, which can cause Fast Retransmit to send a burst of 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 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 1 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 document [RHID]. Rate-Halving also
halving also does not adequately compensate for the implicit window does not adequately compensate for the implicit window reduction
reduction caused by the losses and assumes a net 50% window caused by the losses and assumes a net 50% window reduction, which
reduction, which was completely standard at the time it was written, was completely standard at the time it was written but not
but not appropriate for modern congestion control algorithms such as appropriate for modern congestion control algorithms, such as CUBIC
Cubic [CUBIC], which reduce the window by less than 50%. As a [CUBIC], which reduce the window by less than 50%. As a consequence,
consequence rate-halving often allows the window to fall further than Rate-Halving often allows the window to fall further than necessary,
necessary, reducing performance and increasing the risk of timeouts reducing performance and increasing the risk of timeouts if there are
if there are additional losses. additional losses.
Proportional Rate Reduction (PPR) avoids these excess window PRR avoids these excess window adjustments such that at the end of
adjustments such that at the end of recovery the actual window size recovery the actual window size will be as close as possible to
will be as close as possible to ssthresh, the window size determined ssthresh, the window size as determined by the congestion control
by the congestion control algorithm. It is patterned after Rate algorithm. It is patterned after Rate-Halving, but using the
Halving, but using the fraction that is appropriate for the target fraction that is appropriate for the target window chosen by the
window chosen by the congestion control algorithm. During PRR one of congestion control algorithm. During PRR, one of two additional
two additional reduction bound algorithms limits the total window Reduction Bound algorithms limits the total window reduction due to
reduction due to all mechanisms, including transient application all mechanisms, including transient application stalls and the losses
stalls and the losses themselves. 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, 1 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;
in real networks it does not perform as well as the algorithms however, in real networks it does not perform as well as the
described in RFC 6675, which prove to be more aggressive in a algorithms described in RFC 6675, which prove to be more aggressive
significant number of cases. SSRB offers a compromise by allowing in a significant number of cases. SSRB offers a compromise by
TCP to send one additional segment per ACK relative to CRB in some allowing TCP to send 1 additional segment per ACK relative to CRB in
situations. Although SSRB is less aggressive than RFC 6675 some 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),
outperforms it, due to the lower probability of additional losses it 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, PRR and the Reduction Bound
reduction bound algorithms rely on this self clock process, and are algorithms rely on this self clock process, and are only slightly
only slightly affected by the accuracy of other estimators, such as affected by the accuracy of other estimators, such as pipe [RFC6675]
pipe [RFC6675] and cwnd. This is what gives the algorithms their and cwnd. This is what gives the algorithms their precision in the
precision in the presence of events that cause uncertainty in other 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 6675 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 the Strong Packet Conservation
described in Appendix A, which is defined solely on the basis of data Bound as described in Appendix A, which is defined solely on the
arriving at the receiver. basis of data 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 a companion paper [IMC11] and summarized in study presented in a companion paper [IMC11] and summarized in
Section 5. This measurement study was based on RFC 3517 [RFC3517], Section 5. This measurement study was based on RFC 3517 [RFC3517],
which has since been superseded by RFC 6675. Since there are slight which has since been superseded by RFC 6675. Since there are slight
difference between the two specifications, and we were meticulous differences between the two specifications, and we were meticulous
about our implementation of RFC 3517 we are not comfortable about our implementation of RFC 3517, we are not comfortable
unconditionally asserting that our measurement results apply to RFC unconditionally asserting that our measurement results apply to RFC
6675, although we believe this to be the case. We have instead 6675, although we believe this to be the case. We have instead
chosen to be pedantic about describing measurement results relative chosen to be pedantic about describing measurement results relative
to RFC 3517, on which they were actually based. General discussions to RFC 3517, on which they were actually based. General discussions
algorithms and their properties have been updated to refer to RFC of algorithms and their properties have been updated to refer to RFC
6675. 6675.
We found that for authentic network traffic PRR+SSRB outperforms both We found that for authentic network traffic, PRR-SSRB outperforms
RFC 3517 and Linux Rate Halving even though it is less aggressive both RFC 3517 and Linux Rate-Halving even though it is less
than RFC 3517. We believe that these results apply to RFC 6675 as aggressive than RFC 3517. We believe that these results apply to RFC
well. 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
[RFC6675]. They are most accurate and more easily implemented with algorithm [RFC6675]. They are most accurate and more easily
SACK [RFC2018], but do not require SACK. implemented with SACK [RFC2018], but do not require SACK.
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 (send unacknowledged)
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") 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
scoreboard and counting the total number of bytes covered by all sack the scoreboard and counting the total number of bytes covered by
blocks. If SACK is not in use, SACKd is not defined. all SACK blocks. If SACK is not in use, SACKd is not defined.
DeliveredData: The total number of bytes that the current ACK DeliveredData: The total number of bytes that the current ACK
indicates have been delivered to the receiver. When not in recovery, indicates have been delivered to the receiver. When not in
DeliveredData is the change in snd.una. With SACK, DeliveredData can recovery, DeliveredData is the change in snd.una. With SACK,
be computed precisely as the change in snd.una plus the (signed) DeliveredData can be computed precisely as the change in snd.una,
change in SACKd. In recovery without SACK, DeliveredData is plus the (signed) change in SACKd. In recovery without SACK,
estimated to be 1 SMSS on duplicate acknowledgements, and on a DeliveredData is estimated to be 1 SMSS on duplicate
subsequent partial or full ACK, DeliveredData is estimated to be the acknowledgements, and on a subsequent partial or full ACK,
change in snd.una, minus one SMSS for each preceding duplicate 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 Note that DeliveredData is robust; for TCP using SACK, DeliveredData
can be precisely computed anywhere in the network just by inspecting can be precisely computed anywhere in the network just by inspecting
the returning ACKs. The consequence of missing ACKs is that later the returning ACKs. The consequence of missing ACKs is that later
ACKs will show a larger DeliveredData. Furthermore, for any TCP ACKs will show a larger DeliveredData. Furthermore, for any TCP
(with or without SACK) the sum of DeliveredData must agree with the (with or without SACK), the sum of DeliveredData must agree with the
forward progress over the same time interval. forward progress over the same time interval.
We introduce a local variable "sndcnt", which indicates exactly how We introduce a local variable "sndcnt", which indicates exactly how
many bytes should be sent in response to each ACK. Note that the 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 decision of which data to send (e.g., retransmit missing data or send
more new data) is out of scope for this document. more new data) is out of scope for this document.
3. Algorithms 3. Algorithms
At the beginning of recovery initialize PRR state. This assumes a At the beginning of recovery, initialize PRR state. This assumes a
modern congestion control algorithm, CongCtrlAlg(), that might set modern congestion control algorithm, CongCtrlAlg(), that might set
ssthresh to something other than FlightSize/2: ssthresh to something other than FlightSize/2:
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 6675 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 versions 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
} }
// Attempt to catch up, as permitted by limit // Attempt to catch up, as permitted by limit
sndcnt = MIN(ssthresh - pipe, limit) sndcnt = MIN(ssthresh - pipe, limit)
} }
On any data transmission or retransmission: On any data transmission or retransmission:
prr_out += (data sent) // strictly less than or equal to sndcnt prr_out += (data sent) // strictly less than or equal to sndcnt
3.1. Examples 3.1. Examples
We illustrate these algorithms by showing their different behaviors We illustrate these algorithms by showing their different behaviors
for two scenarios: TCP experiencing either a single loss or a burst for two scenarios: TCP experiencing either a single loss or a burst
of 15 consecutive losses. In all cases we assume bulk data (no of 15 consecutive losses. In all cases we assume bulk data (no
application pauses), standard AIMD congestion control and cwnd = application pauses), standard Additive Increase Multiplicative
FlightSize = pipe = 20 segments, so ssthresh will be set to 10 at the Decrease (AIMD) congestion control, and cwnd = FlightSize = pipe = 20
beginning of recovery. We also assume standard Fast Retransmit and segments, so ssthresh will be set to 10 at the beginning of recovery.
Limited Transmit [RFC3042], so TCP will send two new segments We also assume standard Fast Retransmit and Limited Transmit
followed by one retransmit in response to the first 3 duplicate ACKs [RFC3042], so TCP will send 2 new segments followed by 1 retransmit
following the losses. in response to the first 3 duplicate ACKs following the losses.
Each of the diagrams below shows the per ACK response to the first Each of the diagrams below shows the per ACK response to the first
round trip for the various recovery algorithms when the zeroth round trip for the various recovery algorithms when the zeroth
segment is lost. The top line indicates the transmitted segment segment is lost. The top line indicates the transmitted segment
number triggering the ACKs, with an X for the lost segment. "cwnd" number triggering the ACKs, with an X for the lost segment. "cwnd"
and "pipe" indicate the values of these algorithms after processing and "pipe" indicate the values of these algorithms after processing
each returning ACK. "Sent" indicates how much 'N'ew or each returning ACK. "Sent" indicates how much 'N'ew or
'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 are 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 6675 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
PRR PRR
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
pipe: 19 19 18 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 10 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 sent: N N R N N N N N N N N
RB: s s RB: s s
skipping to change at page 7, line 43 skipping to change at page 7, line 38
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
PRR PRR
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
pipe: 19 19 18 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 10 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 sent: N N R N N N N N N N N
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 3 algorithms send the same total amount of data.
RFC 6675 experiences a "half-window of silence", while the Rate RFC 6675 experiences a "half window of silence", while the
Halving and PRR spread the voluntary window reduction across an Rate-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 6675 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
PRR-CRB PRR-CRB
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 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 6675 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 6675 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 5
ACKs trigger exactly one transmission each (2 new data, 3 old data), 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 three round and cwnd is set to 5. At a window size of 5, it takes 3 round trips
trips to retransmit all 15 lost segments. Rate Halving does not to retransmit all 15 lost segments. Rate-Halving does not raise the
raise the window at all during recovery, so when recovery finally window at all during recovery, so when recovery finally completes,
completes, TCP will slowstart cwnd from 5 up to 10. In this example, TCP will slow start cwnd from 5 up to 10. In this example, TCP
TCP operates at half of the window chosen by the congestion control operates at half of the window chosen by the congestion control for
for more than three RTTs, increasing the elapsed time and exposing it more than 3 RTTs, increasing the elapsed time and exposing it to
to timeouts in the event that there are additional losses. timeouts in the event that there are additional losses.
PRR-CRB implements a conservative reduction bound. Since the total PRR-CRB implements a Conservative Reduction Bound. Since the total
losses bring pipe below ssthresh, data is sent such that 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 data transmitted, prr_out, follows the total data delivered to the
receiver as reported by returning ACKs. Transmission is controlled receiver as reported by returning ACKs. Transmission is controlled
by the sending limit, which was set to prr_delivered - prr_out. This 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 indicated by the RB:b tagging in the figure. In this case,
is exposed to exactly the same problems as Rate Halving, the excess PRR-CRB is exposed to exactly the same problems as Rate-Halving; the
window reduction causes it to take excessively long to recover the excess window reduction causes it to take excessively long to recover
losses and exposes it to additional timeouts. the losses and exposes it to additional timeouts.
PRR-SSRB increases the window by exactly 1 segment per ACK until pipe PRR-SSRB increases the window by exactly 1 segment per ACK until pipe
rises to ssthresh during recovery. This is accomplished by setting rises to ssthresh during recovery. This is accomplished by setting
limit to one greater than the data reported to have been delivered to limit to one greater than the data reported to have been delivered to
the receiver on this ACK, implementing slowstart during recovery, and the receiver on this ACK, implementing slow start during recovery,
indicated by RB:d tagging in the figure. Although increasing the and indicated by RB:d tagging in the figure. Although increasing the
window during recovery seems to be ill advised, it is important to window during recovery seems to be ill advised, it is important to
remember that this is actually less aggressive than permitted by RFC remember that this is actually less aggressive than permitted by RFC
5681, which sends the same quantity of additional data as a single 5681, which sends the same quantity of additional data as a single
burst in response to the ACK that triggered Fast Retransmit burst in response to the ACK that triggered Fast Retransmit.
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 FlightSize and ssthresh, PRR-CRB and PRR-SSRB have
have identical behaviours. identical behaviors.
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 PRR maintains TCP's ACK clocking across most recovery events,
recovery events, including burst losses. RFC 6675 can send large including burst losses. RFC 6675 can send large unclocked bursts
unclocked bursts following burst losses. following burst losses.
Normally Proportional Rate Reduction will spread voluntary window Normally, PRR will spread voluntary window reductions out evenly
reductions out evenly across a full RTT. This has the potential to across a full RTT. This has the potential to generally reduce the
generally reduce the burstiness of Internet traffic, and could be burstiness of Internet traffic, and could be considered to be a type
considered to be a type of soft pacing. Hypothetically, any pacing of soft pacing. Hypothetically, any pacing increases the probability
increases the probability that different flows are interleaved, that different flows are interleaved, reducing the opportunity for
reducing the opportunity for ACK compression and other phenomena that ACK compression and other phenomena that increase traffic burstiness.
increase traffic burstiness. However these effects have not been However, these effects have not been quantified.
quantified.
If there are minimal losses, Proportional Rate Reduction will If there are minimal losses, PRR will converge to exactly the target
converge to exactly the target window chosen by the congestion window chosen by the congestion control algorithm. Note that as TCP
control algorithm. Note that as TCP approaches the end of recovery approaches the end of recovery, prr_delivered will approach RecoverFS
prr_delivered will approach RecoverFS and sndcnt will be computed and sndcnt will be computed such that prr_out approaches ssthresh.
such that prr_out approaches ssthresh.
Implicit window reductions due to multiple isolated losses during Implicit window reductions, due to multiple isolated losses during
recovery cause later voluntary reductions to be skipped. For small recovery, cause later voluntary reductions to be skipped. For small
numbers of losses the window size ends at exactly the window chosen numbers of losses, the window size ends at exactly the window chosen
by the congestion control algorithm. by the congestion control algorithm.
For burst losses, earlier voluntary window reductions can be undone For burst losses, earlier voluntary window reductions can be undone
by sending extra segments in response to ACKs arriving later during by sending extra segments in response to ACKs arriving later during
recovery. Note that as long as some voluntary window reductions are recovery. Note that as long as some voluntary window reductions are
not undone, the final value for pipe will be the same as ssthresh, not undone, the final value for pipe will be the same as ssthresh,
the target cwnd value chosen by the congestion control algorithm. the target cwnd value chosen by the congestion control algorithm.
Proportional Rate Reduction with either reduction bound improves the PRR with either Reduction Bound improves the situation when there are
situation when there are application stalls (e.g. when the sending application stalls, e.g., when the sending application does not queue
application does not queue data for transmission quickly enough or data for transmission quickly enough or the receiver stops advancing
the receiver stops advancing rwnd). When there is an application rwnd (receiver window). When there is an application stall early
stall early during recovery prr_out will fall behind the sum of the during recovery, prr_out will fall behind the sum of the
transmissions permitted by sndcnt. The missed opportunities to send transmissions permitted by sndcnt. The missed opportunities to send
due to stalls are treated like banked voluntary window reductions: due to stalls are treated like banked voluntary window reductions;
specifically they cause prr_delivered-prr_out to be significantly specifically, they cause prr_delivered - prr_out to be significantly
positive. If the application catches up while TCP is still in positive. If the application catches up while TCP is still in
recovery, TCP will send a partial window burst to catch up to exactly recovery, TCP will send a partial window burst to catch up to exactly
where it would have been, had the application never stalled. where it would have been had the application never stalled. Although
Although this burst might be viewed as being hard on the network, this burst might be viewed as being hard on the network, this is
this is exactly what happens every time there is a partial RTT exactly what happens every time there is a partial RTT application
application stall while not in recovery. We have made the partial stall while not in recovery. We have made the partial RTT stall
RTT stall behavior uniform in all states. Changing this behavior is behavior uniform in all states. Changing this behavior is out of
out of scope for this document. scope for this document.
Proportional Rate Reduction with Reduction Bound is less sensitive to PRR with Reduction Bound is less sensitive to errors in the pipe
errors in the pipe estimator. While in recovery, pipe is estimator. While in recovery, pipe is intrinsically an estimator,
intrinsically an estimator, using incomplete information to estimate using incomplete information to estimate if un-SACKed segments are
if un-SACKed segments are actually lost or merely out-of-order in the actually lost or merely out of order in the network. Under some
network. Under some conditions pipe can have significant errors, for conditions, pipe can have significant errors; for example, pipe is
example pipe is underestimated when when a burst of reordered data is underestimated when a burst of reordered data is prematurely assumed
prematurely assumed to be lost and marked for retransmission. If the to be lost and marked for retransmission. If the transmissions are
transmissions are regulated directly by pipe as they are with RFC regulated directly by pipe as they are with RFC 6675, a step
6675, such as step discontinuity in the pipe estimator causes a burst discontinuity in the pipe estimator causes a burst of data, which
of data, which can not be retracted once the pipe estimator is cannot be retracted once the pipe estimator is corrected a few ACKs
corrected a few ACKs later. For PRR, pipe merely determines which later. For PRR, pipe merely determines which algorithm, PRR or the
algorithm, Proportional Rate Reduction or the reduction bound, is Reduction Bound, is used to compute sndcnt from DeliveredData. While
used to compute sndcnt from DeliveredData. While pipe is pipe is underestimated, the algorithms are different by at most 1
underestimated the algorithms are different by at most one segment segment per ACK. Once pipe is updated, they converge to the same
per ACK. Once pipe is updated they converge to the same final window 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
amount of data delivered to the receiver. We claim that this Strong amount of data delivered to the receiver. We claim that this Strong
Packet Conservation Bound is the most aggressive algorithm that does Packet Conservation Bound is the most aggressive algorithm that does
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 Conservation Bound is 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 RFC 6675, which permits large bursts of data when there are bursts as RFC 6675, which permits bursts of data when there are bursts of
of losses. PRR-SSRB is a compromise that permits TCP to send one losses. PRR-SSRB is a compromise that permits TCP to send 1 extra
extra segment per ACK as compared to the packet conserving bound. segment per ACK as compared to the Packet Conserving Bound. From the
From the perspective of a strict packet conserving bound, PRR-SSRB perspective of a strict Packet Conserving Bound, PRR-SSRB does indeed
does indeed open the window during recovery, however it is open the window during recovery; however, it is significantly less
significantly less aggressive than RFC6675 in the presence of burst aggressive than RFC 6675 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 (Section 3.1
(this algorithm was not present in RFC 3517, but a similar algorithm in [FACK]) (this algorithm was not present in RFC 3517, but a similar
has been added to RFC 6675) and lost retransmission detection algorithm has been added to RFC 6675), and lost retransmission
algorithms. We confirmed that the behaviors of Rate Halving (the detection algorithms. We confirmed that the behaviors of Rate-
Linux default), RFC 3517 and PRR were authentic to their respective Halving (the Linux default), RFC 3517, and PRR were authentic to
specifications and that performance and features were comparable to their respective specifications and that performance and features
the kernels in production use. All of the different window reduction were comparable to the kernels in production use. All of the
algorithms were all present in a common kernel and could be selected different window reduction algorithms were all present in a common
with a sysctl, such that we had an absolutely uniform baseline for kernel and could be selected with a sysctl, such that we had an
comparing them. 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
below ssthresh. Precisely this condition was observed for 32% of the below ssthresh. Precisely this condition was observed for 32% of the
recovery events: pipe fell below ssthresh before Fast Retransmit is recovery events: pipe fell below ssthresh before Fast Retransmit was
triggered, thus the various PRR algorithms start in the reduction triggered, thus the various PRR algorithms started in the Reduction
bound phase, and RFC 3517 sends bursts of segments with the fast Bound phase, and RFC 3517 sent bursts of segments with the Fast
retransmit. Retransmit.
In the companion paper we observe that PRR-SSRB spends the least time In the companion paper, we observe that PRR-SSRB spends the least
in recovery of all the algorithms tested, largely because it time in recovery of all the algorithms tested, largely because it
experiences fewer timeouts once it is already in recovery. experiences fewer timeouts once it is already in recovery.
RFC 3517 experiences 29% more detected lost retransmissions and 2.6% RFC 3517 experiences 29% more detected lost retransmissions and 2.6%
more timeouts (presumably due to undetected lost retransmissions) more timeouts (presumably due to undetected lost retransmissions)
than PRR-SSRB. These results are representative of PRR-UB and other than PRR-SSRB. These results are representative of PRR-UB and other
algorithms that send bursts when pipe falls below ssthresh. algorithms that send bursts when pipe falls below ssthresh.
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 Conservation 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, (and by less aggressive and does not perform as well as RFC 3517 (and by
implication RFC 6675), which permit bursts of data when there are implication RFC 6675), which permits bursts of data when there are
bursts of losses. RFC 3517 and RFC 6675 are conservative in the bursts of losses. RFC 3517 and RFC 6675 are conservative in the
original sense of Van Jacobson's packet conservation principle, which original sense of Van Jacobson's packet conservation principle, which
included the assumption that presumed lost segments have indeed left included the assumption that presumed lost segments have indeed left
the network. PRR-CRB makes no such assumption, following instead a the network. PRR-CRB makes no such assumption, following instead a
Strong Packet Conserving Bound, in which only packets that have Strong Packet Conservation Bound in which only packets that have
actually arrived at the receiver are considered to have left the actually arrived at the receiver are considered to have left the
network. PRR-SSRB is a compromise that permits TCP to send one extra network. PRR-SSRB is a compromise that permits TCP to send 1 extra
segment per ACK relative to the Strong Packet Conserving Bound, to segment per ACK relative to the Strong Packet Conservation Bound, to
partially compensate for excess losses. partially compensate for excess losses.
From the perspective of the Strong Packet Conserving Bound, PRR-SSRB From the perspective of the Strong Packet Conservation Bound,
does indeed open the window during recovery, however it is PRR-SSRB does indeed open the window during recovery; however, it is
significantly less aggressive than RFC 3517 (and RFC 6675) in the significantly less aggressive than RFC 3517 (and RFC 6675) in the
presence of burst losses. Even so, it often outperforms RFC 3517, presence of burst losses. Even so, it often outperforms RFC 3517
(and presumably RFC 6675) because it avoids some of the self (and presumably RFC 6675) because it avoids some of the self-
inflicted losses caused by bursts. 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. Furthermore, there is one minor detail of PRR that can be studies. Furthermore, there is one minor detail of PRR that can be
improved by replacing pipe by total_pipe as defined by Laminar TCP improved by replacing pipe by total_pipe, as defined by Laminar TCP
[Laminar]. [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 PRR
proportional rate reduction and every variant of the reduction bound. and every variant of the Reduction Bound. However, we do not
However, we do not anticipate any future exploration of the anticipate any future exploration of the alternative Reduction
alternative reduction bounds. Bounds.
7. Acknowledgements 7. Acknowledgements
This draft is based in part on previous incomplete work by Matt This document is based in part on previous incomplete work by Matt
Mathis, Jeff Semke and Jamshid Mahdavi [RHID] and influenced by Mathis, Jeff Semke, and Jamshid Mahdavi [RHID] and influenced by
several discussion with John Heffner. several discussions with John Heffner.
Monia Ghobadi and Sivasankar Radhakrishnan helped analyze the Monia Ghobadi and Sivasankar Radhakrishnan helped analyze the
experiments. experiments.
Ilpo Jarvinen reviewed the code. Ilpo Jarvinen reviewed the code.
Mark Allman improved the document through his insightful review. Mark Allman improved the document through his insightful review.
8. Security Considerations 8. Security Considerations
Proportional Rate Reduction does not change the risk profile for TCP. PRR does not change the risk profile for TCP.
Implementers that change PRR from counting bytes to segments have to Implementers that change PRR from counting bytes to segments have to
be cautious about the effects of ACK splitting attacks [Savage99], be cautious about the effects of ACK splitting attacks [Savage99],
where the receiver acknowledges partial segments for the purpose of where the receiver acknowledges partial segments for the purpose of
confusing the sender's congestion accounting. confusing the sender's congestion accounting.
9. IANA Considerations 9. References
This document makes no request of IANA.
Note to RFC Editor: this section may be removed on publication as an
RFC.
10. References 9.1. Normative References
10.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 [RFC2018] Mathis, M., Mahdavi, J., Floyd, S., and A. Romanow, "TCP
Selective Acknowledgment Options", RFC 2018, October 1996. Selective Acknowledgment Options", RFC 2018, October
1996.
[RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion [RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion
Control", RFC 5681, September 2009. Control", RFC 5681, September 2009.
[RFC6675] Blanton, E., Allman, M., Wang, L., Jarvinen, I., Kojo, M., [RFC6675] Blanton, E., Allman, M., Wang, L., Jarvinen, I., Kojo,
and Y. Nishida, "A Conservative Loss Recovery Algorithm M., and Y. Nishida, "A Conservative Loss Recovery
Based on Selective Acknowledgment (SACK) for TCP", Algorithm Based on Selective Acknowledgment (SACK) for
RFC 6675, August 2012. TCP", RFC 6675, August 2012.
10.2. Informative References 9.2. Informative References
[RFC3042] Allman, M., Balakrishnan, H., and S. Floyd, "Enhancing [RFC3042] Allman, M., Balakrishnan, H., and S. Floyd, "Enhancing
TCP's Loss Recovery Using Limited Transmit", RFC 3042, TCP's Loss Recovery Using Limited Transmit", RFC 3042,
January 2001. January 2001.
[RFC3517] Blanton, E., Allman, M., Fall, K., and L. Wang, "A [RFC3517] Blanton, E., Allman, M., Fall, K., and L. Wang, "A
Conservative Selective Acknowledgment (SACK)-based Loss Conservative Selective Acknowledgment (SACK)-based Loss
Recovery Algorithm for TCP", RFC 3517, April 2003. Recovery Algorithm for TCP", RFC 3517, April 2003.
[IMC11] Dukkipati, N., Mathis, M., and Y. Cheng, "Proportional [IMC11] Dukkipati, N., Mathis, M., Cheng, Y., and M. Ghobadi,
Rate Reduction for TCP", ACM Internet Measurement "Proportional Rate Reduction for TCP", Proceedings of
Conference IMC11, December 2011. the 11th ACM SIGCOMM Conference on Internet Measurement
2011, Berlin, Germany, November 2011.
[FACK] Mathis, M. and J. Mahdavi, "Forward Acknowledgment: [FACK] Mathis, M. and J. Mahdavi, "Forward Acknowledgment:
Refining TCP Congestion Control", ACM SIGCOMM SIGCOMM96, Refining TCP Congestion Control", ACM SIGCOMM SIGCOMM96,
August 1996. August 1996.
[RHID] Mathis, M., Semke, J., Mahdavi, J., and K. Lahey, "The [RHID] Mathis, M., Semke, J., and J. Mahdavi, "The Rate-Halving
Rate-Halving Algorithm for TCP Congestion Control", Algorithm for TCP Congestion Control", Work in Progress,
draft-mathis-tcp-ratehalving (work in progress), August 1999.
June 1999.
[RHweb] Mathis, M. and J. Mahdavi, "TCP Rate-Halving with Bounding [RHweb] Mathis, M. and J. Mahdavi, "TCP Rate-Halving with
Parameters", Web publication , December 1997. 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 [CUBIC] Rhee, I. and L. Xu, "CUBIC: A new TCP-friendly high-
TCP variant", PFLDnet 2005, Feb 2005. speed TCP variant", PFLDnet 2005, February 2005.
[Jacobson88] [Jacobson88] Jacobson, V., "Congestion Avoidance and Control",
Jacobson, V., "Congestion Avoidance and Control", SIGCOMM SIGCOMM Comput. Commun. Rev. 18(4), August 1988.
Comput. Commun. Rev. 18(4), Aug 1988.
[Savage99] [Savage99] Savage, S., Cardwell, N., Wetherall, D., and T.
Savage, S., Cardwell, N., Wetherall, D., and T. Anderson, Anderson, "TCP congestion control with a misbehaving
"TCP congestion control with a misbehaving receiver", receiver", SIGCOMM Comput. Commun. Rev. 29(5), October
SIGCOMM Comput. Commun. Rev. 29(5), October 1999. 1999.
[Laminar] Mathis, M., "Laminar TCP and the case for refactoring TCP [Laminar] Mathis, M., "Laminar TCP and the case for refactoring
congestion control", draft-mathis-tcpm-tcp-laminar-01 TCP congestion control", Work in Progress, July 2012.
(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
the pipe calculation, but do not affect the outcome of PRR-CRB, once the pipe calculation, but do not affect the outcome of PRR-CRB, once
pipe has fallen below ssthresh. pipe has fallen below ssthresh.
skipping to change at page 16, line 10 skipping to change at page 15, line 36
algorithm will result in an increasing queue or additional losses if algorithm will result in an increasing queue or additional losses if
it is a full drop tail queue. it is a full drop tail queue.
We demonstrate this property with a little thought experiment: We demonstrate this property with a little thought experiment:
Imagine a network path that has insignificant delays in both Imagine a network path that has insignificant delays in both
directions, except for the processing time and queue at a single directions, except for the processing time and queue at a single
bottleneck in the forward path. By insignificant delay, we mean when bottleneck in the forward path. By insignificant delay, we mean when
a packet is "served" at the head of the bottleneck queue, the a packet is "served" at the head of the bottleneck queue, the
following events happen in much less than one bottleneck packet time: following events happen in much less than one bottleneck packet time:
the packet arrives at the receiver; the receiver sends an ACK; which the packet arrives at the receiver; the receiver sends an ACK that
arrives at the sender; the sender processes the ACK and sends some arrives at the sender; the sender processes the ACK and sends some
data; the data is queued at the bottleneck. data; the data is queued at the bottleneck.
If sndcnt is set to DeliveredData and nothing else is inhibiting If sndcnt is set to DeliveredData and nothing else is inhibiting
sending data, then clearly the data arriving at the bottleneck queue sending data, then clearly the data arriving at the bottleneck queue
will exactly replace the data that was served at the head of the 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 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 tail and full, then the queue will stay exactly full. Losses or
reordering on the ACK path only cause wider fluctuations in the queue 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 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 is in order or out of order (including loss recovery from an earlier
RTT). Any more aggressive algorithm which sends additional data will RTT). Any more aggressive algorithm that sends additional data will
overflow the drop tail queue and cause loss. Any less aggressive overflow the drop tail queue and cause loss. Any less aggressive
algorithm will under fill the queue. Therefore setting sndcnt to algorithm will under-fill the queue. Therefore, setting sndcnt to
DeliveredData is the most aggressive algorithm that does not cause DeliveredData is the most aggressive algorithm that does not cause
forced losses in this simple network. Relaxing the assumptions (e.g. forced losses in this simple network. Relaxing the assumptions
making delays more authentic and adding more flows, delayed ACKs, (e.g., making delays more authentic and adding more flows, delayed
etc) are likely to increases the fine grained fluctuations in queue ACKs, etc.) is likely to increase the fine grained fluctuations in
size but do not change its basic behavior. queue size but does not change its basic behavior.
Note that the congestion control algorithm implements a broader Note that the congestion control algorithm implements a broader
notion of optimal that includes appropriately sharing the network. notion of optimal that includes appropriately sharing the network.
Typical congestion control algorithms are likely to reduce the data Typical congestion control algorithms are likely to reduce the data
sent relative to the packet conserving bound implemented by PRR sent relative to the Packet Conserving Bound implemented by PRR,
bringing TCP's actual window down to ssthresh. bringing TCP's actual window down to ssthresh.
Authors' Addresses Authors' Addresses
Matt Mathis Matt Mathis
Google, Inc Google, Inc.
1600 Amphitheater Parkway 1600 Amphitheatre Parkway
Mountain View, California 93117 Mountain View, California 94043
USA USA
Email: mattmathis@google.com EMail: mattmathis@google.com
Nandita Dukkipati Nandita Dukkipati
Google, Inc Google, Inc.
1600 Amphitheater Parkway 1600 Amphitheatre Parkway
Mountain View, California 93117 Mountain View, California 94043
USA USA
Email: nanditad@google.com EMail: nanditad@google.com
Yuchung Cheng Yuchung Cheng
Google, Inc Google, Inc.
1600 Amphitheater Parkway 1600 Amphitheatre Parkway
Mountain View, California 93117 Mountain View, California 94043
USA USA
Email: ycheng@google.com EMail: ycheng@google.com
 End of changes. 111 change blocks. 
359 lines changed or deleted 341 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/