draft-ietf-tcpm-proportional-rate-reduction-01.txt		draft-ietf-tcpm-proportional-rate-reduction-02.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: August 27, 2012 Google, Inc		Expires: January 14, 2013 Google, Inc
	February 24, 2012		July 13, 2012
	Proportional Rate Reduction for TCP		Proportional Rate Reduction for TCP
	draft-ietf-tcpm-proportional-rate-reduction-01.txt		draft-ietf-tcpm-proportional-rate-reduction-02.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
	ACKs arriving from the receiver. Two widely deployed algorithms are		ACKs arriving from the receiver. Two widely deployed algorithms are
	used to implement this window reduction: Fast Recovery and Rate		used to implement this window reduction: Fast Recovery and Rate
	Halving. Both algorithms are needlessly fragile under a number of		Halving. Both algorithms are needlessly fragile under a number of
	conditions, particularly when there is a burst of losses that such		conditions, particularly when there is a burst of losses such that
	that the number of ACKs returning to the sender is small.		the number of ACKs returning to the sender is small. Proportional
	Proportional Rate Reduction minimizes these excess window reductions		Rate Reduction minimizes these excess window reductions such that at
	such that at the end of recovery the actual window size will be as		the end of recovery the actual window size will be as close as
	close as possible to ssthresh, the window size determined by the		possible to ssthresh, the window size determined by the congestion
	congestion control algorithm. It is patterned after Rate Halving,		control algorithm. It is patterned after Rate Halving, but using the
	but using the fraction that is appropriate for target window chosen		fraction that is appropriate for target window chosen by the
	by the congestion control algorithm.		congestion control algorithm.
	Status of this Memo		Status of this Memo
	This Internet-Draft is submitted in full conformance with the		This Internet-Draft is submitted in full conformance with the
	provisions of BCP 78 and BCP 79.		provisions of BCP 78 and BCP 79.
	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 August 27, 2012.		This Internet-Draft will expire on January 14, 2013.
	Copyright Notice		Copyright Notice
	Copyright (c) 2012 IETF Trust and the persons identified as the		Copyright (c) 2012 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
	skipping to change at page 2, line 33		skipping to change at page 2, line 33
	2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 4		2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 4
	3. Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 5		3. Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 5
	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 . . . . . . . . . . . . . . . . . . . . . 13
	10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13		10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13
			10.1. Normative References . . . . . . . . . . . . . . . . . . . 13
			10.2. Informative References . . . . . . . . . . . . . . . . . . 14
	Appendix A. Packet Conservation Bound . . . . . . . . . . . . . . 14		Appendix A. Packet Conservation Bound . . . . . . . . . . . . . . 14
	Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 15		Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 15
	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. It's 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 adjusts the window		clock more data into the network. Fast Recovery adjusts the window
	by waiting for one half RTT of ACKs to pass before sending any data.		by waiting for one half RTT of ACKs to pass before sending any data.
	It is fragile because it can not compensate for the implicit window		It is fragile because it can not compensate for the implicit window
	reduction caused by the losses themselves, and is exposed to		reduction caused by the losses themselves, and is exposed to
	timeouts. For example if half of the data or ACKs are lost, Fast		timeouts. For example if half of the data or ACKs are lost, Fast
	Recovery's expected behavior would be wait for half window of ACKs to		Recovery's expected behavior would be to wait for a half of a window
	pass and then not receive any ACKs for the recovery and suffer a		of (remaining) ACKs to pass. It would then not receive any of the
	timeout.		ACKs needed for recovery and suffer a timeout.
	The rate-halving algorithm improves this situation by sending data on		The rate-halving algorithm improves this situation by sending data on
	alternate ACKs during recovery, such that after one RTT the window		alternate ACKs during recovery, such that after one RTT the window
	has been halved. Rate-having is implemented in Linux after only		has been halved. Rate-halving is implemented in Linux after only
	being informally published [RHweb], including an uncompleted		being informally published [RHweb], including an uncompleted
	Internet-Draft [RHID]. Rate-halving does not adequately compensate		Internet-Draft [RHID]. Rate-halving also does not adequately
	for the implicit window reduction caused by the losses and assumes a		compensate for the implicit window reduction caused by the losses and
	50% window reduction, which was completely standard at the time it		assumes a 50% window reduction, which was completely standard at the
	was written, but not appropriate for modern congestion control		time it was written, but not appropriate for modern congestion
	algorithms such as Cubic [CUBIC], which can reduce the window by less		control algorithms such as Cubic [CUBIC], which reduce the window by
	than 50%. As a consequence rate-halving often allows the window to		less than 50%. As a consequence rate-halving often allows the window
	fall further than necessary, reducing performance and increasing the		to fall further than necessary, reducing performance and increasing
	risk of timeouts if there are additional losses.		the risk of timeouts if there are additional losses.
	Proportional Rate Reduction (PPR) avoids these excess window		Proportional Rate Reduction (PPR) avoids these excess window
	reductions such that at the end of recovery the actual window size		reductions such that at the end of recovery the actual window size
	will be as close as possible to, ssthresh, the window size determined		will be as close as possible to ssthresh, the window size determined
	by the congestion control algorithm. It is patterned after Rate		by the congestion control algorithm. It is patterned after Rate
	Halving, but using the fraction that is appropriate for target window		Halving, but using the fraction that is appropriate for the target
	chosen by the congestion control algorithm. During PRR one of two		window chosen by the congestion control algorithm. During PRR one of
	additional reduction bound algorithms limits the total window		two additional reduction bound algorithms limits the total window
	reduction due to all mechanisms, including application stalls and the		reduction due to all mechanisms, including application stalls and the
	losses themselves.		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 conservative bound described in Appendix A, however in		the strong conservative bound described in Appendix A, however in
	real networks it does not perform as well as the algorithms described		real networks it does not perform as well as the algorithms described
	in RFC 3517, which prove to be non-conservative in a significant		in RFC 3517, which prove to be non-conservative in a significant
	skipping to change at page 4, line 31		skipping to change at page 4, line 31
	We evaluated these and other algorithms in a large scale measurement		We evaluated these and other algorithms in a large scale measurement
	study, summarized below. The most important results from that study		study, summarized below. The most important results from that study
	are presented in an companion paper [IMC11]. PRR+SSRB outperforms		are presented in an companion paper [IMC11]. PRR+SSRB outperforms
	both RFC 3517 and Linux Rate Halving under authentic network traffic,		both RFC 3517 and Linux Rate Halving under authentic network traffic,
	even though it is less aggressive than RFC 3517.		even though it is less aggressive than RFC 3517.
	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		[RFC3517]. They are most accurate and more easily implemented with
	SACK [RFC2018], but they do not require SACK.		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 3517: covered (as in "covered sequence numbers")		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)
	skipping to change at page 5, line 35		skipping to change at page 5, line 35
	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 recov		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 recov		RecoverFS = snd.nxt-snd.una // FlightSize at the start of recovery
	On every ACK during recovery compute:		On every ACK during recovery compute:
	DeliveredData = delta(snd.una) + delta(SACKd)		DeliveredData = change_in(snd.una) + change_in(SACKd)
	prr_delivered += DeliveredData		prr_delivered += DeliveredData
	pipe = (RFC 3517 pipe algorithm)		pipe = (RFC 3517 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
	skipping to change at page 6, line 30		skipping to change at page 6, line 30
	}		}
	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, standard		of 15 consecutive losses. In all cases we assume bulk data (no
	AIMD congestion control and cwnd = FlightSize = pipe = 20 segments,		application pauses), standard AIMD congestion control and cwnd =
	so ssthresh will be set to 10 at the beginning of recovery. We also		FlightSize = pipe = 20 segments, so ssthresh will be set to 10 at the
	assume standard Fast Retransmit and Limited Transmit, so we send two		beginning of recovery. We also assume standard Fast Retransmit and
	new segments followed by one retransmit on the first 3 duplicate ACKs		Limited Transmit, so TCP will send two new segments followed by one
	after the losses.		retransmit 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 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. Since PRR does not		ssthresh - pipe indicated by "s" in the "RB" row.
	use cwnd during recovery it is not shown in the example.
	RFC 3517		RFC 3517
	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
			Cwnd is not shown because PRR does not use it.
	Note that all three algorithms send same total amount of data. RFC		Key for RB
	3517 experiences a "half-window of silence", while the Rate Halving		s: sndcnt = ssthresh - pipe // from ssthresh
	and PRR spread the voluntary window reduction across an entire RTT.		b: sndcnt = prr_delivered - prr_out + SMSS // from banked
			d: sndcnt = DeliveredData + SMSS // from DeliveredData
			(Sometimes more than one applies)
			Note that all three algorithms send the same total amount of data.
			RFC 3517 experiences a "half-window of silence", while the Rate
			Halving and PRR spread the voluntary window reduction across an
			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 3517
	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
	skipping to change at page 8, line 21		skipping to change at page 8, line 21
	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: f f f		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: d d d		RB: bd d d
	In this specific situation, RFC 3517 is very non-conservative,		In this specific situation, RFC 3517 is very non-conservative,
	because once fast retransmit is triggered (on the ACK for segment 17)		because once fast retransmit is triggered (on the ACK for segment 17)
	TCP immediately retransmits sufficient data to bring pipe up to cwnd.		TCP immediately retransmits sufficient data to bring pipe up to cwnd.
	Our measurement data (see Section 5) indicates that RFC 3517		Our measurement data (see Section 5) indicates that RFC 3517
	significantly outperforms Rate Halving, PRR-CRB and some other		significantly outperforms Rate Halving, PRR-CRB and some other
	similarly conservative algorithms that we tested, suggesting that it		similarly conservative algorithms that we tested, suggesting that it
	is significantly common for the actual losses to exceed the window		is significantly common for the actual losses to exceed the window
	reduction determined by the congestion control algorithm.		reduction determined by the congestion control algorithm.
	skipping to change at page 9, line 5		skipping to change at page 9, line 5
	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
	raise the window at all during recovery, so when recovery finally		raise the window at all during recovery, so when recovery finally
	completes, TCP will slowstart cwnd from 5 up to 10. In this example,		completes, TCP will slowstart cwnd from 5 up to 10. In this example,
	TCP operates at half of the window chosen by the congestion control		TCP operates at half of the window chosen by the congestion control
	for more than three RTTs, increasing the elapsed time and exposing it		for more than three RTTs, increasing the elapsed time and exposing it
	to timeouts in the event that there are additional losses.		to timeouts in the event that there are additional losses.
	PRR-CRB implements 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 was set to prr_delivered - prr_out. This
	is indicated by the RB:f tagging in the figure. In this case PRR-CRB		is indicated by the RB:b tagging in the figure. In this case PRR-CRB
	is exposed to exactly the same problems as Rate Halving, the excess		is exposed to exactly the same problems as Rate Halving, the excess
	window reduction causes it to take excessively long to recover the		window reduction causes it to take excessively long to recover the
	losses and exposes it to additional timeouts.		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 sshthresh 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 slowstart during recovery, and
	indicated by RB:d tagging in the figure. Although increasing the		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 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 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
	skipping to change at page 11, line 31		skipping to change at page 11, line 31
	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 results are summarized here.		recovery. The results are 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 [RFC3742], threshold transmit from [FACK]		[CUBIC], limited transmit [RFC3042], threshold transmit from [FACK]
	and lost retransmission detection algorithms. We confirmed that the		and lost retransmission detection algorithms. We confirmed that the
	behaviors of Rate Halving (the Linux default), RFC 3517 and PRR were		behaviors of Rate Halving (the Linux default), RFC 3517 and PRR were
	authentic to their respective specifications and that performance and		authentic to their respective specifications and that performance and
	features were comparable to the kernels in production use. The		features were comparable to the kernels in production use. The
	different window reduction algorithms were all present in the same		different window reduction algorithms were all present in the same
	kernel and could be selected with a sysctl, such that we had an		kernel and could be selected with a sysctl, such that we had an
	absolutely uniform baseline for 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
	skipping to change at page 12, line 41		skipping to change at page 12, line 41
	Although the packet conserving bound is very appealing for a number		Although the packet conserving bound is very appealing for a number
	of reasons, our measurements demonstrate that it is less aggressive		of reasons, our measurements demonstrate that it is less aggressive
	and does not perform as well as RFC3517, which permits significant		and does not perform as well as RFC3517, which permits significant
	bursts of data when there are large bursts of losses. PRR-SSRB is a		bursts of data when there are large bursts of losses. PRR-SSRB is a
	compromise that permits TCP to send one extra segment per ACK as		compromise that permits TCP to send one extra segment per ACK as
	relative to the packet conserving bound. From the perspective of the		relative to the packet conserving bound. From the perspective of the
	packet conserving bound, PRR-SSRB does indeed open the window during		packet conserving bound, PRR-SSRB does indeed open the window during
	recovery, however it is significantly less aggressive than RFC3517 in		recovery, however it is significantly less aggressive than RFC3517 in
	the presence of burst losses. Even so, it often out performs		the presence of burst losses. Even so, it often out performs
	RFC3517, because it avoids some of the self inflicted losses caused		RFC3517, because it avoids some of the self inflicted losses caused
	by bursts from RFC3517.		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.
	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
	skipping to change at page 13, line 16		skipping to change at page 13, line 16
	7. Acknowledgements		7. Acknowledgements
	This draft is based in part on previous incomplete work by Matt		This draft 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 discussion with John Heffner.
	Monia Ghobadi and Sivasankar Radhakrishnan helped analyze the		Monia Ghobadi and Sivasankar Radhakrishnan helped analyze the
	experiments.		experiments.
	Ilpo Jarvinen for reviewing the code.		Ilpo Jarvinen reviewed the code.
	8. Security Considerations		8. Security Considerations
	Proportional Rate Reduction does not change the risk profile for TCP.		Proportional Rate Reduction 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. IANA Considerations
	This document makes no request of IANA.		This document makes no request of IANA.
	Note to RFC Editor: this section may be removed on publication as an		Note to RFC Editor: this section may be removed on publication as an
	RFC.		RFC.
	10. References		10. References
			10.1. Normative References
	[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.
	[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.
	[RFC3742] Floyd, S., "Limited Slow-Start for TCP with Large
	Congestion Windows", RFC 3742, March 2004.
	[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.
			10.2. Informative References
			[RFC3042] Allman, M., Balakrishnan, H., and S. Floyd, "Enhancing
			TCP's Loss Recovery Using Limited Transmit", RFC 3042,
			January 2001.
	[IMC11] Dukkipati, N., Mathis, M., and Y. Cheng, "Proportional		[IMC11] Dukkipati, N., Mathis, M., and Y. Cheng, "Proportional
	Rate Reduction for TCP", ACM Internet Measurement		Rate Reduction for TCP", ACM Internet Measurement
	Conference IMC11, December 2011.		Conference IMC11, December 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., Mahdavi, J., and K. Lahey, "The
	Rate-Halving Algorithm for TCP Congestion Control", draft-		Rate-Halving Algorithm for TCP Congestion Control",
	ratehalving (work in progress), June 1999.		draft-mathis-tcp-ratehalving (work in progress),
			June 1999.
	[RHweb] Mathis, M. and J. Mahdavi, "TCP Rate-Halving with Bounding		[RHweb] Mathis, M. and J. Mahdavi, "TCP Rate-Halving with Bounding
	Parameters", Web publication , December 1997.		Parameters", Web publication , December 1997.
	[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-speed
	TCP variant", PFLDnet 2005, Feb 2005.		TCP variant", PFLDnet 2005, Feb 2005.
	[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",
	skipping to change at page 15, line 7		skipping to change at page 15, line 13
	fluctuation due to differences in packet arrival and exit times. Any		fluctuation due to differences in packet arrival and exit times. Any
	less aggressive algorithm will result in a declining queue at the		less aggressive algorithm will result in a declining queue at the
	bottleneck. Any more aggressive algorithm will result in an		bottleneck. Any more aggressive algorithm will result in an
	increasing queue or additional losses if it is a full drop tail		increasing queue or additional losses if it is a full drop tail
	queue.		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, I 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; which
	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 the peak size, independent of whether the data		size, but do not raise the 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 which sends additional data will
	cause a queue overflow and loss. Any less aggressive algorithm will		overflow the drop tail queue and cause loss. Any less aggressive
	under fill the queue. Therefore setting sndcnt to DeliveredData is		algorithm will under fill the queue. Therefore setting sndcnt to
	the most aggressive algorithm that does not cause forced losses in		DeliveredData is the most aggressive algorithm that does not cause
	this simple network. Relaxing the assumptions (e.g. making delays		forced losses in this simple network. Relaxing the assumptions (e.g.
	more authentic and adding more flows, delayed ACKs, etc) may		making delays more authentic and adding more flows, delayed ACKs,
	increases the fine grained fluctuations in queue size but does not		etc) may increases the fine grained fluctuations in queue size but
	change its basic behavior.		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 of 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 Amphitheater Parkway
	Mountain View, California 93117		Mountain View, California 93117
End of changes. 35 change blocks.
	67 lines changed or deleted		83 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/