Subject: AEAD and header encryption overhead in QUIC

From: Kazuho Oku <[email-masked]>
Date: Thu, 18 Jun 2020 17:23:44 +0900

Hello folks,

TL;DR: When existing crypto libraries are used, the AEAD cost of QUIC can
become somewhat greater than that of TLS over TCP, due to those crypto
libraries not optimized for handling short AEAD blocks. Crypto libraries
optimized for short AEAD blocks can tighten the gap. Also, crypto libraries
optimized for QUIC can combine AEAD operation and header protection vector
generation, effectively eliminating the cost of header protection.

A bit longer story:

Recently, when testing quicly [1] using a NIC with *hardware support* for
UDP GSO offload, we noticed that it uses +30% CPU cycles compared to TLS
over TCP. This was due to our underlying crypto not being optimized for
short AEAD blocks, and due to the call overhead of doing header protection
one packet at a time. [2]

We went on to implement our own AES-GCM library optimized for short AEAD
blocks (i.e. packet-sized), that also generates the header protection
vector while doing AEAD computation. By switching to the new crypto
library, the performance drawback of the crypto itself compared to large
AEAD blocks when down from 30% to 10% [3].

The overhead of header protection (relative to all the crypto cost) on the
send side is now between 0.3% to 1% when using packets sized around 1400
bytes to 1500 bytes. The ratio against the total transport cost is going to
be less than that, and in practice, I think that they are negligible. The
story might be a bit different on the receive-side due to the dependency
between header protection and AEAD, though I am sure there would also be
ways to optimize.

In terms of CPU cycles spent by the QUIC stack, the overhead compared to
TLS-over-TCP came down to 5%. quicly can now sustain the send rate of 5Gbps
while spending about 30% of CPU cycles of one modern Intel CPU core [2].

These numbers are observations from one TLS / QUIC stack doing
micro-benchmarks, though I tend to think that sharing performance numbers
lead to people having better expectations regarding the CPU cost of QUIC.
Some of us were also concerned about the cost of header protection (a.k.a.
packet number encryption) [4]. Hence posting here.

[1] https://github.com/h2o/quicly
[2] https://github.com/h2o/quicly/pull/359
[3] https://github.com/h2o/picotls/pull/310
[4] https://mailarchive.ietf.org/arch/msg/quic/Wy8JXwKyeYgWgRWizWDbyOLg0xc/

-- 
Kazuho Oku

---

From: Nick Banks <[email-masked]>
Date: Thu, 18 Jun 2020 14:51:58 +0000

Hi Kazuho,

Thanks for the information! It’s very interesting. You might try this too:

We’ve found that an easy way to minimize the CPU cost of the header protection (on send and receive) is batching. If you copy 8 packet headers into a single contiguous block of memory, you can do a single crypto operation on it. The cost of doing one batch of 8 is essentially the same as doing just a single header. This effectively cuts the cost of header protection to 1/8th the original cost. Obviously this only works if you have enough packets to batch process, but for high throughput tests, you usually do.

Feel free to take a look at the MsQuic code (receive path<https://github.com/microsoft/msquic/blob/master/src/core/connection.c#L4784>, send path<https://github.com/microsoft/msquic/blob/master/src/core/packet_builder.c#L728>). The nice thing about this design (for those of us who don’t have as much special crypto expertise) is that it doesn’t require any special crypto changes. I’d be interested to see if our two approaches could be combined for even better performance!

Thanks,
- Nick

From: Kazuho Oku<mailto:[email-masked]>
Sent: Thursday, June 18, 2020 1:24 AM
To: IETF QUIC WG<mailto:[email-masked]>
Subject: AEAD and header encryption overhead in QUIC

Hello folks,

TL;DR: When existing crypto libraries are used, the AEAD cost of QUIC can become somewhat greater than that of TLS over TCP, due to those crypto libraries not optimized for handling short AEAD blocks. Crypto libraries optimized for short AEAD blocks can tighten the gap. Also, crypto libraries optimized for QUIC can combine AEAD operation and header protection vector generation, effectively eliminating the cost of header protection.

A bit longer story:

Recently, when testing quicly [1] using a NIC with *hardware support* for UDP GSO offload, we noticed that it uses +30% CPU cycles compared to TLS over TCP. This was due to our underlying crypto not being optimized for short AEAD blocks, and due to the call overhead of doing header protection one packet at a time. [2]

We went on to implement our own AES-GCM library optimized for short AEAD blocks (i.e. packet-sized), that also generates the header protection vector while doing AEAD computation. By switching to the new crypto library, the performance drawback of the crypto itself compared to large AEAD blocks when down from 30% to 10% [3].

The overhead of header protection (relative to all the crypto cost) on the send side is now between 0.3% to 1% when using packets sized around 1400 bytes to 1500 bytes. The ratio against the total transport cost is going to be less than that, and in practice, I think that they are negligible. The story might be a bit different on the receive-side due to the dependency between header protection and AEAD, though I am sure there would also be ways to optimize.

In terms of CPU cycles spent by the QUIC stack, the overhead compared to TLS-over-TCP came down to 5%. quicly can now sustain the send rate of 5Gbps while spending about 30% of CPU cycles of one modern Intel CPU core [2].

These numbers are observations from one TLS / QUIC stack doing micro-benchmarks, though I tend to think that sharing performance numbers lead to people having better expectations regarding the CPU cost of QUIC. Some of us were also concerned about the cost of header protection (a.k.a. packet number encryption) [4]. Hence posting here.

[1] https://github.com/h2o/quicly<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fh2o%2Fquicly&data=02%7C01%7Cnibanks%40microsoft.com%7Cce44384090cd41b9874f08d81360f9dc%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637280654511448872&sdata=hjeugkkQwFtQNx7UriHYA9eQ3z1z9omSxB6XRPiUF1Y%3D&reserved=0>
[2] https://github.com/h2o/quicly/pull/359<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fh2o%2Fquicly%2Fpull%2F359&data=02%7C01%7Cnibanks%40microsoft.com%7Cce44384090cd41b9874f08d81360f9dc%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637280654511458858&sdata=VSe%2Br2rp81U7RIFhRaJ%2FAh4YGXobO4F90v7lUcxqMoA%3D&reserved=0>
[3] https://github.com/h2o/picotls/pull/310<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fh2o%2Fpicotls%2Fpull%2F310&data=02%7C01%7Cnibanks%40microsoft.com%7Cce44384090cd41b9874f08d81360f9dc%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637280654511458858&sdata=xbHdVd9cewW%2BlwSlIQtG4f3sTGYFxqM6c60qnVFkVbI%3D&reserved=0>
[4] https://mailarchive.ietf.org/arch/msg/quic/Wy8JXwKyeYgWgRWizWDbyOLg0xc/<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fmailarchive.ietf.org%2Farch%2Fmsg%2Fquic%2FWy8JXwKyeYgWgRWizWDbyOLg0xc%2F&data=02%7C01%7Cnibanks%40microsoft.com%7Cce44384090cd41b9874f08d81360f9dc%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637280654511468853&sdata=ZT3%2FAtl8HpbN5KKYdI0vY8cmVnoeSJaS1Jys%2F6QiQ9A%3D&reserved=0>

--
Kazuho Oku

---

From: Matt Joras <[email-masked]>
Date: Thu, 18 Jun 2020 10:21:11 -0700

Wow, really interesting results, thanks for sharing!

I was curious, since it's not mentioned on the PRs that I saw, were these
tests done with any adjustments to the ACK frequency on the client? Or is
this with the default ACK policy of ACKing every other?

Matt Joras

On Thu, Jun 18, 2020 at 1:24 AM Kazuho Oku <[email-masked]> wrote:

> [4]
> https://mailarchive.ietf.org/arch/msg/quic/Wy8JXwKyeYgWgRWizWDbyOLg0xc/
>
> --
> Kazuho Oku
>

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 18 Jun 2020 10:35:53 -0700

I agree, thanks for sharing. I am not too surprised by the results though.

I am a bit surprised that it is possible to use bulk encrypt headers as
Nick suggests as I would have thought the key / nonce was associated with
the packet, but I haven’t looked closely recently.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 18 June 2020 at 19.21.44, Matt Joras ([email-masked]) wrote:

Matt Joras

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 19 Jun 2020 06:39:52 +0900

Nick, Matt, Mikkel, thank you for your comments.

2020年6月18日(木) 23:52 Nick Banks <[email-masked]>:

> We’ve found that an easy way to minimize the CPU cost of the header
> protection (on send and receive) is batching. If you copy 8 packet headers
> into a single contiguous block of memory, you can do a single crypto
> operation on it. The cost of doing one batch of 8 is essentially the same
> as doing just a single header. This effectively cuts the cost of header
> protection to 1/8th the original cost. Obviously this only works if you
> have enough packets to batch process, but for high throughput tests, you
> usually do.
>
>
>
> Feel free to take a look at the MsQuic code (receive path
> <https://github.com/microsoft/msquic/blob/master/src/core/connection.c#L4784>
> , send path
> <https://github.com/microsoft/msquic/blob/master/src/core/packet_builder.c#L728>).
> The nice thing about this design (for those of us who don’t have as much
> special crypto expertise) is that it doesn’t require any special crypto
> changes. I’d be interested to see if our two approaches could be combined
> for even better performance!
>

Thank you for sharing your experience. This is indeed a sensible approach
for minimizing the cost of header protection. On the receive side,
processing multiple packets in batch is the only way of minimizing the cost
of header protection, because AEAD unprotection cannot start until the
result of header unprotection is being obtained. Considering that modern
x86-64 CPUs can run 4 to 8 AES block operations in parallel, doing header
protection for one packet at a time is a waste of CPU resources.

To paraphrase, the two approaches are orthogonal on the receive-side, and
combining them would give better performance. My napkin tells me that I can
expect at most 3% reduction in CPU cycles spent in crypto.

On the send side however, I do not expect to see performance increase by
combining the two approaches. This "game" is about keeping the CPU
pipelines that do AES-NI running at their full speed. The cost does not
change as long as the AES operations of header protection are run in
parallel with other AES operations, regardless of that being AEAD or header
protection o other packets.

If there's chance of further improving performance, I tend to think that
that would come from overlapping the AEAD operation of multiple packets.
This "game" is about keeping the AES-NI pipeline busy. With Fusion, we've
reached 90% of the theoretical maximum speed (9th-gen Intel Core CPUs can
do 64 bytes of AES encryption in 40 clocks). The question to us is if we
want to consider changing our API for single-digit performance gain.

> this with the default ACK policy of ACKing every other?

This is an important point, thank you for asking. We did reduce ACK
frequency to 1/8 CWND, as we did in our previous report [1]. In fact, you
cannot turn that off with quicly.

> the packet, but I haven’t looked closely recently.

That's a keen observation. Nonce used for header protection does depend on
the output of AEAD. Though, because the nonce is taken from the very first
few bytes of AEAD output, it is possible to start calculating the header
protection vector before finishing AEAD operation, unless the packet is
tiny. The position of the nonce was deliberately chosen to provide room for
this type of optimization. I recall at least one person (Martin Thomson)
arguing for having this possibility.

[1]
https://www.fastly.com/blog/measuring-quic-vs-tcp-computational-efficiency

-- 
Kazuho Oku

---

From: Matt Joras <[email-masked]>
Date: Thu, 18 Jun 2020 16:24:19 -0700

Thanks for the explanations, Kazuho! Would it be possible to share the
commands you used to produce the given results? It would be interesting so
others can do direct comparisons with their own performance benchmarking.
It is always hard to do comparisons across implementations with varying
hardware and OS versions.

Matt Joras

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 19 Jun 2020 13:42:05 +0900

> hardware and OS versions.

That's a reasonable thing to ask.

While I'm not fully certain if it is helpful to have direct
comparison between the stacks (everybody has different requirements /
deployments), I am at least certain that sharing the setup being used is a
good idea. It also helps me reproduce the results in the future.

I've written down the setup that we used for the benchmark shown in
https://github.com/h2o/quicly/pull/359 at
https://github.com/h2o/quicly/wiki/Benchmarking-CPU-usage. Regarding the
AES-GCM benchmark, I think you can find sufficient information in the last
paragraph of https://github.com/h2o/picotls/pull/310.

>>> I was curious, since it's not mentioned on the PRs that I saw, were
>>> these tests done with any adjustments to the ACK frequency on the client?
>>> Or is this with the default ACK policy of ACKing every other?
>>>
>>
>> That's a keen observation. Nonce used for header protection does depend
>> on the output of AEAD. Though, because the nonce is taken from the very
>> first few bytes of AEAD output, it is possible to start calculating the
>> header protection vector before finishing AEAD operation, unless the packet
>> is tiny. The position of the nonce was deliberately chosen to provide room
>> for this type of optimization. I recall at least one person (Martin
>> Thomson) arguing for having this possibility.
>>
>> [1]

-- 
Kazuho Oku