RFC 4138

Forward RTO-Recovery (F-RTO): An Algorithm for Detecting Spurious Retransmission Timeouts with TCP and the Stream Control Transmission Protocol (SCTP)

📅 published August 2005, from ietf

Forward RTO-Recovery (F-RTO): An Algorithm for Detecting Spurious Retransmission Timeouts with TCP and the Stream Control Transmission Protocol (SCTP) 💖

Okay bestie, this is RFC 4138 🎀 It's from the Network Working Group, written by P. Sarolahti (Nokia Research Center) and M. Kojo (University of Helsinki). It's an Experimental doc, dated August 2005 📅 (very vintage, I'm obsessed). It doesn't obsolete anything and doesn't update anything, because the header doesn't list anything it obsoletes or updates. Lowkey iconic that it just stands on its own ✨

Status of This Memo 📝

So this memo defines an Experimental Protocol for the Internet community 🧪 It does not specify an Internet standard of any kind, no cap. The authors are asking for discussion and suggestions for improvement 💬 And distribution of this memo is unlimited, so share away 🦋

Copyright (C) The Internet Society (2005). ✨

Abstract 🫶

Okay so spurious retransmission timeouts make TCP perform worse than it should 😭 because they often cause unnecessary retransmission of the last window of data. This document describes the F-RTO detection algorithm, which is how you spot spurious TCP retransmission timeouts 🔍 F-RTO is a TCP sender-only algorithm, and it does not require any TCP options to operate, which is so clean 💅 After the first unacknowledged segment gets retransmitted because of a timeout, the F-RTO sender watches the incoming acknowledgments to figure out whether the timeout was spurious. Then it decides whether to send new segments or retransmit unacknowledged segments. The whole point is avoiding extra unnecessary retransmissions, so TCP performance gets better when a timeout turns out to be spurious 🚀 And the F-RTO algorithm can also be applied to the Stream Control Transmission Protocol (SCTP) 🧚

Table of Contents 📜

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . .   2
       1.1.  Terminology . . . . . . . . . . . . . . . . . . . .   4
   2.  F-RTO Algorithm . . . . . . . . . . . . . . . . . . . . .   4
       2.1.  The Algorithm . . . . . . . . . . . . . . . . . . .   5
       2.2.  Discussion  . . . . . . . . . . . . . . . . . . . .   6
   3.  SACK-Enhanced Version of the F-RTO Algorithm  . . . . . .   8
   4.  Taking Actions after Detecting Spurious RTO . . . . . . .  10
   5.  SCTP Considerations . . . . . . . . . . . . . . . . . . .  10
   6.  Security Considerations . . . . . . . . . . . . . . . . .  11
   7.  Acknowledgements  . . . . . . . . . . . . . . . . . . . .  12
   8.  References  . . . . . . . . . . . . . . . . . . . . . . .  12
       8.1.  Normative References. . . . . . . . . . . . . . . .  12
       8.2.  Informative References. . . . . . . . . . . . . . .  13
   Appendix A: Scenarios . . . . . . . . . . . . . . . . . . . .  15
   Appendix B: SACK-Enhanced F-RTO and Fast Recovery . . . . . .  20
   Appendix C: Discussion of Window-Limited Cases  . . . . . . .  21

1. Introduction 🌸

Okay so TCP [Pos81] has two ways of triggering retransmissions 🔁 First, the TCP sender relies on incoming duplicate ACKs, which tell it 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 [APS99] and keeps going with a loss recovery algorithm like NewReno [FHG04] or SACK-based loss recovery [BAFW03]. Second, the TCP sender runs a retransmission timer that triggers retransmission of segments if they haven't been acknowledged before the retransmission timeout (RTO) expires ⏰ When the retransmission timeout happens, the TCP sender enters the RTO recovery, where the congestion window gets set to one segment and unacknowledged segments get retransmitted using the slow-start algorithm 🐢 The retransmission timer adjusts itself dynamically, based on the 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 have been lost 😭 [LK00, GL02, LM03] After a spurious retransmission timeout, the late acknowledgments of the original segments show up at the sender, which usually triggers unnecessary retransmissions of a whole window of segments during the RTO recovery 💀 Furthermore, after a spurious retransmission timeout, a conventional TCP sender grows the congestion window on each late acknowledgment in slow start. That dumps a large number of data segments into the network within one round-trip time, which violates the packet conservation principle [Jac88] 🙈 Not it 🙅‍♀️

There are a bunch of potential reasons for spurious retransmission timeouts 🌈 First, some mobile networking technologies have sudden delay spikes on transmission because of actions taken during a hand-off 📱 Second, given a low-bandwidth link or some other change in available bandwidth, the arrival of competing traffic (possibly with higher priority) can cause a sudden increase of 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 are lost for some reason 🫠 This document doesn't distinguish between the different causes of such a delay spike. Instead, it discusses spurious retransmission timeouts caused by a delay spike in general 💜

This document describes the F-RTO detection algorithm 🦋 It's based on the detection mechanism of the "Forward RTO-Recovery" (F-RTO) algorithm [SKR03], which is used for detecting spurious retransmission timeouts and therefore avoids unnecessary retransmissions after the retransmission timeout. When the timeout isn't spurious, F-RTO reverts back to the conventional RTO recovery algorithm, so it has similar behavior and performance ✨ Compared to the other options for detecting unnecessary retransmissions (Eifel [LK00], [LM03] and DSACK-based 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] to detect a spurious timeout when the first acknowledgment after the retransmission arrives. 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, so the sender can figure out afterwards whether it retransmitted segments unnecessarily 🕵️‍♀️ The F-RTO algorithm only tries to detect and avoid unnecessary retransmissions after an RTO. Eifel and DSACK can also be used to detect unnecessary retransmissions caused by other events, such as packet reordering 🔀

When an RTO expires, the F-RTO sender retransmits the first unacknowledged segment as usual [APS99] ⏪ Then it does something different from normal post-timeout behavior: for the first acknowledgment that arrives after the timeout, as long as that acknowledgment advances the window, it tries to transmit new, previously unsent data 🎯 If the second acknowledgment that arrives after the timeout advances the window (i.e., it acknowledges data that was not retransmitted), the F-RTO sender declares the timeout spurious and exits the RTO recovery 🎉 But if either of those two acknowledgments 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 does. With a SACK-enhanced version of F-RTO, spurious timeouts can still be detected even if duplicate ACKs arrive after an RTO retransmission 🧠

F-RTO can also be applied to the Stream Control Transmission Protocol (SCTP) [Ste00], since SCTP has acknowledgment and packet retransmission concepts that are similar to TCP 🧚 For convenience, this document mostly talks about TCP, but the algorithms and other discussion are valid for SCTP as well 💖

Here's how this doc is laid out 🗺️ Section 2 describes the basic F-RTO algorithm. Section 3 outlines an optional enhancement to the F-RTO algorithm that takes advantage of the TCP SACK option. Section 4 discusses the possible actions to take after detecting a spurious RTO. Section 5 gives considerations on applying F-RTO with SCTP, and Section 6 discusses the security considerations 🔐

1.1. Terminology 📖

The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD, SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL, when they show up in this document, get interpreted as described in [RFC2119] 🤓

2. F-RTO Algorithm 🦋

Okay so a timeout counts as spurious if it would have been avoided had the sender just waited longer for an acknowledgment to arrive [LM03] ⏳ F-RTO only changes TCP sender behavior after a retransmission timeout. Otherwise, TCP behaves exactly the same 💅 When the RTO expires, the F-RTO algorithm watches incoming acknowledgments. If the TCP sender gets an acknowledgment for a segment that was not retransmitted due to the timeout, the F-RTO algorithm declares the timeout spurious 🎀 What the sender actually does in response to a spurious timeout isn't specified in this document, but we talk about some alternatives in Section 4 🌷 This section introduces the algorithm first, and then goes through the different steps in more detail 🔍

Following the practice used with the Eifel Detection algorithm [LM03], we use the SpuriousRecovery variable to show whether the sender has declared the retransmission spurious ✨ That variable can be used as an input for a matching response algorithm 🧩 With F-RTO, SpuriousRecovery can be either SPUR_TO (meaning a spurious retransmission timeout) or FALSE (meaning the timeout is not declared spurious), and the TCP sender should follow the conventional RTO recovery algorithm 🐢💕

2.1. The Algorithm 💅

okay so a TCP sender MAY implement the basic F-RTO algorithm 🦋 totally optional, bestie. But if she does pick it, the following steps MUST be taken once the retransmission timer expires 💀. Also, if the sender runs some loss recovery algorithm that isn't Reno or NewReno [FHG04], F-RTO SHOULD NOT be entered while earlier fast recovery is already happening. Do NOT mix these up 🙈

  1. When RTO expires, retransmit the first unacknowledged segment and set SpuriousRecovery to FALSE. Also, stash the highest sequence number sent so far in the variable "recover" 📦
  2. When the first acknowledgment after the RTO retransmission shows up, the sender picks one of two paths, depending on whether the ACK moves the window forward or whether it's a duplicate ACK 👀
    • a) If the acknowledgment is a duplicate ACK OR it acknowledges a sequence number equal to the value of "recover" OR it doesn't acknowledge all of the data that got retransmitted in step 1, the sender goes back to conventional RTO recovery and keeps retransmitting unacknowledged data in slow start 🐢. It does NOT enter step 3 of this algorithm, and SpuriousRecovery just stays FALSE 🙅‍♀️
    • b) Else, if the acknowledgment advances the window AND it's below the value of "recover", the sender transmits up to two new (previously unsent) segments and enters step 3 of this algorithm 🚀. If there isn't enough unsent data, it can only send one segment. The TCP sender MAY also override the Nagle algorithm [Nag84] and send a segment right away if needed ⚡. And yes, sending two segments here is allowed by the TCP congestion control requirements [APS99]. An F-RTO TCP sender is just picking different segments to send, no drama 💖

If the TCP sender has no new data to send, or the advertised window blocks new transmissions, the recommended move is to skip step 3 and keep going with slow start retransmissions, following conventional RTO recovery 🌸. Alternative ways to handle these window-limited cases, which could give better performance, are covered in Appendix C ✨

  1. When the second acknowledgment after the RTO retransmission shows up, 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 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 gone by since the RTO, and a conventional TCP sender would have bumped cwnd up to 3 in that same time ⏱️. Leave SpuriousRecovery set to FALSE 💜
    • b) If the acknowledgment advances the window (meaning it acknowledges data that wasn't 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 🧚

The F-RTO sender is extremely cautious when duplicate acknowledgments show up after a retransmission timeout 🙈 Duplicate ACKs can mean segments were lost, and since there isn't much extra information to go on, reliably detecting a spurious timeout is really hard 😭. So it's wise to just follow conventional TCP recovery in those cases 🫶.

If the first acknowledgment after the RTO retransmission covers the "recover" point in 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 TCP receiver just fine before the retransmission timeout 🙃. So the timeout can't be declared spurious in this case, periodt 💅

If the first acknowledgment 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 could acknowledge only partial segments and trick the sender into declaring the timeout spurious when data was actually lost 💀 not on my watch 🛡️

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 🦋. But if sending new data isn't possible in branch (2b), or the receiver window is limiting 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 further acknowledgments would ever arrive 🥲. That's why, in the window-limited case, the recommendation is to go back to conventional RTO recovery with slow start retransmissions 🐢. Appendix C talks through some alternative solutions for window-limited situations ✨

If the retransmission timeout is declared spurious, the TCP sender sets the "recover" variable to SND.UNA so it can do a fast retransmit [FHG04] 🚀. The "recover" variable was originally proposed to avoid unnecessary, multiple fast retransmits when RTO expires during fast recovery with NewReno TCP 🙌. Because the sender only retransmits the segment that triggered the timeout, the problem of unnecessary multiple fast retransmits [FHG04] can't happen here 🌈. 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 come in 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 can't tell whether the unnecessary RTO retransmission was lost too 🤔. In principle, losing that 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 decides 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 find out whether the retransmitted segment actually made it to the receiver 🎀

F-RTO also has a side effect on TCP round-trip time measurement, and it's a good one 🌟 Because the TCP sender can avoid most unnecessary retransmissions after detecting a spurious timeout, it's able to take round-trip time samples on the delayed segments 🧠. Without TCP timestamps, the regular RTO recovery couldn't do this because of retransmission ambiguity 🙅‍♀️. So after a spurious timeout caused by delayed segments, the RTO tends to end up with more accurate and larger values under F-RTO than under regular TCP 📈. We believe this is a real advantage on networks that are prone to delay spikes 🌊💜

There are some situations where F-RTO may 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 🔀. And 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 too 🥴. However, 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 much like regular RTO recovery 🫶✨

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

okay bestie, this section is where F-RTO gets a glow-up with SACK 🦋 The SACK option ([MMFR96]) lets the TCP sender spot spurious timeouts in most cases where packets get reordered or duplicated 💅. If the SACK blocks acknowledge new data that wasn't sent after the RTO retransmission, the sender can declare the timeout spurious, even when duplicate ACKs come in after the RTO 🫶

Okay so the rule is: if the TCP Selective Acknowledgment Option ([MMFR96]) is turned on for a connection, a TCP sender MAY implement the SACK-enhanced F-RTO algorithm 🌸 If it does, it MUST follow the steps below. This algorithm SHOULD NOT be used if the sender is already in SACK loss recovery when the retransmission timeout happens 😭 Like, when the RTO goes off during existing loss recovery, it should be possible to apply the F-RTO principle within certain limits, but that's a topic for further research 🔥 Appendix B briefly talks about the related issues 🧚

Here are the steps of the SACK-enhanced F-RTO algorithm 💜

  1. When the RTO expires, retransmit the first unacknowledged segment and set SpuriousRecovery to FALSE. Set the variable "recover" to the highest segment transmitted so far 🎀 Then, following the recommendation in the SACK specification ([MMFR96]), reset the SACK scoreboard ✨
  2. Wait until the acknowledgment for the data retransmitted because of the timeout shows up at the sender. If duplicate ACKs arrive before the cumulative acknowledgment for the retransmitted data, adjust the scoreboard using the incoming SACK info. Stay in step 2 and wait for the next new acknowledgment 🦋 If the RTO expires again, go back to step 1 🍓

a) If a cumulative ACK acknowledges a sequence number equal to "recover", revert to conventional RTO recovery and set the congestion window to no more than 2 * MSS, just like a regular TCP would do 👑 Do not enter step 3 of this algorithm 🙈

b) Else, if a cumulative ACK acknowledges a sequence number (smaller than "recover", but larger than SND.UNA), transmit up to two new (previously unsent) segments and proceed to step 3 💖 If the TCP sender can't send any previously unsent data, either because of the receiver window limit or because it has no new data to send, the recommended action is to refrain from entering step 3 of this algorithm 🌈 Instead, keep doing slow start retransmissions following the conventional RTO recovery algorithm 🫶

It's also possible to use some of the alternatives for handling window-limited cases from Appendix C ✨ In that case, the TCP sender should follow the recommendations about acknowledgments of retransmitted segments given in Appendix B 💅

  1. The next acknowledgment arrives at the sender. Either a duplicate ACK or a new cumulative ACK (advancing the window) applies in this step 🔥

a) If the ACK acknowledges a sequence number above "recover", either in SACK blocks or as a cumulative ACK, set the congestion window to no more than 3 * MSS and proceed with conventional RTO recovery, retransmitting unacknowledged segments 🎀 Take this branch also when the acknowledgment is a duplicate ACK and it doesn't acknowledge any new, previously unacknowledged data below "recover" in the SACK blocks 💜 Leave SpuriousRecovery set to FALSE 🙈

b) If the ACK does not acknowledge sequence numbers above "recover" AND it acknowledges data that wasn't acknowledged earlier (either with a cumulative ACK or using SACK blocks), declare the timeout spurious and set SpuriousRecovery to SPUR_TO 🦋 The 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 blocks, those segments get retransmitted similarly to the conventional SACK recovery algorithm ([BAFW03]) 🌸 If the algorithm exits with SpuriousRecovery set to SPUR_TO, "recover" is set to SND.UNA, which allows fast recovery on incoming duplicate acknowledgments 💖

4. Taking Actions after Detecting Spurious RTO 🎀

okay so, a conventional TCP sender assumes outstanding segments are lost after an RTO and starts retransmitting the unacknowledged segments 😭 When the timeout turns out to be spurious, the TCP sender SHOULD NOT keep retransmitting based on that timeout 💅 For example, if the sender was in the congestion avoidance phase sending new, previously unsent segments, it SHOULD continue sending previously unsent segments after detecting a spurious RTO 🫶 This document doesn't describe the response to spurious timeouts, but a response algorithm is described in RFC 4015 ([LG04]) ✨

There are also different response variants to spurious retransmission timeouts discussed in various research papers ([SKR03, GL03, Sar03]) and IETF documents ([SL03]) 🦋 The alternatives mainly differ in whether the spurious timeout should be treated as a congestion signal (which reduces the congestion window or slow start threshold at the sender), or whether the congestion control state should be fully reverted to what it was before the RTO 🔥

5. SCTP Considerations 🧚

SCTP has similar retransmission algorithms and congestion control to TCP 💜 The SCTP T3-rtx timer for one destination address is maintained the same way as the TCP retransmission timer, and after a T3-rtx expires, an SCTP sender retransmits unacknowledged data chunks in slow start, just like TCP 😭 So SCTP is vulnerable to the negative effects of spurious retransmission timeouts, similar to TCP 💀 Because the RTO recovery algorithms are similar, F-RTO logic can be applied to SCTP too 🌈 Since SCTP uses selective acknowledgments, the SACK-based variant is RECOMMENDED, though the basic version can also be applied to SCTP 🎀 SCTP does have features that TCP doesn't, and those need discussing when applying F-RTO 🙈

SCTP associations can be multi-homed 🌸 The current retransmission policy says retransmissions should go to alternative addresses 🫶 If the retransmission was caused by a spurious timeout from a delay spike, the acknowledgment for the retransmission might arrive back at the sender before the acknowledgments for the original transmissions do 😭 If that happens, a possible loss of the original transmission of the retransmitted data chunk might go undetected when F-RTO is applied 💅 Because the timeout was caused by a delay spike and was spurious in that respect, the right move is to keep sending new data 🦋 But if the original transmission was actually lost, fully reverting the congestion control parameters is too aggressive 🔥 So taking conservative congestion control actions is RECOMMENDED when the SCTP association is multi-homed and retransmissions go to alternative addresses 💖 The information in duplicate TSNs can then be used to revert congestion control, if desired ([BA04]) 🧚

Note that the forward transmissions made in F-RTO algorithm step (2b) SHOULD be destined to the primary address, since they are not retransmissions 🎀

When making a retransmission, an SCTP sender can bundle a number of unacknowledged data chunks and include them in the same packet 🌈 This needs to be considered when implementing F-RTO for SCTP 👑 The basic principle still holds: to declare the timeout spurious, the sender MUST get an acknowledgment for a data chunk that was not retransmitted after the retransmission timeout 💜 In other words, acknowledgments for data chunks bundled in the RTO retransmission MUST NOT be used to declare the timeout spurious 🙈

6. Security Considerations 💀

The main security threat for F-RTO is that a receiver could trick the sender into setting too large a congestion window after an RTO 😱 There are two ways a malicious receiver could cause a wrong output from the F-RTO algorithm 🔥 First, the receiver can acknowledge data it hasn't received 😭 Second, it can delay acknowledging a segment it has received earlier, then acknowledge it after the TCP sender has been fooled into entering algorithm step 3 💀

If the receiver acknowledges a segment it hasn't really received, the sender can be led to declare a spurious timeout in F-RTO algorithm step 3 🦋 But because the sender now has an incorrect state, it can't retransmit the segment that never reached the receiver 🫶 So this attack is unlikely to be useful for a receiver trying to gain a larger congestion window maliciously 🙈

A common case for a retransmission timeout is that a fast retransmission of a segment gets lost 🌸 If all other segments were 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 acknowledges only 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 isn't 😱 So it's suggested that, when an RTO expires during fast recovery, 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 more than one segment is missing at the time of a retransmission timeout, the receiver gains nothing from tricking the sender into declaring a spurious timeout 🧚 The sender would have to go through another recovery period to retransmit the missing segments, usually after an RTO has elapsed 🌈

7. Acknowledgements 🫶

We're 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 for the discussion and feedback they contributed to this text 💖✨

8. References 📚

8.1. Normative References 📚

  • [APS99] Allman, M., Paxson, V., and W. Stevens, "TCP Congestion Control", RFC 2581, April 1999.
  • [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 Acknowledgement 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.
  • [Ste00] Stewart, R., Xie, Q., Morneault, K., Sharp, C., Schwarzbauer, H., Taylor, T., Rytina, I., Kalla, M., Zhang, L., and V. Paxson, "Stream Control Transmission Protocol", RFC 2960, October 2000.

8.2. 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.
  • [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] A. Gurtov and R. Ludwig. Evaluating the Eifel Algorithm for TCP in a GPRS Network. In Proc. of European Wireless, Florence, Italy, February 2002.
  • [GL03] A. Gurtov and R. Ludwig, Responding to Spurious Timeouts in TCP. In Proceedings of IEEE INFOCOM 03, San Francisco, CA, USA, March 2003.
  • [Jac88] V. Jacobson. Congestion Avoidance and Control. In Proceedings of ACM SIGCOMM 88.
  • [LG04] Ludwig, R. and A. Gurtov, "The Eifel Response Algorithm for TCP", RFC 4015, February 2005.
  • [LK00] R. Ludwig 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.
  • [SKR03] P. Sarolahti, M. Kojo, and K. Raatikainen. F-RTO: An Enhanced Recovery Algorithm for TCP Retransmission Timeouts. ACM SIGCOMM Computer Communication Review, 33(2), April 2003.
  • [Sar03] P. Sarolahti. Congestion Control on Spurious TCP Retransmission Timeouts. In Proceedings of IEEE Globecom 2003, San Francisco, CA, USA. December 2003.
  • [SL03] Y. Swami and K. Le, "DCLOR: De-correlated Loss Recovery using SACK Option for Spurious Timeouts", work in progress, September 2003.

Appendix A: Scenarios 🧚

This section is the fun part, bestie! 🎀 It walks through different situations where RTOs (retransmission timeouts) happen and shows how the basic F-RTO algorithm handles each one. The scenarios that are actually interesting are: a sudden delay that sets off a retransmission timeout, losing a retransmitted packet during fast recovery, a link outage that knocks out several packets at once, and packet reordering. If you want a deeper performance evaluation of F-RTO on a real implementation, check out [SKR03]. 💖

A.1. Sudden Delay ⏳

Okay so the whole reason F-RTO exists is to make TCP perform better when a delay spike causes a spurious retransmission timeout. 😭 The example below shows the segments and acknowledgments the TCP end hosts send when a spurious timeout happens but nothing is actually lost. Quick heads up: delayed acknowledgments are left out to keep things simple. The example also applies the Eifel Response Algorithm [LG04] once a spurious timeout has been detected. 🫶

         ...
          (cwnd = 6, ssthresh < 6, FlightSize = 6)
         1.          <---------------------------- ACK 5
         2.  SEND 10 ---------------------------->
          (cwnd = 6, ssthresh < 6, FlightSize = 6)
         3.          <---------------------------- ACK 6
         4.  SEND 11 ---------------------------->
          (cwnd = 6, ssthresh < 6, FlightSize = 6)
         5.                       |
                               [delay]
                                  |
             [RTO]
             [F-RTO step (1)]
         6.  SEND 6  ---------------------------->
          (cwnd = 6, ssthresh = 3, FlightSize = 6)
                     <earlier xmitted SEG 6>  --->
         7.          <---------------------------- ACK 7
             [F-RTO step (2b)]
         8.  SEND 12 ---------------------------->
         9.  SEND 13 ---------------------------->
          (cwnd = 7, ssthresh = 3, FlightSize = 7)
                     <earlier xmitted SEG 7>  --->
         10.         <---------------------------- ACK 8
             [F-RTO step (3b)]
             [SpuriousRecovery <- SPUR_TO]
           (cwnd = 7, ssthresh = 6, FlightSize = 6)

         11. SEND 14 ---------------------------->
           (cwnd = 7, ssthresh = 6, FlightSize = 7)
         12.         <---------------------------- ACK 9
         13. SEND 15 ---------------------------->
           (cwnd = 7, ssthresh = 6, FlightSize = 7)
         14.         <---------------------------- ACK 10
         15. SEND 16 ---------------------------->
           (cwnd = 7, ssthresh = 6, FlightSize = 7)
         ...

So here's the tea ☕. When a sudden delay (long enough to trigger a timeout) hits at step 5, the TCP sender retransmits the first unacknowledged segment (step 6). The next ACK covers that RTO retransmission, because the originally sent segment 6 finally arrived at the receiver, and the sender keeps going by sending two new data segments (steps 8 and 9). 🌸

Now, here's the slightly sneaky bit 👀. During F-RTO steps (1) and (2b), the congestion window and FlightSize are not reset yet, because in a spurious timeout the segments sent before the timeout are still floating around in the network. The sender should still be equally aggressive toward conventional TCP though, so it's not just chilling. 💅

Then the second acknowledgment that arrives after the RTO retransmission acknowledges data that was not retransmitted because of the timeout (step 10). That's the giveaway! The sender declares the timeout spurious and starts sending new data on the next acknowledgments. And the congestion control state gets reversed, as the Eifel Response Algorithm requires. Iconic behaviour, honestly. 🦋

A.2. Loss of a Retransmission 💀

Okay, this one is a bit of a nightmare scenario 😭. If a retransmitted segment gets lost, the only way to resend it is to wait for the timeout to fire the retransmission. Once the segment finally gets through, the receiver usually acknowledges several segments in one go, because other segments in the same window were delivered while the retransmission was still on its way. The example below shows a case where the retransmission of segment 6 is lost, along with a later segment (segment 9) in the same window. Heads up: the limited transmit [ABF01] and SACK TCP [MMFR96] enhancements are not in use in this example. 🙈

         ...
          (cwnd = 6, ssthresh < 6, FlightSize = 6)
             <segment 6 lost>
             <segment 9 lost>
         1.          <---------------------------- ACK 5
         2.  SEND 10 ---------------------------->
          (cwnd = 6, ssthresh < 6, FlightSize = 6)
         3.          <---------------------------- ACK 6
         4.  SEND 11 ---------------------------->
          (cwnd = 6, ssthresh < 6, FlightSize = 6)

         5.          <---------------------------- ACK 6
         6.          <---------------------------- ACK 6
         7.          <---------------------------- ACK 6
         8.  SEND 6  --------------X
          (cwnd = 6, ssthresh = 3, FlightSize = 6)
             <segment 6 lost>
         9.          <---------------------------- ACK 6
         10. SEND 12 ---------------------------->
          (cwnd = 7, ssthresh = 3, FlightSize = 7)
         11.         <---------------------------- ACK 6
         12. SEND 13 ---------------------------->
          (cwnd = 8, ssthresh = 3, FlightSize = 8)
             [RTO]
         13. SEND 6  ---------------------------->
          (cwnd = 8, ssthresh = 2, FlightSize = 8)
         14.         <---------------------------- ACK 9
             [F-RTO step (2b)]
         15. SEND 14 ---------------------------->
         16. SEND 15 ---------------------------->
          (cwnd = 7, ssthresh = 2, FlightSize = 7)
         17.         <---------------------------- ACK 9
             [F-RTO step (3a)]
             [SpuriousRecovery <- FALSE]
          (cwnd = 3, ssthresh = 2, FlightSize = 7)
         18. SEND 9  ---------------------------->
         19. SEND 10 ---------------------------->
         20. SEND 11 ---------------------------->
         ...

So in this example, segment 6 gets lost, and the sender retransmits it after three duplicate ACKs in step 8. Plot twist: that retransmission is lost too 😩, so the sender has to sit and wait for the RTO to expire before trying again. Because the first ACK after the RTO retransmission acknowledges that RTO retransmission (step 14), the sender can transmit two new segments. 🎀

The second ACK in step 17 doesn't acknowledge any previously unacknowledged data, and that's the key clue. So the F-RTO sender enters slow start and sets cwnd to 3 * MSS. Why three segments? Because two round-trips have elapsed since the retransmission timeout. ⏱️ Finally, the receiver acknowledges all the segments that were sent before recovery started, and the sender can carry on transmitting new data in congestion avoidance. Main character energy, honestly 👑✨

okay so this one shows F-RTO when 4 consecutive packets get lost, which makes the sender fall back to RTO recovery 😭 Limited Transmit and SACK aren't used in this example, so it's just the basics.

         ...
          (cwnd = 6, ssthresh < 6, FlightSize = 6)
             <segments 6-9 lost>
         1.          <---------------------------- ACK 5
         2.  SEND 10 ---------------------------->
          (cwnd = 6, ssthresh < 6, FlightSize = 6)
         3.          <---------------------------- ACK 6
         4.  SEND 11 ---------------------------->
          (cwnd = 6, ssthresh < 6, FlightSize = 6)
         5.          <---------------------------- ACK 6
                                  |
                                  |
             [RTO]
         6.  SEND 6  ---------------------------->
          (cwnd = 6, ssthresh = 3, FlightSize = 6)
         7.          <---------------------------- ACK 7
             [F-RTO step (2b)]
         8.  SEND 12 ---------------------------->
         9.  SEND 13 ---------------------------->
          (cwnd = 7, ssthresh = 3, FlightSize = 7)
         10.         <---------------------------- ACK 7
             [F-RTO step (3a)]
             [SpuriousRecovery <- FALSE]
          (cwnd = 3, ssthresh = 3, FlightSize = 7)
         11. SEND 7  ---------------------------->
         12. SEND 8  ---------------------------->
         13. SEND 9  ---------------------------->

Again, the F-RTO sender fires off two new segments (steps 8 and 9) once the RTO retransmission gets acked 💅 Then, when the ACK in step 10 doesn't acknowledge any data that wasn't retransmitted after the retransmission timeout, the sender just goes with conventional recovery and slow start retransmissions 🫶

A.4. Packet Reordering 🌀

F-RTO only changes how the sender behaves after an RTO, and it's meant to avoid unnecessary retransmissions after a spurious timeout. So we're only looking at reordering for the cases where it happens right after the RTO 👀 When the receiver gets an out-of-order segment, it generates a duplicate ACK. If the sender runs the basic F-RTO algorithm, that duplicate ACK may stop it from detecting a spurious timeout 😬

BUT if the sender applies the SACK-enhanced F-RTO, it's possible to detect a spurious timeout even when reordering happens 🙌 Here's how SACK-enhanced F-RTO behaves when segment 8 arrives before segments 6 and 7, and everything starting from segment 6 is delayed in the network. In this example, the sender reduces the congestion window and slow start threshold in response to the spurious timeout.

         ...
          (cwnd = 6, ssthresh < 6, FlightSize = 6)
         1.          <---------------------------- ACK 5
         2.  SEND 10 ---------------------------->
          (cwnd = 6, ssthresh < 6, FlightSize = 6)
         3.          <---------------------------- ACK 6
         4.  SEND 11 ---------------------------->
         5.                       |
                               [delay]
                                  |
             [RTO]
         6.  SEND 6  ---------------------------->
          (cwnd = 6, ssthresh = 3, FlightSize = 6)
                     <earlier xmitted SEG 8>  --->
         7.          <---------------------------- ACK 6
                                                   [SACK 8]
             [SACK F-RTO stays in step 2]
         8.          <earlier xmitted SEG 6>  --->
         9.          <---------------------------- ACK 7
                                                   [SACK 8]
             [SACK F-RTO step (2b)]
         10. SEND 12 ---------------------------->
         11. SEND 13 ---------------------------->
           (cwnd = 7, ssthresh = 3, FlightSize = 7)
         12.         <earlier xmitted SEG 7>  --->
         13.         <---------------------------- ACK 9
             [SACK F-RTO step (3b)]
             [SpuriousRecovery <- SPUR_TO]
           (cwnd = 7, ssthresh = 6, FlightSize = 6)
         14. SEND 14 ---------------------------->
           (cwnd = 7, ssthresh = 6, FlightSize = 7)
         15.         <---------------------------- ACK 10
         16. SEND 15 ---------------------------->
         ...

So after the RTO expires and the sender retransmits segment 6 (step 6), the receiver gets segment 8 and sends a duplicate ACK with SACK for segment 8. The sender doesn't send anything in response and just stays in F-RTO step 2 🧘‍♀️ Then the next acknowledgment moves the cumulative ACK point forward (step 9), so the sender can transmit two new segments under SACK-enhanced F-RTO. The following segment acknowledges new data between 7 and 11 that wasn't acknowledged earlier (segment 7), which means the F-RTO sender declares the timeout spurious 🎉

Appendix B: SACK-enhanced F-RTO and Fast Recovery 🦋

We believe a slightly tweaked, SACK-enhanced F-RTO algorithm can detect spurious timeouts even when the RTO expires while an earlier loss recovery is still going. There are some issues to think about if F-RTO gets applied in this case though 🤔

In step 3, the original SACK-based F-RTO algorithm requires that an ACK acknowledges previously unacknowledged non-retransmitted data between SND.UNA and send_high. If the RTO expires during an earlier (SACK-based) loss recovery, the F-RTO sender has to use only acknowledgments for non-retransmitted segments that were transmitted before the SACK-based loss recovery started. This means that, to declare the timeout spurious, the TCP sender must receive an acknowledgment for a non-retransmitted segment between SND.UNA and RecoveryPoint in algorithm step 3. RecoveryPoint is defined in the conservative SACK-recovery algorithm [BAFW03], and it's set to indicate the highest segment transmitted so far when SACK-based loss recovery begins. In other words, if the TCP sender receives an acknowledgment for a segment that was transmitted more than one RTO ago, it can declare the timeout spurious. Defining an efficient algorithm for checking these conditions is still a future work item 📝

When a spurious timeout is detected according to the rules above, the response algorithm may need to treat this case separately. For example, it might need to think about which segments to retransmit after the RTO expires, and whether it's safe to revert the congestion control parameters. This is considered a topic for future research 🔮

Appendix C: 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 downside is that the sender may keep doing unnecessary retransmissions because of a possible spurious timeout 😩 This section briefly talks through options that could help performance when sending previously unsent data isn't 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 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. Thus, this option is not encouraged, except for hosts that are known to operate in an environment that is prone to spurious timeouts. On the other hand, with this method it is possible to limit unnecessary retransmissions due to spurious timeout to one retransmission.
  • Send a zero-sized segment below SND.UNA, similar to 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 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.

Authors' Addresses 🖋️

Pasi Sarolahti
Nokia Research Center
P.O. Box 407
FIN-00045 NOKIA GROUP
Finland

Phone: +358 50 4876607
EMail: pasi.sarolahti@nokia.com
http://www.cs.helsinki.fi/u/sarolaht/


Markku Kojo
University of Helsinki
Department of Computer Science
P.O. Box 68
FIN-00014 UNIVERSITY OF HELSINKI
Finland

Phone: +358 9 191 51305
EMail: kojo@cs.helsinki.fi

Copyright (C) The Internet Society (2005).

This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property 🔏

The IETF takes no position on the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document, or on the extent to which any license under such rights might or might not be available. It also doesn't claim to have made any independent effort to identify any such rights. Info on the procedures for rights in RFC documents can be found in BCP 78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat, any assurances of licenses to be made available, or the results of any attempt to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please send that information to the IETF at ietf-ipr@ietf.org.

Acknowledgement 🌸

Funding for the RFC Editor function is currently provided by the Internet Society.

📦 where this page comes from