Discussion:
found another good use for a queue today, possibly
Add Reply
Dave Taht
2018-11-27 02:17:32 UTC
Reply
Permalink
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
Stephen Hemminger
2018-11-27 04:08:05 UTC
Reply
Permalink
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
2018-11-27 04:17:19 UTC
Reply
Permalink
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
2018-11-29 04:37:52 UTC
Reply
Permalink
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
Loading...