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

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

[Dave Taht]

I had been investigating various hashing schemes for speeding up the
babeld routing protocol daemon, and dealing with annoying bursty cpu
behavior (resizing memory, bursts of packets, thundering herds of
retractions), and, although it's a tough slog of a read, this adds a
queue to cuckoo hashing to good effect in flattening out insertion
time.

https://arxiv.org/pdf/0903.0391.pdf

But for all I know it's dependent on angels dancing on saddles mounted
on unicorns. I skip to the graphs for insertion time and go back to
the text for another round...

"polylog(n)-wise Independent Hash Function". OK, my google-foo fails
me: The authors use sha1, would something lighter weight suit?


-- 

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-205-9740

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

[Stephen Hemminger]

On Mon, 26 Nov 2018 18:17:32 -0800
Dave Taht <dave.taht@gmail.com> wrote:

> I had been investigating various hashing schemes for speeding up the
> babeld routing protocol daemon, and dealing with annoying bursty cpu
> behavior (resizing memory, bursts of packets, thundering herds of
> retractions), and, although it's a tough slog of a read, this adds a
> queue to cuckoo hashing to good effect in flattening out insertion
> time.
> 
> https://arxiv.org/pdf/0903.0391.pdf
> 
> But for all I know it's dependent on angels dancing on saddles mounted
> on unicorns. I skip to the graphs for insertion time and go back to
> the text for another round...
> 
> "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.

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

[Jonathan Morton]

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

 - Jonathan Morton

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

[Dave Taht]

Jonathan Morton <chromatix99@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@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel

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

[Dave Taht]

His thesis is more clear:
https://sites.google.com/site/yuriyarbitman/Home/de-amortizedcuckoohashing

He did exclude the cost of a resize, but, still... I find the core
idea very attractive.

We swapped an email and he said:

>   In general, I would say that a cryptographic hash function will do.
>   If you want to use a non-cryptographic hash function, then the
>   question is what provable random properties it has. This is also
>   discussed in the thesis and in the paper.

On Mon, Nov 26, 2018 at 6:17 PM Dave Taht <dave.taht@gmail.com> wrote:
>
> I had been investigating various hashing schemes for speeding up the
> babeld routing protocol daemon, and dealing with annoying bursty cpu
> behavior (resizing memory, bursts of packets, thundering herds of
> retractions), and, although it's a tough slog of a read, this adds a
> queue to cuckoo hashing to good effect in flattening out insertion
> time.
>
> https://arxiv.org/pdf/0903.0391.pdf
>
> But for all I know it's dependent on angels dancing on saddles mounted
> on unicorns. I skip to the graphs for insertion time and go back to
> the text for another round...
>
> "polylog(n)-wise Independent Hash Function". OK, my google-foo fails
> me: The authors use sha1, would something lighter weight suit?
>
>
> --
>
> Dave Täht
> CTO, TekLibre, LLC
> http://www.teklibre.com
> Tel: 1-831-205-9740



-- 

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-205-9740