RFC 3517

RFC 3517: A Conservative Selective Acknowledgment (SACK)-based Loss Recovery Algorithm for TCP ✨

Okay bestie, here's the header situation 📜. This is RFC 3517 from the Network Working Group, dated April 2003, and it's a Standards Track doc 🦋. The authors are E. Blanton (Purdue University), M. Allman (BBN/NASA GRC), K. Fall (Intel Research), and L. Wang (University of Kentucky) 🫶.

Status of this Memo 💅

Okay so this is an Internet standards track protocol spec for the Internet community 🌈. It also asks for discussion and suggestions for improvements, so speak up! For the 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, so share it with everyone 💖.

Copyright Notice 🎀

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

Abstract 🌸

So this doc lays out a conservative loss recovery algorithm for TCP that's built on the selective acknowledgment (SACK) TCP option 🔥. It keeps the spirit of the current congestion control spec (RFC 2581), but it lets TCP senders recover way better when multiple segments get lost from one single flight of data 😭✨.

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] 🫶.

1. Introduction 🦋

Okay so this doc is giving a conservative loss recovery algorithm for TCP that runs on the selective acknowledgment (SACK) TCP option 💅. The TCP SACK [RFC2018] is being steadily deployed on the Internet [All00], but there's evidence that hosts aren't actually using the SACK information when they make retransmission and congestion control decisions [PF01] 💀. The goal here is to outline one straightforward method that TCP implementations can use to pull SACK info and boost performance 🚀.

Here's the vibe check. [RFC2581] lets advanced loss recovery algorithms get used by TCP [RFC793], as long as they follow the spirit of TCP's congestion control algorithms [RFC2581, RFC2914] 👑. [RFC2582] lays out one of those advanced recovery algorithms, called NewReno 🌈. This doc describes a loss recovery algorithm that uses the SACK [RFC2018] TCP option to level up TCP's loss recovery 💜. The algorithm here is heavily based on the algorithm detailed in [FF96], and it's a conservative replacement of the fast recovery algorithm [Jac90, RFC2581] 🍓. It's a straightforward SACK-based loss recovery strategy that follows the guidelines set in [RFC2581], and it can safely be used in TCP implementations ✨.

Implementers can use alternate SACK-based loss recovery methods in TCP as they see fit, as long as those alternates follow the guidelines provided in [RFC2581] 🌸. But heads up: the SACK-based decisions in this document (like what segments get sent at what time) are largely decoupled from the congestion control algorithms. So they can be treated as separate issues if you want 🙈.

2. Definitions 🎀

You're expected to already know the definitions given in [RFC2581] 📖.

You're also assumed to be familiar with selective acknowledgments, as specified in [RFC2018] 🧠.

To explain the SACK-based loss recovery algorithm, we define four variables that a TCP sender stores 🔥:

• HighACK is the sequence number of the highest byte of data that has been cumulatively ACKed at a given point.
• HighData is the highest sequence number transmitted at a given point.
• HighRxt is the highest sequence number that has been retransmitted during the current loss recovery phase.
• Pipe is a sender's estimate of the number of bytes outstanding in the network. It's used during recovery to limit the sender's sending rate 💅. The pipe variable lets TCP use a fundamentally different congestion control than the one specified in [RFC2581]. This is often called the "pipe algorithm" 🌊.

For this spec, a "duplicate acknowledgment" is a segment that arrives with no data and an acknowledgment (ACK) number equal to the current value of HighACK, as described in [RFC2581] 🫶.

We define a variable "DupThresh" that holds the number of duplicate acknowledgments required to trigger a retransmission 💖. Per [RFC2581], this threshold is defined to be 3 duplicate acknowledgments. However, implementers should consult any updates to [RFC2581] to determine the current value for DupThresh (or the method for determining its value) 🙌.

Last but not least, a range of sequence numbers [A,B] is said to "cover" sequence number S if A <= S <= B ✨.

3. Keeping Track of SACK Information 🗂️

For a TCP sender to implement the algorithm in the next section, it must keep a data structure that stores incoming selective acknowledgment info on a per connection basis 💅. This is commonly called the "scoreboard" 🎀. The specifics of the scoreboard data structure are out of scope for this document, as long as the implementation can perform all the functions required by this specification 🦋.

Quick note: this doc talks about keeping account of (marking) individual octets of data transferred across a TCP connection 🌈. A real-world implementation of the scoreboard would probably prefer to manage this data as sequence number ranges 💜. The algorithms here allow that, but they require arbitrary sequence number ranges to be marked as selectively acknowledged 🍓.

4. Processing and Acting Upon SACK Information 🔥

For the algorithm in this document, the scoreboard SHOULD implement the following functions 👑:

Update ()

Given the information provided in an ACK, each octet that is cumulatively ACKed or SACKed should be marked accordingly in the scoreboard data structure. The total number of octets SACKed should be recorded too ✨.

Note: SACK information is advisory, and therefore SACKed data MUST NOT be removed from TCP's retransmission buffer until the data is cumulatively acknowledged [RFC2018] 🚨.

IsLost (SeqNum)

This routine returns whether the given sequence number is considered to be lost 🙈. It returns true when either DupThresh discontiguous SACKed sequences have arrived above 'SeqNum', or (DupThresh * SMSS) bytes with sequence numbers greater than 'SeqNum' have been SACKed. Otherwise, it returns false 💀.

SetPipe ()

This routine traverses the sequence space from HighACK to HighData, and it MUST set the "pipe" variable to an estimate of the number of octets that are currently in transit between the TCP sender and the TCP receiver 🚀. After initializing pipe to zero, the following steps are taken for each octet 'S1' in the sequence space between HighACK and HighData that has not been SACKed 🌸:

(a) If IsLost (S1) returns false:

Pipe is incremented by 1 octet. The effect is that pipe gets incremented for packets that haven't been SACKed and haven't been determined to be lost (aka the segments still assumed to be in the network) 🦋.

(b) If S1 <= HighRxt:

Pipe is incremented by 1 octet. The effect is that pipe gets incremented for the retransmission of the octet 🔁.

Note that octets retransmitted without being considered lost are counted twice by the above mechanism 👀.

NextSeg ()

This routine uses the scoreboard data structure maintained by the Update() function to figure out what to transmit, based on the SACK info that has arrived from the data receiver (and so has been marked in the scoreboard) 💅. NextSeg () MUST return the sequence number range of the next segment to be transmitted, following these rules 🎀:

(1) If there exists a smallest unSACKed sequence number 'S2' that meets all three of the following criteria for determining loss, the sequence range of one segment of up to SMSS octets starting with S2 MUST be returned 🔥.

(1.a) S2 is greater than HighRxt.

(1.b) S2 is less than the highest octet covered by any received SACK.

(1.c) IsLost (S2) returns true.

(2) If no sequence number 'S2' per rule (1) exists, but there's available unsent data and the receiver's advertised window allows it, the sequence range of one segment of up to SMSS octets of previously unsent data starting with sequence number HighData+1 MUST be returned ✨.

(3) If the conditions for rules (1) and (2) fail, but there exists an unSACKed sequence number 'S3' that meets the criteria for detecting loss given in steps (1.a) and (1.b) above (specifically excluding step (1.c)), then one segment of up to SMSS octets starting with S3 MAY be returned 🧚.

Rule (3) is a sort of retransmission "last resort" 🆘. It allows retransmission of sequence numbers even when the sender is less certain a segment has been lost than it is under rule (1). Retransmitting segments via rule (3) helps sustain TCP's ACK clock, and therefore can potentially help avoid retransmission timeouts 💜. However, when the sender sends these segments, it has two copies of the same data considered to be in the network (and also in the Pipe estimate). When an ACK or SACK arrives covering this retransmitted segment, the sender can't be sure exactly how much data left the network (one of the two transmissions of the packet, or both transmissions of the packet). So the sender may underestimate Pipe by considering both segments to have left the network when it's possible that only one of the two has 😬.

We believe that rule (3) will be triggered rarely, and that the implications are likely limited to corner cases relative to the entire recovery algorithm 🌈. So we leave the decision of whether or not to use rule (3) to implementors 🫶.

(4) If the conditions for each of (1), (2), and (3) are not met, then NextSeg () MUST indicate failure, and no segment is returned 🚫.

Note: The SACK-based loss recovery algorithm in this document needs more computational resources than previous TCP loss recovery strategies 🧮. However, we believe the scoreboard data structure can be implemented in a reasonably efficient manner (both in terms of computational complexity and memory usage) in most TCP implementations 🌸.

5. Algorithm Details 🎀

Upon the receipt of any ACK containing SACK information, the scoreboard MUST be updated via the Update () routine 💖.

okay so when the first (DupThresh - 1) duplicate ACKs roll in, you just update the scoreboard like normal 💖 no drama 🎀 ✨ bestie, the first and second duplicate ACKs can also be used to kick off sending previously unsent segments with the Limited Transmit algorithm [RFC3042] 🦋

the second the TCP sender gets the duplicate ACK that hits DupThresh 🔥, the scoreboard MUST be updated with the new SACK info (through Update (), obviously) 💅 if there's been no earlier loss event on the connection, or the cumulative ACK point is already past the last value of RecoveryPoint, then a loss recovery phase SHOULD be started, using the fast retransmit algorithm from [RFC2581] ✨ these steps MUST be taken, periodt:

• (1) RecoveryPoint = HighData 🌸 once the sender gets a cumulative ACK for that data octet, the loss recovery phase is over.
• (2) ssthresh = cwnd = (FlightSize / 2) 🍓 the congestion window (cwnd) and slow start threshold (ssthresh) both get chopped to half of FlightSize, per [RFC2581].
• (3) Retransmit the first data segment that's presumed dropped, the one starting at sequence number HighACK + 1 🦋 to stop the same data from getting resent over and over, set HighRxt to the highest sequence number in the retransmitted segment.
• (4) Run SetPipe () 🧚 the pipe variable is the number of outstanding octets currently "in the pipe." That's data the sender has transmitted, with no cumulative or selective ACK yet, and that hasn't been figured out to be dropped in the network. It's assumed to still be traveling along the path 🌊
• (5) to make the most of any extra cwnd that's floating around, go on to step (C) below 💜

once a TCP is in the loss recovery phase, it MUST follow this procedure for every arriving ACK:

• (A) if an incoming cumulative ACK is for a sequence number greater than RecoveryPoint, that's the signal that loss recovery is done, and the loss recovery phase MUST be terminated 👑 the scoreboard info for sequence numbers above the new HighACK value SHOULD NOT be cleared when leaving the loss recovery phase, so don't wipe it 🫶
• (B) if the ACK does NOT cover RecoveryPoint, the following actions MUST be taken 🌈
  • (B.1) use Update () to record the new SACK info that the incoming ACK carries
  • (B.2) use SetPipe () to recalculate how many octets are still in the network
• (C) if cwnd - pipe >= 1 SMSS, the sender SHOULD transmit one or more segments like this ⭐
  • (C.1) the scoreboard MUST be queried with NextSeg () for the sequence number range of the next segment to send (if there is one), and then that segment gets sent. If NextSeg () comes back with failure (no data to send), just return without sending anything. Basically you're ending steps C.1 through C.5 right there 🙈
  • (C.2) if any of the data octets sent in (C.1) are below HighData, HighRxt MUST be set to the highest sequence number of the retransmitted segment 🔥
  • (C.3) if any of the data octets sent in (C.1) are above HighData, HighData must be updated to reflect that previously unsent data went out ✨
  • (C.4) the estimate of outstanding data in the network must be updated by adding the number of octets sent in (C.1) to pipe 💖
  • (C.5) if cwnd - pipe >= 1 SMSS, go back to (C.1) 🎀

---

5.1 Retransmission Timeouts 🌸

okay this part is spicy 🌶️ receivers are allowed to throw out data they've already SACKed, so they don't run out of memory 🧠 because of that, [RFC2018] suggests that a TCP sender SHOULD clear out the SACK info it collected from the receiver when a retransmission timeout happens, "since the timeout might indicate that the data receiver has reneged." Also, a TCP sender MUST "ignore prior SACK information in determining which data to retransmit." 💀 but a SACK TCP sender SHOULD still use all the SACK info that shows up during the slow start phase of loss recovery after an RTO 🫶

if an RTO happens during loss recovery as described in this document, RecoveryPoint MUST be set to HighData 😭 that new RecoveryPoint MUST be kept, and the loss recovery algorithm from this document MUST be terminated. On top of that, a brand new recovery phase (as described in section 5) MUST NOT be started until HighACK is greater than or equal to the new value of RecoveryPoint 🚫

as described in Sections 4 and 5, Update () SHOULD keep being used properly whenever ACKs come in ✨ that way the slow start recovery period still gets to use all the info the receiver provides, even though the SACK info got wiped because of the RTO 🦋

if there are still segments missing from the receiver's buffer after the retransmitted segment gets processed, the matching ACK will carry SACK info. In that case, a TCP sender SHOULD use that SACK info to decide what data goes in each segment during slow start 🧚 the exact algorithm for picking that data isn't specified in this document (and NextSeg () is NOT the move during slow start after an RTO, so don't use it there 🙈). a pretty straightforward approach to "filling in" the sequence space reported as missing should be a reasonable choice 💅

6 Managing the RTO Timer 💜

the standard TCP RTO estimator is defined in [RFC2988] 🍓 because the SACK algorithm in this document can change how that estimator behaves, implementers may wish to think about how they manage the timer. [RFC2988] says the RTO timer should be re-armed every time an ACK comes in that moves the cumulative ACK point forward. But this algorithm can keep the ACK clock ticking through a pretty big loss event (way longer than the one in [RFC2581]), so on some networks the loss event could last longer than the RTO. When that happens, the RTO timer would fire too early, and a segment that didn't actually need retransmitting would get resent 😭

so we give implementers the latitude to use the standard [RFC2988] style of RTO management, or, optionally, a more careful variant that re-arms the RTO timer on each retransmission sent during recovery MAY be used 🌈 this gives a more conservative timer than [RFC2988] describes, so it might not always be the most attractive option. But in some cases it can stop needless retransmissions, go-back-N transmission, and further reduction of the congestion window 👑

7 Research 🧚

the algorithm in this document gets analyzed in [FF96], which shows it's effective at cutting transfer time compared to standard TCP Reno [RFC2581] when multiple segments get dropped from one window of data (the more drops, the better it does) ⭐ [AHKO97] shows that this algorithm can seriously boost throughput on connections going over satellite channels 🛰️

8 Security Considerations 💀

the algorithm presented in this paper shares its security considerations with [RFC2581] 👀 the big difference is that a SACK-based algorithm is way more robust against attackers forging duplicate ACKs to trick the TCP sender into reducing cwnd. With SACKs, TCP senders get an extra check on whether a particular ACK is legit. It's not fool-proof, but SACK does give you some protection in this area 🛡️💅

Acknowledgments 🫶

the authors want to thank Sally Floyd for encouraging this document and commenting on early drafts 💖 the algorithm described here is loosely based on one outlined by Kevin Fall and Sally Floyd in [FF96], but the authors of this document take the blame for any mistakes in the text above 🙈 Murali Bashyam, Ken Calvert, Tom Henderson, Reiner Ludwig, Jamshid Mahdavi, Matt Mathis, Shawn Ostermann, Vern Paxson and Venkat Venkatsubra gave super valuable feedback on earlier versions of this document 🎀 we also thank Matt Mathis and Jamshid Mahdavi for implementing the scoreboard in ns, which helped guide our thinking about keeping track of SACK state 🔥

the first author would like to thank Ohio University and the Ohio University Internetworking Research Group for supporting most of his work on this project 🌸

Normative References 📚

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

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

[RFC2026] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996.

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

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

Informative References 🌈

[AHKO97] Mark Allman, Chris Hayes, Hans Kruse, Shawn Ostermann. TCP Performance Over Satellite Links. Proceedings of the Fifth International Conference on Telecommunications Systems, Nashville, TN, March, 1997.

[All00] Mark Allman. A Web Server's View of the Transport Layer. ACM Computer Communication Review, 30(5), October 2000.

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

[Jac90] Van Jacobson. Modified TCP Congestion Avoidance Algorithm. Technical Report, LBL, April 1990.

[PF01] Jitendra Padhye, Sally Floyd. Identifying the TCP Behavior of Web Servers, ACM SIGCOMM, August 2001.

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

[RFC2914] Floyd, S., "Congestion Control Principles", BCP 41, RFC 2914, September 2000.

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

[RFC3042] Allman, M., Balakrishnan, H, and S. Floyd, "Enhancing TCP's Loss Recovery Using Limited Transmit", RFC 3042, January 2001.

Intellectual Property Rights Notice 🎀

the IETF doesn't take a position on whether any intellectual property or other rights that might be claimed to apply to the implementation or use of the technology in this document are valid or in scope, or how far any license under those rights might or might not be available. It also doesn't say it has tried to identify any such rights 💅 info about the IETF's procedures for rights in standards-track and standards-related documents can be found in BCP-11. Copies of claimed rights submitted for publication, any assurances of licenses to be made available, or the results of an attempt to get a general license or permission for implementers or users to use such proprietary rights can be obtained from the IETF Secretariat 📬

the IETF invites any interested party to bring to its attention any copyrights, patents, patent applications, or other proprietary rights that may cover technology that may be required to practice this standard 🦋 send that info to the IETF Executive Director 💖

Authors' Addresses 💌

Here's where to find the crew behind this one, bestie 🫶 Each person gets their own contact block, so you can reach out if you ever have a question.

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

   EMail: eblanton@cs.purdue.edu


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

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


   Kevin Fall
   Intel Research
   2150 Shattuck Ave., PH Suite
   Berkeley, CA 94704

   EMail: kfall@intel-research.net


   Lili Wang
   Laboratory for Advanced Networking
   210 Hardymon Building
   University of Kentucky
   Lexington, KY 40506-0495

   EMail: lwang0@uky.edu

---

Full Copyright Statement ⚖️

Okay, the legal bit, but I'll make it quick 💅

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

Anyone can copy and share this document, and translations of it, and make derivative works that comment on or explain it or help implement it. You can publish and distribute those copies and works, in whole or in part, with no restrictions at all, as long as the copyright notice and this paragraph stay on every single copy and derivative work 🎀

But the document itself may not be changed in any way. That means you can't remove the copyright notice or the references to the Internet Society or other Internet organizations. The exceptions are when it's needed for developing Internet standards, where the copyright procedures in the Internet Standards process must be followed, or when it's being translated into a language other than English 🌈

The permissions above are limited, but they're also perpetual. The Internet Society, or its successors or assigns, will not revoke them ✨

This document and the information in it are 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. Thank you for keeping the lights on, Internet Society 🦋