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 ACD562002EC for ; Tue, 15 Nov 2011 14:19:39 -0800 (PST) Received: by faan24 with SMTP id n24so1651563faa.16 for ; Tue, 15 Nov 2011 14:19: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=tW8JmKtg4LGxWxk53EZv23PBfyep85gga4W15ov9Pm4=; b=mVpFwC3qQg3jPeNjcZpjWzns1MxQVY7fhNNqOweuoh6Fdr9W39Cef2XkdIJq2mUcP2 xOOEjJ9W/qNvLz4BSqMNsIOG+W+MW7BcU8cxs2yGZCbUGeNZCQsM/MsQ+dygpfFnbFJS 08i8/TGMuPthfjpJnpbGywCJ/7SmeW7LyQ8B0= MIME-Version: 1.0 Received: by 10.182.216.105 with SMTP id op9mr6487687obc.57.1321395577202; Tue, 15 Nov 2011 14:19:37 -0800 (PST) Received: by 10.182.15.40 with HTTP; Tue, 15 Nov 2011 14:19:37 -0800 (PST) In-Reply-To: <3879FC19-038C-49FB-9C83-6D2F1EFCE56A@gmail.com> References: <20111115211416.GA12236@brevard.conman.org> <3879FC19-038C-49FB-9C83-6D2F1EFCE56A@gmail.com> Date: Tue, 15 Nov 2011 23:19:37 +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:19:40 -0000 On Tue, Nov 15, 2011 at 10:44 PM, Jonathan Morton w= rote: > > 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 sele= ction >> of MAC addresses. =A0Out of the 38 machines currently on the segment, th= e >> lower twelve bits of each MAC addresses are unique (this excluding broad= cast >> 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 c= ollision 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))) ^ ((up= per << 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). =A0= When X and Y are equal, that is equivalent to taking the bottom 16 bits. = =A0The rotate operations are usually compiled to single instructions on mod= ern CPUs and halfway competent compilers, and the available unique combinat= ions 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 !=3D q->prev_mac) { if(m->permuted !=3D q->permuted) { q->permuted =3D m->permuted; } > > Of course, some of the 16-bit subsets of the MAC probably have low entrop= y, 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 > --=20 Dave T=E4ht SKYPE: davetaht US Tel: 1-239-829-5608 FR Tel: 0638645374 http://www.bufferbloat.net