RFC 5682

Forward RTO-Recovery (F-RTO): An Algorithm for Detecting Spurious Retransmission Timeouts with TCP ✨

Okay bestie, so this is RFC 5682 🎀 It's a Standards Track doc from September 2009, written by P. Sarolahti (Nokia Research Center), M. Kojo (University of Helsinki), K. Yamamoto, and M. Hata (NTT Docomo). It updates RFC 4138 💅 and it's basically the glow-up that moves F-RTO for TCP from Experimental to Standards Track 🦋. The SCTP side of RFC 4138 stays Experimental though, so don't get confused 🙈

This is part 1 of 4, so more is coming, no cap 🫶

Abstract

Okay so the whole point of this doc is to move the F-RTO (Forward RTO-Recovery) stuff for TCP from RFC 4138 up to Standards Track 🌸 The F-RTO support for Stream Control Transmission Protocol (SCTP) in RFC 4138 stays at Experimental status ✨ See Appendix B for the differences between this document and RFC 4138 💜

Spurious retransmission timeouts are lowkey bad for TCP performance, because they often cause unnecessary retransmission of the last window of data 😭 This doc describes the F-RTO detection algorithm, which is how a TCP sender figures out whether a timeout was spurious 🔥 F-RTO is a TCP sender-only algorithm, so it doesn't need any TCP options to work 💅 After the sender retransmits the first unacknowledged segment because of a timeout, it watches the incoming ACKs to decide if the timeout was spurious 👑 Then it chooses whether to send new segments or retransmit the unacknowledged ones 🎀 The whole thing helps avoid extra unnecessary retransmissions and makes TCP performance better in a spurious timeout situation 🦋

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

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

1. Introduction 🧚

Okay so TCP [Pos81] has two ways of triggering retransmissions 💖 First, the TCP sender listens for incoming duplicate ACKs, which basically means the receiver is missing some data 😭 Once a required number of successive duplicate ACKs show up, the sender retransmits the first unacknowledged segment [APB09] and keeps going with a loss recovery algorithm like NewReno [FHG04] or SACK-based (Selective Acknowledgment) loss recovery [BAFW03] 🔥 Second, the TCP sender runs a retransmission timer that triggers retransmission of segments that haven't been acknowledged before the retransmission timeout (RTO) happens ⏰ When the RTO happens, the TCP sender enters RTO recovery, where the congestion window is set to one segment and unacknowledged segments are retransmitted using slow start 🌸 The retransmission timer adjusts dynamically based on measured round-trip times [PA00] ✨

It's been pointed out that the retransmission timer can expire spuriously and cause unnecessary retransmissions even when no segments were lost [LK00, GL02, LM03] 🙈 After a spurious retransmission timeout, the late ACKs for the original segments show up at the sender and usually trigger unnecessary retransmission of a whole window of segments during RTO recovery 💀 Also, after a spurious retransmission timeout, a conventional TCP sender grows the congestion window on each late ACK in slow start 😭 That shoves a huge number of data segments into the network within one round-trip time, which breaks the packet conservation principle [Jac88] 🫶

There are a bunch of potential reasons for spurious retransmission timeouts 💜 First, some mobile networking technologies have sudden delay spikes during transmission because of actions taken during a hand-off 🦋 Second, a hand-off may go from a low latency path to a high latency path, which suddenly bumps the round-trip time past the current RTO value 🌈 Third, on a low-bandwidth link, competing traffic (possibly with higher priority), or some other change in available bandwidth, can cause a sudden increase in round-trip time 👑 That 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 get lost for some reason 💅 This document doesn't distinguish between the different causes of such a delay spike 🎀 Instead, it talks about spurious retransmission timeouts caused by a delay spike in general 🍓

This doc describes the F-RTO detection algorithm for TCP 🦋 It's based on the detection mechanism of the "Forward RTO-Recovery" (F-RTO) algorithm [SKR03], which detects spurious retransmission timeouts and avoids unnecessary retransmissions after the timeout 💖 When the timeout isn't spurious, F-RTO goes back to the conventional RTO recovery algorithm, so it has similar behavior and performance 🌸 Compared to other ways of detecting unnecessary retransmissions, like Eifel [LK00, LM03] and DSACK-based (Duplicate SACK) algorithms [BA04], F-RTO doesn't need any TCP options and can be implemented by only modifying the TCP sender 🔥 The Eifel algorithm uses TCP timestamps [BBJ92] to detect a spurious timeout when the first ACK after the retransmission arrives 🧚 The DSACK-based algorithms need the TCP Selective Acknowledgment Option [MMFR96], with the DSACK extension [FMMP00], to be in use 🌈 With DSACK, the TCP receiver can report if it got a duplicate segment, so the sender can figure out afterwards whether it retransmitted segments unnecessarily 👑 F-RTO only tries to detect and avoid unnecessary retransmissions after an RTO ✨ Eifel and DSACK can also detect unnecessary retransmissions caused by other events, like packet reordering 💅

When the retransmission timer expires, the F-RTO sender retransmits the first unacknowledged segment as usual [APB09] 🎀 Then, unlike normal operation after a timeout, it tries to send new, previously unsent data for the first ACK that arrives after the timeout, as long as that ACK advances the window 🦋 If the second ACK that arrives after the timeout advances the window (meaning it acknowledges data that wasn't retransmitted), the F-RTO sender declares the timeout spurious and exits RTO recovery 💖 But if either of those two ACKs is a duplicate ACK, there isn't enough evidence of a spurious timeout 😭 So the F-RTO sender retransmits the unacknowledged segments in slow start, just like the traditional algorithm 🌸 With the SACK-enhanced version of F-RTO, spurious timeouts may still 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 for 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], which has acknowledgment and packet retransmission concepts similar to TCP 🧚 The considerations for applying F-RTO to SCTP are discussed in RFC 4138, but F-RTO support for SCTP stays at Experimental status 💜

This document is organized as follows 🫶 Section 2 covers the basic F-RTO algorithm, and the SACK-enhanced F-RTO algorithm is in Section 3 💅 Section 4 talks about possible actions to take after detecting a spurious RTO 👑 Section 5 summarizes the experience with F-RTO implementations and the experimental results, and Section 6 covers 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. 🎀

---

To be continued in part 2 💖 Don't go anywhere, bestie 🫶

2. Basic F-RTO Algorithm ✨

okay so a timeout is spurious if it would have been avoided had the sender just waited a bit longer for an ACK to show up [LM03] 🙈 F-RTO only changes what the TCP sender does after a retransmission timeout. Before that, TCP behaves exactly the same 💅 Once the retransmission timer goes off, F-RTO watches the incoming ACKs, and if the sender gets an ACK for a segment that was not retransmitted because of the timeout, F-RTO declares the timeout spurious 🦋 What you do after a spurious timeout isn't specified in this doc, but we talk about some options in Section 4 🧚 This section introduces the algorithm, then breaks down each step in more detail 🫶

Following the same approach as the Eifel Detection algorithm [LM03] 💜, we use a variable called SpuriousRecovery to track whether the sender has declared the retransmission spurious. It can be used as an input for a matching response algorithm 🎀 With F-RTO, SpuriousRecovery is either SPUR_TO (a spurious retransmission timeout) or FALSE (the timeout is not declared spurious, so the TCP sender should follow the conventional RTO recovery algorithm) 🌸 We also use the recover variable from the NewReno algorithm [FHG04] ⭐

2.1. The Algorithm 💖

A TCP sender running the basic F-RTO algorithm MUST take the following steps after the retransmission timer expires 👑 If the retransmission timer expires again while F-RTO is running, the TCP sender MUST re-start the algorithm from step 1 🔥 If the sender uses a loss recovery algorithm other than Reno or NewReno [FHG04], then F-RTO SHOULD NOT be entered when earlier fast recovery is underway 🙅‍♀️

F-RTO acts differently depending on whether an incoming ACK advances the cumulative acknowledgment point for a received in-order segment, or whether it's a duplicate ACK signalling an out-of-order segment 🧠 Duplicate ACK is defined in [APB09] ✨ F-RTO doesn't specify any actions for a segment that neither acknowledges new data nor is a duplicate ACK 🤷‍♀️ The TCP sender SHOULD ignore those segments and wait for one that either acknowledges new data or is a duplicate ACK 💅

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 sent so far in recover and keep going with slow-start retransmissions, following the conventional RTO recovery algorithm 🔁
2. When the first ACK after the RTO retransmission arrives, store the highest sequence number sent so far in recover 📦 Then the TCP sender picks one of the following actions, depending on whether the ACK advances the window or is a duplicate ACK 👀
   • a) If the ACK is a duplicate ACK, OR the Acknowledgment field covers recover but not more than recover, OR the ACK doesn't acknowledge all of the data that was retransmitted in step 1, go back to conventional RTO recovery and keep retransmitting unacknowledged data in slow start 🐢 Do not enter step 3 of this algorithm. SpuriousRecovery stays FALSE 😤
   • b) Else, if the ACK 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 doesn't have enough unsent data, it can only send one segment 🥺 Also, the TCP sender MAY override the Nagle algorithm [Nag84] and send a segment right away if needed ⚡ Sending two segments in this step is allowed by TCP congestion control requirements [APB09], because an F-RTO sender just picks different segments to transmit 💜

If the TCP sender has no new data to send, or the advertised window blocks new transmissions, the recommended action is to skip step 3 of this algorithm and keep going with slow-start retransmissions, following the conventional RTO recovery algorithm 🫠 That said, there are other ways to handle the window-limited cases that could perform better, and they're discussed in Appendix A 🌈

3. When the second ACK after the RTO retransmission arrives, the TCP sender either declares the timeout spurious, or starts retransmitting the unacknowledged segments 🥁
   • a) If the ACK is a duplicate ACK, set the congestion window to no more than 3 * MSS (where MSS indicates Maximum Segment Size), and keep going with the slow-start algorithm, retransmitting unacknowledged segments 🐣 The congestion window can be set to 3 * MSS because two round-trip times have passed since the RTO, and a conventional TCP sender would have grown cwnd to 3 in the same time 📈 Leave SpuriousRecovery set to FALSE 🙃
   • b) If the ACK advances the window (meaning it acknowledges data that was not retransmitted after the timeout), declare the timeout spurious, set SpuriousRecovery to SPUR_TO, and set the recover variable to SND.UNA (the oldest unacknowledged sequence number [Pos81]) 🎉🎉

2.2. Discussion 🧁

F-RTO is extra cautious when it gets duplicate ACKs after a retransmission timeout 🫣 Duplicate ACKs can mean segments were lost, and without extra info it's really hard to reliably detect a spurious timeout 😬 So it's smart to just follow conventional TCP recovery in those cases 🛡️

The condition in step 1 stops F-RTO from running if a previous RTO recovery is already happening when the retransmission timer expires 🚫 The exception is when the timer expires multiple times for the same segment 🔄 If the timer goes off during an earlier RTO-based loss recovery, ACKs for retransmitted segments could wrongly convince the TCP sender that the timeout was spurious 🤯

If the first ACK after the RTO retransmission covers the "recover" point at algorithm step (2a), there isn't enough evidence that a non-retransmitted segment reached the receiver after the timeout 🕵️‍♀️ This happens a lot when a fast retransmission gets lost and then gets retransmitted again after an RTO, while the rest of the unacknowledged segments were delivered to the receiver before the timeout 📬 So the timeout can't be declared spurious in this case 🙅‍♀️

If the first ACK after the RTO retransmission doesn't acknowledge all of the data retransmitted in step 1, the TCP sender goes back to conventional RTO recovery 🔙 Otherwise, a malicious receiver acknowledging only partial segments could trick the sender into declaring the timeout spurious when data was actually lost 😈 Not cute 💀

The TCP sender is allowed to send two new segments in algorithm branch (2b) because a conventional TCP sender would transmit two segments when the first new ACK arrives after the RTO retransmission 👯‍♀️ If sending new data isn't possible in branch (2b), or the receiver window limits the transmission, the TCP sender still has to send something so the transfer doesn't stall 😵 If nothing gets sent, the pipe between sender and receiver might run out of segments, and no more ACKs would arrive 🥲 So in the window-limited case, the recommendation is to go back to conventional RTO recovery with slow-start retransmissions 🩷 Appendix A talks about some alternative solutions for window-limited situations ✨

If the retransmission timeout is declared spurious, the TCP sender sets recover to SND.UNA so it can do fast retransmit [FHG04] 🏃‍♀️ The recover variable was originally proposed to avoid unnecessary, multiple fast retransmits when the retransmission timer expires during fast recovery with NewReno TCP 🧩 Since F-RTO only retransmits the segment that triggered the timeout, the problem of unnecessary multiple fast retransmits [FHG04] can't happen 🙌 So if three duplicate ACKs arrive at the sender after the timeout, they probably mean a packet was lost, and fast retransmit should be used for efficient recovery 💫 If not enough duplicate ACKs arrive after a packet loss, the retransmission timer expires again and the sender enters step 1 of this algorithm again 🔁

When the timeout is declared spurious, the TCP sender can't tell whether the unnecessary RTO retransmission was lost 🫥 In principle, losing the RTO retransmission should be treated as a congestion signal 🚨 So there's a small chance the F-RTO sender could break the congestion control rules if it fully reverts congestion control parameters after detecting a spurious timeout ⚠️ The Eifel Detection algorithm has a similar property, while the DSACK option can be used to check whether the retransmitted segment was successfully delivered to the receiver 📮

F-RTO also has a side effect on TCP round-trip time measurement 🕰️ Because the TCP sender can avoid most unnecessary retransmissions after detecting a spurious timeout, it can take round-trip time samples on the delayed segments 📏 If regular RTO recovery was used without TCP timestamps, that wouldn't be possible because of retransmission ambiguity 🙃 As a result, the RTO is likely to have more accurate and larger values with F-RTO than with regular TCP after a spurious timeout triggered by delayed segments 📈 We think that's a win for networks that are prone to delay spikes 🌊

There are some situations where F-RTO might not avoid unnecessary retransmissions after a spurious timeout 🫤 If packet reordering or packet duplication happens on the segment that triggered the spurious timeout, F-RTO may not detect the spurious timeout because of incoming duplicate ACKs 🌀 Also, if a spurious timeout happens during fast recovery, F-RTO often can't detect it, because the segments sent before fast recovery trigger duplicate ACKs 🙄 Still, we consider these cases rare 🤞 And in cases where F-RTO fails to detect the spurious timeout, it retransmits the unacknowledged segments in slow start, so it performs the same as regular RTO recovery 🫶💖

3. SACK-Enhanced Version of the F-RTO Algorithm ✨

okay so this section is the glow-up 💅 version of F-RTO, and it uses the TCP Selective Acknowledgment Option [MMFR96]. with SACK on board, the TCP sender can catch spurious timeouts in most of the cases where packet reordering or packet duplication is happening 🔥. if the SACK info acknowledges new data that wasn't sent after the RTO retransmission, the sender may declare the timeout spurious, even when duplicate ACKs follow the RTO 🫶

3.1. The Algorithm 🎀

so if the TCP Selective Acknowledgment Option [MMFR96] is enabled for a TCP connection, a TCP sender MAY apply the SACK-enhanced F-RTO algorithm 🦋. if it does, 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 go like this. if the retransmission timer expires again while the SACK-enhanced F-RTO algorithm is running, the TCP sender MUST re-start the algorithm processing from step 1 🌸

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 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 it uses the extra info from the SACK option 💖. when a genuine retransmission timeout happens 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 those segments would have triggered the SACK loss recovery or the transmission of new segments 🫶

so if the F-RTO sender gets acknowledgments for segments sent before the retransmission timeout, in response to the two new segments sent at algorithm step 2, the normal operation of TCP has just been delayed, and the retransmission timeout is considered spurious. the vibe check: this reasoning only works 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 stops F-RTO from running if a previous loss recovery, either RTO recovery or SACK loss recovery, is underway when the retransmission timer expires. however, it does allow F-RTO to run if the retransmission timer expires multiple times for the same segment 💅

---

4. Taking Actions after Detecting Spurious RTO 🎀

so a conventional TCP sender assumes outstanding segments are lost when an RTO hits, and it starts retransmitting the unacknowledged segments 😬. when the timeout is detected to be spurious, the TCP sender should not continue retransmitting based on the timeout. for example, if the sender was in the congestion 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 🍓. the experience gained has been documented in a separate document [KYHS07], and it can be summarized like this 💅

if the TCP sender employs F-RTO, it can detect spurious RTOs and avoid unnecessarily retransmitting the whole window of data 🔥. because F-RTO avoids those unnecessary retransmissions after a spurious RTO, it can adhere to the packet conservation principle. a regular TCP, on the other hand, enters 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 🫶. and because F-RTO avoids unnecessary retransmissions, it can take the round-trip time of the delayed segments into account when calculating the RTO estimate, which may help avoid further spurious retransmission timeouts 🌈

experimental results with the basic F-RTO have been reported in an emulated network using a Linux implementation [SKR03]. different congestion control responses along with the SACK-enhanced version of F-RTO were also 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]. and Microsoft reported positive experiences with their implementation of F-RTO at the IETF-68 meeting 👑✨

it's known that some spurious RTOs may remain undetected by F-RTO if duplicate acknowledgments arrive at the sender right 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, and that could lead to inappropriate behavior with a non-conservative congestion control response. first, if massive packet reordering occurred so that the acknowledgment of the RTO retransmission arrived at the sender before the acknowledgments of the 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. but that kind of receiver would risk breaking the consistency of the TCP state between sender and receiver, causing the connection to become unusable, which can't be of any benefit to the receiver 💀. so we believe it's 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 🔒✨

okay so the big security worry with F-RTO is that a receiver could trick the sender into setting a window that's way too big after an RTO 😤 There are two ways a sneaky receiver could make F-RTO give a wrong answer. First, it can ACK data it never actually got 🙃. Second, it can sit on an ACK for a segment it did get earlier, and only send that ACK after the sender has already been fooled into going to algorithm step 3 💀

If the receiver ACKs a segment it never really received, the sender can be led to declare a spurious timeout in step 3 of F-RTO. BUT, because the sender now has an incorrect state, it can't retransmit the segment that never reached the receiver. So this attack isn't really useful for the receiver if it wants to maliciously grab a bigger congestion window 🙄

A super common case for an RTO is that a fast retransmission gets lost too 🥲 If every other segment was received, the RTO retransmission gets the whole window ACKed in one go. That case is handled in F-RTO algorithm branch (2a) 💖 However, if the receiver only ACKs one segment after getting the RTO retransmission, and then ACKs the rest, it could make the timeout look spurious when it actually wasn't 😬 So it's suggested that when an RTO happens during the fast recovery phase, the sender should not fully revert the congestion window even if the timeout gets declared spurious. Instead, the sender would drop the congestion window down to 1 🎀

If there's more than one segment missing at the time of a retransmission timeout, the receiver gets nothing from tricking the sender into a spurious timeout 🙅‍♀️ The sender would have to go through another recovery period to retransmit the missing segments anyway, and that usually happens after an RTO has elapsed ⏳

---

7. Acknowledgments 🫶

the authors want to thank Alfred Hoenes, Ilpo Jarvinen, and Murari Sridharan for their comments on this document 💜

we're also so grateful 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 🌸🙌

---

Appendix A. Discussion of Window-Limited Cases 🪟

okay so when the advertised window only lets through two new, previously unsent segments, or there's no new data to send at all, it is recommended in F-RTO algorithm step (2b) that the TCP sender just keeps going with the conventional RTO recovery algorithm 🧸 The downside is that the sender may keep doing unnecessary retransmissions because of a possible spurious timeout 😩 This section briefly looks at options that could help performance when sending previously unsent data just isn't possible 👀

• The TCP sender could reserve an unused space of one or two segments in the advertised window, so algorithms like F-RTO or Limited Transmit [ABF01] can be used in receiver window-limited situations 🦋 On the other hand, while doing this, the TCP sender should make sure the window of outstanding segments is big enough to properly use the available pipe 💅
• Use additional information if it's available, e.g., TCP timestamps with the Eifel Detection algorithm, to detect a spurious timeout ✨ However, Eifel detection may give different results from F-RTO when ACK losses and an RTO happen 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's possible that the retransmission gets made unnecessarily 😭 Also, the operation of the SACK-based F-RTO algorithm would need to handle this case separately, so it doesn't use the retransmitted segment to indicate a spurious timeout. Given all of that, 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 can tell whether the timeout was spurious from the incoming acknowledgment 🙌 This method doesn't send data unnecessarily, but it delays recovery by one round-trip time in cases where the timeout wasn't 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's possible the receiver will have free buffer space to take the data by the time the segment has traveled through the network, in which case no harm is done ✨ If the receiver can't accept the segment, it rejects it and sends a duplicate ACK 💅

---

Appendix B. Changes since RFC 4138 📝

the 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 so the TCP sender doesn't apply F-RTO if the retransmission timer expires while 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 don't acknowledge new data but aren't duplicate acknowledgments 💜
• Clarified the SACK algorithm a bit, and added one paragraph describing 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 a 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.

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

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

---

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