[Bloat] [Codel] found another good use for a queue today, possibly

[Dave Taht]

Jonathan Morton <chromatix99 at gmail.com> writes:

>>> "polylog(n)-wise Independent Hash Function". OK, my google-foo fails
>>> me: The authors use sha1, would something lighter weight suit?
>
>> The current favorite in DPDK land seems to be Cuckoo hashing.
>> It has better cache behavior than typical chaining.
>
> That paper describes an improved variant of cuckoo hashing, using a
> queue to help resolve collisions with better time complexity.  The
> proof relies on (among other things) a particular grade of hash
> function being used.  SHA1 is described as being suitable since it
> offers cryptographic-level performance… We actually need two hashes
> with independent behaviour on the same input, one for each table.
>
> If we were to assume table sizes up to 64K, using both halves of a
> good 32-bit hash might be suitable.  It may be that plain old Jenkins
> hash would work in that context.  Supplement that with a 64-entry
> queue with linear search (in software) or constant-time CAM search (in
> hardware).

I was aiming for 2million routes.

I gave up trying to wade through it and pinged the authors.

fiddling with blake at the moment

>
>  - Jonathan Morton
>
> _______________________________________________
> Codel mailing list
> Codel at lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel