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