[Bloat] 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?

[Stephen Hemminger]

On Mon, 26 Nov 2018 18:17:32 -0800

Post by 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?

The current favorite in DPDK land seems to be Cuckoo hashing.
It has better cache behavior than typical chaining.

[Jonathan Morton]

Post by Stephen Hemminger

Post by Dave Taht
"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

[Dave Taht]

Post by Jonathan Morton

Post by Stephen Hemminger

Post by Dave Taht
"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

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