diff options
Diffstat (limited to 'doc/rfc/rfc5682.txt')
| -rw-r--r-- | doc/rfc/rfc5682.txt | 1067 |
1 files changed, 1067 insertions, 0 deletions
diff --git a/doc/rfc/rfc5682.txt b/doc/rfc/rfc5682.txt new file mode 100644 index 0000000..7e3efc8 --- /dev/null +++ b/doc/rfc/rfc5682.txt @@ -0,0 +1,1067 @@ + + + + + + +Network Working Group P. Sarolahti +Request for Comments: 5682 Nokia Research Center +Updates: 4138 M. Kojo +Category: Standards Track University of Helsinki + K. Yamamoto + M. Hata + NTT Docomo + September 2009 + + + Forward RTO-Recovery (F-RTO): An Algorithm for Detecting + Spurious Retransmission Timeouts with TCP + +Abstract + + The purpose of this document is to move the F-RTO (Forward + RTO-Recovery) functionality for TCP in RFC 4138 from + Experimental to Standards Track status. The F-RTO support for Stream + Control Transmission Protocol (SCTP) in RFC 4138 remains with + Experimental status. See Appendix B for the differences between this + document and RFC 4138. + + Spurious retransmission timeouts cause suboptimal TCP performance + because they often result in unnecessary retransmission of the last + window of data. This document describes the F-RTO detection + algorithm for detecting spurious TCP retransmission timeouts. F-RTO + is a TCP sender-only algorithm that does not require any TCP options + to operate. After retransmitting the first unacknowledged segment + triggered by a timeout, the F-RTO algorithm of the TCP sender + monitors the incoming acknowledgments to determine whether the + timeout was spurious. It then decides whether to send new segments + or retransmit unacknowledged segments. The algorithm effectively + helps to avoid additional unnecessary retransmissions and thereby + improves TCP performance in the case of a spurious timeout. + +Status of This Memo + + This document specifies an Internet standards track protocol for the + Internet community, and requests discussion and suggestions for + improvements. Please refer to the current edition of the "Internet + Official Protocol Standards" (STD 1) for the standardization state + and status of this protocol. Distribution of this memo is unlimited. + + + + + + + + + +Sarolahti, et al. Standards Track [Page 1] + +RFC 5682 F-RTO September 2009 + + +Copyright and License Notice + + Copyright (c) 2009 IETF Trust and the persons identified as the + document authors. All rights reserved. + + This document is subject to BCP 78 and the IETF Trust's Legal + Provisions Relating to IETF Documents + (http://trustee.ietf.org/license-info) in effect on the date of + publication of this document. Please review these documents + carefully, as they describe your rights and restrictions with respect + to this document. Code Components extracted from this document must + include Simplified BSD License text as described in Section 4.e of + the Trust Legal Provisions and are provided without warranty as + described in the BSD License. + +Table of Contents + + 1. Introduction ....................................................3 + 1.1. Conventions and Terminology ................................5 + 2. Basic F-RTO Algorithm ...........................................5 + 2.1. The Algorithm ..............................................5 + 2.2. Discussion .................................................7 + 3. SACK-Enhanced Version of the F-RTO Algorithm ....................9 + 3.1. The Algorithm ..............................................9 + 3.2. Discussion ................................................11 + 4. Taking Actions after Detecting Spurious RTO ....................11 + 5. Evaluation of RFC 4138 .........................................12 + 6. Security Considerations ........................................13 + 7. Acknowledgments ................................................14 + Appendix A. Discussion of Window-Limited Cases ....................15 + Appendix B. Changes since RFC 4138 ................................16 + References ........................................................16 + Normative References ...........................................16 + Informative References .........................................17 + + + + + + + + + + + + + + + + + +Sarolahti, et al. Standards Track [Page 2] + +RFC 5682 F-RTO September 2009 + + +1. Introduction + + The Transmission Control Protocol (TCP) [Pos81] has two methods for + triggering retransmissions. First, the TCP sender relies on incoming + duplicate acknowledgments (ACKs), which indicate that the receiver is + missing some of the data. After a required number of successive + duplicate ACKs have arrived at the sender, it retransmits the first + unacknowledged segment [APB09] and continues with a loss recovery + algorithm such as NewReno [FHG04] or SACK-based (Selective + Acknowledgment) loss recovery [BAFW03]. Second, the TCP sender + maintains a retransmission timer that triggers retransmission of + segments, if they have not been acknowledged before the + retransmission timeout (RTO) occurs. When the retransmission timeout + occurs, the TCP sender enters the RTO recovery where the congestion + window is initialized to one segment and unacknowledged segments are + retransmitted using the slow-start algorithm. The retransmission + timer is adjusted dynamically, based on the measured round-trip times + [PA00]. + + It has been pointed out that the retransmission timer can expire + spuriously and cause unnecessary retransmissions when no segments + have been lost [LK00, GL02, LM03]. After a spurious retransmission + timeout, the late acknowledgments of the original segments arrive at + the sender, usually triggering unnecessary retransmissions of a whole + window of segments during the RTO recovery. Furthermore, after a + spurious retransmission timeout, a conventional TCP sender increases + the congestion window on each late acknowledgment in slow start. + This injects a large number of data segments into the network within + one round-trip time, thus violating the packet conservation principle + [Jac88]. + + There are a number of potential reasons for spurious retransmission + timeouts. First, some mobile networking technologies involve sudden + delay spikes on transmission because of actions taken during a hand- + off. Second, a hand-off may take place from a low latency path to a + high latency path, suddenly increasing the round-trip time beyond the + current RTO value. Third, on a low-bandwidth link the arrival of + competing traffic (possibly with higher priority), or some other + change in available bandwidth, can cause a sudden increase of the + round-trip time. This may trigger a spurious retransmission timeout. + A persistently reliable link layer can also cause a sudden delay when + a data frame and several retransmissions of it are lost for some + reason. This document does not distinguish between the different + causes of such a delay spike. Rather, it discusses the spurious + retransmission timeouts caused by a delay spike in general. + + + + + + +Sarolahti, et al. Standards Track [Page 3] + +RFC 5682 F-RTO September 2009 + + + This document describes the F-RTO detection algorithm for TCP. It is + based on the detection mechanism of the "Forward RTO-Recovery" + (F-RTO) algorithm [SKR03] that is used for detecting spurious + retransmission timeouts and thus avoids unnecessary retransmissions + following the retransmission timeout. When the timeout is not + spurious, the F-RTO algorithm reverts back to the conventional RTO + recovery algorithm, and therefore has similar behavior and + performance. In contrast to alternative algorithms proposed for + detecting unnecessary retransmissions (Eifel [LK00, LM03] and DSACK- + based (Duplicate SACK) algorithms [BA04]), F-RTO does not require any + TCP options for its operation, and it can be implemented by modifying + only the TCP sender. The Eifel algorithm uses TCP timestamps [BBJ92] + for detecting a spurious timeout upon arrival of the first + acknowledgment after the retransmission. The DSACK-based algorithms + require that the TCP Selective Acknowledgment Option [MMFR96], with + the DSACK extension [FMMP00], is in use. With DSACK, the TCP + receiver can report if it has received a duplicate segment, enabling + the sender to detect afterwards whether it has retransmitted segments + unnecessarily. The F-RTO algorithm only attempts to detect and avoid + unnecessary retransmissions after an RTO. Eifel and DSACK can also + be used for detecting unnecessary retransmissions caused by other + events, such as packet reordering. + + When the retransmission timer expires, the F-RTO sender retransmits + the first unacknowledged segment as usual [APB09]. Deviating from + the normal operation after a timeout, it then tries to transmit new, + previously unsent data for the first acknowledgment that arrives + after the timeout, given that the acknowledgment advances the window. + If the second acknowledgment that arrives after the timeout advances + the window (i.e., acknowledges data that was not retransmitted), the + F-RTO sender declares the timeout spurious and exits the RTO + recovery. However, if either of these two acknowledgments is a + duplicate ACK, there will not be sufficient evidence of a spurious + timeout. Therefore, the F-RTO sender retransmits the unacknowledged + segments in slow start similar to the traditional algorithm. With a + SACK-enhanced version of the F-RTO algorithm, spurious timeouts may + be detected even if duplicate ACKs arrive after an RTO + retransmission. + + This document specifies the F-RTO algorithm for TCP only, replacing + the F-RTO functionality with TCP in RFC 4138 [SK05] and moving it + from Experimental to Standards Track status. The algorithm can also + be applied to the Stream Control Transmission Protocol (SCTP) [Ste07] + that has acknowledgment and packet retransmission concepts similar to + TCP. The considerations on applying F-RTO to SCTP are discussed in + RFC 4138, but the F-RTO support for SCTP remains with Experimental + status. + + + + +Sarolahti, et al. Standards Track [Page 4] + +RFC 5682 F-RTO September 2009 + + + This document is organized as follows. Section 2 describes the basic + F-RTO algorithm, and the SACK-enhanced F-RTO algorithm is given in + Section 3. Section 4 discusses the possible actions to be taken + after detecting a spurious RTO. Section 5 summarizes the experience + with F-RTO implementations and the experimental results, and Section + 6 discusses the security considerations. + +1.1. Conventions and 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 BCP 14, RFC 2119 + [RFC2119] and indicate requirement levels for protocols. + +2. Basic F-RTO Algorithm + + A timeout is considered spurious if it would have been avoided had + the sender waited longer for an acknowledgment to arrive [LM03]. + F-RTO affects the TCP sender behavior only after a retransmission + timeout. Otherwise, the TCP behavior remains the same. When the + retransmission timer expires, the F-RTO algorithm monitors incoming + acknowledgments, and if the TCP sender gets an acknowledgment for a + segment that was not retransmitted due to the timeout, the F-RTO + algorithm declares a timeout spurious. The actions taken in response + to a spurious timeout are not specified in this document, but we + discuss some alternatives in Section 4. This section introduces the + algorithm and then discusses the different steps of the algorithm in + more detail. + + Following the practice used with the Eifel Detection algorithm + [LM03], we use the "SpuriousRecovery" variable to indicate whether + the retransmission is declared spurious by the sender. This variable + can be used as an input for a corresponding response algorithm. With + F-RTO, the value of SpuriousRecovery can be either SPUR_TO + (indicating a spurious retransmission timeout) or FALSE (indicating + that the timeout is not declared spurious and the TCP sender should + follow the conventional RTO recovery algorithm). In addition, we use + the "recover" variable specified in the NewReno algorithm [FHG04]. + +2.1. The Algorithm + + A TCP sender implementing the basic F-RTO algorithm MUST take the + following steps after the retransmission timer expires. If the + retransmission timer expires again during the execution of the F-RTO + algorithm, the TCP sender MUST re-start the algorithm processing from + step 1. If the sender implements some loss recovery algorithm other + than Reno or NewReno [FHG04], the F-RTO algorithm SHOULD NOT be + entered when earlier fast recovery is underway. + + + +Sarolahti, et al. Standards Track [Page 5] + +RFC 5682 F-RTO September 2009 + + + The F-RTO algorithm takes different actions based on whether an + incoming acknowledgment advances the cumulative acknowledgment point + for a received in-order segment, or whether it is a duplicate + acknowledgment to indicate an out-of-order segment. Duplicate + acknowledgment is defined in [APB09]. The F-RTO algorithm does not + specify actions for receiving a segment that neither acknowledges new + data nor is a duplicate acknowledgment. The TCP sender SHOULD ignore + such segments and wait for a segment that either acknowledges new + data or is a duplicate acknowledgment. + + 1) When the retransmission timer expires, retransmit the first + unacknowledged segment and set SpuriousRecovery to FALSE. If the + TCP sender is already in RTO recovery AND "recover" is larger than + or equal to SND.UNA (the oldest unacknowledged sequence number + [Pos81]), do not enter step 2 of this algorithm. Instead, store + the highest sequence number transmitted so far in variable + "recover" and continue with slow-start retransmissions following + the conventional RTO recovery algorithm. + + 2) When the first acknowledgment after the RTO retransmission arrives + at the TCP sender, store the highest sequence number transmitted + so far in variable "recover". The TCP sender chooses one of the + following actions, depending on whether the ACK advances the + window or whether it is a duplicate ACK. + + a) If the acknowledgment is a duplicate ACK, OR the Acknowledgment + field covers "recover" but not more than "recover", OR the + acknowledgment does not acknowledge all of the data that was + retransmitted in step 1, revert to the conventional RTO + recovery and continue by retransmitting unacknowledged data in + slow start. Do not enter step 3 of this algorithm. The + SpuriousRecovery variable remains as FALSE. + + b) Else, if the acknowledgment advances the window AND the + Acknowledgment field does not cover "recover", transmit up to + two new (previously unsent) segments and enter step 3 of this + algorithm. If the TCP sender does not have enough unsent data, + it can send only one segment. In addition, the TCP sender MAY + override the Nagle algorithm [Nag84] and immediately send a + segment if needed. Note that sending two segments in this step + is allowed by TCP congestion control requirements [APB09]: an + F-RTO TCP sender simply chooses different segments to transmit. + + If the TCP sender does not have any new data to send, or the + advertised window prohibits new transmissions, the recommended + action is to skip step 3 of this algorithm and continue with + slow-start retransmissions, following the conventional RTO + + + + +Sarolahti, et al. Standards Track [Page 6] + +RFC 5682 F-RTO September 2009 + + + recovery algorithm. However, alternative ways of handling the + window-limited cases that could result in better performance + are discussed in Appendix A. + + 3) When the second acknowledgment after the RTO retransmission + arrives at the TCP sender, the TCP sender either declares the + timeout spurious, or starts retransmitting the unacknowledged + segments. + + + a) If the acknowledgment is a duplicate ACK, set the congestion + window to no more than 3 * MSS (where MSS indicates Maximum + Segment Size), and continue with the slow-start algorithm + retransmitting unacknowledged segments. The congestion window + can be set to 3 * MSS, because two round-trip times have + elapsed since the RTO, and a conventional TCP sender would have + increased cwnd to 3 during the same time. Leave + SpuriousRecovery set to FALSE. + + b) If the acknowledgment advances the window (i.e., if it + acknowledges data that was not retransmitted after the + timeout), declare the timeout spurious, set SpuriousRecovery to + SPUR_TO, and set the value of the "recover" variable to SND.UNA + (the oldest unacknowledged sequence number [Pos81]). + +2.2. Discussion + + The F-RTO sender takes cautious actions when it receives duplicate + acknowledgments after a retransmission timeout. Because duplicate + ACKs may indicate that segments have been lost, reliably detecting a + spurious timeout is difficult due to the lack of additional + information. Therefore, it is prudent to follow the conventional TCP + recovery in those cases. + + The condition in step 1 prevents the execution of the F-RTO algorithm + in case a previous RTO recovery is underway when the retransmission + timer expires, except in case the retransmission timer expires + multiple times for the same segment. If the retransmission timer + expires during an earlier RTO-based loss recovery, acknowledgments + for retransmitted segments may falsely lead the TCP sender to declare + the timeout spurious. + + If the first acknowledgment after the RTO retransmission covers the + "recover" point at algorithm step (2a), there is not enough evidence + that a non-retransmitted segment has arrived at the receiver after + the timeout. This is a common case when a fast retransmission is + lost and has been retransmitted again after an RTO, while the rest of + + + + +Sarolahti, et al. Standards Track [Page 7] + +RFC 5682 F-RTO September 2009 + + + the unacknowledged segments were successfully delivered to the TCP + receiver before the retransmission timeout. Therefore, the timeout + cannot be declared spurious in this case. + + If the first acknowledgment after the RTO retransmission does not + acknowledge all of the data that was retransmitted in step 1, the TCP + sender reverts to the conventional RTO recovery. Otherwise, a + malicious receiver acknowledging partial segments could cause the + sender to declare the timeout spurious in a case where data was lost. + + The TCP sender is allowed to send two new segments in algorithm + branch (2b) because the conventional TCP sender would transmit two + segments when the first new ACK arrives after the RTO retransmission. + If sending new data is not possible in algorithm branch (2b), or if + the receiver window limits the transmission, the TCP sender has to + send something in order to prevent the TCP transfer from stalling. + If no segments were sent, the pipe between sender and receiver might + run out of segments, and no further acknowledgments would arrive. + Therefore, in the window-limited case, the recommendation is to + revert to the conventional RTO recovery with slow-start + retransmissions. Appendix A discusses some alternative solutions for + window-limited situations. + + If the retransmission timeout is declared spurious, the TCP sender + sets the value of the "recover" variable to SND.UNA in order to allow + fast retransmit [FHG04]. The "recover" variable was proposed for + avoiding unnecessary, multiple fast retransmits when the + retransmission timer expires during fast recovery with NewReno TCP. + Because the F-RTO sender retransmits only the segment that triggered + the timeout, the problem of unnecessary multiple fast retransmits + [FHG04] cannot occur. Therefore, if three duplicate ACKs arrive at + the sender after the timeout, they probably indicate a packet loss, + and thus fast retransmit should be used to allow efficient recovery. + If there are not enough duplicate ACKs arriving at the sender after a + packet loss, the retransmission timer expires again and the sender + enters step 1 of this algorithm. + + When the timeout is declared spurious, the TCP sender cannot detect + whether the unnecessary RTO retransmission was lost. In principle, + the loss of the RTO retransmission should be taken as a congestion + signal. Thus, there is a small possibility that the F-RTO sender + will violate the congestion control rules, if it chooses to fully + revert congestion control parameters after detecting a spurious + timeout. The Eifel Detection algorithm has a similar property, while + the DSACK option can be used to detect whether the retransmitted + segment was successfully delivered to the receiver. + + + + + +Sarolahti, et al. Standards Track [Page 8] + +RFC 5682 F-RTO September 2009 + + + The F-RTO algorithm has a side effect on the TCP round-trip time + measurement. Because the TCP sender can avoid most of the + unnecessary retransmissions after detecting a spurious timeout, the + sender is able to take round-trip time samples on the delayed + segments. If the regular RTO recovery was used without TCP + timestamps, this would not be possible due to the retransmission + ambiguity. As a result, the RTO is likely to have more accurate and + larger values with F-RTO than with the regular TCP after a spurious + timeout that was triggered due to delayed segments. We believe this + is an advantage in networks that are prone to delay spikes. + + There are some situations where the F-RTO algorithm may not avoid + unnecessary retransmissions after a spurious timeout. If packet + reordering or packet duplication occurs on the segment that triggered + the spurious timeout, the F-RTO algorithm may not detect the spurious + timeout due to incoming duplicate ACKs. Additionally, if a spurious + timeout occurs during fast recovery, the F-RTO algorithm often cannot + detect the spurious timeout because the segments that were + transmitted before the fast recovery trigger duplicate ACKs. + However, we consider these cases rare, and note that in cases where + F-RTO fails to detect the spurious timeout, it retransmits the + unacknowledged segments in slow start, and thus performs the same as + the regular RTO recovery. + +3. SACK-Enhanced Version of the F-RTO Algorithm + + This section describes an alternative version of the F-RTO algorithm + that uses the TCP Selective Acknowledgment Option [MMFR96]. By using + the SACK option, the TCP sender detects spurious timeouts in most of + the cases when packet reordering or packet duplication is present. + If the SACK information acknowledges new data that was not + transmitted after the RTO retransmission, the sender may declare the + timeout spurious, even when duplicate ACKs follow the RTO. + +3.1. The Algorithm + + Given that the TCP Selective Acknowledgment Option [MMFR96] is + enabled for a TCP connection, a TCP sender MAY apply the SACK- + enhanced F-RTO algorithm. If the sender applies the SACK-enhanced + F-RTO algorithm, it MUST follow the steps below. This algorithm + SHOULD NOT be applied if the TCP sender is already in loss recovery + when a retransmission timeout occurs. + + The steps of the SACK-enhanced version of the F-RTO algorithm are as + follows. If the retransmission timer expires again during the + execution of the SACK-enhanced F-RTO algorithm, the TCP sender MUST + re-start the algorithm processing from step 1. + + + + +Sarolahti, et al. Standards Track [Page 9] + +RFC 5682 F-RTO September 2009 + + + 1) When the retransmission timer expires, retransmit the first + unacknowledged segment and set SpuriousRecovery to FALSE. + Following the recommendation in the SACK specification [MMFR96], + reset the SACK scoreboard. If "RecoveryPoint" is larger than or + equal to SND.UNA, do not enter step 2 of this algorithm. Instead, + set variable "RecoveryPoint" to indicate the highest sequence + number transmitted so far and continue with slow-start + retransmissions following the conventional RTO recovery algorithm. + + 2) Wait until the acknowledgment of the data retransmitted due to the + timeout arrives at the sender. If duplicate ACKs arrive before + the cumulative acknowledgment for retransmitted data, adjust the + scoreboard according to the incoming SACK information. Stay in + step 2 and wait for the next new acknowledgment. If the + retransmission timeout expires again, go to step 1 of the + algorithm. When a new acknowledgment arrives, set variable + "RecoveryPoint" to indicate the highest sequence number + transmitted so far. + + a) If the Cumulative Acknowledgment field covers "RecoveryPoint" + but not more than "RecoveryPoint", revert to the conventional + RTO recovery and set the congestion window to no more than 2 * + MSS, like a regular TCP would do. Do not enter step 3 of this + algorithm. + + b) Else, if the Cumulative Acknowledgment field does not cover + "RecoveryPoint" but is larger than SND.UNA, transmit up to two + new (previously unsent) segments and proceed to step 3. If the + TCP sender is not able to transmit any previously unsent data + -- either due to receiver window limitation or because it does + not have any new data to send -- the recommended action is to + refrain from entering step 3 of this algorithm. Rather, + continue with slow-start retransmissions following the + conventional RTO recovery algorithm. + + It is also possible to apply some of the alternatives for + handling window-limited cases discussed in Appendix A. + + 3) The next acknowledgment arrives at the sender. Either a duplicate + ACK or a new cumulative ACK (advancing the window) applies in this + step. Other types of ACKs are ignored without any action. + + a) If the Cumulative Acknowledgment field or the SACK information + covers more than "RecoveryPoint", set the congestion window to + no more than 3 * MSS and proceed with the conventional RTO + recovery, retransmitting unacknowledged segments. Take this + branch also when the acknowledgment is a duplicate ACK and it + does not acknowledge any new, previously unacknowledged data + + + +Sarolahti, et al. Standards Track [Page 10] + +RFC 5682 F-RTO September 2009 + + + below "RecoveryPoint" in the SACK information. Leave + SpuriousRecovery set to FALSE. + + b) If the Cumulative Acknowledgment field or a SACK information in + the ACK does not cover more than "RecoveryPoint" AND it + acknowledges data that was not acknowledged earlier (either + with cumulative acknowledgment or using SACK information), + declare the timeout spurious and set SpuriousRecovery to + SPUR_TO. The retransmission timeout can be declared spurious, + because the segment acknowledged with this ACK was transmitted + before the timeout. + + If there are unacknowledged holes between the received SACK + information, those segments are retransmitted similarly to the + conventional SACK recovery algorithm [BAFW03]. If the algorithm + exits with SpuriousRecovery set to SPUR_TO, "RecoveryPoint" is set to + SND.UNA, thus allowing fast recovery on incoming duplicate + acknowledgments. + +3.2. Discussion + + The SACK-enhanced algorithm works on the same principle as the basic + algorithm, but by utilizing the additional information from the SACK + option. When a genuine retransmission timeout occurs during a steady + state of a connection, it can be assumed that there are no segments + left in the pipe. Otherwise, the acknowledgments triggered by these + segments would have triggered the SACK loss recovery or transmission + of new segments. Therefore, if the F-RTO sender receives + acknowledgments for segments transmitted before the retransmission + timeout in response to the two new segments sent at the algorithm + step 2, the normal operation of TCP has been just delayed, and the + retransmission timeout is considered spurious. Note that this + reasoning works only when the TCP sender is not in loss recovery at + the time the retransmission timeout occurs. The condition in step 1 + checking that "RecoveryPoint" is larger than or equal to SND.UNA + prevents the execution of the F-RTO algorithm in case a previous loss + recovery, either RTO recovery or SACK loss recovery, is underway when + the retransmission timer expires. It, however, allows the execution + of the F-RTO algorithm, if the retransmission timer expires multiple + times for the same segment. + +4. Taking Actions after Detecting Spurious RTO + + Upon a retransmission timeout, a conventional TCP sender assumes that + outstanding segments are lost and starts retransmitting the + unacknowledged segments. When the retransmission timeout is detected + to be spurious, the TCP sender should not continue retransmitting + based on the timeout. For example, if the sender was in congestion + + + +Sarolahti, et al. Standards Track [Page 11] + +RFC 5682 F-RTO September 2009 + + + avoidance phase transmitting new, previously unsent segments, it + should continue transmitting previously unsent segments in congestion + avoidance. + + There are currently two alternatives specified for a spurious timeout + response algorithm, the Eifel Response Algorithm [LG05], and an + algorithm for adapting the retransmission timeout after a spurious + RTO [BBA06]. If no specific response algorithm is implemented, the + TCP SHOULD respond to spurious timeout conservatively, applying the + TCP congestion control specification [APB09]. Different response + algorithms for spurious retransmission timeouts have been analyzed in + some research papers [GL03, Sar03] and IETF documents [SL03]. + +5. Evaluation of RFC 4138 + + F-RTO was first specified in an Experimental RFC (RFC 4138) that has + been implemented in a number of operating systems since it was + published. Gained experience has been documented in a separate + document [KYHS07], and can be summarized as follows. + + If the TCP sender employs F-RTO, it is able to detect spurious RTOs + and avoid the unnecessary retransmission of the whole window of data. + Because F-RTO avoids the unnecessary retransmissions after a spurious + RTO, it is able to adhere to the packet conservation principle, + unlike a regular TCP that enters the slow-start recovery + unnecessarily and inappropriately restarts the ACK clock while there + are segments outstanding in the network. When a spurious RTO has + been detected, a sender can select an appropriate congestion control + response instead of setting the congestion window to one segment. + Because F-RTO avoids unnecessary retransmissions, it is able to take + the round-trip time of the delayed segments into account when + calculating the RTO estimate, which may help in avoiding further + spurious retransmission timeouts. + + Experimental results with the basic F-RTO have been reported in an + emulated network using a Linux implementation [SKR03]. Also, + different congestion control responses along with the SACK-enhanced + version of F-RTO were tested in a similar environment [Sar03]. There + are publications analyzing F-RTO performance over commercial Wideband + Code Division Multiple Access (W-CDMA) networks, and in an emulated + High-Speed Downlink Packet Access (HSDPA) network [Yam05, Hok05]. + Also, Microsoft reported positive experiences with their + implementation of F-RTO at the IETF-68 meeting. + + It is known that some spurious RTOs may remain undetected by F-RTO if + duplicate acknowledgments arrive at the sender immediately after the + spurious RTO, for example due to packet reordering or packet loss. + There are rare corner cases where F-RTO could "hide" a packet loss + + + +Sarolahti, et al. Standards Track [Page 12] + +RFC 5682 F-RTO September 2009 + + + and therefore lead to inappropriate behavior with non-conservative + congestion control response: first, if a massive packet reordering + occurred so that the acknowledgment of RTO retransmission arrived at + the sender before the acknowledgments of original transmissions, the + sender might not detect the loss of the segment that triggered the + RTO. Second, a malicious receiver could lead F-RTO to make a wrong + conclusion after an RTO by acknowledging segments it has not + received. Such a receiver would, however, risk breaking the + consistency of the TCP state between the sender and receiver, causing + the connection to become unusable, which cannot be of any benefit to + the receiver. Therefore, we believe it is not likely that receivers + would start employing such tricks on a significant scale. Finally, + loss of the unnecessary RTO retransmission cannot be detected without + using some explicit acknowledgment scheme such as DSACK. This is + common to the other mechanisms for detecting spurious RTO, as well as + to regular TCP that does not use DSACK. We note that if the + congestion control response to spurious RTO is conservative enough, + the above corner cases do not cause problems due to increased + congestion. + +6. Security Considerations + + The main security threat regarding F-RTO is the possibility that a + receiver could mislead the sender into setting too large a congestion + window after an RTO. There are two possible ways a malicious + receiver could trigger a wrong output from the F-RTO algorithm. + First, the receiver can acknowledge data that it has not received. + Second, it can delay acknowledgment of a segment it has received + earlier, and acknowledge the segment after the TCP sender has been + deluded to enter algorithm step 3. + + If the receiver acknowledges a segment it has not really received, + the sender can be led to declare spurious timeout in the F-RTO + algorithm, step 3. However, because the sender will have an + incorrect state, it cannot retransmit the segment that has never + reached the receiver. Therefore, this attack is unlikely to be + useful for the receiver to maliciously gain a larger congestion + window. + + A common case for a retransmission timeout is that a fast + retransmission of a segment is lost. If all other segments have been + received, the RTO retransmission causes the whole window to be + acknowledged at once. This case is recognized in F-RTO algorithm + branch (2a). However, if the receiver only acknowledges one segment + after receiving the RTO retransmission, and then the rest of the + segments, it could cause the timeout to be declared spurious when it + is not. Therefore, it is suggested that, when an RTO occurs during + + + + +Sarolahti, et al. Standards Track [Page 13] + +RFC 5682 F-RTO September 2009 + + + the fast recovery phase, the sender would not fully revert the + congestion window even if the timeout was declared spurious. + Instead, the sender would reduce the congestion window to 1. + + If there is more than one segment missing at the time of a + retransmission timeout, the receiver does not benefit from misleading + the sender to declare a spurious timeout because the sender would + have to go through another recovery period to retransmit the missing + segments, usually after an RTO has elapsed. + +7. Acknowledgments + + The authors would like to thank Alfred Hoenes, Ilpo Jarvinen, and + Murari Sridharan for the comments on this document. + + We are also thankful to Reiner Ludwig, Andrei Gurtov, Josh Blanton, + Mark Allman, Sally Floyd, Yogesh Swami, Mika Liljeberg, Ivan Arias + Rodriguez, Sourabh Ladha, Martin Duke, Motoharu Miyake, Ted Faber, + Samu Kontinen, and Kostas Pentikousis who gave valuable feedback + during the preparation of RFC 4138, the precursor of this document. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Sarolahti, et al. Standards Track [Page 14] + +RFC 5682 F-RTO September 2009 + + +Appendix A. Discussion of Window-Limited Cases + + When the advertised window limits the transmission of two new + previously unsent segments, or there are no new data to send, it is + recommended in F-RTO algorithm step (2b) that the TCP sender continue + with the conventional RTO recovery algorithm. The disadvantage is + that the sender may continue unnecessary retransmissions due to + possible spurious timeout. This section briefly discusses the + options that can potentially improve performance when transmitting + previously unsent data is not possible. + + - The TCP sender could reserve an unused space of a size of one or + two segments in the advertised window to ensure the use of + algorithms such as F-RTO or Limited Transmit [ABF01] in receiver + window-limited situations. On the other hand, while doing this, + the TCP sender should ensure that the window of outstanding + segments is large enough for proper utilization of the available + pipe. + + - Use additional information if available, e.g., TCP timestamps with + the Eifel Detection algorithm, for detecting a spurious timeout. + However, Eifel detection may yield different results from F-RTO + when ACK losses and an RTO occur within the same round-trip time + [SKR03]. + + - Retransmit data from the tail of the retransmission queue and + continue with step 3 of the F-RTO algorithm. It is possible that + the retransmission will be made unnecessarily. Furthermore, the + operation of the SACK-based F-RTO algorithm would need to consider + this case separately, to not use the retransmitted segment to + indicate spurious timeout. Given these considerations, this option + is not recommended. + + - Send a zero-sized segment below SND.UNA, similar to a TCP Keep- + Alive probe, and continue with step 3 of the F-RTO algorithm. + Because the receiver replies with a duplicate ACK, the sender is + able to detect whether the timeout was spurious from the incoming + acknowledgment. This method does not send data unnecessarily, but + it delays the recovery by one round-trip time in cases where the + timeout was not spurious. Therefore, this method is not + encouraged. + + - In receiver-limited cases, send one octet of new data, regardless + of the advertised window limit, and continue with step 3 of the + F-RTO algorithm. It is possible that the receiver will have free + buffer space to receive the data by the time the segment has + + + + + +Sarolahti, et al. Standards Track [Page 15] + +RFC 5682 F-RTO September 2009 + + + propagated through the network, in which case no harm is done. If + the receiver is not capable of receiving the segment, it rejects + the segment and sends a duplicate ACK. + +Appendix B. Changes since RFC 4138 + + Changes from RFC 4138 are summarized below, apart from minor + editing and language improvements. + + * Modified the basic F-RTO algorithm and the SACK-enhanced F-RTO + algorithm to prevent the TCP sender from applying the F-RTO + algorithm if the retransmission timer expires when an earlier RTO + recovery is underway, except when the retransmission timer expires + multiple times for the same segment. + + * Clarified behavior on multiple timeouts. + + * Added a paragraph on acknowledgments that do not acknowledge new + data but are not duplicate acknowledgments. + + * Clarified the SACK-algorithm a bit, and added one paragraph of + description of the basic idea of the algorithm. + + * Removed SCTP considerations. + + * Removed earlier Appendix sections, except Appendix C from RFC 4138, + which is now Appendix A. + + * Clarified text about the possible response algorithms. + + * Added section that summarizes the evaluation of RFC 4138. + +References + +Normative References + + [APB09] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion + Control", RFC 5681, September 2009. + + [BAFW03] Blanton, E., Allman, M., Fall, K., and L. Wang, "A + Conservative Selective Acknowledgment (SACK)-based Loss + Recovery Algorithm for TCP", RFC 3517, April 2003. + + [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate + Requirement Levels", BCP 14, RFC 2119, March 1997. + + + + + + +Sarolahti, et al. Standards Track [Page 16] + +RFC 5682 F-RTO September 2009 + + + [FHG04] Floyd, S., Henderson, T., and A. Gurtov, "The NewReno + Modification to TCP's Fast Recovery Algorithm", RFC 3782, + April 2004. + + [MMFR96] Mathis, M., Mahdavi, J., Floyd, S., and A. Romanow, "TCP + Selective Acknowledgment Options", RFC 2018, October 1996. + + [PA00] Paxson, V. and M. Allman, "Computing TCP's Retransmission + Timer", RFC 2988, November 2000. + + [Pos81] Postel, J., "Transmission Control Protocol", STD 7, RFC + 793, September 1981. + +Informative References + + [ABF01] Allman, M., Balakrishnan, H., and S. Floyd, "Enhancing + TCP's Loss Recovery Using Limited Transmit", RFC 3042, + January 2001. + + [BA04] Blanton, E. and M. Allman, "Using TCP Duplicate Selective + Acknowledgement (DSACKs) and Stream Control Transmission + Protocol (SCTP) Duplicate Transmission Sequence Numbers + (TSNs) to Detect Spurious Retransmissions", RFC 3708, + February 2004. + + [BBA06] Blanton, J., Blanton, E., and M. Allman, "Using Spurious + Retransmissions to Adapt the Retransmission Timeout", Work + in Progress, December 2006. + + [BBJ92] Jacobson, V., Braden, R., and D. Borman, "TCP Extensions + for High Performance", RFC 1323, May 1992. + + [FMMP00] Floyd, S., Mahdavi, J., Mathis, M., and M. Podolsky, "An + Extension to the Selective Acknowledgement (SACK) Option + for TCP", RFC 2883, July 2000. + + [GL02] Gurtov A. and R. Ludwig, "Evaluating the Eifel Algorithm + for TCP in a GPRS Network", In Proc. European Wireless, + Florence, Italy, February 2002. + + [GL03] Gurtov A. and R. Ludwig, "Responding to Spurious Timeouts + in TCP", In Proc. IEEE INFOCOM 03, San Francisco, CA, USA, + March 2003. + + [Jac88] Jacobson, V., "Congestion Avoidance and Control", In Proc. + ACM SIGCOMM 88. + + + + + +Sarolahti, et al. Standards Track [Page 17] + +RFC 5682 F-RTO September 2009 + + + [Hok05] Hokamura, A., et al., "Performance Evaluation of F-RTO and + Eifel Response Algorithms over W-CDMA packet network", In + Proc. Wireless Personal Multimedia Communications + (WPMC'05), Sept. 2005. + + [KYHS07] Kojo, M., Yamamoto, K., Hata, M., and P. Sarolahti, + "Evaluation of RFC 4138", Work in Progress, November 2007. + + [LG05] Ludwig, R. and A. Gurtov, "The Eifel Response Algorithm for + TCP", RFC 4015, February 2005. + + [LK00] Ludwig R. and R.H. Katz, "The Eifel Algorithm: Making TCP + Robust Against Spurious Retransmissions", ACM SIGCOMM + Computer Communication Review, 30(1), January 2000. + + [LM03] Ludwig, R. and M. Meyer, "The Eifel Detection Algorithm for + TCP", RFC 3522, April 2003. + + [Nag84] Nagle, J., "Congestion control in IP/TCP internetworks", + RFC 896, January 1984. + + [SK05] Sarolahti, P. and M. Kojo, "Forward RTO-Recovery (F-RTO): + An Algorithm for Detecting Spurious Retransmission Timeouts + with TCP and the Stream Control Transmission Protocol + (SCTP)", RFC 4138, August 2005. + + [SKR03] Sarolahti, P., Kojo, M., and K. Raatikainen, "F-RTO: An + Enhanced Recovery Algorithm for TCP Retransmission + Timeouts", ACM SIGCOMM Computer Communication Review, + 33(2), April 2003. + + [Sar03] Sarolahti, P., "Congestion Control on Spurious TCP + Retransmission Timeouts", In Proc. of IEEE Globecom 2003, + San Francisco, CA, USA. December 2003. + + [SL03] Swami Y. and K. Le, "DCLOR: De-correlated Loss Recovery + using SACK Option for spurious timeouts", Work in Progress, + September 2003. + + [Ste07] Stewart, R., Ed., "Stream Control Transmission Protocol", + RFC 4960, September 2007. + + [Yam05] Yamamoto, K., et al., "Effects of F-RTO and Eifel Response + Algorithms for W-CDMA and HSDPA networks", In Proc. + Wireless Personal Multimedia Communications (WPMC'05), + September 2005. + + + + + +Sarolahti, et al. Standards Track [Page 18] + +RFC 5682 F-RTO September 2009 + + +Authors' Addresses + + Pasi Sarolahti + Nokia Research Center + P.O. Box 407 + FI-00045 NOKIA GROUP + Finland + Phone: +358 50 4876607 + EMail: pasi.sarolahti@iki.fi + + Markku Kojo + University of Helsinki + P.O. Box 68 + FI-00014 UNIVERSITY OF HELSINKI + Finland + Phone: +358 9 19151305 + EMail: kojo@cs.helsinki.fi + + Kazunori Yamamoto + NTT Docomo, Inc. + 3-5 Hikarinooka, Yokosuka, Kanagawa, 239-8536, Japan + Phone: +81-46-840-3812 + EMail: yamamotokaz@nttdocomo.co.jp + + Max Hata + NTT Docomo, Inc. + 3-5 Hikarinooka, Yokosuka, Kanagawa, 239-8536, Japan + Phone: +81-46-840-3812 + EMail: hatama@s1.nttdocomo.co.jp + + + + + + + + + + + + + + + + + + + + + + +Sarolahti, et al. Standards Track [Page 19] + |