From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-fx0-f43.google.com (mail-fx0-f43.google.com [209.85.161.43]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id 3D45E2002EC for ; Tue, 15 Nov 2011 14:20:39 -0800 (PST) Received: by faan24 with SMTP id n24so1653179faa.16 for ; Tue, 15 Nov 2011 14:20:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=nGrirLpSczaZxhyQXu2nxjhU6ztu/Ai8hY7KkAvhOlY=; b=grh4C+fi19NhEpS+YFUT41dkNxG/RLwcCOH7l+7S/kon/1jR1AZjlbqVYth2gCouHg dsJX+Z3zTAK0uwjo6pjOkkY9QPU3Ul4pfOgMl7kj5OPCiS6n+Hob2Mpwvp5Z0mdEmNyV TTE602ZfU7HAu9+hSEBgPV9f1jKfdYxAWCga8= MIME-Version: 1.0 Received: by 10.182.222.99 with SMTP id ql3mr6486654obc.67.1321395636942; Tue, 15 Nov 2011 14:20:36 -0800 (PST) Received: by 10.182.15.40 with HTTP; Tue, 15 Nov 2011 14:20:36 -0800 (PST) In-Reply-To: References: <20111115211416.GA12236@brevard.conman.org> <3879FC19-038C-49FB-9C83-6D2F1EFCE56A@gmail.com> Date: Tue, 15 Nov 2011 23:20:36 +0100 Message-ID: Subject: Re: A tiny almost sorta kinda nearly minimal perfect hash for a mac classifier? From: Dave Taht To: Jonathan Morton Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Cc: bloat-devel@lists.bufferbloat.net X-BeenThere: bloat-devel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: "Developers working on AQM, device drivers, and networking stacks" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 15 Nov 2011 22:20:39 -0000 On Tue, Nov 15, 2011 at 11:19 PM, Dave Taht wrote: > On Tue, Nov 15, 2011 at 10:44 PM, Jonathan Morton = 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. >>> >>> =A0More on this. =A0Now that I'm at the office, I can scan a larger sel= ection >>> of MAC addresses. =A0Out of the 38 machines currently on the segment, t= he >>> lower twelve bits of each MAC addresses are unique (this excluding broa= dcast >>> and multicast MAC addresses). >>> >>>> Does anything elegant exist? Anything worthy in the kernel? >>> >>> =A0For 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. =A0Dave wants to scale up to 2048 hosts= . =A0So consider the following: >> >> uint32_t upper =3D (mac >> 16) & MASK; >> uint16_t hash =3D 0xFFFF & (mac ^ ((upper << X)|(upper >> (32-X))) ^ ((u= pper << Y)|(upper >> (32-Y)))); >> >> When a collision is detected on a new MAC, X and Y can be searched in th= e 0..31 space for a combination with minimal collisions (probably zero). = =A0When X and Y are equal, that is equivalent to taking the bottom 16 bits.= =A0The rotate operations are usually compiled to single instructions on mo= dern CPUs and halfway competent compilers, and the available unique combina= tions of X and Y are normally over 490, giving a fairly good defence agains= t 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 !=3D q->prev_mac) { > =A0 if(m->permuted !=3D q->permuted) { > q->permuted =3D 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 entro= py, especially if an organisation has bought a lot of network hardware from= the same vendor, but hopefully that doesn't matter in practice. >> >> =A0- Jonathan Morton >> >> _______________________________________________ >> Bloat-devel mailing list >> Bloat-devel@lists.bufferbloat.net >> https://lists.bufferbloat.net/listinfo/bloat-devel >> > > > > -- > Dave T=E4ht > SKYPE: davetaht > US Tel: 1-239-829-5608 > FR Tel: 0638645374 > http://www.bufferbloat.net > --=20 Dave T=E4ht SKYPE: davetaht US Tel: 1-239-829-5608 FR Tel: 0638645374 http://www.bufferbloat.net