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 datagrams are encrypted, as the authentication tag above might already hint to. But if the client sends the first datagram in the connection, which key does it actually use to encrypt?

QUIC's encryption levels: Initial, Handshake and Data

It's kind of impossible to start a connection encrypted right away (assuming you don't have exchanged secrets some other way previously). This means the client needs to reach out with something that's essentially plain text. Well, in QUIC, even the initial packets are encrypted, but you derive the key from a hard-coded secret and some randomness you attach to the first datagram. In effect this means that your packet can be encrypted by anyone who reads it, if they know it might be a QUIC packet, but at least it makes it easer for me to talk about the encryption levels. I can just say: All datagrams are encrypted (even if the ones in the initial encryption level are trivially decryptable by anyone).

So, when do we actually start to really encrypt datagrams? Like, in a way that makes it impossible for network observers to read them? Well, the client sends the initial datagram to the server. This datagram contains what we call a "CRYPTO" frame. Which in turn contains whatever the underlying cryptography library (be that TLS or some libnoise implementation) needs to start doing its key exchange. The server receives this datagram, and derives the first key using said key exchange algorithm! The server can now talk to the client in the so-called "handshake encryption level" or sometimes also called the "handshake space".

- 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)

But for the client to be able to decrypt packets in the handshake space, it needs to receive the server's key share, which the client needs to be able to read. That means the server will send the key share in a CRYPTO frame encrypted using the initial encryption level, and then also send the first parts of actually-encrypted data in a CRYPTO frame encrypted using the handshake key.

Once the client receives those two packets, it does something similar: It sends a key share in the handshake space and can at the same time start sending in the data encryption level.

Wait. Send in two encryption levels simultaneously?

Ah yes, right. Here comes the first optimization that complicates the simple picture from above: Almost every handshake in QUIC will want to send data in two encryption levels essentially "at once".

If we had to send these two packets in two different UDP datagrams, we'd be wasting datagrams!

So the actual response to a datagram from the server to the client will look 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

(The "CRYPTO" frames essentially contain the TLS handshake data.)

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

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, then we won't support those network conditions.)

Our above datagrams are not that big, though. Let's pad them.

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 20 bytes are just zeroes, they will be interpreted as twenty 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.

For anyone who wants to work on QUIC implementations, I want to point out how deviously complicated this part of building packets actually is:

• 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.
• To know whether you can fit the handshake packet, you need to know if frames will fit into it.

This kind of predicting-if-you-need-padding logic is can be really 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, you read correctly, not a cat on my keyboard!)

There are other cases where we need to pad packets. Specifically, just like we make sure that the initial network path that the handshake uses can support a 1200 MTU, we also need to ensure any other paths we use can support a 1200 MTU. This is not only important if you intend to implement QUIC multipath, as plain QUIC also supports migrating the main path it uses to new network paths. Anytime you do so, you need to verify the new path can also support the 1200 MTU, otherwise you try to keep using the old path.

Another case is when we probe 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. But we can't know if the network will support these kinds of packets in advance of sending them, which is why we're occasionally sending bigger probing packets intentionally. This is what's behind the incredible DPLPMTUD acronym: "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.

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.