[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
Internet Engineering Task Force                            Ethan Blanton
INTERNET DRAFT                                         Purdue University
File: draft-blanton-tcp-reordering-00.txt                  Robert Dimond
                                                        Verizon/NASA GRC
                                                             Mark Allman
                                                            BBN/NASA GRC
                                                          February, 2003
                                                     Expires: July, 2003

                Practices for TCP Senders in the Face of
                           Segment Reordering

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 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

    The list of Internet-Draft Shadow Directories can be accessed at


    This document outlines actions a TCP sender can take after
    determining that a spurious fast retransmission has been sent due to
    packet reordering.  The document outlines the method a TCP
    connection can use to "undo" needless changes made to the congestion
    control state.  In addition, several methods to help prevent future
    fast retransmits are outlined.


    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
    document are to be interpreted as described in RFC 2119 [RFC2119].

1   Introduction

    As outlined in [RFC793] TCP receivers always indicate the next
    in-order byte of data they expect to receive in the acknowledgments
    (ACKs) they send.  Therefore, if a segment arrives that does not
    include the next expected byte of data, the receiver generates a

Expires: July 2003                                              [Page 1]

draft-blanton-tcp-reordering-00.txt                        February 2003

    duplicate ACK.  This situation can arise from either packet loss or
    from packet reordering in the network.

    Meanwhile, TCP's fast retransmit algorithm [Jac88,RFC2581] uses the
    arrival of three duplicate ACKs as an indication that the network
    lost the packet containing the indicated data byte.  Upon detection
    of a lost segment via fast retransmit the sender resends the given
    data segment before the expiration of the retransmission timer
    (RTO).  The sender waits for three duplicate ACKs in an attempt to
    distinguish between actual packet loss and small amounts of packet

    Several Internet measurement studies have shown that waiting for the
    arrival of three duplicate ACKs may not be sufficient to distinguish
    between packet loss and packet reordering over some network paths
    [Pax97,BPS99].  Therefore, in some cases a TCP sender may send a
    spurious fast retransmit.  This spurious retransmit wastes network
    resources on needless work, as well as causing the TCP sender to
    infer that the network is experiencing congestion and thus the
    sender should reduce its sending rate.  [BA02a] shows the
    performance impact of various levels of reordering on TCP

    This document offers several experimental strategies for mitigating
    the impact of spurious fast retransmits.  The first mitigation is to
    allow the sender to revert to its previous sending rate when
    spurious retransmissions are detected.  The second mitigation is to
    dynamically vary the number of duplicate ACKs required to trigger
    fast retransmit in an attempt to prevent spurious retransmissions.

    Explicitly out of scope for this document is the subject of spurious
    RTOs.  This subject is covered by others (as outlined in section 3
    on related work).

    We hope the community will experiment with the mechanisms presented
    in this document and provide their experience and input to a future
    decision on which mechanisms (if any) may be appropriate to include
    as part of the TCP's standard congestion control algorithms.

    This document is organized as follows.  Section 2 offers
    definitions.  Section 3 outlines related work.  Section 4 details
    how a TCP sender can revert to a previous congestion control state
    after a spurious retransmit has been detected.  Section 5 outlines
    the methods for dynamically adjusting the number of duplicate ACKs
    required to trigger fast retransmit.  Section 6 discusses
    interactions between adjusting the duplicate ACK threshold and the
    RTO.  Section 7 sketches future work in this area.  Section 8
    outlines security considerations.

2   Definitions

    It is assumed that the reader is familiar with the congestion
    control concepts and terminology for TCP from [RFC2581].

Expires: July 2003                                              [Page 2]

draft-blanton-tcp-reordering-00.txt                        February 2003

    In addition, the following terms will be used:

        ``dupthresh'' represents the number of duplicate ACKs required
        to trigger a fast retransmit.  [RFC2581] defines dupthresh to be
        3 duplicate ACKs.

3   Related Work

    [Editor's note: Additional related work outlined in [SL02] will be
     included in a later version of this document.]

    A number of documents have been written on the subject of spurious
    retransmits.  In this space, there are three categories of

    (1) Mechanisms for detecting spurious retransmits.

        The changes specified in this document require a mechanism to
        detect when a TCP sender has needlessly retransmitted.  We do
        not specify any one algorithm that must be used with our
        mitigation strategies because the exact method employed does not
        have a direct impact on this specification.  (That is not to say
        that the choice of detection mechanism is immaterial in a larger

        [BA02b] outlines a scheme that uses the DSACK TCP option
        [RFC2883] to detect spurious retransmits.

        [LM02] outlines the Eifel algorithm that uses the TCP timestamp
        option [RFC1323] to detect unneeded retransmissions.  (An
        additional variant of the Eifel algorithm uses reserved bits
        from the TCP header rather than timestamps [LK00].)

        [SK02] outlines the F-RTO algorithm that uses a slight
        modification to TCP's sending pattern after a retransmission
        timeout (RTO) and the resulting ACKs to detect spurious RTOs.

    (2) Mechanisms for undoing needless changes to congestion control

        Section 4 of this document specifies the appropriate method for
        reverting to a previous set of congestion control parameters
        after reliably detecting a needless retransmit (and in the
        presence of no other congestion signals).  The scheme specified
        in this document draws on the spirit outlined in [RFC2883].

        [LG02] outlines the response to spurious retransmits (both
        spurious fast retransmits and spurious timeouts) after detection
        by the Eifel detection algorithm [LM02].  The mechanism for
        undoing needless changes to the congestion control state of the
        connection is similar to the mechanism we outline in section 4.

    (3) Mechanisms for making TCP more tolerant to reordering events
        such that future spurious retransmits are avoided.

Expires: July 2003                                              [Page 3]

draft-blanton-tcp-reordering-00.txt                        February 2003

        [LG02] outlines one particular method for adjusting dupthresh in
        an attempt to prevent future needless fast retransmissions.  (In
        addition, [LG02] provides a method for adjusting the RTO after a
        spurious RTO.)

        [ZKFP02] outlines a scheme whereby the TCP sender's SACK
        scoreboard data structure is annotated with information about
        packet reordering in an attempt to adjust the dupthresh to
        prevent packet reordering from causing needless retransmits.

        Finally, section 5 of this document outlines several schemes to
        avoid needlessly evoking the fast retransmit algorithm.  The
        mechanisms in section 5 are based on [BA02a].  Each of the above
        proposals has its pros and cons.  An in-depth analysis of each
        proposal is beyond the scope of this document.

4   Reverting Congestion Control State

    [RFC2883,LK00,BA02a] all mention the possibility of reverting
    congestion control state when a sender determines that the
    congestion window was reduced unnecessarily due to a spurious
    retransmission.  This document specifies that a sender that reliably
    detects a spurious retransmission MAY ``undo'' the needless
    congestion control state changes.  If the sender wishes to undo
    needless changes it MUST use the following algorithm:

    (1) When retransmitting a segment and before reducing cwnd or
        ssthresh, save the value of cwnd as cwnd_prev and the value of
        ssthresh as ssthresh_prev.

    (2) Upon the detection of a spurious retransmit, set ssthresh to

        This causes a 1 RTT slow start back to the cwnd in use before
        the sender needlessly changed the congestion control state.
        This rule causes a smooth increase of cwnd, whereas simply
        setting cwnd to cwnd_prev upon detection of a spurious
        retransmit would cause the transmission of a potentially large

    (3) Optional.  When cwnd reaches ssthresh set ssthresh to

        This rule allows a TCP that is using slow start when a spurious
        retransmission is detected to resume that slow start after
        detection.  Without this rule the cwnd would be reverted to its
        previous value, however further cwnd growth would be limited to
        the linear growth of congestion avoidance.

    If a sender uses the above algorithm, one of the algorithms
    specified in the next section MUST be used in an attempt to prevent
    further needless retransmissions.

Expires: July 2003                                              [Page 4]

draft-blanton-tcp-reordering-00.txt                        February 2003

5   Preventing Spurious Fast Retransmits

    Undoing congestion control changes caused by reordering events
    increases the overall performance of a TCP connection [BA02a].
    However, [BA02a] shows that when the steps in section 4 are taken
    alone the number of unnecessary retransmits (and, therefore, wasted
    network resources) still remains significantly high.  Therefore,
    further performance gains and network resource savings can be
    realized if we can prevent subsequent spurious fast retransmits.
    Simulations in [BA02a] show that a strategy of reversing erroneous
    congestion control decisions, coupled with a fast retransmit
    mitigation scheme, achieves good performance (within 1-2% of a
    transfer that experiences no reordering) while reducing the number
    of unnecessary retransmits by roughly a factor of 6.

    This document purposes several options that deal with postponing the
    fast retransmit algorithm to allow the reordered segments to be
    acknowledged by the receiver.  This is achieved by increasing the
    duplicate acknowledgment threshold, or directly delaying fast
    retransmit by an increment of time when a spurious retransmission
    has occurred previously.

    Regardless of which approach is taken to avoid spurious retransmits,
    caution should be taken in their implementation.  For example, more
    aggressive manipulations of dupthresh can result in faster
    convergence in the face of a connection facing persistent
    reordering, but may increase the chance of relying on the RTO to
    recover from real loss.  The RTO is often lengthy and cuts cwnd to
    one segment and invokes slow start.

5.1 Increase dupthresh By K

    A TCP sender that implements this strategy MUST increase dupthresh
    by some small constant, K, each time a spurious fast retransmit is
    detected.  In [BA02a] K is set to increment dupthresh by one after a
    spurious retransmission is detected.

    This method requires minimal state to implement, but a conservative
    increment of K may be slow to converge in connections where
    persistent large reordering events are present.  In connections
    where the reordering event lengths are varied convergence becomes
    problematical at best.

5.2 Increase dupthresh Based On Reordering Length

    A TCP sender that implements this strategy MUST increase dupthresh
    based on the length of the most recent reordering event that causes
    a spurious fast retransmit.  With this method a TCP sender
    determines the number of duplicate ACKs, C, that would have
    disambiguated the reordering event from the perceived loss.  C is
    then averaged with the current value of dupthresh, per

                    dupthresh = (C + dupthresh) / 2                (1)

Expires: July 2003                                              [Page 5]

draft-blanton-tcp-reordering-00.txt                        February 2003

    If the new value for dupthresh is less than or equal to its
    predecessor, dupthresh SHOULD be incremented by one.

    This method allows for a varied growth of dupthresh, accommodating
    the varied reordering event lengths mentioned in the previous
    option.  Unfortunately, reordering events significantly longer than
    the connection's average reordering events may result in skewing
    dupthresh to an overly optimistic value, preventing fast retransmit
    before the RTO timer expires.

5.3 Delay of Fast Retransmit

    As proposed in [Pax97], the fast retransmit can be delayed by some
    small amount of time after dupthresh duplicate ACKs have been
    received in an effort to distinguish between loss and reordering.  A
    sender that implements this strategy MUST track of the duration in
    time, T, of the reordering event from the reception of the first
    duplicate ACK to the first cumulative or partial ACK.  This
    represents the time necessary to disambiguate the longest reordering
    event in the current connection from its perceived loss. The sender
    MUST then, on subsequent perceived loss events, wait T seconds after
    the third duplicate acknowledgment for subsequent reordering/loss
    events before invoking the fast retransmit algorithm.  Should a
    cumulative ACK be received before this timer expires, the sender
    MUST NOT invoke fast retransmit.

    Similar in approach to the scheme sketched in section 5.2, this
    method considers the length of the reordering event.  In using the
    passage of time, as opposed to counting duplicate ACKs, the strategy
    is more robust where ACK loss is present.  Unfortunately this
    potential advantage comes at a cost of requiring more overhead than
    in the previously outlined methods in the form of an additional
    timer for each TCP connection.

5.4 Average Duplicate ACK Tracking

    In an attempt to use a connection's history while still being
    adaptive to reordering events which are uncharacteristically
    divergent, an Exponentially Weighted Moving Average (EWMA) is tried
    in [BA02a].  The EWMA gives the values needed to mitigate recent
    spurious fast retransmits a higher weight over the values used in
    previous fast retransmit mitigation attempts in the connections
    history.  Unfortunately, initial results for this mechanism yielded
    little or no advantages over TCP variants which did not use any
    mechanisms to mitigate spurious fast retransmits.  Therefore, we do
    not recommend using an EWMA scheme in this document, but rather
    offer it as a future research area.

6   Preventing Spurious Timeouts

    In section 5, we outline several methods to increase dupthresh, or
    insert delay before fast retransmit, in hopes of maintaining cwnd to
    mitigate TCP performance issues in the face of reordering.
    Regardless of the method used, since reordering events may vary in

Expires: July 2003                                              [Page 6]

draft-blanton-tcp-reordering-00.txt                        February 2003

    length and ACK loss will effect the number of duplicate ACKs
    returned to the sender there exists a possibility that dupthesh will
    be set to an overly optimistic value.  In this case the RTO will
    expire before enough duplicate ACKs are received for fast
    retransmit.  In addition to the often lengthy timeout imposed by the
    RTO [RFC2988] the TCP sender will reduce cwnd to one segment and
    restart transmission with slow start.  This document sketches
    several additional methods for coping with RTOs caused by an overly
    optimistic dupthresh in the next subsections.  In addition, the
    outline of future work below (section 7) offers some thoughts in
    this area.

6.1 Reducing dupthresh

    In addition to the performance issues involved with the expiration
    of the RTO, the sender should consider an RTO as an indication that
    the current dupthresh is no longer a valid estimate of the
    reordering conditions in the network.  The TCP sender MUST reset
    dupthresh to the default value of from [RFC2581] (currently 3).
    This conservative approach guards against subsequent RTOs stemming
    from an optimistic dupthresh value, but may allow spurious
    retransmissions to resume until the sender's dupthresh estimate

6.2 Bounding dupthresh

    This document specifies that the dupthresh MUST never be larger than
    cwnd-1 segments.  Furthermore, to be more conservative we RECOMMEND
    that dupthresh never be more than 90% of cwnd.  This means that
    whenever cwnd is reduced in the course of a TCP transfer the stack
    must also ensure that dupthresh is likewise reduced, if necessary.

6.3 Extending Limited Transmit

    A final strategy that MAY be used by a TCP sender in an attempt to
    prevent RTOs is to extend the limited transmit algorithm [RFC3042].
    Limited transmit calls for a TCP sender to transmit one previously
    unsent data segment upon reception of each of the first two
    duplicate ACKs.  This document allows that a a TCP sender MAY
    transmit a previously unsent data segment on every second duplicate
    ACK received after the first two and before dupthresh is met.  So,
    when used in conjunction with [RFC3042], a TCP sender with a
    dupthresh of 7 could transmit new data segments on duplicate ACKs 1,
    2, 4, and 6.

    This mechanism allows the TCP sender to sustain the ACK clock and
    possibly generate new duplicate ACKs that will help trigger fast
    retransmit and prevent an RTO.  The mechanism is conservative
    because in the case when loss is the cause of the duplicate ACKs
    (rather than reordering) the rate the TCP sender is transmitting new
    segments into the network is gradually being reduced by sending only
    on every second duplicate ACK.

    This mechanism is similar to the rate-halving proposals [].

Expires: July 2003                                              [Page 7]

draft-blanton-tcp-reordering-00.txt                        February 2003

7   Future Work

    All the schemes for varying dupthresh in this document involve
    increasing the number of duplicate ACKs required to trigger fast
    retransmit.  While we provide one scheme to reduce dupthresh
    (collapsing back to the default value after an RTO) [ZKFP02] shows
    that schemes that offer both dupthresh increase and decrease offer
    more performance benefit.  One area for future work is to extend the
    strategies outlined in section 5 to allow for decreasing dupthresh.

8   Security Considerations

    Reversion of congestion control state has no obvious security
    considerations given an accurate signal that indicates a needless
    retransmit.  Any security considerations pertaining to the method of
    determining that a fast retransmit was spurious are directly
    applicable to this document.

    The adjustment of dupthresh may be vulnerable to any third party who
    wishes to illegitimately gain network resources and/or cause a
    denial of service between the sender and receiver.  The
    vulnerability exists when a third party sends fictitious duplicate
    acknowledgments to the sender with a sequence number within the
    sender's current cwnd.  As a result, the sender may needlessly
    retransmit and also grow dupthresh to an overly optimistic value,
    resulting in future RTOs.  Such RTOs cause the sender to drop cwnd
    to 1 segment, relinquishing network resources at the cost of the
    connection's performance.


    The authors would like to thank Sally Floyd, Reiner Ludwig, Vern
    Paxson and Randall Stewart for spurring this work through their
    previous work for providing input during the formative stages of
    this draft.


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

    [BA02b] E. Blanton, M. Allman.  Using TCP DSACKs and SCTP Duplicate
        TSNs to Detect Spurious Retransmissions. Internet-Draft
        draft-blanton-dsack-use-02.txt, October 2002.  Work in progress.

    [BPS99] J. Bennett, C. Partridge, N. Shectman.  Packet Reordering
        is Not Pathological Network Behavior.  IEEE/ACM Transactions
        on Networking, December 1999.

    [Jac88] Van Jacobson.  Congestion Avoidance and Control.  ACM
        SIGCOMM 1988.

Expires: July 2003                                              [Page 8]

draft-blanton-tcp-reordering-00.txt                        February 2003

    [LG02] R. Ludwig, A. Gurtov.  The Eifel Response Algorithm for TCP.
        Internet-Draft draft-ietf-tsvwg-tcp-eifel-response-01.txt,
        October 2002.  Work in progress.

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

    [LM02] R. Ludwig, M. Meyer.  The Eifel Detection Algorithm for TCP.
        Internet-Draft draft-ietf-tsvwg-tcp-eifel-alg-06.txt, October
        2002.  Work in progress.

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

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

    [RFC2581] M. Allman, V. Paxson, W. Stevens, TCP Congestion Control,
        RFC 2581, April 1999.

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

    [RFC2988] Vern Paxson, Mark Allman.  Computing TCP's Retransmission
        Timer, RFC 2988, November 2000.

    [RFC3042] Mark Allman, Hari Balkrishnan, Sally Floyd.  Enhancing
        TCP's Loss Recovery Using Limited Transmit.  RFC 3042,
        January 2001

    [SL02] Yogesh Swami, Khiem Le.  DCLOR: De-correlated Loss Recovery
        using SACK Option for Spurious Timeouts.  Internet-Draft
        draft-swami-tsvwg-tcp-dclor-00.txt, November 2002.  Work in

    [SK02] P. Sarolahti, M. Kojo.  F-RTO: A TCP RTO Recovery Algorithm
        for Avoiding Unnecessary Retransmissions.  Internet-Draft
        draft-sarolahti-tsvwg-tcp-frto-02.txt, November 2002.  Work in

    [ZKFP02] M. Zhang, B. Karp, S. Floyd, L. Peterson.  RR-TCP: A
        Reordering-Robust TCP with DSACK.  ICSI Technical Report
        TR-02-006, July 2002.

Authors' Addresses:

    Ethan Blanton
    Purdue University Computer Sciences
    1398 Computer Science Building
    West Lafayette, IN  47907

Expires: July 2003                                              [Page 9]

draft-blanton-tcp-reordering-00.txt                        February 2003

    Robert Dimond
    Verizon FNS/NASA Glenn Research Center
    Lewis Field
    21000 Brookpark Rd.  MS 142-1
    Cleveland, OH  44135
    Phone: 216-433-8468

    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

Expires: July 2003                                             [Page 10]