Re: A tiny almost sorta kinda nearly minimal perfect hash for a mac classifier?

[Dave Taht <dave.taht@gmail.com>]

On Mon, Nov 14, 2011 at 3:22 AM, Sean Conner <sean@conman.org> wrote:
> 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?)


In describing it, I realized that what I mostly wanted to do was toss
the increasingly weighty wireless multicast/broadcast packets into
their own class to be scheduled specially, which is easily done by
checking for that bit first then having the hash... The effects of
hash collisions elsewhere would be less dramatic.

but to continue:

The property I was specifically looking for was:

One of a small number (say, x < 2048) of queues, that needs to be
absolutely unique per mac. It's ok if 99% of the queues
are idle at any given point.

*It's OK if the initial classification collides with another mac so
long as eventually it doesn't*

I'd hate to be the guy with the two machines that are colliding (all
the time), scratching his head as to why.

What I wanted was something that would keep permuting a hash algorithm
over time until it actually became perfect (see for example the cmph
library, which can do this for large static data sets).

>
>
>
> _______________________________________________
> Bloat-devel mailing list
> Bloat-devel@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat-devel
>



-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
FR Tel: 0638645374
http://www.bufferbloat.net