Subject: New Plaintext QUIC-LB Design

From: Martin Duke <[email-masked]>
Date: Mon, 11 Jan 2021 13:40:41 -0800

Hi all,

Ian proposed a radical new plaintext CID algorithm for for quic-lb. I
already merged it into the draft alongside the current one, to make things
clearer. See Section 4.2 of the draft
<https://quicwg.org/load-balancers/draft-ietf-quic-load-balancers.html#name-ecmp-cid-algorithm>.
I suspect this may not be the final result, but this is another one of
those value judgments I'd like input on.

*TL;DR*: instead of assigning individual server IDs as a configuration
step, load balancers assign them ad hoc and remember those assignments.
Servers can observe their assignments from the CIDs they receive.

*Tradeoffs*: The existing PCID design has precisely zero per-connection
state at the load balancer. This design requires the load balancer to have
a potentially very large table of SIDs mapped to servers. On the other
hand, Ian's proposal completely eliminates the process of configuring the
load balancer with a server ID mapping, and configuring each server
separately with its SID.

As a practical matter, Ian's proposal is also an easier transition path for
Google's load balancers, and presumably others as well. Their
implementation experience suggests that the memory load is manageable.

As Ian’s design has per-connection state, it is less robust to the load
balancer rebooting or handing off to a standby device.

*So we have three options*:
1) Stick with PCID and ditch this.
2) Replace PCID with this proposal.
3) Have two standard unencrypted algorithms to capture the tradeoff -- I
would prefer not to complicate things in this way unless there is real
disagreement about how to resolve the tradeoffs.

Thoughts?

Thanks,
Martin

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 11 Jan 2021 17:06:33 -0500

Hi Martin,

> those value judgments I'd like input on.

This is the correct link:

  https://quicwg.org/load-balancers/draft-ietf-quic-load-balancers.html#name-low-config-cid-algorithm

> implementation experience suggests that the memory load is manageable.

Well, then it looks like they are going to do it anyway, so you might as
well put it into the draft!

> disagreement about how to resolve the tradeoffs.

In a bit of synchronicity (may the force be with you!), I was reading the
LB I-D just as your email arrived.  I vote for option (3): the two PCID
can coexist in the document.

  - Dmitri.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Tue, 12 Jan 2021 00:19:07 +0100

I’m trying to read through the LB document that I haven’t looked at for quite a while. It isn’t very clear to me, I am sorry to say.

I do not understand why the highest configuration value is chosen since this value would eventually wrap? Is there an implied wider config value where only the lower bits are visible, similar to packet numbers?

Also, I do not understand how the server receives the assigned SID. Is the ODCID replaced in first packets, or are the packets unmodified, or is the SID prefixed the real packet?

I can see that once the server chooses the DCID for later communication, things get easier.

If the ODCID is modified, what about message authentication, also in future versions and with possible shared keys?

Is the state table affected by the clients choice of ODCID (think abuse)?

Mikkel

> On 11 Jan 2021, at 22.40, Martin Duke <[email-masked]> wrote:
> 
> Hi all,
> 
> Ian proposed a radical new plaintext CID algorithm for for quic-lb. I already merged it into the draft alongside the current one, to make things clearer. See Section 4.2 of the draft <https://quicwg.org/load-balancers/draft-ietf-quic-load-balancers.html#name-ecmp-cid-algorithm>. I suspect this may not be the final result, but this is another one of those value judgments I'd like input on.
> 
> TL;DR: instead of assigning individual server IDs as a configuration step, load balancers assign them ad hoc and remember those assignments. Servers can observe their assignments from the CIDs they receive.
> 
> Tradeoffs: The existing PCID design has precisely zero per-connection state at the load balancer. This design requires the load balancer to have a potentially very large table of SIDs mapped to servers. On the other hand, Ian's proposal completely eliminates the process of configuring the load balancer with a server ID mapping, and configuring each server separately with its SID.
> 
> As a practical matter, Ian's proposal is also an easier transition path for Google's load balancers, and presumably others as well. Their implementation experience suggests that the memory load is manageable.
> 
> As Ian’s design has per-connection state, it is less robust to the load balancer rebooting or handing off to a standby device.
> 
> So we have three options:
> 3) Have two standard unencrypted algorithms to capture the tradeoff -- I would prefer not to complicate things in this way unless there is real disagreement about how to resolve the tradeoffs.
> 
> Thoughts?
> 
> Thanks,
> Martin

---

From: Martin Duke <[email-masked]>
Date: Mon, 11 Jan 2021 15:32:11 -0800

Hi Mikkel,

Answers inline

On Mon, Jan 11, 2021 at 3:19 PM Mikkel Fahnøe Jørgensen <[email-masked]>
wrote:

> I’m trying to read through the LB document that I haven’t looked at for
> quite a while. It isn’t very clear to me, I am sorry to say.
>
> I do not understand why the highest configuration value is chosen since
> this value would eventually wrap? Is there an implied wider config value
> where only the lower bits are visible, similar to packet numbers?
>

In general, client-generated CIDs might come in with config rotation bits
that don't correspond to an existing config. For the other algorithms, it's
randomly routed and after that the server-generated CID is used. But for
this algorithm, the server needs to extract a server ID somehow. If there's
one configuration, that's simple. If there's more than one, there has to be
deterministic behavior. The choice to use the highest is completely
arbitrary; I'm open to other suggestions that have better properties.

> Also, I do not understand how the server receives the assigned SID. Is the
> ODCID replaced in first packets, or are the packets unmodified, or is the
> SID prefixed the real packet?
>

No, any 8-byte CID will contain a server ID. So the client, in effect,
generates an SID and the load balancer decides which server will get it
(and then use that SID in the future)

> If the ODCID is modified, what about message authentication, also in
> future versions and with possible shared keys?
>

It is not modified, see above

Yes, if CIDs are chosen to maximize the number of different SIDs, that will
grow the table. IMO this isn't substantially different from randomly chosen
CIDs, which is of course normal behavior.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Tue, 12 Jan 2021 01:10:16 +0100

Right, thanks for clarifying.

I was reading over the text several more times and I slowly came to the same conclusion as you have explained below.

So the problem with state table is if you send a lot of small random garbage packets to the LB. It’s probably expensive for one endpoint, but easy to DDOS.

The other problem is sending a lot of the same packet to DDOS a target server, but that is probably unavoidable regardless of algorithm, except perhaps this:

If the DCID is not understood by the LB, the LB chooses a random target server but does not store any state. The expectation being that the server will assign its own DCID on the return path.

The LB will understand how to route the server assigned DCID. The problem being that this generally requires shared state - which Low-Config aims to avoid in exchange of local state.

Perhaps there is a middleground where initial packets are routed stateless and semi-randomly, but the server assigned DCID is computed using prime multiplication instead of cryptographic primitives if performance or complexity is a concern.

Note that lookups in Gigabyte tables are likely significantly slower than AES block encryption, especially if AES can be pipelined, due to memory access latency. Therefore I would not expect the proposed Low-Config solution to be faster for heavily loaded loadbalancers, especially under attack.

Mikkel

> On 12 Jan 2021, at 00.32, Martin Duke <[email-masked]> wrote:
> 
> Hi Mikkel,
> 
> Answers inline
> 
> On Mon, Jan 11, 2021 at 3:19 PM Mikkel Fahnøe Jørgensen <[email-masked] <mailto:[email-masked]>> wrote:
> In general, client-generated CIDs might come in with config rotation bits that don't correspond to an existing config. For the other algorithms, it's randomly routed and after that the server-generated CID is used. But for this algorithm, the server needs to extract a server ID somehow. If there's one configuration, that's simple. If there's more than one, there has to be deterministic behavior. The choice to use the highest is completely arbitrary; I'm open to other suggestions that have better properties.
>  
> No, any 8-byte CID will contain a server ID. So the client, in effect, generates an SID and the load balancer decides which server will get it (and then use that SID in the future)
>   
> Yes, if CIDs are chosen to maximize the number of different SIDs, that will grow the table. IMO this isn't substantially different from randomly chosen CIDs, which is of course normal behavior.
>

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Tue, 12 Jan 2021 01:14:15 +0100

Sorry, the following text is out of context - it was a suggestion that I decided not to persue.

> On 12 Jan 2021, at 01.10, Mikkel Fahnøe Jørgensen <[email-masked]> wrote:
>

---

From: Christian Huitema <[email-masked]>
Date: Mon, 11 Jan 2021 16:52:25 -0800

I am looking at the text of section 4.2, and I am not sure how I would 
implement that. What should be the value of the config rotation bits in 
CID created by the server? Should the 6 other bits in the first octet be 
set to a CID Len or to a random value? Is the timer set when the server 
ID is first added to the table, or is the timer reset each time a packet 
is received with that CID? In the latter case, is it reset when any 
packet is received, or only when a "first initial" packet is received?

-- Christian Huitema

On 1/11/2021 4:14 PM, Mikkel Fahnøe Jørgensen wrote:
>> On 12 Jan 2021, at 01.10, Mikkel Fahnøe Jørgensen <[email-masked] 
>> <mailto:[email-masked]>> wrote:
>>
>> If the DCID is not understood by the LB, the LB chooses a random 
>> target server but does not store any state. The expectation being 
>> that the server will assign its own DCID on the return path.
>>
>> The LB will understand how to route the server assigned DCID. The 
>> problem being that this generally requires shared state - which 
>> Low-Config aims to avoid in exchange of local state.
>>
>

---

From: Martin Duke <[email-masked]>
Date: Mon, 11 Jan 2021 17:22:44 -0800

Perhaps I should make some edits for clarity!

On Mon, Jan 11, 2021, 16:52 Christian Huitema <[email-masked]> wrote:

> implement that. What should be the value of the config rotation bits in CID
> created by the server?
>
Any config includes the corresponding CR bits, and when generating the CID
it would use those bits.

The confusing part is that, for this algorithm, a usable SID has to be
extracted from any CID, hence all the weird stuff about CIDs with undefined
configs.

Aside from that, it's like PCID: any server-generated CID uses the CR bits
in the config, optional length encoding, SID, server-use octets.

Should the 6 other bits in the first octet be set to a CID Len or to a
> random value?
It depends on the rest of the config, as with the other algorithms.

> Issss the timer set when the server ID is first added to the table, or is
> the timer reset each time a packet is received with that CID? In the latter
> case, is it reset when any packet is received, or only when a "first
> initial" packet is received?
>
When any packet is received with that SID (not CID), the expiration is
refreshed.

> If the DCID is not understood by the LB, the LB chooses a random target
> server but does not store any state. The expectation being that the server
> will assign its own DCID on the return path.
>
> The LB will understand how to route the server assigned DCID. The problem
> being that this generally requires shared state - which Low-Config aims to
> avoid in exchange of local state.
>
>
>

---

From: Martin Duke <[email-masked]>
Date: Mon, 11 Jan 2021 17:26:47 -0800

Re: DDoS

For this to be a new DDoS vector, the lookup has to be more expensive than
a crypto algorithm. Ian says it isn't; a binary search would be on the
order of (bits) operations, no?

On Mon, Jan 11, 2021, 16:10 Mikkel Fahnøe Jørgensen <[email-masked]>
wrote:

> I was reading over the text several more times and I slowly came to the
> same conclusion as you have explained below.
>
> So the problem with state table is if you send a lot of small random
> garbage packets to the LB. It’s probably expensive for one endpoint, but
> easy to DDOS.
>
> The other problem is sending a lot of the same packet to DDOS a target
> server, but that is probably unavoidable regardless of algorithm, except
> perhaps this:
>
> Perhaps there is a middleground where initial packets are routed stateless
> and semi-randomly, but the server assigned DCID is computed using prime
> multiplication instead of cryptographic primitives if performance or
> complexity is a concern.
>
> Note that lookups in Gigabyte tables are likely significantly slower than
> AES block encryption, especially if AES can be pipelined, due to memory
> access latency. Therefore I would not expect the proposed Low-Config
> solution to be faster for heavily loaded loadbalancers, especially under
> attack.
>
> Mikkel
>
>
> On Mon, Jan 11, 2021 at 3:19 PM Mikkel Fahnøe Jørgensen <
> [email-masked]> wrote:
>
>> Also, I do not understand how the server receives the assigned SID. Is
>> the ODCID replaced in first packets, or are the packets unmodified, or is
>> the SID prefixed the real packet?
>>
>
> Yes, if CIDs are chosen to maximize the number of different SIDs, that
> will grow the table. IMO this isn't substantially different from randomly
> chosen CIDs, which is of course normal behavior.
>
>
>

---

From: Christian Huitema <[email-masked]>
Date: Mon, 11 Jan 2021 17:53:53 -0800

On 1/11/2021 5:22 PM, Martin Duke wrote:
> On Mon, Jan 11, 2021, 16:52 Christian Huitema <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     I am looking at the text of section 4.2, and I am not sure how I
>     would implement that. What should be the value of the config
>     rotation bits in CID created by the server?
>
> Any config includes the corresponding CR bits, and when generating the 
> CID it would use those bits.
>
> extracted from any CID, hence all the weird stuff about CIDs with 
> undefined configs.
>
> Aside from that, it's like PCID: any server-generated CID uses the CR 
> bits in the config, optional length encoding, SID, server-use octets.
>
>     Should the 6 other bits in the first octet be set to a CID Len or
>     to a random value?
>
>     Issss the timer set when the server ID is first added to the
>     table, or is the timer reset each time a packet is received with
>     that CID? In the latter case, is it reset when any packet is
>     received, or only when a "first initial" packet is received?
>

OK. So we can have the following:

1) Server learns of Server-ID = X.

2) Server creates new CID with that server ID, uses it to complete 
handshake.

3) Client maintains a long running connection with that CID.

4) Server keeps receiving messages with CID pointing to server-ID = X

5) server-ID=X never expires.

Is that by design?

-- Christian Huitema

---

From: Martin Duke <[email-masked]>
Date: Mon, 11 Jan 2021 18:50:34 -0800

Yes. Do you have an alternate suggestion?

---

From: Martin Duke <[email-masked]>
Date: Fri, 15 Jan 2021 12:04:34 -0800

To muddy this discussion a little further, after a little more thinking I
believe there's a way to generalize this approach to all three of the
original algorithms, encrypted or unencrypted, so there is never a need to
manually allocate server IDs.

Again, the main tradeoff here is simpler configuration vs. more complexity
and state at the load balancer.

As a document organization matter, rather than have six different
algorithms I would prefer to specify three with a separate section
describing the two separate ways to allocate a server ID.

But it is not too late to yell "stop" at this multiplicity of options if
people feel the tradeoffs are clear-cut in one way or the other.

On Mon, Jan 11, 2021 at 6:50 PM Martin Duke <[email-masked]> wrote:

>>> Issss the timer set when the server ID is first added to the table, or
>>> is the timer reset each time a packet is received with that CID? In the
>>> latter case, is it reset when any packet is received, or only when a "first

---

From: Nick Banks <[email-masked]>
Date: Fri, 15 Jan 2021 20:11:15 +0000

I also would at least explore a generalized approach before solidifying the current designs.

Thanks,
- Nick

Sent from Outlook<http://aka.ms/weboutlook>

________________________________
From: QUIC <[email-masked]> on behalf of Martin Duke <[email-masked]>
Sent: Friday, January 15, 2021 12:04 PM
To: Christian Huitema <[email-masked]>
Cc: IETF QUIC WG <[email-masked]>
Subject: Re: New Plaintext QUIC-LB Design

To muddy this discussion a little further, after a little more thinking I believe there's a way to generalize this approach to all three of the original algorithms, encrypted or unencrypted, so there is never a need to manually allocate server IDs.

Again, the main tradeoff here is simpler configuration vs. more complexity and state at the load balancer.

As a document organization matter, rather than have six different algorithms I would prefer to specify three with a separate section describing the two separate ways to allocate a server ID.

But it is not too late to yell "stop" at this multiplicity of options if people feel the tradeoffs are clear-cut in one way or the other.

On Mon, Jan 11, 2021 at 6:50 PM Martin Duke <[email-masked]<mailto:[email-masked]>> wrote:
Yes. Do you have an alternate suggestion?

On Mon, Jan 11, 2021 at 5:54 PM Christian Huitema <[email-masked]<mailto:[email-masked]>> wrote:

On Mon, Jan 11, 2021, 16:52 Christian Huitema <[email-masked]<mailto:[email-masked]>> wrote:

I am looking at the text of section 4.2, and I am not sure how I would implement that. What should be the value of the config rotation bits in CID created by the server?

Any config includes the corresponding CR bits, and when generating the CID it would use those bits.

The confusing part is that, for this algorithm, a usable SID has to be extracted from any CID, hence all the weird stuff about CIDs with undefined configs.

Aside from that, it's like PCID: any server-generated CID uses the CR bits in the config, optional length encoding, SID, server-use octets.

Should the 6 other bits in the first octet be set to a CID Len or to a random value?

Issss the timer set when the server ID is first added to the table, or is the timer reset each time a packet is received with that CID? In the latter case, is it reset when any packet is received, or only when a "first initial" packet is received?

When any packet is received with that SID (not CID), the expiration is refreshed.

2) Server creates new CID with that server ID, uses it to complete handshake.

Is that by design?

-- Christian Huitema

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Fri, 15 Jan 2021 21:18:04 +0100

I would be hesitant to introduce a situation where a load balancer is forced to use memory, especially memory it doesn’t fully control. It may be fine as a choice, but not the only choice.

Aside from potential attacks, there is also the hardware cost/complexity. SHA256 and AES is pretty standard in almost anything, but lots of RAM is a cost driver.

It is really hard to estimate crypto vs lookup overhead, but it is far from a given that lookup will be faster once the tables grow large.

Less coordination is a good thing though. I’m afraid that without out of band payload to coordinate, there will have to be a choice between configuration and state.

Mikkel

> On 15 Jan 2021, at 21.04, Martin Duke <[email-masked]> wrote:
> 
> On Mon, Jan 11, 2021 at 6:50 PM Martin Duke <[email-masked] <mailto:[email-masked]>> wrote:
> On Mon, Jan 11, 2021 at 5:54 PM Christian Huitema <[email-masked] <mailto:[email-masked]>> wrote:
> 
> 
>> On Mon, Jan 11, 2021, 16:52 Christian Huitema <[email-masked] <mailto:[email-masked]>> wrote:

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Fri, 15 Jan 2021 21:25:58 +0100

There is also

https://en.wikipedia.org/wiki/Rendezvous_hashing <https://en.wikipedia.org/wiki/Rendezvous_hashing>

> On 15 Jan 2021, at 21.18, Mikkel Fahnøe Jørgensen <[email-masked]> wrote:
> 
>> On 15 Jan 2021, at 21.04, Martin Duke <[email-masked] <mailto:[email-masked]>> wrote:
>>

---

From: Martin Duke <[email-masked]>
Date: Fri, 15 Jan 2021 17:09:35 -0800

I've been playing with Ian's algorithm (specifically, the way I had to
modify it to fit into the QUIC-LB framework) and filed an issue.

https://github.com/quicwg/load-balancers/issues/84

This is very long and hard to reason about, but the upshot is there are
significant problems and without some clever design I'm not sure how to
make this work.

On Fri, Jan 15, 2021 at 12:26 PM Mikkel Fahnøe Jørgensen <[email-masked]>
wrote:

> There is also
>
> https://en.wikipedia.org/wiki/Rendezvous_hashing
>
>
> I would be hesitant to introduce a situation where a load balancer is
> forced to use memory, especially memory it doesn’t fully control. It may be
> fine as a choice, but not the only choice.
>
> Aside from potential attacks, there is also the hardware cost/complexity.
> SHA256 and AES is pretty standard in almost anything, but lots of RAM is a
> cost driver.
>
> It is really hard to estimate crypto vs lookup overhead, but it is far
> from a given that lookup will be faster once the tables grow large.
>
> Less coordination is a good thing though. I’m afraid that without out of
> band payload to coordinate, there will have to be a choice between
> configuration and state.
>
> Mikkel
>

---

From: Behcet Sarikaya <[email-masked]>
Date: Mon, 18 Jan 2021 10:04:30 -0600

Hi Martin,

> modify it to fit into the QUIC-LB framework) and filed an issue.

What is QUIC-LB?

Is it public domain?

Behcet

> On Fri, Jan 15, 2021 at 12:26 PM Mikkel Fahnøe Jørgensen <
>> Again, the main tradeoff here is simpler configuration vs. more
>> complexity and state at the load balancer.
>>

---

From: Martin Duke <[email-masked]>
Date: Sun, 24 Jan 2021 14:17:48 -0800

Hi Behcet,

QUIC-LB is QUIC Load Balancers, the draft we've been talking about this
whole time:
https://datatracker.ietf.org/doc/draft-ietf-quic-load-balancers/

On Mon, Jan 18, 2021 at 8:04 AM Behcet Sarikaya <[email-masked]>
wrote:

>>> Aside from potential attacks, there is also the hardware
>>> cost/complexity. SHA256 and AES is pretty standard in almost anything, but
>>> lots of RAM is a cost driver.
>>>
>>> To muddy this discussion a little further, after a little more thinking
>>> I believe there's a way to generalize this approach to all three of the
>>>>>> would implement that. What should be the value of the config rotation bits
>>>>>> in CID created by the server?
>>>>>>
>>>>>> Issss the timer set when the server ID is first added to the table,
>>>>>> or is the timer reset each time a packet is received with that CID? In the