A tiny almost sorta kinda nearly minimal perfect hash for a mac classifier?
Sean Conner
sean at conman.org
Sun Nov 13 21:22:10 EST 2011
It was thus said that the Great Dave Taht once stated:
> There's this class of non-algorithms where stupid and brute force
> nearly works. Then there are the be-all end-all algorithms which scale
> beautifully O(1) over n - so long as n is large enough to wipe out the
> overhead of the be-all-end-all algorithm, and taking locks, allocating
> memory at bad times, etc, is ok.
>
> I keep running into problems where brute force and a simple table
> lookup is almost enough.
>
> Here's one. I'd like to classify network streams so that they end up
> in a unique queue[x], based on their nexthop mac address in the ip
> header.
I've checked my home network, and the network of a small webhosting
company I do work for, and in both cases, the MAC addresses were all unique
in the lower 10-12 bits, which is understandable given that's the portion of
the MAC address vendors control.
Why not just use the lower N bits as the hash function?
-spc (Or am I missing something?)
More information about the Bloat-devel
mailing list