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

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

[Dave Taht]

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.

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.

Algo needs to be fast and lock free, relying only on a very few atomic
increment and/or swaps, only in rare cases...

On most networks today, you are usually talking to a VERY few
machines. The number of machines that appear and disappear is rather
small and stable over very long periods of time (proof: go type arp -a
on your home network)

Yet mac addresses are 48 bits wide.

Even in the case of an access point, you are never going to see more
than 2048 of them, and most APs stop at around 127 stations, and most
wireless networks have many fewer endpoints than that...

So great, I figure a mere 2 bin table lookup and random replacement
will work fine, I stuck my first attempt up at
http://www.teklibre.com/~d/mactoclass.c

and I hate it. Didn't get so far as writing garbage collection.
(double buffer it) Does anything elegant exist? Anything worthy in the
kernel?

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

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

[Sean Conner]

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?)

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

[Fred Baker]

On Nov 14, 2011, at 10:22 AM, Sean Conner wrote:

>  Why not just use the lower N bits as the hash function?

or

unsigned macHash (unsigned long long  macAddressClone) {
     return 0xFFF & (macAddressClone ^ (macAddressClone >> 12));
}

That allows you to keep different OUIs separated somewhat.

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

[Dave Taht]

On Mon, Nov 14, 2011 at 3:41 AM, Fred Baker <fred@cisco.com> wrote:
>
> On Nov 14, 2011, at 10:22 AM, Sean Conner wrote:
>
>>  Why not just use the lower N bits as the hash function?
>
> or
>
> unsigned macHash (unsigned long long  macAddressClone) {
>     return 0xFFF & (macAddressClone ^ (macAddressClone >> 12));
> }
>
> That allows you to keep different OUIs separated somewhat.

I should probably not have used 'arp' as an example, but suggested tcpdump.

Multicast and broadcast on 802.11 are 'special'. They are always
transmitted at the lowest rate possible (and eat up correspondingly
far more airtime), and in the case of power save mode, can be deferred
up to 200 ms, to wait for stations to be awake enough to 'hear' them.
So anything with the multicast mac bit set should end up dumped in a
special queue to manage that better.

Virtual interfaces on a given radio twiddle on the local mac bit and
then do arbitrary transforms elsewhere on the mac

> _______________________________________________
> 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

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

[Sean Conner]

It was thus said that the Great Dave Taht once stated:
> On Mon, Nov 14, 2011 at 3:41 AM, Fred Baker <fred@cisco.com> wrote:
> >
> > On Nov 14, 2011, at 10:22 AM, Sean Conner wrote:
> >
> >>  Why not just use the lower N bits as the hash function?
> >
> > or
> >
> > unsigned macHash (unsigned long long  macAddressClone) {
> >     return 0xFFF & (macAddressClone ^ (macAddressClone >> 12));
> > }
> >
> > That allows you to keep different OUIs separated somewhat.
> 
> I should probably not have used 'arp' as an example, but suggested tcpdump.
> 
> Multicast and broadcast on 802.11 are 'special'. They are always
> transmitted at the lowest rate possible (and eat up correspondingly
> far more airtime), and in the case of power save mode, can be deferred
> up to 200 ms, to wait for stations to be awake enough to 'hear' them.
> So anything with the multicast mac bit set should end up dumped in a
> special queue to manage that better.
> 
> Virtual interfaces on a given radio twiddle on the local mac bit and
> then do arbitrary transforms elsewhere on the mac

  The format for a MAC address is:

+--------+--------+--------+--------+--------+--------+
|      lg|        |        |        |        |        |
+--------+--------+--------+--------+--------+--------+
\______||____OUI___________/
       ||
       |+-- group/individual bit (1 = multicast/broadcast)
       +--- global/local assigned address (1 = local)

Given that, I would then write the hash code as:

typdef union macaddr
{
  uint8_t  bit8[6];
  uint16_t bit16[3];
} macaddr__t;

typedef enum macqueue
{
  MACQ_NORMAL,
  MACQ_SPECIAL
} macqueue__t;

macqueue__t mac_hash(unsigned int *phash,macaddr__t addr)
{
  *phash = addr.bit16[2] & 0x0FFF;
  if (addr.bit8[0] & 0x01)
    return MACQ_SPECIAL;
  else
    return MACQ_NORMAL;
  /*------------
  ; if I was very concerned with speed, I would do:
  ;     return addr.bit8[0] & 0x01;
  ; but I opted for clarity here, not speed
  ;---------------*/
}

The broadcast MAC address is FF:FF:FF:FF:FF:FF while a multicast MAC address
is based off the IP multicast address, but the global bit is set, for
example: 01:00:5E:7F:00:01.  This way, if you want to set
broadcasts/multicasts on their own special queue, you can (heck, you can
even have a separate hash table for them given this).  I don't see how
locally defined addresses will mess this up, unless I see actual, real world
evidence.  

  -spc (Measure twice, cut once and all that ... )

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

[Dave Taht]

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

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

[Sean Conner]

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.

  -spc

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

[Jonathan Morton]

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.

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

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

[Dave Taht]

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;
}


>
> 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

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

[Dave Taht]

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

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

[Sean Conner]

It was thus said that the Great Dave Taht once stated:
> On Mon, Nov 14, 2011 at 3:41 AM, Fred Baker <fred@cisco.com> wrote:
> >
> > On Nov 14, 2011, at 10:22 AM, Sean Conner wrote:
> >
> >> �Why not just use the lower N bits as the hash function?
> >
> > or
> >
> > unsigned macHash (unsigned long long �macAddressClone) {
> > � � return 0xFFF & (macAddressClone ^ (macAddressClone >> 12));
> > }
> >
> > That allows you to keep different OUIs separated somewhat.
> 
> I should probably not have used 'arp' as an example, but suggested tcpdump.
> 
> Multicast and broadcast on 802.11 are 'special'. They are always
> transmitted at the lowest rate possible (and eat up correspondingly
> far more airtime), and in the case of power save mode, can be deferred
> up to 200 ms, to wait for stations to be awake enough to 'hear' them.
> So anything with the multicast mac bit set should end up dumped in a
> special queue to manage that better.
> 
> Virtual interfaces on a given radio twiddle on the local mac bit and
> then do arbitrary transforms elsewhere on the mac

  The format for a MAC address is:

+--------+--------+--------+--------+--------+--------+
|      lg|        |        |        |        |        |
+--------+--------+--------+--------+--------+--------+
\______||____OUI___________/
       ||
       |+-- group/individual bit (1 = multicast/broadcast)
       +--- global/local assigned address (1 = local)

Given that, I would then write the hash code as:

typdef union macaddr
{
  uint8_t  bit8[6];
  uint16_t bit16[3];
} macaddr__t;

typedef enum macqueue
{
  MACQ_NORMAL,
  MACQ_SPECIAL
} macqueue__t;

macqueue__t mac_hash(unsigned int *phash,macaddr__t addr)
{
  *phash = addr.bit16[2] & 0x0FFF;
  if (addr.bit8[0] & 0x01)
    return MACQ_SPECIAL;
  else
    return MACQ_NORMAL;
  /*------------
  ; if I was very concerned with speed, I would do:
  ;     return addr.bit8[0] & 0x01;
  ; but I opted for clarity here, not speed
  ;---------------*/
}

The broadcast MAC address is FF:FF:FF:FF:FF:FF while a multicast MAC address
is based off the IP multicast address, but the global bit is set, for
example: 01:00:5E:7F:00:01.  This way, if you want to set
broadcasts/multicasts on their own special queue, you can (heck, you can
even have a separate hash table for them given this).  I don't see how
locally defined addresses will mess this up, unless I see actual, real world
evidence.  

  -spc (Measure twice, cut once and all that ... )