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