From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-gy0-f171.google.com (mail-gy0-f171.google.com [209.85.160.171]) (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 17231200411 for ; Mon, 14 Nov 2011 00:21:44 -0800 (PST) Received: by gyg8 with SMTP id 8so6814749gyg.16 for ; Mon, 14 Nov 2011 00:21:43 -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=ucU7bLX6/Vxp6/usBJp4Jb52QLOfChHxOupSz/rFrQ8=; b=NSe/4v76dLaLyLLN74q9TLR2wk6RKT6F6Vwri79o0QtcFwNOWKfNFWqB7u9Z/3K9sm y8+9o0Cbk2O0w87b6AG2FsVigW3786pVCqiIGhC6PmI0FPKvJe6JqVA3co316zSt9XD7 VgBcCJ4MdX0gfyWST+B/Zk7aI+LDFhckh54t4= MIME-Version: 1.0 Received: by 10.182.12.66 with SMTP id w2mr1621072obb.7.1321258903080; Mon, 14 Nov 2011 00:21:43 -0800 (PST) Received: by 10.182.15.40 with HTTP; Mon, 14 Nov 2011 00:21:43 -0800 (PST) In-Reply-To: <20111114022209.GA5769@brevard.conman.org> References: <20111114022209.GA5769@brevard.conman.org> Date: Mon, 14 Nov 2011 09:21:43 +0100 Message-ID: Subject: Re: A tiny almost sorta kinda nearly minimal perfect hash for a mac classifier? From: Dave Taht To: Sean Conner 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: Mon, 14 Nov 2011 08:21:44 -0000 On Mon, Nov 14, 2011 at 3:22 AM, Sean Conner 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. > > =A0I'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 uniq= ue > in the lower 10-12 bits, which is understandable given that's the portion= of > the MAC address vendors control. > > =A0Why not just use the lower N bits as the hash function? > > =A0-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 > --=20 Dave T=E4ht SKYPE: davetaht US Tel: 1-239-829-5608 FR Tel: 0638645374 http://www.bufferbloat.net