From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-gx0-f171.google.com (mail-gx0-f171.google.com [209.85.161.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 2A0482005F8 for ; Sun, 13 Nov 2011 12:44:00 -0800 (PST) Received: by ggnk1 with SMTP id k1so568205ggn.16 for ; Sun, 13 Nov 2011 12:44:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=OaYEQ6nUThu1kFoC+hAP/LfVT3OB/8/sov0hmgw2PJ8=; b=LK1T5xltlMDBR0/yHXbFihPlmlitSo+izApHACvO921CrZzHvPsvm6HwTI/+pDDO4O zB5ktkXp/aDx9aCrZpgnrR4ljRzsU8/Iok7g4eNBCtt2as3n/IERMjZ11f8MH0FSyniG lEK6ghylJKO9ptsJf6Tt1VRiXzVeVKlIJt424= MIME-Version: 1.0 Received: by 10.182.41.69 with SMTP id d5mr4416761obl.47.1321217039813; Sun, 13 Nov 2011 12:43:59 -0800 (PST) Received: by 10.182.15.40 with HTTP; Sun, 13 Nov 2011 12:43:59 -0800 (PST) Date: Sun, 13 Nov 2011 21:43:59 +0100 Message-ID: Subject: A tiny almost sorta kinda nearly minimal perfect hash for a mac classifier? From: Dave Taht To: bloat-devel Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable 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: Sun, 13 Nov 2011 20:44:01 -0000 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. 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. Algo needs to be fast and lock free, relying only on a very few atomic increment and/or swaps, only in rare cases... On most networks today, you are usually talking to a VERY few machines. The number of machines that appear and disappear is rather small and stable over very long periods of time (proof: go type arp -a on your home network) Yet mac addresses are 48 bits wide. Even in the case of an access point, you are never going to see more than 2048 of them, and most APs stop at around 127 stations, and most wireless networks have many fewer endpoints than that... So great, I figure a mere 2 bin table lookup and random replacement will work fine, I stuck my first attempt up at http://www.teklibre.com/~d/mactoclass.c and I hate it. Didn't get so far as writing garbage collection. (double buffer it) Does anything elegant exist? Anything worthy in the kernel? --=20 Dave T=E4ht SKYPE: davetaht US Tel: 1-239-829-5608 FR Tel: 0638645374 http://www.bufferbloat.net