Internet Engineering Task Force                            Ethan Blanton
INTERNET DRAFT                                         Purdue University
File: draft-ietf-tsvwg-dsack-use-00.txt                      Mark Allman
                                                            BBN/NASA GRC
                                                              June, 2003
                                                Expires:  December, 2003

               Using TCP DSACKs and SCTP Duplicate TSNs
                  to Detect Spurious Retransmissions

Status of this Memo

    This document is an Internet-Draft and is in full conformance with
    all provisions of Section 10 of [RFC2026].

    Internet-Drafts are working documents of the Internet Engineering
    Task Force (IETF), its areas, and its working groups.  Note that
    other groups may also distribute working documents as
    Internet-Drafts.

    Internet-Drafts are draft documents valid for a maximum of six
    months and may be updated, replaced, or obsoleted by other documents
    at any time.  It is inappropriate to use Internet-Drafts as
    reference material or to cite them other than as "work in progress."

    The list of current Internet-Drafts can be accessed at
    http://www.ietf.org/ietf/1id-abstracts.txt

    The list of Internet-Draft Shadow Directories can be accessed at
    http://www.ietf.org/shadow.html.

Abstract

    TCP and SCTP provide notification of duplicate segment receipt
    through DSACK and Duplicate TSN notification, respectively. This
    document presents a conservative method of using this information to
    identify unnecessary retransmissions for various applications.

Terminology

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
    "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
    document are to be interpreted as described in RFC 2119 [RFC2119].

1   Introduction

    TCP [RFC793] and SCTP [RFC2960] provide notification of duplicate
    segment receipt through duplicate selective acknowledgment (DSACK)
    [RFC2883] and Duplicate TSN notifications, respectively.  Using this
    information, a TCP or SCTP sender can generally determine when a
    retransmission was sent in error.  This document presents two
    methods for using duplicate notifications.  The first method is
    simple and can be used for accounting applications.  The second
    method is a conservative algorithm to disambiguate unnecessary
    retransmissions from loss events for the purpose of undoing

Expires: December 2003                                          [Page 1]


draft-ietf-tsvwg-dsack-use-00.txt                              June 2003

    unnecessary congestion control changes.

    This document is intended to outline reasonable and safe algorithms
    for detecting spurious retransmissions and discuss some of the
    considerations involved.  It is not intended to describe the only
    possible method for achieving the goal, although the guidelines in
    this document should be taken into consideration when designing
    alternate algorithms.  Additionally, this document does not outline
    what a TCP or SCTP sender may do after a spurious retransmission is
    detected.  A number of proposals have been developed (e.g., [RFC3522],
    [SK03]), but it is not yet clear which of these proposals are
    appropriate.  In addition, they all rely on detecting spurious
    retransmits and so can share the algorithm specified in this
    document.


2   Counting Duplicate Notifications

    For certain applications a straight count of duplicate notifications
    will suffice.  For instance, if a stack simply wants to know (for
    some reason) the number of spuriously retransmitted segments,
    counting all duplicate notifications for retransmitted segments
    should work well.  Another application of this strategy is to
    monitor and adapt transport algorithms so that the transport is not
    sending large amounts of spurious data into the network.  For
    instance, monitoring duplicate notifications could be used by the
    Early Retransmit [AAAB03] algorithm to determine whether fast
    retransmitting [RFC2581] segments with a lower than normal duplicate
    ACK threshold is working or if segment reordering is causing
    spurious retransmits.

3   Congestion/Duplicate Disambiguation Algorithm

    When the purpose of detecting spurious retransmissions is to
    ``undo'' unnecessary changes made to the congestion control state,
    as suggested in [RFC2883], the data sender ideally needs to
    determine:

    (a) That spurious retransmissions in a particular window of data do
        not mask real segment loss (congestion).

        For example, assume segments N and N+1 are retransmitted even
        though only segment N was dropped by the network (thus, segment
        N+1 was needlessly retransmitted).  When the sender receives the
        notification that segment N+1 arrived more than once it can
        conclude that segment N+1 was needlessly resent.  However, it
        cannot conclude that it is appropriate to revert the congestion
        control state because the window of data contained at least one
        valid congestion indication (i.e., segment N was lost).

    (b) That network duplication is not the cause of the duplicate
        notification.

        Determining whether a duplicate notification is caused by

Expires: December 2003                                          [Page 2]


draft-ietf-tsvwg-dsack-use-00.txt                              June 2003

        network duplication or a spurious retransmit is a nearly
        impossible task in theory.  Since [Pax97] shows that packet
        duplication by the network is rare the algorithm in this section
        simply ceases to function when network duplication is detected
        (by receiving a duplication notification for a segment that was
        not retransmitted by the sender).

    The algorithm specified below gives reasonable protection against
    both of these cases.

    We assume the TCP sender has a data structure to hold selective
    acknowledgment information (e.g., as outlined in [RFC3517]).  The
    following steps MUST be taken upon the receipt of each DSACK or
    duplicate TSN notification:

    (A) Check the corresponding sequence range or TSN to determine
        whether the segment has been retransmitted.

        (A.1) If the segment was retransmitted, mark it as a duplicate.

        (A.2) If the segment was not retransmitted the incoming DSACK
            indicates that the network duplicated the segment in
            question.  Processing of this DSACK MUST be terminated.  In
            addition, the algorithm specified in this document MUST NOT
            be used for the remainder of the connection, as future DSACK
            reports may be indicating network duplication rather than
            unnecessary retransmission.  Note that some techniques to
            further disambiguate network duplication from unnecessary
            retransmission (e.g., the TCP timestamp option [RFC1323])
            may be used to refine the algorithm in this document
            further.  Using such a technique in conjunction with an
            algorithm similar to the one presented herein may allow for
            the continued use of the algorithm in the face of duplicated
            segments.  We do not delve into such an algorithm in this
            document due the current rarity of network duplication.
            However, future work should include tackling this problem.

    (B) Check all retransmitted segments in the previous window of
        data.

        (B.1) If all segments or chunks marked as retransmitted have
            also been marked as duplicate, we conclude that all
            retransmissions in the previous window of data were spurious
            and no loss occurred.

        (B.2) If any segment or chunk is still marked as retransmitted
            but not marked as duplicate, there are outstanding
            retransmissions that could indicate loss within this window
            of data.  We can make no conclusions based on this
            particular DSACK/duplicate TSN notification.

    In addition to keeping the state mentioned in [RFC3517] (for TCP)
    and [RFC2960] (for SCTP), an implementation of this algorithm must
    track all sequence numbers or TSNs that have been acknowledged as

Expires: December 2003                                          [Page 3]


draft-ietf-tsvwg-dsack-use-00.txt                              June 2003

    duplicates.

4   Related Work

    In addition to the mechanism for detecting spurious retransmits
    outlined in this document, several other proposals for finding
    needless retransmits have been developed.

    [BA02] uses the algorithm outlined in this document as the basis for
    investigating several methods to make TCP more robust to reordered
    packets.

    The Eifel detection algorithm [RFC3522] uses the TCP timestamp
    option [RFC1323] to determine whether the ACK for a given retransmit
    is for the original transmission or a retransmission.  More
    generally, [LK00] outlines the benefits of detecting spurious
    retransmits and reverting from needless congestion control changes
    using the timestamp-based scheme or a mechanism that uses a
    "retransmit bit" to flag retransmits (and ACKs of retransmits).  The
    Eifel detection algorithm can detect spurious retransmits more
    rapidly than a DSACK-based scheme.  However, the tradeoff is that
    the overhead of the 12-byte timestamp option must be incurred in
    every packet transmitted for Eifel to function.

    The F-RTO scheme [SK03] slightly alters TCP's sending pattern
    immediately following a retransmission timeout and then observes the
    pattern of the returning ACKs.  This pattern can indicate whether
    the retransmitted segment was needed.  The advantage of F-RTO is
    that the algorithm only needs to be implemented on the sender side
    of the TCP connection and that nothing extra needs to cross the
    network (e.g., DSACKs, timestamps, special flags, etc.).  The
    downside is that the algorithm is a heuristic that can be confused
    by network pathologies (e.g., duplication or reordering of key
    packets).  Finally, note that F-RTO only works for spurious
    retransmits triggered by the transport's retransmission timer.

    Finally, [AP99] briefly investigates using the time between
    retransmitting a segment via the retransmission timeout and the
    arrival of the next ACK as an indicator of whether the retransmit
    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
    delta if less than f*minRTT then the retransmit is labeled
    spurious.  When f=1/2 the algorithm identifies roughly 59% of the
    needless retransmission timeouts and identifies needed retransmits
    only 2.5% of the time.  As with F-RTO, this scheme only detects
    spurious retransmits sent by the transport's retransmission timer.

5   Security Considerations

    It is possible for the receiver to falsely indicate spurious
    retransmissions in the case of actual loss, potentially causing a
    TCP or SCTP sender to inaccurately conclude that no loss took place
    (and possibly cause inappropriate changes to the senders congestion
    control state).  Consider the following scenario:

Expires: December 2003                                          [Page 4]


draft-ietf-tsvwg-dsack-use-00.txt                              June 2003


    A receiver watches every segment or chunk that arrives and
    acknowledges any segment that arrives out of order by more than
    some threshold amount as a duplicate, assuming that it is a
    retransmission.  A sender using the above algorithm will assume
    that the retransmission was spurious.

    The ECN nonce sum proposal [SWE02] would help mitigate the ability
    of the receiver to hide real losses from the sender.  In the common
    case of receiving an original transmission and a spurious retransmit
    a TCP receiver will have received the nonce from the original
    transmission and therefore can "prove" to the sender that the
    duplication notification is valid.

References

    [AAAB03] M. Allman, K. Avrachenkov, U. Ayesta, J. Blanton.  Early
        Retransmit for TCP.  Internet-Draft
        draft-allman-tcp-early-rexmt-00.txt, February 2003.  Work in
        progress.

    [AP99] Allman, M. and V. Paxson, "On Estimating End-to-End Network
        Path Properties", SIGCOMM 99.

    [BA02] E. Blanton, M. Allman.  On Making TCP More Robust to Packet
        Reordering.  ACM Computer Communication Review, 32(1), January
        2002.

    [LK00] R. Ludwig, R. H. Katz.  The Eifel Algorithm: Making TCP
        Robust Against Spurious Retransmissions.  ACM Computer
        Communication Review, 30(1), January 2000.

    [Pax97] V. Paxson.  End-to-End Internet Packet Dynamics.  In ACM
        SIGCOMM, September 1997.

    [RFC793] Jon Postel.  Transmission Control Protocol.  Std 7, RFC
        793.  September 1981.

    [RFC1323] Van Jacobson, Robert Braden, David Borman.  TCP Extensions
        for High Performance.  RFC 1323.  May 1992.

    [RFC2883] S. Floyd, J. Mahdavi, M. Mathis, M. Podolsky.  An
        Extension to the Selective Acknowledgement (SACK) Option for
        TCP.  RFC 2883, July 2000.

    [RFC2960] R. Stewart, Q. Xie, K. Morneault, C. Sharp, H.
        Schwarzbauer, T. Taylor, I. Rytina, M. Kalla, L. Zhang, V.
        Paxson.  Stream Control Transmission Protocol.  October 2000.

    [RFC3517] Ethan Blanton, Mark Allman, Kevin Fall, Lili Wang. A
        Conservative Selective Acknowledgment (SACK)-based Loss Recovery
        Algorithm for TCP, April 2003. RFC 3517.

    [RFC3522] R. Ludwig, M. Meyer.  The Eifel Detection Algorithm for

Expires: December 2003                                          [Page 5]


draft-ietf-tsvwg-dsack-use-00.txt                              June 2003

        TCP, April 2003.  RFC 3522.

    [SK03] P. Sarolahti, M. Kojo.  F-RTO: An Algorithm for Detecting
        Spurious Retransmission Timeouts with TCP and SCTP.
        Internet-Draft draft-sarolahti-tsvwg-tcp-frto-04.txt, June 2003.
        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:

    Ethan Blanton
    Purdue University Computer Sciences
    1398 Computer Science Building
    West Lafayette, IN  47907
    eblanton@cs.purdue.edu

    Mark Allman
    BBN Technologies/NASA Glenn Research Center
    Lewis Field
    21000 Brookpark Rd.  MS 54-5
    Cleveland, OH  44135
    Phone: 216-433-6586
    Fax: 216-433-8705
    mallman@bbn.com
    http://roland.grc.nasa.gov/~mallman



























Expires: December 2003                                          [Page 6]