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

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

On Tue, Nov 15, 2011 at 11:19 PM, Dave Taht <dave.taht@gmail.com> wrote:
> On Tue, Nov 15, 2011 at 10:44 PM, Jonathan Morton <chromatix99@gmail.com> wrote:
>>
>> On 15 Nov, 2011, at 11:14 pm, Sean Conner wrote:
>>
>>> It was thus said that the Great Dave Taht once stated:
>>>>
>>>> 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.
>>>
>>>  More on this.  Now that I'm at the office, I can scan a larger selection
>>> of MAC addresses.  Out of the 38 machines currently on the segment, the
>>> lower twelve bits of each MAC addresses are unique (this excluding broadcast
>>> and multicast MAC addresses).
>>>
>>>> Does anything elegant exist? Anything worthy in the kernel?
>>>
>>>  For non-broadcast/multicast MAC addresses, take the last N bits.
>>
>> For 16 bits, the birthday theorem predicts a 50% chance of at least one collision when there are 256 hosts.  Dave wants to scale up to 2048 hosts.  So consider the following:
>>
>> uint32_t upper = (mac >> 16) & MASK;
>> uint16_t hash = 0xFFFF & (mac ^ ((upper << X)|(upper >> (32-X))) ^ ((upper << Y)|(upper >> (32-Y))));
>>
>> When a collision is detected on a new MAC, X and Y can be searched in the 0..31 space for a combination with minimal collisions (probably zero).  When X and Y are equal, that is equivalent to taking the bottom 16 bits.  The rotate operations are usually compiled to single instructions on modern CPUs and halfway competent compilers, and the available unique combinations of X and Y are normally over 490, giving a fairly good defence against the birthday theorem.
>
> Heh. This is getting to be fun. I note multicast/broadcast will be
> filtered out entirely before it hits this stage.
>
> So the hash collision detection stage happens in the downstream queue,
> where all it knows about is the current mac, and the previous mac.
>
> psueudocode:
>
> queue[mortonhash(skb->mac) % 2048];
>
> if (skb->current_mac != q->prev_mac) {
>   if(m->permuted != q->permuted) {
> q->permuted = m->permuted;
> }

Aggh, didn't finish writing that yet, hit send by accident, pls
ignore. State machine needs mental work...

>
>>
>> Of course, some of the 16-bit subsets of the MAC probably have low entropy, especially if an organisation has bought a lot of network hardware from the same vendor, but hopefully that doesn't matter in practice.
>>
>>  - Jonathan Morton
>>
>> _______________________________________________
>> 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
>



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