draft-ietf-tsvwg-dsack-use-00.txt   draft-ietf-tsvwg-dsack-use-01.txt 
Internet Engineering Task Force Ethan Blanton Internet Engineering Task Force Ethan Blanton
INTERNET DRAFT Purdue University INTERNET DRAFT Purdue University
File: draft-ietf-tsvwg-dsack-use-00.txt Mark Allman File: draft-ietf-tsvwg-dsack-use-01.txt Mark Allman
BBN/NASA GRC BBN/NASA GRC
June, 2003 August, 2003
Expires: December, 2003 Expires: February, 2004
Using TCP DSACKs and SCTP Duplicate TSNs Using TCP DSACKs and SCTP Duplicate TSNs
to Detect Spurious Retransmissions to Detect Spurious Retransmissions
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of [RFC2026]. all provisions of Section 10 of [RFC2026].
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
skipping to change at page 1, line 38 skipping to change at page 1, line 38
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
Abstract Abstract
TCP and SCTP provide notification of duplicate segment receipt TCP and SCTP provide notification of duplicate segment receipt
through DSACK and Duplicate TSN notification, respectively. This through DSACK and Duplicate TSN notification, respectively. This
document presents a conservative method of using this information to document presents conservative methods of using this information to
identify unnecessary retransmissions for various applications. identify unnecessary retransmissions for various applications.
Terminology Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119]. document are to be interpreted as described in RFC 2119 [RFC2119].
1 Introduction 1 Introduction
skipping to change at page 2, line 13 skipping to change at page 2, line 13
retransmissions from loss events for the purpose of undoing retransmissions from loss events for the purpose of undoing
unnecessary congestion control changes. unnecessary congestion control changes.
This document is intended to outline reasonable and safe algorithms This document is intended to outline reasonable and safe algorithms
for detecting spurious retransmissions and discuss some of the for detecting spurious retransmissions and discuss some of the
considerations involved. It is not intended to describe the only considerations involved. It is not intended to describe the only
possible method for achieving the goal, although the guidelines in possible method for achieving the goal, although the guidelines in
this document should be taken into consideration when designing this document should be taken into consideration when designing
alternate algorithms. Additionally, this document does not outline alternate algorithms. Additionally, this document does not outline
what a TCP or SCTP sender may do after a spurious retransmission is what a TCP or SCTP sender may do after a spurious retransmission is
detected. A number of proposals have been developed (e.g., [RFC3522], detected. A number of proposals have been developed (e.g.,
[SK03]), but it is not yet clear which of these proposals are [RFC3522], [SK03], [BDA03]), but it is not yet clear which of these
appropriate. In addition, they all rely on detecting spurious proposals are appropriate. In addition, they all rely on detecting
retransmits and so can share the algorithm specified in this spurious retransmits and so can share the algorithm specified in
document. this document.
Finally, we note that to simplify the text much of the following
discussion is in terms of TCP DSACKs, while applying to both TCP and
SCTP.
2 Counting Duplicate Notifications 2 Counting Duplicate Notifications
For certain applications a straight count of duplicate notifications For certain applications a straight count of duplicate notifications
will suffice. For instance, if a stack simply wants to know (for will suffice. For instance, if a stack simply wants to know (for
some reason) the number of spuriously retransmitted segments, some reason) the number of spuriously retransmitted segments,
counting all duplicate notifications for retransmitted segments counting all duplicate notifications for retransmitted segments
should work well. Another application of this strategy is to should work well. Another application of this strategy is to
monitor and adapt transport algorithms so that the transport is not monitor and adapt transport algorithms so that the transport is not
sending large amounts of spurious data into the network. For sending large amounts of spurious data into the network. For
instance, monitoring duplicate notifications could be used by the instance, monitoring duplicate notifications could be used by the
Early Retransmit [AAAB03] algorithm to determine whether fast Early Retransmit [AAAB03] algorithm to determine whether fast
retransmitting [RFC2581] segments with a lower than normal duplicate retransmitting [RFC2581] segments with a lower than normal duplicate
ACK threshold is working or if segment reordering is causing ACK threshold is working, or if segment reordering is causing
spurious retransmits. spurious retransmits.
More speculatively, duplicate notification has been proposed as an
integral part of estimating TCP's total loss rate [AEO03] for the
purposes of mitigating the impact of corruption-based losses on
transport protocol performance. [EOA03] proposes altering the
transport's congestion response to the fraction of losses that are
actually due to congestion by requiring the network to provide the
corruption-based loss rate and making the transport sender estimate
the total loss rate. Duplicate notifications are a key part of
estimating the total loss rate accurately [AEO03].
3 Congestion/Duplicate Disambiguation Algorithm 3 Congestion/Duplicate Disambiguation Algorithm
When the purpose of detecting spurious retransmissions is to When the purpose of detecting spurious retransmissions is to
``undo'' unnecessary changes made to the congestion control state, ``undo'' unnecessary changes made to the congestion control state,
as suggested in [RFC2883], the data sender ideally needs to as suggested in [RFC2883], the data sender ideally needs to
determine: determine:
(a) That spurious retransmissions in a particular window of data do (a) That spurious retransmissions in a particular window of data do
not mask real segment loss (congestion). not mask real segment loss (congestion).
skipping to change at page 3, line 4 skipping to change at page 3, line 18
notification that segment N+1 arrived more than once it can notification that segment N+1 arrived more than once it can
conclude that segment N+1 was needlessly resent. However, it conclude that segment N+1 was needlessly resent. However, it
cannot conclude that it is appropriate to revert the congestion cannot conclude that it is appropriate to revert the congestion
control state because the window of data contained at least one control state because the window of data contained at least one
valid congestion indication (i.e., segment N was lost). valid congestion indication (i.e., segment N was lost).
(b) That network duplication is not the cause of the duplicate (b) That network duplication is not the cause of the duplicate
notification. notification.
Determining whether a duplicate notification is caused by Determining whether a duplicate notification is caused by
network duplication or a spurious retransmit is a nearly network duplication of a packet or a spurious retransmit is a
impossible task in theory. Since [Pax97] shows that packet nearly impossible task in theory. Since [Pax97] shows that
duplication by the network is rare the algorithm in this section packet duplication by the network is rare, the algorithm in this
simply ceases to function when network duplication is detected section simply ceases to function when network duplication is
(by receiving a duplication notification for a segment that was detected (by receiving a duplication notification for a segment
not retransmitted by the sender). that was not retransmitted by the sender).
The algorithm specified below gives reasonable protection against The algorithm specified below gives reasonable, but not complete,
both of these cases. protection against both of these cases.
We assume the TCP sender has a data structure to hold selective We assume the TCP sender has a data structure to hold selective
acknowledgment information (e.g., as outlined in [RFC3517]). The acknowledgment information (e.g., as outlined in [RFC3517]). The
following steps MUST be taken upon the receipt of each DSACK or following steps MUST be taken upon the receipt of each DSACK or
duplicate TSN notification: duplicate TSN notification:
(A) Check the corresponding sequence range or TSN to determine (A) Check the corresponding sequence range or TSN to determine
whether the segment has been retransmitted. whether the segment has been retransmitted.
(A.1) If the segment was retransmitted, mark it as a duplicate. (A.1) If the SACK scoreboard is empty (i.e., the TCP sender has
received no SACK information from the receiver) processing
of this DSACK MUST be terminated and the congestion control
state MUST NOT be reverted during the current window of
data. This clause intends to cover the case when an entire
window of acknowledgments have been dropped by the network.
In such a case, the reverse path seems to be in a congested
state and so reducing TCP's sending rate is the conservative
approach.
(A.2) If the segment was not retransmitted the incoming DSACK (A.2) If the segment was retransmitted exactly one time, mark it
as a duplicate.
(A.3) If the segment was retransmitted more than once processing
of this DSACK MUST be terminated and the congestion control
state MUST NOT be reverted to its previous state during the
current window of data.
(A.4) If the segment was not retransmitted the incoming DSACK
indicates that the network duplicated the segment in indicates that the network duplicated the segment in
question. Processing of this DSACK MUST be terminated. In question. Processing of this DSACK MUST be terminated. In
addition, the algorithm specified in this document MUST NOT addition, the algorithm specified in this document MUST NOT
be used for the remainder of the connection, as future DSACK be used for the remainder of the connection, as future DSACK
reports may be indicating network duplication rather than reports may be indicating network duplication rather than
unnecessary retransmission. Note that some techniques to unnecessary retransmission. Note that some techniques to
further disambiguate network duplication from unnecessary further disambiguate network duplication from unnecessary
retransmission (e.g., the TCP timestamp option [RFC1323]) retransmission (e.g., the TCP timestamp option [RFC1323])
may be used to refine the algorithm in this document may be used to refine the algorithm in this document
further. Using such a technique in conjunction with an further. Using such a technique in conjunction with an
algorithm similar to the one presented herein may allow for algorithm similar to the one presented herein may allow for
the continued use of the algorithm in the face of duplicated the continued use of the algorithm in the face of duplicated
segments. We do not delve into such an algorithm in this segments. We do not delve into such an algorithm in this
document due the current rarity of network duplication. document due the current rarity of network duplication.
However, future work should include tackling this problem. However, future work should include tackling this problem.
(B) Check all retransmitted segments in the previous window of (B) Assuming processing is allowed to continue (per the (A) rules),
data. check all retransmitted segments in the previous window of data.
(B.1) If all segments or chunks marked as retransmitted have (B.1) If all segments or chunks marked as retransmitted have
also been marked as duplicate, we conclude that all also been marked as acknowledged and duplicated, we conclude
retransmissions in the previous window of data were spurious that all retransmissions in the previous window of data were
and no loss occurred. spurious and no loss occurred.
(B.2) If any segment or chunk is still marked as retransmitted (B.2) If any segment or chunk is still marked as retransmitted
but not marked as duplicate, there are outstanding but not marked as duplicate, there are outstanding
retransmissions that could indicate loss within this window retransmissions that could indicate loss within this window
of data. We can make no conclusions based on this of data. We can make no conclusions based on this
particular DSACK/duplicate TSN notification. particular DSACK/duplicate TSN notification.
In addition to keeping the state mentioned in [RFC3517] (for TCP) In addition to keeping the state mentioned in [RFC3517] (for TCP)
and [RFC2960] (for SCTP), an implementation of this algorithm must and [RFC2960] (for SCTP), an implementation of this algorithm must
track all sequence numbers or TSNs that have been acknowledged as track all sequence numbers or TSNs that have been acknowledged as
skipping to change at page 4, line 45 skipping to change at page 5, line 20
downside is that the algorithm is a heuristic that can be confused downside is that the algorithm is a heuristic that can be confused
by network pathologies (e.g., duplication or reordering of key by network pathologies (e.g., duplication or reordering of key
packets). Finally, note that F-RTO only works for spurious packets). Finally, note that F-RTO only works for spurious
retransmits triggered by the transport's retransmission timer. retransmits triggered by the transport's retransmission timer.
Finally, [AP99] briefly investigates using the time between Finally, [AP99] briefly investigates using the time between
retransmitting a segment via the retransmission timeout and the retransmitting a segment via the retransmission timeout and the
arrival of the next ACK as an indicator of whether the retransmit arrival of the next ACK as an indicator of whether the retransmit
was needed. The scheme compares this time delta with a fraction (f) was needed. The scheme compares this time delta with a fraction (f)
of the minimum RTT observed thus far on the connection. If the time of the minimum RTT observed thus far on the connection. If the time
delta if less than f*minRTT then the retransmit is labeled delta is less than f*minRTT then the retransmit is labeled
spurious. When f=1/2 the algorithm identifies roughly 59% of the spurious. When f=1/2 the algorithm identifies roughly 59% of the
needless retransmission timeouts and identifies needed retransmits needless retransmission timeouts and identifies needed retransmits
only 2.5% of the time. As with F-RTO, this scheme only detects only 2.5% of the time. As with F-RTO, this scheme only detects
spurious retransmits sent by the transport's retransmission timer. spurious retransmits sent by the transport's retransmission timer.
5 Security Considerations 5 Security Considerations
It is possible for the receiver to falsely indicate spurious It is possible for the receiver to falsely indicate spurious
retransmissions in the case of actual loss, potentially causing a retransmissions in the case of actual loss, potentially causing a
TCP or SCTP sender to inaccurately conclude that no loss took place TCP or SCTP sender to inaccurately conclude that no loss took place
(and possibly cause inappropriate changes to the senders congestion (and possibly cause inappropriate changes to the senders congestion
control state). Consider the following scenario: control state).
A receiver watches every segment or chunk that arrives and Consider the following scenario: A receiver watches every segment or
acknowledges any segment that arrives out of order by more than chunk that arrives and acknowledges any segment that arrives out of
some threshold amount as a duplicate, assuming that it is a order by more than some threshold amount as a duplicate, assuming
retransmission. A sender using the above algorithm will assume that it is a retransmission. A sender using the above algorithm
that the retransmission was spurious. will assume that the retransmission was spurious.
The ECN nonce sum proposal [SWE02] would help mitigate the ability The ECN nonce sum proposal [RFC3540] would help mitigate the ability
of the receiver to hide real losses from the sender. In the common of the receiver to hide real losses from the sender. In the common
case of receiving an original transmission and a spurious retransmit case of receiving an original transmission and a spurious retransmit
a TCP receiver will have received the nonce from the original a receiver will have received the nonce from the original
transmission and therefore can "prove" to the sender that the transmission and therefore can "prove" to the sender that the
duplication notification is valid. duplication notification is valid. In the case when the receiver
did not receive the original and is trying to improperly induce
the sender into transmitting at an inappropriately high rate, the
receiver will not know the ECN nonce from the original segment and
therefore will probabilistically not be able to fool the sender for
long.
References Acknowledgments
Reiner Ludwig made several useful comments on an earlier version of
this document.
References
[AAAB03] M. Allman, K. Avrachenkov, U. Ayesta, J. Blanton. Early [AAAB03] M. Allman, K. Avrachenkov, U. Ayesta, J. Blanton. Early
Retransmit for TCP. Internet-Draft Retransmit for TCP. Internet-Draft
draft-allman-tcp-early-rexmt-00.txt, February 2003. Work in draft-allman-tcp-early-rexmt-01.txt, June 2003. Work in
progress. progress.
[AEO03] Mark Allman, Wesley Eddy, Shawn Ostermann. Estimating Loss
Rates With TCP. August 2003. Under submission.
[AP99] Allman, M. and V. Paxson, "On Estimating End-to-End Network [AP99] Allman, M. and V. Paxson, "On Estimating End-to-End Network
Path Properties", SIGCOMM 99. Path Properties", SIGCOMM 99.
[BA02] E. Blanton, M. Allman. On Making TCP More Robust to Packet [BA02] E. Blanton, M. Allman. On Making TCP More Robust to Packet
Reordering. ACM Computer Communication Review, 32(1), January Reordering. ACM Computer Communication Review, 32(1), January
2002. 2002.
[BDA03] Ethan Blanton, Robert Dimond, Mark Allman. Practices for TCP
Senders in the Face of Segment Reordering, February
2003. Internet-Draft draft-blanton-tcp-reordering-00.txt (work
in progress).
[EOA03] Wesley Eddy, Shawn Ostermann, Mark Allman. New Techniques
for Making Transport Protocols Robust to Corruption-Based
Loss. July 2003. Under submission.
[LK00] R. Ludwig, R. H. Katz. The Eifel Algorithm: Making TCP [LK00] R. Ludwig, R. H. Katz. The Eifel Algorithm: Making TCP
Robust Against Spurious Retransmissions. ACM Computer Robust Against Spurious Retransmissions. ACM Computer
Communication Review, 30(1), January 2000. Communication Review, 30(1), January 2000.
[Pax97] V. Paxson. End-to-End Internet Packet Dynamics. In ACM [Pax97] V. Paxson. End-to-End Internet Packet Dynamics. In ACM
SIGCOMM, September 1997. SIGCOMM, September 1997.
[RFC793] Jon Postel. Transmission Control Protocol. Std 7, RFC [RFC793] Jon Postel. Transmission Control Protocol. Std 7, RFC
793. September 1981. 793. September 1981.
skipping to change at page 6, line 6 skipping to change at page 6, line 56
Schwarzbauer, T. Taylor, I. Rytina, M. Kalla, L. Zhang, V. Schwarzbauer, T. Taylor, I. Rytina, M. Kalla, L. Zhang, V.
Paxson. Stream Control Transmission Protocol. October 2000. Paxson. Stream Control Transmission Protocol. October 2000.
[RFC3517] Ethan Blanton, Mark Allman, Kevin Fall, Lili Wang. A [RFC3517] Ethan Blanton, Mark Allman, Kevin Fall, Lili Wang. A
Conservative Selective Acknowledgment (SACK)-based Loss Recovery Conservative Selective Acknowledgment (SACK)-based Loss Recovery
Algorithm for TCP, April 2003. RFC 3517. Algorithm for TCP, April 2003. RFC 3517.
[RFC3522] R. Ludwig, M. Meyer. The Eifel Detection Algorithm for [RFC3522] R. Ludwig, M. Meyer. The Eifel Detection Algorithm for
TCP, April 2003. RFC 3522. TCP, April 2003. RFC 3522.
[RFC3540] N. Spring, D. Wetherall, D. Ely. Robust Explicit
Congestion Notification (ECN) Signaling with Nonces, June 2003.
RFC 3540.
[SK03] P. Sarolahti, M. Kojo. F-RTO: An Algorithm for Detecting [SK03] P. Sarolahti, M. Kojo. F-RTO: An Algorithm for Detecting
Spurious Retransmission Timeouts with TCP and SCTP. Spurious Retransmission Timeouts with TCP and SCTP.
Internet-Draft draft-sarolahti-tsvwg-tcp-frto-04.txt, June 2003. Internet-Draft draft-sarolahti-tsvwg-tcp-frto-04.txt, June 2003.
Work in progress. Work in progress.
[SWE02] N. Spring, D. Wetherall, D. Ely. Robust ECN Signaling with
Nonces. Internet-Draft draft-ietf-tsvwg-tcp-nonce-04.txt,
October 2002. Work in progress.
Authors' Addresses: Authors' Addresses:
Ethan Blanton Ethan Blanton
Purdue University Computer Sciences Purdue University Computer Sciences
1398 Computer Science Building 1398 Computer Science Building
West Lafayette, IN 47907 West Lafayette, IN 47907
eblanton@cs.purdue.edu eblanton@cs.purdue.edu
Mark Allman Mark Allman
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/