Implement TCP selective acknowledgement extension (sACK)

[jhwgh1968]

The TCP extension is described in RFC 2018.

I am opening a tracking issue for this since I didn't see one. If no one else wants to pick this up, I volunteer.

@whitequark previously made some offhanded comments suggesting it would be easy to send sACK records in acknowledgements based on current gaps tracked by the TCP reassembly code. I tend to agree, based on my understanding of the code.

The more difficult part is actually using information in sACK records sent by the remote TCP. While completely ignoring the remote's sACK records is legal -- the ACK field must not advance past the first gap to prevent mismatching state -- it defeats the extension's purpose, and so is highly discouraged.

[jhwgh1968]

A quick update: I have made some progress on this, but am running into blocking issues when creating unit tests.

It seems when I write a straightforward case (do a bunch of send! calls with frames but one missing from the sequence), the recv! call at the end -- expecting an ACK with sACK in the TCP options -- gets Ok(None), which causes an assert failure. And I cannot figure out why.

[whitequark]

It seems when I write a straightforward case (do a bunch of send! calls with frames but one missing from the sequence), the recv! call at the end -- expecting an ACK with sACK in the TCP options -- gets Ok(None), which causes an assert failure. And I cannot figure out why.

Where is your SACK code located? Is it just in TcpSocket::process or are you also emitting SACKs in TcpSocket::dispatch?

[jhwgh1968]

I mostly changed ack_reply to add the sACK information if needed, but I think my problem is much more basic.

This branch contains none of the new feature at all, and just a unit test I am trying to base my tests from. All the test does is:

1. Set up a particular sequence number
2. Send a series of packets, but skip the first one (i.e. it got lost)
3. Assert that each one gets an ACK back, and the ACK number has not advanced past that missing segment.

Even this code, however, gets Ok(None). I would guess there is some detail about send! or recv! -- or perhaps the ACK timing -- that I fail to grasp.

[whitequark]

@jhwgh1968 You can't call s.rx_buffer.dequeue* if you want to continue using the socket afterwards. Take a look at the implementation of TcpSocket::recv; you're skipping TcpSocket::recv_impl, which means s.remote_seq_no doesn't get updated, and the assembler gets confused afterwards.

I think it would be ideal if we replaced all uses of s.rx_buffer.dequeue* in tests with s.recv*.

[jhwgh1968]

I have updated my test branch, and replaced the dequeue calls with recv. It seems to still return Ok(None).

What else am I missing?

[jhwgh1968]

FWIW, I am still working on this. Life just got really busy for a while.

I did get around my Ok(None) problem. Hopefully there will be a PR before too long! 🤞

[whitequark]

Great to hear, and thanks for your work and patience!

[jhwgh1968]

Since it didn't get linked to this issue, I have a phase 1 implementation in #266.

I will probably work on a phase 1.5 next, where it actually becomes fully "should" compliant with its receiving behavior.

[jhwgh1968]

Unfortunately, I have not had time to work on this. If anyone else wants to take this issue, feel free. Otherwise, I may get to it later in the year.

[jabedude]

@jhwgh1968 what is left to implement?

[jhwgh1968]

I'm glad you asked, @jabedude! I tried to finish this at one point during the year, and didn't get very far.

The way I planned it in my mind, there will be several phases. As you will see, the further into the future the plan is, the more vague it is.

Sender Side Phase 1

This is what I have merged already. To quote myself:

This PR correctly handles all "must" requirements of RFC 2018:

• The sACK Permitted and sACK Range options are transmitted in accordance with the RFC.
• If the remote does not send sACK permitted, sACK range options are never transmitted.
• When a sACK range is transmitted, it contains the range of data corresponding to the segment that triggered the ACK unless the segment caused the ACK field to update (i.e. filled in an assembler hole that permitted progress).
• Once a sACK range is announced, that data is never thrown away. (This is not a "must" requirement, but if the TCP does this, then additional "must" requirements are added.)

However, since this is a "phase 1" PR, compliance is all this implementation has to offer. In practical terms, it only improves throughput in one case, and even then, only for data flowing in one direction.

This is because of the shortcuts taken to save significant complexity:

• All sACK information received from the remote side is ignored
• Only one sACK range will ever be transmitted, even though the data structures support up to 3
• If the segment causes an update in the ACK field, smoltcp will choose a "helpful hint" range if there are still holes in the assembler. The algorithm it uses to select this is contrary to a "should" in the RFC.

Each one of these is avoiding a significant effort. The first is a whole new data structure, the second two are because the "should" algorithm is based on keeping a history of transmitted sACK ranges on a queue, and pulling them off as holes are filled.

Sender Side Phase 2

This finishes the sender side implementation to be "should" compliant with the RFC.

In particular, RFC case 3 should be turned into a test. (In addition to several other interesting edge case tests, of course.)

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)

The algorithm described in the RFC requires smoltcp to treat the header's contents as a list, which is head-insert only, remove in-place. It is not difficult, but it requires quite a bit of new code.

One piece of code I did get a good start on was a new iterator on the Assembler, necessary for building the entire list of holes we have:

pub struct HolesIter<'a> {
    offset: usize,
    last_data: Option<(usize, usize)>,
    iter: DataIter<'a>
}

impl<'a> Iterator for HolesIter<'a> {
    type Item = (usize, usize);

    fn next(&mut self) -> Option<(usize, usize)> {
        let mut product = Some((0, 0));
        while product.filter(|(l, r)| l == r).is_some() {
            product = match (self.last_data, self.iter.next()) {
                (Some((_, l)), Some((r, x))) => {
                    self.last_data = Some((r, x));
                    Some((l.saturating_sub(self.offset), r.saturating_sub(self.offset)))
                },
                (_, None) => {
                    self.last_data = None;
                    None
                },
                (_, _) => panic!("logic error: data iterator not fused")
            }
        }
        product.map(|(l, r)| (l + self.offset, r + self.offset))
    }
}

Once this phase is completed, there should be significant performance gains talking to non-smoltcp TCP/IP stacks.

Receiver Side Phase 1

This is to implement basic header handling when smoltcp is the receiver. Currently, smoltcp completely ignores any sender's header if it sends one, which is legal but not very nice.

This straightforward implementation is designed to be simple:

• Create a new Assembler for the remote side, based on the contents of headers our side has received.
• Send packets where the Assembler has a hole when it is to our advantage.
• Once we send a packet from the Assembler, fill the hole. (This is to handle falsely advertised windows, and avoids messing up other timeout algorithms.)

This is only an incremental improvement in practice over completely ignoring the window, but it would get the groundwork into the project. I expect there will be a lot of messy integration work, in addition to testing required.

Receiver Side Phase 2

This final phase is the big one: generate the correct packet sequences in response to the RFC case above.

There are also some questions about timing that need exploration. The RFC states that all information in the header is advisory, and so it is possible for a sender to send us a window that, if we fulfill it, their ACK sequence number still will not move.

Such "over-eager senders" will need smoltcp to fall back to its Go-Back-N behavior, rather than sending the Assembler hole ranges infinitely.

So, it's a lot of work, including a lot of testing. I hope you are still interested in the challenge!

[loriopatrick]

Is anyone currently working on this or planning to pick it up?

[Dirbaio]

Not as far as I know.

[loriopatrick]

👍, getting a start on it: #256

[jhwgh1968]

@loriopatrick I presume you meant to link to #450

[loriopatrick]

Oops, yes that's the link