Date: Tue, 5 Dec 2006 16:17:45 -0800 From: Luigi Rizzo <rizzo@icir.org> To: Max Laier <max@love2party.net> Cc: freebsd-ipfw@freebsd.org Subject: Re: Better "hash_packet6" Message-ID: <20061205161744.A48319@xorpc.icir.org> In-Reply-To: <200612052010.36789.max@love2party.net>; from max@love2party.net on Tue, Dec 05, 2006 at 08:10:30PM %2B0100 References: <200612052010.36789.max@love2party.net>
next in thread | previous in thread | raw e-mail | index | archive | help
On Tue, Dec 05, 2006 at 08:10:30PM +0100, Max Laier wrote:
> Hi,
>
> with a lot of help from David Malone and JINMEI Tatuya we came up with the
> following hash function for IPv6 connections using universal hashing.
I followed the discussion on the topic a few days (weeks ?)
ago and investigated around a bit, also following some of the pointers
that passed on the list. So I have the following comments:
First, this proposal, with 36 multiplies and one division, the
function seems rather expensive for e.g. a low end cpu (arm or
soekris) as you might find on network-appliance boxes.
Any chance to get performance numbers on that hardware ?
I wonder if you have considered alternatives such as the one at
http://www.azillionmonkeys.com/qed/hash.html
which seems reasonable in terms of theoretical background, performance
and also in terms of license (see the reference about being used
in Apple products).
Second, and related to this specific hash function: if we end up
using it, i think it would be good to add a bit of documentation
on algorithm used and on constraints that there are (e.g. wrt operand
sizes and values of the hash keys) so that people don't break it
in the future trying to optimze things that they should not touch.
In particular, i have the following questions:
- is the algorithm defined on a byte-by-byte basis, or it is just
your decision to implement it this way ? (having it work on 16-bit
entries would e.g. halve the number of multiplies).
- i guess that you use addr6_cmp() to sort the components of the
address insuring the algorithm hashes forward and reverse traffic
to the same value. symmetric. But for this, one of the suggestions
was to xor SRC and DST to achieve the same thing, and i don't
understand why you use this different approach (which doubles the
input size and the number of multiplications).
- what are the requirements on ipfw_hash_key[] values ?
E.g. it seems that 0 should not be allowed or the corresponding
byte would have no contribution in the hash. Any other invalid
value, recommended range etc ?
In any case i am glad that people are looking at improving some code
that i am certainly guilty of :)
cheers
luigi
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20061205161744.A48319>