RFC 3042

Enhancing TCP's Loss Recovery Using Limited Transmit

📅 published January 2001, from ietf

RFC 3042: Enhancing TCP's Loss Recovery Using Limited Transmit 🎀

Okay bestie, here's the title block tea ☕. This is RFC 3042 from the Network Working Group, dated January 2001. The authors are M. Allman (NASA GRC/BBN), H. Balakrishnan (MIT), and S. Floyd (ACIRI). It's on the Standards Track 🔥, and it doesn't list anything it obsoletes or updates, so it's totally standing on its own ✨.

Status of This Memo 📝

This document specifies an Internet standards track protocol for the Internet community, and it's basically asking everyone to discuss it and suggest improvements 🫶. For the official standardization state and status of this protocol, check the current edition of the "Internet Official Protocol Standards" (STD 1). Distribution of this memo is unlimited 💅.

Copyright (C) The Internet Society (2001). All Rights Reserved.

Abstract 🦋

Okay so this doc proposes a brand-new TCP (Transmission Control Protocol) mechanism 💖. Its whole job is to help recover lost segments more effectively when a connection's congestion window is small, or when a bunch of segments get lost in one transmission window 😭. The "Limited Transmit" algorithm says to send a new data segment in response to each of the first two duplicate acknowledgments that show up at the sender ✨. Why does that matter? Sending those segments makes it more likely that TCP can recover from a single lost segment with the fast retransmit algorithm, instead of waiting around for a costly retransmission timeout 🙈. And it's giving flexibility: Limited Transmit can be used together with the TCP selective acknowledgment (SACK) mechanism, or without it 🌈.

1. Introduction 🧚

A bunch of researchers have noticed that TCP's loss recovery strategies don't work super well when the congestion window at a TCP sender is small 💀. This can happen for a few reasons. Maybe there's only a limited amount of data to send, or the receiver-advertised window is the limit, or the constraints from end-to-end congestion control over a connection with a small bandwidth-delay product are doing it [Riz96,Mor97,BPS+98,Bal98,LK98]. When a TCP detects a missing segment, it enters a loss recovery phase using one of two methods 👑.

Method one: if an acknowledgment (ACK) for a given segment isn't received within a certain amount of time, a retransmission timeout occurs and the segment gets resent [RFC793,PA00]. Method two: the "Fast Retransmit" algorithm resends a segment when three duplicate ACKs arrive at the sender [Jac88,RFC2581]. Here's the thing though 🤔. Duplicate ACKs from the receiver can also be triggered by packet reordering on the Internet, so the TCP sender waits for three duplicate ACKs to tell segment loss apart from reordering 🍓. Once TCP is in a loss recovery phase, it can use a bunch of techniques to retransmit lost segments. These include slow start-based recovery or Fast Recovery [RFC2581], NewReno [RFC2582], and loss recovery based on selective acknowledgments (SACKs) [RFC2018,FF96] 🌸.

TCP's retransmission timeout (RTO) is based on measured round-trip times (RTT) between the sender and receiver, as specified in [PA00] ⏱️. To stop spurious retransmissions of segments that are only delayed and not actually lost, the minimum RTO is conservatively set to 1 second 🫠. So it's lowkey important for TCP senders to detect and recover from as many losses as possible, without sitting through a lengthy timeout when the connection is idle 😤. But if not enough duplicate ACKs arrive from the receiver, the Fast Retransmit algorithm never gets triggered. This happens when the congestion window is small, or when a large number of segments in a window are lost 💔. Let's say the congestion window (cwnd) is three segments. If the network drops one segment, at most two duplicate ACKs can arrive at the sender. Since three duplicate ACKs are required to trigger Fast Retransmit, a timeout is needed to resend the dropped packet 😩.

Now the receipts 🧾. [BPS+97] found that roughly 56% of retransmissions sent by a busy web server were sent after the RTO expired, while only 44% were handled by Fast Retransmit 😭. Only 4% of those RTO-based retransmissions could have been avoided with SACK, and SACK still has to keep telling reordering apart from genuine loss 🙄. In contrast, using the technique outlined in this document and in [Bal98], about 25% of the RTO-based retransmissions in that dataset would likely have been avoided 🎉.

The next section outlines small changes to TCP senders that reduce the reliance on the retransmission timer, which improves TCP performance when Fast Retransmit isn't triggered 🦋. And the vibe is that these changes don't adversely affect TCP's performance or interact badly with other connections in other circumstances either ✨🫶.

1.1. Terminology

okay so before we get into the good stuff, you need the vocab 💅 in this doc, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", AND "OPTIONAL" are read the way [1] (RFC 2119) describes, and they're how the doc tells you how strict each protocol rule is 📚🫶

2. The Limited Transmit Algorithm ✨

okay bestie, this is the main event 🔥 when a TCP sender has new data sitting in the queue, it SHOULD use Limited Transmit. The move is: send new data when the first two consecutive duplicate ACKs show up, but ONLY if both of these are true:

  • The receiver's advertised window has room for the segment 🪟
  • The outstanding data would still be less than or equal to the congestion window plus 2 segments. Basically the sender can only poke two segments past cwnd 🦋

The congestion window (cwnd) MUST NOT be changed when those new segments go out 🚫 And if the new segments and their ACKs aren't dropped, the sender can figure out loss using the usual Fast Retransmit threshold of three duplicate ACKs [RFC2581]. This is way more robust to reordered packets than retransmitting an old packet on the first or second duplicate ACK, which is honestly iconic 👑

Note: if the connection is using selective acknowledgments [RFC2018], the data sender MUST NOT send new segments in response to duplicate ACKs that carry no new SACK information 🙅‍♀️ The reason is that a misbehaving receiver can generate those ACKs just to trigger sneaky data transmissions. Go read [SCWA99] if you want the tea on attacks by misbehaving receivers 🍵

Limited Transmit follows the "conservation of packets" congestion control principle [Jac88] 🧚 Each of the first two duplicate ACKs means a segment has left the network. The sender also hasn't decided a segment was dropped yet, so it has no reason to think its congestion control state is wrong. So sending segments doesn't go against the spirit of TCP's congestion control, and that's a real vibe ✨

[BPS99] shows that packet reordering is not a rare network event 👀 [RFC2581] doesn't allow sending data on the first two duplicate ACKs, so when an ACK for new data finally arrives after reordering, you get a burst of segments. With Limited Transmit, the data packets get clocked out by the incoming ACKs instead, so the transmission isn't nearly as bursty 🌊

Note: Limited Transmit is implemented in the ns simulator [NS] 🎀 Researchers who want to dig into it can turn on "singledup_" for the given TCP connection.

okay so ECN is giving main character energy 🌸 Deployment of Explicit Congestion Notification (ECN) [Flo94,RFC2481] may benefit connections with small congestion window sizes [SA00]. ECN signals congestion to the end-host without dropping segments 💌 Some segment drops may still happen, but ECN may let TCP do better with small congestion windows, because the sender can skip a lot of the Fast Retransmits and Retransmit Timeouts it would otherwise need to detect dropped segments [SA00] 🙌

When ECN-enabled TCP traffic competes with non-ECN-enabled TCP traffic, the ECN-enabled traffic can receive up to 30% higher goodput 📈 For bulk transfers, the biggest relative benefit from ECN shows up when, on average, each flow has 3-4 outstanding packets during each round-trip time [ZQ00] 🍓 This should be a good estimate for the performance impact of a flow using Limited Transmit, since both ECN and Limited Transmit cut down on how much everyone leans on the retransmission timer to signal congestion 🧠

The Rate-Halving congestion control algorithm [MSML99] uses a form of limited transmit 💫 It sends a data segment on every second duplicate ACK that arrives at the sender. It also splits the decision of what to send from the decision of when to send it. Still, just like Limited Transmit, it will always send a new data segment on the second duplicate ACK that arrives at the sender 🫧

4. Security Considerations 🔐

Okay, real talk bestie, this section is serious even though I'm being extra 💀 The extra security implications of the changes in this document, compared to TCP's current vulnerabilities, are minimal ✅ The actual risk is about subverting end-to-end congestion control with "false" duplicate ACKs. A "false" duplicate ACK is a duplicate ACK that doesn't actually acknowledge new data the TCP receiver got. False duplicate ACKs could come from duplicate ACKs that get duplicated somewhere in the network, or from misbehaving TCP receivers that send false duplicate ACKs to subvert end-to-end congestion control [SCWA99,RFC2581] 😤

When the TCP data receiver has agreed to use the SACK option, the TCP data sender gets pretty strong protection against false duplicate ACKs 🛡️ With SACK, a duplicate ACK that acknowledges new data reports the sequence numbers of that new data. So the sender can check that an arriving duplicate ACK acknowledges data it actually sent, and that no earlier acknowledgment has covered it, before sending new data because of that ACK 🔍 For extra protection, the TCP sender could keep a record of packet boundaries for transmitted data packets, and recognize at most one valid acknowledgment for each packet (for example, the first acknowledgment that acknowledges receipt of all the sequence numbers in that packet) 🧾

Picture some limited protection against false duplicate ACKs for a non-SACK TCP connection 🖼️ The TCP sender would keep a count of the packets it transmitted and recognize at most one acknowledgment per packet to trigger sending new data. But tracking packets transmitted and acknowledged this way would need extra state and complexity at the TCP sender, and it doesn't seem necessary 🤷‍♀️

The most important protection against false duplicate ACKs comes from how limited duplicate ACKs are at subverting end-to-end congestion control 💅 There are two cases to think about: when the TCP sender gets less than a threshold number of duplicate ACKs, and when it gets at least a threshold number. In the second case, a TCP with Limited Transmit behaves essentially the same as a TCP without it: the congestion window gets halved and a loss recovery period starts 📉

When the TCP sender gets less than a threshold number of duplicate ACKs, a misbehaving receiver could send two duplicate ACKs after each regular ACK 😈 You might imagine the TCP sender sending at three times its allowed rate. But with Limited Transmit as outlined in section 2, the sender is only allowed to exceed the congestion window by less than the duplicate ACK threshold (three segments). So it wouldn't send a new packet for each duplicate ACK it receives 🙅‍♀️✨

Acknowledgments 🫶

okay shoutout to Bill Fenner, Jamshid Mahdavi and the Transport Area Working Group 📣 They gave valuable feedback on an early version of this document, and that's so sweet of them 🥹💖

References 📚

bestie, here's every reference, exactly as the doc lists them 🦋

   [Bal98]   Hari Balakrishnan.  Challenges to Reliable Data Transport
             over Heterogeneous Wireless Networks.  Ph.D. Thesis,
             University of California at Berkeley, August 1998.

   [BPS+97]  Hari Balakrishnan, Venkata Padmanabhan, Srinivasan Seshan,
             Mark Stemm, and Randy Katz.  TCP Behavior of a Busy Web
             Server:  Analysis and Improvements.  Technical Report
             UCB/CSD-97-966, August 1997.  Available from
             http://nms.lcs.mit.edu/~hari/papers/csd-97-966.ps.  (Also
             in Proc. IEEE INFOCOM Conf., San Francisco, CA, March
             1998.)

   [BPS99]   Jon Bennett, Craig Partridge, Nicholas Shectman.  Packet
             Reordering is Not Pathological Network Behavior.  IEEE/ACM
             Transactions on Networking, December 1999.

   [FF96]    Kevin Fall, Sally Floyd.  Simulation-based Comparisons of
             Tahoe, Reno, and SACK TCP.  ACM Computer Communication
             Review, July 1996.

   [Flo94]   Sally Floyd.  TCP and Explicit Congestion Notification.
             ACM Computer Communication Review, October 1994.

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

   [LK98]    Dong Lin, H.T. Kung.  TCP Fast Recovery Strategies:
             Analysis and Improvements.  Proceedings of InfoCom, March
             1998.

   [MSML99]  Matt Mathis, Jeff Semke, Jamshid Mahdavi, Kevin Lahey.  The
             Rate Halving Algorithm, 1999. URL:
             http://www.psc.edu/networking/rate_halving.html.

   [Mor97]   Robert Morris.  TCP Behavior with Many Flows.  Proceedings
             of the Fifth IEEE International Conference on Network
             Protocols.  October 1997.

   [NS]      Ns network simulator.  URL: http://www.isi.edu/nsnam/.

   [PA00]    Paxson, V. and M. Allman, "Computing TCP's Retransmission
             Timer", RFC 2988, November 2000.

   [Riz96]   Luigi Rizzo.  Issues in the Implementation of Selective
             Acknowledgments for TCP.  January, 1996.  URL:
             http://www.iet.unipi.it/~luigi/selack.ps

   [SA00]    Hadi Salim, J. and U. Ahmed, "Performance Evaluation of
             Explicit Congestion Notification (ECN) in IP Networks", RFC
             2884, July 2000.

   [SCWA99]  Stefan Savage, Neal Cardwell, David Wetherall, Tom
             Anderson.  TCP Congestion Control with a Misbehaving
             Receiver.  ACM Computer Communications Review, October
             1999.

   [RFC793]  Postel, J., "Transmission Control Protocol", STD 7, RFC
             793, September 1981.

   [RFC2018] Mathis, M., Mahdavi, J., Floyd, S. and A. Romanow, "TCP
             Selective Acknowledgement Options", RFC 2018, October 1996.

   [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
             Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC2481] Ramakrishnan, K. and S. Floyd, "A Proposal to Add Explicit
             Congestion Notification (ECN) to IP", RFC 2481, January
             1999.

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

   [RFC2582] Floyd, S. and T. Henderson, "The NewReno Modification to
             TCP's Fast Recovery Algorithm", RFC 2582, April 1999.

   [ZQ00]    Yin Zhang and Lili Qiu, Understanding the End-to-End
             Performance Impact of RED in a Heterogeneous Environment,
             Cornell CS Technical Report 2000-1802, July 2000.  URL
             http://www.cs.cornell.edu/yzhang/papers.htm.

Authors' Addresses 🎀

these are the people who wrote it, and their contact info is right here 💌

   Mark Allman
   NASA Glenn Research Center/BBN Technologies
   Lewis Field
   21000 Brookpark Rd.  MS 54-5
   Cleveland, OH  44135

   Phone: +1-216-433-6586
   Fax:   +1-216-433-8705
   EMail: mallman@grc.nasa.gov
   http://roland.grc.nasa.gov/~mallman


   Hari Balakrishnan
   Laboratory for Computer Science
   545 Technology Square
   Massachusetts Institute of Technology
   Cambridge, MA 02139

   EMail: hari@lcs.mit.edu
   http://nms.lcs.mit.edu/~hari/


   Sally Floyd
   AT&T Center for Internet Research at ICSI (ACIRI)
   1947 Center St, Suite 600
   Berkeley, CA 94704

   Phone: +1-510-666-2989
   EMail: floyd@aciri.org
   http://www.aciri.org/floyd/

okay bestie, this part is the legal stuff, but it still matters so we're keeping every bit 🫶

Copyright (C) The Internet Society (2001). All Rights Reserved.

so here's the deal 💅 anyone can copy and share this document and its translations, and make derivative works that comment on or explain it or help people implement it. they can publish and distribute those too, in whole or in part, no restriction of any kind. the one condition is that the above copyright notice and this paragraph stay on all those copies and derivative works 📜

BUT the document itself can't be modified in any way 🙅‍♀️ that includes removing the copyright notice or the references to the Internet Society or other Internet organizations. the exceptions are when it's needed to develop Internet standards, in which case the copyright procedures in the Internet Standards process must be followed, or when it's translated into a language other than English 🌍

the permissions here are perpetual, which means they will not be revoked by the Internet Society or its successors or assigns 💜

and this is the important disclaimer, so read it carefully 👀

This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS 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. 💀

Acknowledgement 💖

funding for the RFC Editor function is currently provided by the Internet Society 🌸 iconic supporting cast energy 👑

📦 where this page comes from