Re: Fibonaccing CID lengths

[Christian Huitema <[e-mail]>]

On 5/22/2019 9:10 AM, Mikkel Fahnøe Jørgensen wrote:
> 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
> ([e-mail] <mailto:[e-mail]>) wrote:
>
>> 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

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

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

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

-- Christian Huitema