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 frame 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 a handshake and a data packet 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 implementations just flat out ignore loss in the initial and handshake spaces. 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.

In noq, we actually store a congestion controller for each "packet number space" separately. And yes, this is again really weird if you're building coalesced packets, because e.g. you'll ask the congestion controller for the "handshake" space if you have congestion window first, even though and won't ask the congestion controller for the data space next, because you're coalescing into the same datagram, even if you might not actually have congestion window for the data space. This is weird!

Also - clearly the three congestion controllers share the same network path, so they should measure the same thing, right? Luckily this doesn't have a strong effect on performance in the grand scheme of things, and only has an affect while the intial and handshake spaces are in play, which is during the handshake which usually is relatively uneventful when it comes to congestion events.

That said, this is definitely an area where we'd love to improve in the future.

Wait. Packet number space or encryption level?

Which one is it?

Ehm right. Yeah, they're encryption levels. But congestion control actually works on packet number spaces. This distinction in terminology is useful when you consider multipath: The data space gains the ability to have many packet number spaces under the same encryption level: One for each path.

The packets on each path are counter up sequentially independently of all other paths. But the same keys from the data encryption level are used across all paths.

Now what does this mean for congestion control?

Each path has its own congestion controller. This is quite useful: Different paths have different RTTs, and different loss characteristics and different bandwidth available.