Subject: Fibonaccing CID lengths

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 22 May 2019 10:12:39 -0400

Idea: we can keep the one-byte SCIDL/DCIDL field but map the 4-bit
parts to a larger range of values.  For example, we could map the
16 values to a range of Fibonacci numbers:

    0   ->  0
    1   ->  1
    2   ->  2
    3   ->  3
    4   ->  5
    5   ->  8
    6   ->  13
    7   ->  21
    8   ->  34
    9   ->  55
    10  ->  89
    11  ->  144
    12  ->  233
    13  ->  377
    14  ->  610
    15  ->  987

This particular mapping has several profitable properties:

    - It covers the whole range of values from zero to the
      practical maximum imposed by the protocol (about 1K).

    - There is a good selection of small values.

    - 8 is one of the values, convenient for storage in
      uint64_t.

    - Each step up is not too large (double or more) or too
      small (less than 50% increase).

    - The mapping can be easily generated: its name says how.

  - Dmitri.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Wed, 22 May 2019 12:10:44 -0400

Another benefit: I get to use Fibonachi numbers again :)

But, it would arbitrarily consume more bandwidth than necessary, much more
than what is saved in a single byte SCIL/DCIL field.

If we keep the recenlty proposes 1 byte DCIL  and 1 byte SCIL fields we
have 0..255 bytes.
If we need more without the complexity of varints that are bad for hardware
and fast routing in general, we could make all lengths <= 127 single byte
multiples, and all above 127 8 byte multiples. That gives you 2K of routing
bits and is stil easy to decode in hardware.

On 22 May 2019 at 16.13.07, Dmitri Tikhonov ([email-masked])
wrote:

0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 5
5 -> 8
6 -> 13
7 -> 21
8 -> 34
9 -> 55
10 -> 89
11 -> 144
12 -> 233
13 -> 377
14 -> 610
15 -> 987

- Dmitri.

---

From: Christian Huitema <[email-masked]>
Date: Wed, 22 May 2019 10:19:38 -0700

On 5/22/2019 9:10 AM, Mikkel Fahnøe Jørgensen wrote:
> But, it would arbitrarily consume more bandwidth than necessary, much
> more than what is saved in a single byte SCIL/DCIL field.
>
> If we keep the recenlty proposes 1 byte DCIL  and 1 byte SCIL fields
> we have 0..255 bytes.
> If we need more without the complexity of varints that are bad for
> hardware and fast routing in general, we could make all lengths <= 127
> single byte multiples, and all above 127 8 byte multiples. That gives
> you 2K of routing bits and is stil easy to decode in hardware.
>
>
> On 22 May 2019 at 16.13.07, Dmitri Tikhonov
> ([email-masked] <mailto:[email-masked]>) wrote:
>

Hey, wait a minute. Doesn't the Fibonacci sequence start by 1,1,2,3? Why
do you have a zero there?

>> - The mapping can be easily generated: its name says how.

Yes, that looks like a proposal that we should seriously consider.

-- Christian Huitema

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 22 May 2019 16:04:07 -0400

> Yes, that looks like a proposal that we should seriously consider.

While the example is lighthearted, the proposal is serious: that is,
remap 0 - 15 values of the nybble to a different set.  Do we need to
represent every intermediate number between 0 and 48 (the maximum of
the current PR)?

What if instead we do the following:

     0 -> 0
     1 -> 1
     2 -> 2
     3 -> 3
     4 -> 4
     5 -> 6
     6 -> 8
     7 -> 12
     8 -> 16
     9 -> 20
     10 -> 24
     11 -> 28
     12 -> 32
     13 -> 40
     14 -> 48
     15 -> 64

This is as valid an approach as encoding the length in 8 bits and
having to deal with invalid values or using a varint and having
to deal with even more invalid values.

  - Dmitri.

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 23 May 2019 04:36:54 +0100

> represent every intermediate number between 0 and 48 (the maximum of

The question is what you gain by compressing the length to 4 bits.

I'd argue that the downside of compression is that endpoints would be
required to use a CID that is longer than necessary. For example, if
we are to allow only CID length of even-number bytes, there would be
in average one byte (8-bit) overhead per CID. That dwarfs the benefit
of saving 4-bit in the length of the CIDL field.

While I think using a 4-bit CIDL field could be beneficial for
avoiding ossification, I think I might agree with Martin Duke that
CIDL is currently an invariant that we are happy to accept
ossification.

So, what's the benefit?

-- 
Kazuho Oku

---

From: Roberto Peon <[email-masked]>
Date: Thu, 23 May 2019 05:07:48 +0000

I'd be fibbing if I said I liked the encoding proposal.
A byte seems to offer enough range of possibilities that we are wanting to constrain them ready.

How about we simply assert for all bit-patterns who represent values <= the intended max, they mean what you'd naively expect?
This doesn't imply a linear mapping or any mapping for values in excess of max
-=R

From: Kazuho Oku
Sent: Thursday, May 23, 4:37 AM
Subject: Re: Fibonaccing CID lengths
To: Christian Huitema, Mikkel Fahnøe Jørgensen, IETF QUIC WG

So, what's the benefit?

--
Kazuho Oku

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 23 May 2019 04:21:30 -0400

> The question is what you gain by compressing the length to 4 bits.
----- 8< --- 8< --- 8< ---
> So, what's the benefit?

Smaller change to the drafts -- and existing code.

  - Dmitri.

---

From: David Schinazi <[email-masked]>
Date: Thu, 23 May 2019 16:08:16 +0100

This encoding would be harder to deploy on our servers than having two
8-bit lengths. The only benefit of this is saving 8 bits on long headers,
and that's not worth the complexity.

---

From: Marten Seemann <[email-masked]>
Date: Thu, 23 May 2019 16:13:39 +0100

Using an 8-bit encoding would also prevent ossification of the first two
bits of each connection ID length field. These bits would always be 0 (in
QUIC v1), since connection ID lengths above 48 can never occur.

On Thu, May 23, 2019 at 4:08 PM David Schinazi <[email-masked]>
wrote:

> On Thu, May 23, 2019 at 9:21 AM Dmitri Tikhonov <
> [email-masked]> wrote:
>

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 23 May 2019 08:18:00 -0700

I’m all for the 8 bit lengths, but I don’t see how they prevent
ossification of the first two bits?

Regardless this kind of ossification is not important since middle boxes
will lock down on CID lengths they support and mistreat other lengths. The
length field is just one part of this.

On 23 May 2019 at 17.13.51, Marten Seemann ([email-masked]) wrote:

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 24 May 2019 08:55:58 -0400

> ossification of the first two bits?

I believe Marten meant 8-bit encoding for both DCID and SCID length,
just like what we have now.  In the 4-bits-per-length scheme, it is
likely that no single bit will be found to always have a particular
value.  This would prevent ossification.

  - Dmitri.

---

From: Christian Huitema <[email-masked]>
Date: Fri, 24 May 2019 20:11:51 -0700

> value.  This would prevent ossification.

The current format of the long header encodes two lengths in one byte,
followed by the Dest CID and the Source CID. The proposal that got
consensus in London is to replace that by one byte of length of DCID,
DCID, one byte of SCID, SCID. The general agreement is that given the
usage of the long header, it is not necessary to compress the length field.

This would be a change in the invariants. Ossification of the format is
not really a concern. By definition, the invariants are supposed to
ossify. But there is an ossification risk for the actual length.

As far as V1 is concerned, we agreed to limit the actual length to less
than 64 bytes. The two most significant bits of the two length fields
will be zero, so there is a possibility that middle-boxes will use that
to detect whether a packet is using QUIC. The risk there is that this
would prevent future versions from using CID lengths larger than 64 bytes.

-- Christian Huitema