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

[Dave Taht <dave.taht@gmail.com>]

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