RFC 2018

Okay Bestie, Here's RFC 2018 💖

Okay so this is RFC 2018, "TCP Selective Acknowledgment Options" 🦋. It's a Standards Track doc, which means it's an official spec, not just a vibe. It came out in October 1996 and the authors are M. Mathis, J. Mahdavi (PSC), S. Floyd (LBNL), and A. Romanow (Sun Microsystems). It doesn't list anything it obsoletes or updates, so it's giving independent main character 👑.

---

Status of this Memo 📜

Okay so this is an Internet standards track protocol for the Internet community 🌸. The authors are asking for discussion and suggestions for improvements 💅. If you want the current standardization state and status of this protocol, check out the "Internet Official Protocol Standards" (STD 1) 🔍. Distribution of this memo is unlimited ✨.

---

Abstract 🧠

Okay this part is so important 😭. TCP can have really rough performance when a bunch of packets get lost from the same window of data 💀. With only the info from cumulative acknowledgments, a TCP sender can only find out about one lost packet per round trip time 🙈. A sender could be aggressive and retransmit packets early, but those retransmitted segments might have already arrived just fine 😬.

A Selective Acknowledgment (SACK) mechanism, paired with a selective repeat retransmission policy, can help fix these limits 🔥. The receiving TCP sends SACK packets back to the sender to say what data it got 🎀. The sender can then retransmit only the missing data segments 🫶.

This memo proposes an implementation of SACK and talks about its performance and related issues 🌈.

---

Acknowledgements 🫶

A lot of the text in this document is taken directly from RFC1072 "TCP Extensions for Long-Delay Paths" by Bob Braden and Van Jacobson 💜. The authors want to thank Kevin Fall (LBNL), Christian Huitema (INRIA), Van Jacobson (LBNL), Greg Miller (MITRE), Greg Minshall (Ipsilon), Lixia Zhang (XEROX PARC and UCLA), Dave Borman (BSDI), Allison Mankin (ISI) and others for reviewing it and giving constructive comments 🧚.

---

1. Introduction ✨

Okay so multiple packet losses from one window of data can absolutely wreck TCP throughput 💀. TCP [Postel81] uses a cumulative acknowledgment scheme, where received segments that aren't at the left edge of the receive window don't get acknowledged 🙃. That leaves the sender stuck either waiting a roundtrip time to hear about each lost packet, or retransmitting segments that were already received just fine [Fall95] 😭. With cumulative acknowledgments, multiple dropped segments usually make TCP lose its ACK-based clock, and overall throughput takes the hit 📉.

Selective Acknowledgment (SACK) is a strategy that fixes this behavior when multiple segments get dropped 💖. With selective acknowledgments, the data receiver can tell the sender about every segment that arrived successfully, so the sender only needs to retransmit the segments that were actually lost 🎯.

A bunch of transport protocols have used selective acknowledgment already: NETBLT [Clark87], XTP [Strayer92], RDP [Velten84], NADIR [Huitema81], and VMTP [Cheriton88] 🍓. There's some real evidence backing selective acknowledgments too. Simple experiments with RDP showed that turning off the selective acknowledgment facility greatly increases the number of retransmitted segments over a lossy, high-delay Internet path [Partridge87] 😳. A recent simulation study by Kevin Fall and Sally Floyd [Fall95] shows TCP with SACK beating the non-SACK Tahoe and Reno TCP implementations 🏆.

RFC1072 [VJ88] describes one possible implementation of SACK options for TCP 🧩. Sadly it was never deployed on the Internet 😢, because people disagreed about how SACK options should be used alongside the TCP window shift option (initially described RFC1072 and revised in [Jacobson92]) 🙄.

We're proposing some slight tweaks to the SACK options from RFC1072 💅. The big one is that sending a selective acknowledgment for the most recently received data cuts down the need for long SACK options [Keshav94, Mathis95] 🧠. Also, the SACK option now carries full 32 bit sequence numbers 🔢. Those two changes are the only changes to the RFC1072 proposal 🫶. They make SACK easier to implement and address concerns about robustness 🛡️.

The selective acknowledgment extension uses two TCP options 🎀. The first is an enabling option called "SACK-permitted". It may be sent in a SYN segment to say the SACK option can be used once the connection is established 🔓. The second is the SACK option itself, which may be sent over an established connection once SACK-permitted has given permission 💌.

The SACK option gets sent from the TCP that's receiving data to the TCP that's sending that data. We'll call these the data receiver and the data sender, respectively 🦋. We'll look at one particular simplex data flow. Any data flowing the other way over the same connection can be treated independently 🔁.

2. Sack-Permitted Option 🔓

This two-byte option may be sent in a SYN by a TCP that's been extended to receive (and presumably process) the SACK option once the connection has opened ✨. It MUST NOT be sent on non-SYN segments 🚫.

       TCP Sack-Permitted Option:

       Kind: 4

       +---------+---------+
       | Kind=4  | Length=2|
       +---------+---------+

3. Sack Option Format 🎀

The SACK option is used to carry extended acknowledgment info from the receiver to the sender over an established TCP connection 💫.

       TCP SACK Option:

       Kind: 5

       Length: Variable

                         +--------+--------+
                         | Kind=5 | Length |
       +--------+--------+--------+--------+
       |      Left Edge of 1st Block       |
       +--------+--------+--------+--------+
       |      Right Edge of 1st Block      |
       +--------+--------+--------+--------+
       |                                   |
       /            . . .                  /
       |                                   |
       +--------+--------+--------+--------+
       |      Left Edge of nth Block       |
       +--------+--------+--------+--------+
       |      Right Edge of nth Block      |
       +--------+--------+--------+--------+

The data receiver sends the SACK option to tell the data sender about non-contiguous blocks of data it's received and queued 📦. The data receiver waits for data (maybe through retransmissions) to fill the gaps in sequence space between received blocks ⏳. Once the missing segments show up, the data receiver acknowledges everything normally by moving the left window edge in the Acknowledgement Number Field of the TCP header 🙌. The SACK option doesn't change what the Acknowledgement Number field means 🙅‍♀️.

This option holds a list of some of the blocks of contiguous sequence space that the received, queued data sits in, within the window 🧺.

Every contiguous block of data queued at the data receiver gets defined in the SACK option by two 32-bit unsigned integers in network byte order 🔢:

• Left Edge of Block

This is the first sequence number of this block.

• Right Edge of Block

This is the sequence number immediately following the last sequence number of this block.

Each block is received bytes of data that are contiguous and isolated 💅. That means the bytes just below the block, (Left Edge of Block - 1), and just above the block, (Right Edge of Block), haven't been received 🙅‍♀️.

A SACK option that specifies n blocks has a length of 8*n+2 bytes, so the 40 bytes available for TCP options can carry a max of 4 blocks 🧮. SACK is often going to be used alongside the Timestamp option used for RTTM [Jacobson92] 🕰️. That takes an extra 10 bytes (plus two bytes of padding), so in that case a max of 3 SACK blocks is allowed 😤.

The SACK option is advisory 🤔. It tells the data sender that the data receiver has received the indicated segments, but the data receiver is allowed to discard data later on that was reported in a SACK option 🗑️. Section 8 below talks about what advisory SACK means, especially that the data receiver may renege, or drop data it already SACKed 😱.

4. Generating Sack Options: Data Receiver Behavior 🧠

If the data receiver got a SACK-Permitted option on the SYN for this connection, the data receiver MAY choose to generate SACK options like described below 🦋. If the data receiver generates SACK options under any circumstance, it SHOULD generate them under all permitted circumstances 💯. If the data receiver never got a SACK-Permitted option for a given connection, it MUST NOT send SACK options on that connection 🚫.

If SACK options get sent at all, they SHOULD be included in all ACKs that don't ACK the highest sequence number in the data receiver's queue 🔍. In this situation the network has lost or mis-ordered data, so the receiver is holding non-contiguous data in its queue 😵‍💫. RFC 1122, Section 4.2.2.21, talks about why the receiver sends ACKs in response to extra segments received in this state 📚. The receiver SHOULD send an ACK for every valid segment that arrives containing new data, and each of these "duplicate" ACKs SHOULD bear a SACK option 🫶.

If the data receiver decides to send a SACK option, these rules apply 📋:

• The first SACK block (i.e., the one immediately following the kind and length fields in the option) MUST specify the contiguous block of data containing the segment which triggered this ACK, unless that segment advanced the Acknowledgment Number field in the header 🎯. This makes sure the ACK with the SACK option reflects the most recent change in the data receiver's buffer queue 💌.
• The data receiver SHOULD include as many distinct SACK blocks as possible in the SACK option 📦. Heads up that the max available option space might not be enough to report every block in the receiver's queue 😬.
• The SACK option SHOULD be filled out by repeating the most recently reported SACK blocks (based on first SACK blocks in previous SACK options) that aren't subsets of a SACK block already in the SACK option being built 🔁. This makes sure that in normal operation, any segment that's still part of a non-contiguous block held by the data receiver gets reported in at least three successive SACK options, even for large-window TCP implementations [RFC1323]) 🪟. After the first SACK block, the following SACK blocks in the SACK option may be listed in arbitrary order 🎲.

It is very important that the SACK option always reports the block containing the most recently received segment 🚨. This gives the sender the most up-to-date info about the state of the network and the data receiver's queue 🧠✨.

5. Interpreting the Sack Option and Retransmission Strategy: Data Sender Behavior ✨

Okay so when the data sender gets an ACK carrying a SACK option, it SHOULD record that selective acknowledgment for future reference 🫶. Picture a retransmission queue. It holds the segments that were sent but aren't acked yet, lined up in sequence-number order 📋. If the sender re-packetizes before it retransmits, the block boundaries in the SACK might not line up with the segment boundaries in that queue, but ngl that's not a serious problem for the sender 💅.

Here's one way the sender could handle this (not the only way, bestie) 🧚. Give every segment in the queue a brand new flag bit called "SACKed". It marks whether that segment has been reported in a SACK option 🎀.

When an acknowledgment segment arrives with a SACK option, the sender turns on the SACKed bits for the segments that were selectively acknowledged. For each block in the SACK option, it turns on the SACKed flags for every segment in the retransmission queue that is wholly contained within that block. This just takes straightforward sequence number comparisons, nothing spicy 🔥.

After the SACKed bit gets turned on (because a SACK option was processed), the sender skips that segment during any later retransmission 🙅‍♀️. Any segment that still has its SACKed bit off and sits below the highest SACKed segment is available for retransmission 🦋.

After a retransmit timeout, the sender SHOULD turn off all of the SACKed bits, because that timeout might mean the data receiver has reneged 😭. The sender MUST retransmit the segment at the left edge of the window after a retransmit timeout, whether or not that segment's SACKed bit is on 💜. A segment won't be dequeued and its buffer won't be freed until the left window edge moves past it 🌸.

5.1 Congestion Control Issues

This document doesn't try to spell out the congestion control algorithms for TCP with SACK in detail 🙈. Still, the congestion control algorithms in the de facto standard TCP implementations MUST be preserved [Stevens94]. Specifically, to keep things robust when the network reorders packets, recovery is not triggered by a single ACK reporting out-of-order packets at the receiver. Also, during recovery the data sender limits how many segments it sends in response to each ACK. Existing implementations limit the data sender to one segment during Reno-style fast recovery, or to two segments during slow-start [Jacobson88]. Other aspects of congestion control, like reducing the congestion window in response to congestion, must similarly be preserved.

Time-outs are still the fall-back for detecting dropped packets, and SACK doesn't change that 🕰️. Because the data receiver is allowed to discard SACKed data, the data sender MUST ignore prior SACK information when it works out which data to retransmit after a retransmit timeout.

Future research into congestion control may take advantage of the extra information SACK provides 🔬. One area for that research is changes to TCP for wireless or satellite environments, where packet loss isn't necessarily a sign of congestion 🛰️.

6. Efficiency and Worst Case Behavior 🏆

If the return path carrying ACKs and SACK options were lossless, one block per SACK option packet would always be enough 🌈. Every segment that arrives while the data receiver is holding discontinuous data would make the receiver send an ACK with a SACK option containing the one changed block in its queue. That means the data sender could build a perfect replica of the receiver's queue just by taking the union of all the first SACK blocks.

The return path isn't lossless, though, so the SACK option is defined to include more than one SACK block in a single packet 😤. Those redundant blocks make SACK delivery sturdier when ACKs get lost. A receiver that also uses the time stamp option [Jacobson92] has room for three SACK blocks in the SACK option. So each SACK block will generally be repeated at least three times, if needed, once in each of three successive ACK packets 🎯. Still, if every ACK packet reporting a particular SACK block gets dropped, the sender might assume that data in that block was never received, and it could unnecessarily retransmit those segments 🙃.

Other TCP options can shrink the number of available SACK blocks to 2, or even to 1 🥺. That cuts the redundancy of SACK delivery when ACKs are lost. Even so, the exposure of TCP SACK to unnecessary retransmission is strictly less than the exposure of current TCP implementations 💖. The worst-case conditions needed for the sender to needlessly retransmit data are discussed in more detail in a separate document [Floyd96].

Older TCP implementations without the SACK option won't be unfairly disadvantaged when they compete against SACK-capable TCPs ⚖️. This issue is discussed in more detail in [Floyd96].

7. Sack Option Examples 🎀

The following examples show the proper behavior of SACK generation by the data receiver 🧁.

Assume the left window edge is 5000 and the data transmitter sends a burst of 8 segments, each containing 500 data bytes.

Case 1: The first 4 segments are received but the last 4 are dropped.

The data receiver returns a normal TCP ACK segment acknowledging sequence number 7000, with no SACK option. Simple and iconic 💅.

Case 2: The first segment is dropped but the remaining 7 are received.

Each time one of the last seven packets arrives, the data receiver returns a TCP ACK segment that acknowledges sequence number 5000 and contains a SACK option specifying one block of queued data 📦:

    Triggering    ACK      Left Edge   Right Edge
    Segment

    5000         (lost)
    5500         5000     5500       6000
    6000         5000     5500       6500
    6500         5000     5500       7000
    7000         5000     5500       7500
    7500         5000     5500       8000
    8000         5000     5500       8500
    8500         5000     5500       9000

Case 3: The 2nd, 4th, 6th, and 8th (last) segments are dropped.

The data receiver ACKs the first packet normally. The third, fifth, and seventh packets trigger SACK options as follows 🫠:

    Triggering  ACK    First Block   2nd Block     3rd Block
    Segment            Left   Right  Left   Right  Left   Right
                       Edge   Edge   Edge   Edge   Edge   Edge

    5000       5500
    5500       (lost)
    6000       5500    6000   6500
    6500       (lost)
    7000       5500    7000   7500   6000   6500
    7500       (lost)
    8000       5500    8000   8500   7000   7500   6000   6500
    8500       (lost)

Now suppose the 4th packet is received out of order 👀. (This could be because the data was badly misordered in the network, or because the 2nd packet was retransmitted and lost, and then the 4th packet was retransmitted.) At this point the data receiver only has two SACK blocks to report, so it replies with the following Selective Acknowledgment:

    Triggering  ACK    First Block   2nd Block     3rd Block
    Segment            Left   Right  Left   Right  Left   Right
                       Edge   Edge   Edge   Edge   Edge   Edge

    6500       5500    6000   7500   8000   8500

Now suppose the 2nd segment is received. The data receiver then replies with the following Selective Acknowledgment 🎉:

    Triggering  ACK    First Block   2nd Block     3rd Block
    Segment            Left   Right  Left   Right  Left   Right
                       Edge   Edge   Edge   Edge   Edge   Edge

    5500       7500    8000   8500

8. Data Receiver Reneging 🫣

Heads up: the data receiver is allowed to discard data in its queue that hasn't been acknowledged to the data sender, even if that data was already reported in a SACK option 🙈. Discarding SACKed packets like this is discouraged, but it may be used if the receiver runs out of buffer space.

The data receiver MAY elect not to keep data it has reported in a SACK option. If it does, its SACK generation gets extra rules 📜:

• The first SACK block MUST reflect the newest segment. Even if the newest segment is going to be discarded, and the receiver has already discarded adjacent segments, the first SACK block MUST report, at a minimum, the left and right edges of the newest segment.
• Except for the newest segment, all SACK blocks MUST NOT report any old data which is no longer actually held by the receiver.

Since the data receiver may later discard data it reported in a SACK option, the sender MUST NOT discard data before it is acknowledged by the Acknowledgment Number field in the TCP header 🔐.

9. Security Considerations 🔒

This document neither strengthens nor weakens TCP's current security properties. No new security holes, no fixes, just the same vibes as before 🫶.

10. References 📚

[Cheriton88] Cheriton, D., "VMTP: Versatile Message Transaction Protocol", RFC 1045, Stanford University, February 1988.

[Clark87] Clark, D., Lambert, M., and L. Zhang, "NETBLT: A Bulk Data Transfer Protocol", RFC 998, MIT, March 1987.

[Fall95] Fall, K. and Floyd, S., "Comparisons of Tahoe, Reno, and Sack TCP", ftp://ftp.ee.lbl.gov/papers/sacks.ps.Z, December 1995.

[Floyd96] Floyd, S., "Issues of TCP with SACK", ftp://ftp.ee.lbl.gov/papers/issues_sa.ps.Z, January 1996.

[Huitema81] Huitema, C., and Valet, I., An Experiment on High Speed File Transfer using Satellite Links, 7th Data Communication Symposium, Mexico, October 1981.

[Jacobson88] Jacobson, V., "Congestion Avoidance and Control", Proceedings of SIGCOMM '88, Stanford, CA., August 1988.

[Jacobson88}, Jacobson, V. and R. Braden, "TCP Extensions for Long-Delay Paths", RFC 1072, October 1988.

[Jacobson92] Jacobson, V., Braden, R., and D. Borman, "TCP Extensions for High Performance", RFC 1323, May 1992.

[Keshav94] Keshav, presentation to the Internet End-to-End Research Group, November 1994.

[Mathis95] Mathis, M., and Mahdavi, J., TCP Forward Acknowledgment Option, presentation to the Internet End-to-End Research Group, June 1995.

[Partridge87] Partridge, C., "Private Communication", February 1987.

[Postel81] Postel, J., "Transmission Control Protocol - DARPA Internet Program Protocol Specification", RFC 793, DARPA, September 1981.

[Stevens94] Stevens, W., TCP/IP Illustrated, Volume 1: The Protocols, Addison-Wesley, 1994.

[Strayer92] Strayer, T., Dempsey, B., and Weaver, A., XTP -- the xpress transfer protocol. Addison-Wesley Publishing Company, 1992.

[Velten84] Velten, D., Hinden, R., and J. Sax, "Reliable Data Protocol", RFC 908, BBN, July 1984.

11. Authors' Addresses ✨

Okay bestie, this is the squad that cooked up SACK 🎀 Matt Mathis and Jamshid Mahdavi were both at the Pittsburgh Supercomputing Center, and you can totally reach them at mathis@psc.edu and mahdavi@psc.edu 💌 Sally Floyd was over at Lawrence Berkeley National Laboratory, reachable at floyd@ee.lbl.gov 🦋 And Allyn Romanow was at Sun Microsystems, Inc., with allyn@eng.sun.com 🌸 Literal dream team, no cap 💅

Matt Mathis and Jamshid Mahdavi
Pittsburgh Supercomputing Center
4400 Fifth Ave
Pittsburgh, PA 15213
mathis@psc.edu
mahdavi@psc.edu

Sally Floyd
Lawrence Berkeley National Laboratory
One Cyclotron Road
Berkeley, CA 94720
floyd@ee.lbl.gov

Allyn Romanow
Sun Microsystems, Inc.
2550 Garcia Ave., MPK17-202
Mountain View, CA 94043
allyn@eng.sun.com