Date: Wed, 6 Dec 2006 03:54:41 -0800 From: Luigi Rizzo <rizzo@icir.org> To: David Malone <dwmalone@maths.tcd.ie> Cc: Max Laier <max@love2party.net>, freebsd-ipfw@freebsd.org Subject: Re: Better "hash_packet6" Message-ID: <20061206035441.A58131@xorpc.icir.org> In-Reply-To: <20061206113847.GA78558@walton.maths.tcd.ie>; from dwmalone@maths.tcd.ie on Wed, Dec 06, 2006 at 11:38:47AM %2B0000 References: <200612052010.36789.max@love2party.net> <20061205161744.A48319@xorpc.icir.org> <200612060451.58473.max@love2party.net> <20061206012931.A56288@xorpc.icir.org> <20061206113847.GA78558@walton.maths.tcd.ie>
next in thread | previous in thread | raw e-mail | index | archive | help
On Wed, Dec 06, 2006 at 11:38:47AM +0000, David Malone wrote: > 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? maybe just ipfw2-ipv4 on and a single accept rule. that's to give an estimate of all the remaining packet processing costs that you were mentioning (interrupts etc.) > 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 i am not saying that this is the only option, the page lists other hashes. > > (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 i think all of this is irrelevant if we go for a complex hash with many operations. Caching gives/saves is a constant overhead, which for a very simple hash maybe doubles the time (from 0.8 to 2us/pkt) but it is negligible on the 11us and 27us consumed by the hsieh and universal hashes. > 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? no, and i think we should not bother on the cache effects as they are negligible here _and_ almost completely out of our control. If i may make a modest proposal, lets make the hashing algorithm a compile (or run) time option so people worried about collisions will be able to use the expensive function, and others can select a simpler one e.g. some simpler hash that xor's the addresses instead of sorting them. > (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.) with the 36 bytes strings we have to work on, i doubt we can find something that is not a memory killer yet runs in decent times! cheers luigi
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20061206035441.A58131>