From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from brevard.conman.org (brevard.conman.org [66.252.224.242]) by huchra.bufferbloat.net (Postfix) with ESMTP id 811E4200B10 for ; Sun, 13 Nov 2011 18:22:12 -0800 (PST) Received: by brevard.conman.org (Postfix, from userid 500) id 8C09F2EBD517; Sun, 13 Nov 2011 21:22:10 -0500 (EST) Date: Sun, 13 Nov 2011 21:22:10 -0500 From: Sean Conner To: bloat-devel@lists.bufferbloat.net Subject: Re: A tiny almost sorta kinda nearly minimal perfect hash for a mac classifier? Message-ID: <20111114022209.GA5769@brevard.conman.org> References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.4.1i 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: Mon, 14 Nov 2011 02:22:12 -0000 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?)