From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-bw0-f43.google.com (mail-bw0-f43.google.com [209.85.214.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 CC266200762 for ; Tue, 15 Nov 2011 13:44:30 -0800 (PST) Received: by bkbzt12 with SMTP id zt12so13546726bkb.16 for ; Tue, 15 Nov 2011 13:44:28 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=subject:mime-version:content-type:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to:x-mailer; bh=cux8ePIQ8uZ4T8LEjeTv1Z0ekZx9uzwz6yOgH61UPaE=; b=ax8/KoH5FqyFpRVlwB7L+btdUEjdWXi/gK/j7BKdSDEdkYvUUUHl1Yl0xbSVntMR4d n/sAsLlVYOK9u/ZAKLGmu/lr+hym/Upjz11WwsgDmPTxSJmFdwtdn5mxTyK/smkI7CDC sbxFoijJAK8Yw/Q5N0RSu0ot8EzfnsQ0WU8h8= Received: by 10.205.130.133 with SMTP id hm5mr21448140bkc.41.1321393468330; Tue, 15 Nov 2011 13:44:28 -0800 (PST) Received: from [192.168.239.42] (xdsl-83-150-84-172.nebulazone.fi. [83.150.84.172]) by mx.google.com with ESMTPS id n19sm5605127bka.0.2011.11.15.13.44.26 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 15 Nov 2011 13:44:27 -0800 (PST) Subject: Re: A tiny almost sorta kinda nearly minimal perfect hash for a mac classifier? Mime-Version: 1.0 (Apple Message framework v1084) Content-Type: text/plain; charset=us-ascii From: Jonathan Morton In-Reply-To: <20111115211416.GA12236@brevard.conman.org> Date: Tue, 15 Nov 2011 23:44:25 +0200 Content-Transfer-Encoding: quoted-printable Message-Id: <3879FC19-038C-49FB-9C83-6D2F1EFCE56A@gmail.com> References: <20111115211416.GA12236@brevard.conman.org> To: Sean Conner X-Mailer: Apple Mail (2.1084) 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 21:44:31 -0000 On 15 Nov, 2011, at 11:14 pm, Sean Conner wrote: > It was thus said that the Great Dave Taht once stated: >>=20 >> 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. >=20 > 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). =20 >=20 >> Does anything elegant exist? Anything worthy in the kernel? >=20 > 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 =3D (mac >> 16) & MASK; uint16_t hash =3D 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