When we originally set out to implement QUIC multipath in rust, we knew we had to modify the main internal transmission loop that produces UDP datagrams. With QUIC multipath need to check not only a single path for any frames that should be transmitted or retransmitted or loss probes to send, but instead need to do this for each currently open path. It turns out that the logic for how frames make it into datagrams turns out to be quite complicated. To this day, we keep improving the logic. This blog post is essentially an engineer's braindump of how this logic works and why it works the way it does.

One would think stuffing QUIC frames into datagrams would be an easy task. Let's assume something else has already prepared which frames we want to write into our datagrams, but not necessarily their size. In a simple case, constructing a datagram from a bunch of QUIC frames can look like this:

- One big box
- Outside has written: `src_ip: 192.168.0.101` and `dest: 200.200.200.200:443`
- Inside:
  - A smaller box with the text "QUIC Header" inside
  - The majority of the outer box filled with boxes that say "QUIC Frame 0", "QUIC Frame 1", and so on
  - A small box at the bottom that says "Authentication tag"

But that's just the tip of the iceberg. Let us dive into the complex world of generic segmentation offload (GSO), QUIC encryption levels, QUIC multipath and packet padding.

First: Wait, what key do we actually use to encrypt?

QUIC packets are encrypted, as the authentication tag above might already hint to. But if the client sends the first packet in the connection, which key does it actually use to encrypt?

QUIC's encryption levels: Initial, Handshake and Data

These three encryption levels are in the order of increasing guarantees. A connection starts out using "Initial" keys, then during the handshake moves to "Handshake" keys and after the full key exchange moves on to the "data" encryption level. We only ever send application data using the "data" encryption level, also sometimes called the 1-RTT encryption level.

The first encryption level actually uses a key derived from public information: the connection's source connection ID which is attached to each QUIC packet in its QUIC header. This means anyone can read the contents of packets encrypted using the "Initial" encryption level. Why encrypt them then? Well, most importantly it helps to prevent certain amplification attacks, but it also prevents protocol ossification to a degree and it's also just neat to not have to special-case initial packets in terms of encryption too much.

While the first encryption level is mostly used for the first TLS message ("CRYPTO" frame) from the client to the server, the second encryption level already begins once the server has processed the first message from the client. At this point, the server has derived a shared secret using the client's key share and its own key share, and starts sending the first message from server to client in with this encryption level.

Finally, the client can derive the same key for the handshake encryption level once it received the server's key share. At this point it can also derive the key in the data encryption level. Although both keys are derived using the ephemeral key shares from the client and server, the data encryption level provides some important required guarantees by including a hash of the whole handshake transcript.

- sequence diagram with client and server
- first from client to server:
  - "Initial" containing "ClientHello" (incl. client key share)
- second from server to client:
  - "Initial" with ACK + "ServerHello" (incl. server key share)
  - "Handshake" with "server authentication"
    (EncryptedExtensions + CertificateRequest + Certificate + CertificateVerify + Finished)
  - server can now derive data keys
- third from client to server:
  - "Initial" with ACK (then Initial keys discarded)
  - "Handshake" with ACK + "client authentication"
    (client Certificate + CertificateVerify + Finished)
  - client can now derive data keys

(TODO: trim the above diagram down to what I actually want to show, and link https://quic.xargs.org/ somewhere)

Now, it's not quite as simple as sending some data in initial, then responding with some in handshake, and finally switching to data. For example, in order for the client to be able to read the handshake data it needs to know the server's key share. But to be able to read that key share, it needs to be encrypted only with the initial encryption level. That said, once the client has read this key share it could immediately read the next server message in the handshake encryption level.

This means ideally the server sends both its key share and first message in the handshake message in one go. It turns out that in many cases both of these packets would easily fit into a single datagram (less than 1200 bytes).

So that's exactly what is done in practice: We send both packets in one datagram.

Wait. Send in two encryption levels simultaneously?

Ah yes, right. Here comes the first optimization that complicates the simple picture from above.

The actual first handshake datagram from the server to the client looks like this:

- One big box again
- Outside has written: `src_ip: 192.168.0.101` and `dest: 200.200.200.200:443`
- Inside:
  - Two medium sized boxes with different titles:
    - One box saying "In Initial Space:" containing two QUIC frames: An "ACK" and a "CRYPTO" frame.
    - One box saying "In Handshake Space:" containing one "CRYPTO" QUIC frame.
  - Both the above boxes have a QUIC header at the top and an authentication tag at the bottom

This optimization is called "coalescing packets into datagrams". Coalescing is exactly why the distinction between packet and datagram terminiology is useful.

In terms of how it works, it's actually a fairly simple operation: Each packet in the initial or handshake encryption level is a so-called "long header" packet which means it also has a length field indicating where the packet ends. This allows us to put two packets prepended with their QUIC headers back-to-back into a datagram.

This does not work with data encryption level, as that uses a "short QUIC header". That header type doesn't contain a length field, presumably to save some bytes, as packet coalescing really only is useful during the handshake and it's worth saving those bytes after the handshake when no coalescing happens instead.

Politely Pleading: Please Properly Prepare Packets Padded!

There's another small caveat to the above diagram. The QUIC RFC requires checking that the minimal transmissible unit (MTU) that the network can handle is at least datagrams of 1200 bytes. How do you check this? Well, by sending such datagrams and seeing if they make it through! If they don't, the connection will time out.

Our above datagrams are not that big, though. A typical initial packet is roughly 300 bytes. Let's pad the datagram its in.

Okay, but where do we put the bytes?

Sure, just add some bytes. Seems like there's a QUIC frame for exactly this! The PADDING frame. Its identifier is 0x00: Just a zero byte. This means that if you encode a QUIC packet and the last 900 bytes are just zeroes, they will be interpreted as 900 PADDING frames. Isn't that neat?

So let's put in some bytes.

- Same diagram as the last one
- In the handshake space packet, "PADDING" frames below the CRYPTO frame.

We need to remember to leave enough space for our authentication tag (typically 16 bytes), which is added to the end of our packets.

I want to point out that besides this caveat, there is actually a surprising amount of complexity in making padding decisions. The biggest problem is that it can be difficult to guess whether you will have space to coalesce another packet while you're trying to figure out whether to going to add padding or not to your current packet:

• Before you begin the handshake packet, you need to finish the initial packet.
• Before you finish the initial packet, you need to know if you need to put in padding into the initial packet or not.
• To decide whether you need to put padding into the initial packet or not, you need to figure out whether you'll coalesce with another handshake packet.
• You only really how big the handshake packet is once you start building it.

This kind of predicting-if-you-need-padding logic is can be surprisingly brittle and complicated! It's usually safer to go with just some "minimum required remaining space" bytes constant to ensure that you'll be able to fit another packet when coalescing, but deciding what constant to use here is not trivial.

DPLPMTUD and other causes of padding

Yes, DPLPMTUD is one of those ridiculous acronyms used in the QUIC specification.

We're now moving on from the handshake to an established connection, during which there are other cases in which we'd like to make sure datagrams have certain sizes. When we're migrating from one network path to using another (both using normal QUIC RFC 9000 connection migration as well as opening new QUIC multipath paths), we like to ensure the new path supports an MTU of 1200.

Another case for is DPLPMTUD, which probes bigger datagram sizes to see if we can send packets bigger than the 1200 MTU. Ethernet might support packets of up to around 1500 bytes, with the payload being as big as 1472 bytes maximum. This can help goodput by reducing the propotion of headers to actual payloads. Behind the incredible DPLPMTUD acronym is "Datagram Packetization Layer PMTU Discovery" where PMTU in turn stands for "Path Maximum Transmission Unit".

So unfortunately this means we can't have padding be a special-case for handshake packets only.

It also means we can't (TODO)

Is your head spinning yet? Well, I hope it's not due to bad explanations! But buckle up, there are even more constraints coming to our frame stuffing.

GSO and more constraints for producing datagrams

There's a pretty cricital performance improvement for linux systems: generic segmentation offload (GSO). It's something you can enable on your UDP socket in linux to allow you to send multiple datagrams with a single syscall. This helps a ton in getting syscall overhead of UDP connections down compared to TCP: In TCP you can queue up way more than the measily 1472 bytes of data at a time in a single syscall for the operation system to send. (Typical values for what a single TCP syscall will copy into kernel memory for sending it are between 16KiB and 4MiB, depending on OS configuration and how big the congestion window is.) With GSO, you can send a full "batch" of UDP packets in one syscall. On my linux system I'm writing this blog post on right now, the GSO maximum batch size is 64. So with our 1472 bytes of data per UDP packet, I'll be able to queue up to ~1472 * 64 = 94208 in the good case. Great! This reduces syscall overhead a ton.

- A diagram that shows the contrast between non-GSO and GSO-ed transmit of a batch of datagrams.
- Top row:
  - multiple rounded-corner datagrams, there's a small header for each datagram (small part on the left of each datagram)
  - a line indicating user-kernel boundary
  - many arrows going across the boundary for each datagram
- Bottom row:
  - One large rounded-corner GSO batch roughly the width of all the datagrams above with only one small header on the left side
    - the individual datagrams are hinted at with dashed line separators between them
  - a line indicating user-kernel boundary
  - an arrow going across said boundary only once and the GSO batch being split into datagrams only behind the boundary

What's the catch? Well, in order to make the syscall as efficient as possible, you specify datagram metadata only once for all of the datagrams you want to send in the batch. This includes:

1. The interface you want to use for sending all datagrams.
2. The destination socket address you want to use for all datagrams.
3. The size of all datagrams.

Oh yes. Yet another size constraint :)

Clipping to Segment Size

Because we need to provide one "segment size"/"stride" for all datagrams in a GSO batch, the first datagram we produce determines the exact size of all further datagrams (except for the last one, but that's yet another edge case). Let's look at an example: There's a QUIC extension for sending "datagrams" in a QUIC connection. This allows an application to re-use a QUIC connection's congestion control and encryption for its own purposes, all while the connection can still use streams at the same time, without having to initiate a secondary connection (again, neat!). These "datagrams" (yo dawg, what if we put a datagram into your datagram) are guaranteed to be sent in one UDP datagram or otherwise are dropped, but not fragmented by the QUIC implementation itself. So let's say an application queues two 800-byte "datagrams" via the QUIC datagram extension. The first datagram will be put into the first actual UDP datagram in the GSO batch. At this point, we have less than 800 bytes of space left in our packet, so we end the packet. Because we still have more data to send, we continue our GSO batch and start another datagram. However, the first datagram in our GSO batch is now set to an exact size (TODO: find out what that would be in practice) ~850 bytes. This means the second datagram in our GSO batch can't be bigger than 850 bytes.

- Yet another diagram with a big box with a src_ip and destination
- However this box is split into two:
  - The upper part with a QUIC header and a DATAGRAM frame
  - The lower part with a QUIC header and another DATAGRAM frame
- a bracket going across the whole box that annotates the whole thing as "one transmit buffer"
- a bracket going across each header & datagram box annotating these as "850 byte datagram" each

In turn this means we can't decide whether to send MTU probes on a per-datagram basis, but need to make that decision at the start of a new GSO batch, otherwise we'd be stuck with the MTUD probe size on following datagrams. Similarly, it also means whenever we want to send any other kind of path-validating probe, we need to decide to do so in the first datagram. Luckily, structuring your code to do so in advance of the whole batch is quite natural.

But do we send at all? - Congestion Control

When the application reads a file and pumps its contents into noq in an expectation that it will send them, noq will intentionally limit how much it sends. Even if we technically have the CPU resources to process the data (to encrypt and queue it into the kernel), we don't do so. For good reason.

The part of the system that does this is called "congestion control": Simplifying a bit, the congestion controller prevents sending more data than you have bandwidth. Of course, you cannot know how much bandwidth you'll have: This depends not only on your upload or download speed, but also on your peer's internet link as well as any traffic going through the system at the whole same time. When you send more than what the link between you and your peer can handle, the network will start to drop your datagrams: This is called "tail-loss", and it means you've wasted valuable bytes encrypting packets and needlessly overwhelmed some hardware somewhere, so we try to minimize how much this happens. Congestion controllers are quite complicated to get right (and are a very much active area of research!). Our goal in this post is not to explain how they work. Suffice it to say they try to estimate a "congestion window", the maximum number of bytes we should aim to have in-flight at once, based on the bytes we send, when we send them, the bytes we receive and when we receive them, and any evidence for lost datagrams.

Which congestion controller though?

I said congestion controllers collect "evidence for lost datagrams". The QUIC RFC 9000 explains in detail how evidence for loss should be detected. Obviously you never know when a datagram you sent was actually lost or whether it's just stuck in traffic somewhere. So we depend on two heuristics. The first is just "if our peer hasn't acknowledged anything in flight for more than one RTTs". The second is based on the idea that even though UDP is unordered, most of the time datagrams arrive roughly in the order that they're sent. So if the acknowledgments we receive from our peer indicate that there's a "gap" in what it received (this could be due to reordering), we wait for a very short time to see if this gap sorts itself out. Otherwise we assume that packet was lost.

Uhm. Packets or datagrams?

Well... sigh.

Technically what's lost are datagrams, because that's the atomic unit of what can be lost or transmitted at once. However, what we detect is lost or not are actually packets, because as you might be able to infer from the above heuristics, they're based on acknowledgements, which are in turn based on packet numbers. The reason for this is quite technical. At the end of the day you have certain "packet number spaces", and they roughly correspond with which keys you use for encryption. If you encrypt packets with different keys, most of the time, you'll use a different "counter" (packet number) to identify these packets.

This makes it somewhat awkward if you consider packet loss of coalesced packets: If you lose a datagram with both handshake and data packets inside, you don't want to count this loss twice in your congestion controller.

The way that QUIC implementations deal with this in practice is different. Some QUIC implementations just flat out ignore loss in the initial and handshake spaces for congestion control. This simplifies the congestion controller: It can assume just one type of "packet number" and e.g. assume there will always be one "latest packet number" that's monotonically increasing.

We don't do this in noq though, instead, we let the congestion controller look at only the highest space that we've sent in. This makes it ignore loss in the inital and handshake space, if we've already sent in the data space. In practice this works reasonably well, since the initial and handshake spaces are active only for a relatively short time.

There's another approach to doing this where you could be using unique packet numbers across the initial, handshake and data spaces. Skipping packet numbers is allowed by the QUIC specification and doing it this way has the benefit of making it much easier to manage a single congestion controller across all three encryption levels simultaneously. We haven't done this work yet, but are definitely considering it.

Enter multipath, again

Now with multipath, this situation gets more complicated yet again.

There are now many "packet number spaces" associated with the data encryption level. And according to the QUIC multipath specification, these packet number spaces need to be backed by different congestion controllers.

In the general case, you'll have separate paths on separate actual network paths, so this makes sense, but in theory there's nothing preventing you from opening two paths on the same 4-tuple. This means there now exist both cases in which a single congestion controller is managing multiple packet number spaces that all run on the same 4-tuple (the initial, handshake, and data in path 0), while other times the congestion controller is not shared across packet number spaces, even though they're on the same 4-tuple.

- Diagram with a table with three columns with rows of differnt rowspans.
  - Column 1: The different 4-tuples/network paths
    - one 4-tuple spans 4 rows, one 4-tuple spans 1 row
  - Column 2: The encryption levels
    - init and hs span 1 row, dat spans 3 rows
  - Column 3: The multipath path IDs
    - path 0 spans 3 rows, path 1 and path 2 one row each
  - There are "circled regions" across some rows and all columns marking what congestion controllers cover:
    - first 3 rows are one CC, then two more CCs per row

Oh, did we tell you about migrations yet?

QUIC even without multipath actually allows you to switch from one 4-tuple to another one (if you don't use zero-length connection IDs).

Sometimes in those cases, you need to reset your congestion controller state. And additionally, you need to protect yourself from spoofed datagram remote IPs: An attacker can intercept a datagram in a QUIC connection and spoof its source address to make the peer think the connection migrated. In those cases, you need to keep "looking for datagrams" on both "old" and new 4-tuples, accepting packets from both. You simulatenously start probing both paths, and the first path that successfully proves it is authentic will be switched to. In the mean time, you already start using the new path, but you remember the congestion controller state from the old path, in case you need to revert back to it.

This means you now have two congestion controllers on the same path! Yay to yet again a little more complexity.

Unfortunately, multipath doesn't absolve us of this complexity. In fact, we need to handle both migrations of paths and multiple paths at the same time, so the complexity just multiplies. That is because although multipath would allow really seamless switching to another path, it doesn't solve cases where clients need to migrate involutarily due to NAT rebinding or default interface switching. (needs a footnote: We can protect against default interface switching by specifying the interface we want to send datagram on. However, we can only do that if we actually know which one that is supposed to be, which can be tricky to figure out. Using the default interface is often preferrable, but figuring that one out is OS- and application-specific)

Putting it all together

All of this complexity ends up being handled by one public function in noq-proto: noq_proto::Connection::poll_transmit. That function essentially allows the user to say "Hey, I'm ready to send a GSO batch, tell me if you have one for me right now":

let socket = /* your socket implementation */;
let mut conn: noq_proto::Connection = /* ... */;
let mut buf = Vec::new();
// this is ignoring other APIs like feeding the connection with received packets or handling timers
while let Some(transmit) = conn.poll_transmit(Instant::now(), socket.max_gso_batch_size(), &mut buf); {
    socket.send_gso_batch(
        transmit.destination,
        transmit.src_ip,
        transmit.segment_size,
        transmit.size,
        &buf,
    );
}

Then it's noq_proto::Connection::poll_transmit's job to handle all of the complexity around choosing the above complexity we were talking about:

• Coalescing packets
• Deciding on padding
• Handling GSO segment size
• Suspending sending based on congestion control
• Choosing the path to send on and a bunch of other things.

Since the start of implementing QUIC multipath on top of Quinn, poll_transmit is where we've spent most of our time. We've since split up its definition into many separate functions, added helpers to make it easier to create packets, handle padding, and deal with congestion control.

We're now in a much better place than just half a year ago, but there's still lots of things to improve and bugs to squash, given this just ends up being something somewhat complex to handle.

Anyways, there's not really a conclusion to this piece, and I'm sorry if you were looking for one. In any case, I hope you enojyed this braindump of some of the things that are going on in a QUIC multipath implementation.