Skip site navigation (1)Skip section navigation (2)
Date:      Wed, 6 Dec 2006 11:38:47 +0000
From:      David Malone <dwmalone@maths.tcd.ie>
To:        Luigi Rizzo <rizzo@icir.org>
Cc:        Max Laier <max@love2party.net>, freebsd-ipfw@freebsd.org
Subject:   Re: Better "hash_packet6"
Message-ID:  <20061206113847.GA78558@walton.maths.tcd.ie>
In-Reply-To: <20061206012931.A56288@xorpc.icir.org>
References:  <200612052010.36789.max@love2party.net> <20061205161744.A48319@xorpc.icir.org> <200612060451.58473.max@love2party.net> <20061206012931.A56288@xorpc.icir.org>

next in thread | previous in thread | raw e-mail | index | archive | help
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.



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20061206113847.GA78558>