From owner-freebsd-ipfw@FreeBSD.ORG Wed Dec 6 11:48:26 2006 Return-Path: X-Original-To: freebsd-ipfw@freebsd.org Delivered-To: freebsd-ipfw@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 9118016A416 for ; Wed, 6 Dec 2006 11:48:26 +0000 (UTC) (envelope-from dwmalone@maths.tcd.ie) Received: from salmon.maths.tcd.ie (salmon.maths.tcd.ie [134.226.81.11]) by mx1.FreeBSD.org (Postfix) with SMTP id A9C864419E for ; Wed, 6 Dec 2006 11:38:10 +0000 (GMT) (envelope-from dwmalone@maths.tcd.ie) Received: from walton.maths.tcd.ie ([134.226.81.10] helo=walton.maths.tcd.ie) by salmon.maths.tcd.ie with SMTP id ; 6 Dec 2006 11:38:48 +0000 (GMT) Date: Wed, 6 Dec 2006 11:38:47 +0000 From: David Malone To: Luigi Rizzo Message-ID: <20061206113847.GA78558@walton.maths.tcd.ie> References: <200612052010.36789.max@love2party.net> <20061205161744.A48319@xorpc.icir.org> <200612060451.58473.max@love2party.net> <20061206012931.A56288@xorpc.icir.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20061206012931.A56288@xorpc.icir.org> User-Agent: Mutt/1.5.6i Sender: dwmalone@maths.tcd.ie Cc: Max Laier , freebsd-ipfw@freebsd.org Subject: Re: Better "hash_packet6" X-BeenThere: freebsd-ipfw@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: IPFW Technical Discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 06 Dec 2006 11:48:26 -0000 On Wed, Dec 06, 2006 at 01:29:31AM -0800, Luigi Rizzo wrote: > the top forwarding performance of a soekris is around 30-35kpps if > i remember well - this translates in around 30us/packet all included. Is that the peak with ipfw2, IPv6 packets and dynamic rules turned on? > as you see from the absolute numbers in my other posting, > the overhead is very significant. OK - it looks like they could be significant then. > I have slightly modified/extended the program adding the hsieh hash > that i mentioned below, and made it easy to add more methods. the > code is at I've read the description of the Hsieh hash now and I'm pretty sure it should be possible to produce lots of collisions fairly easily with it. It may be possible to make it a keyed hash, but I wouldn't be up to doing any cryptanalysis on it to show if the result might be secure. > (here we probably overflow some cache so the simple algorithm > suffers a lot by increasing the number of different packets) I guess by default, this will always be a cache miss, because the packet will just have been DMAed into memory? (Or, we will recently have paid for the cache miss.) > Surely we need to experiment a bit more, but the cost > is significant especially on low end boxes. I think we really need to test the code in-place and look at the increase in CPU usage at different packet rates? That way the relative overhead and cache conditions will be closet to realistic. Do you have any suitable setup for this? > Maybe we could restrict the hash to just a part of the address ? If we leave out part of the address, then you can produce collisions by generating lots of addresses that are the same, except for the bits that we ignore. (The other option, is to replace the use of hash tables for dynamic rules with some other data structure that has better worst-case behaviour.) David.