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

Stephen Hemminger stephen at networkplumber.org
Mon Nov 26 23:08:05 EST 2018

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.

More information about the Codel mailing list