Re: Fibonaccing CID lengths

[Kazuho Oku <[e-mail]>]

2019年5月22日(水) 21:04 Dmitri Tikhonov <[e-mail]>:
>
> On Wed, May 22, 2019 at 10:19:38AM -0700, Christian Huitema wrote:
> > 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)?

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?

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


-- 
Kazuho Oku