On Wednesday 06 December 2006 01:17, Luigi Rizzo wrote:
> 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 tried the reference machines (see hacked up attachment):
78x ia64
40x amd64
60x p3
16x p4
I don't have my Soekris set up, so if somebody could give it a try.
> 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).
It needs a seed at very least.
> Second, and related to this specific hash function: if we end up
^ not? In which case I'd agree.
> 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).
If an attacker can set src and dst it remains trivial to create (many)
collisions. In order to degrade the hash table it is enough to spoof
SYNs, isn't it? On that note, if I'm correct it might be a good idea to
use a seeded hash for IPv4 as well.
> - 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 ?
I think the answer is "good random data" in [0, HASH_PRIME). That
includes zero, but I agree that using zero is a bit pointless. I'll let
others speak to the details of universal hashing.
> In any case i am glad that people are looking at improving some code
> that i am certainly guilty of :)
--
/"\ Best regards, | mlaier@xxxxxxxxxxx
\ / Max Laier | ICQ #67774661
X http://pf4freebsd.love2party.net/ | mlaier@EFnet
/ \ ASCII Ribbon Campaign | Against HTML Mail and News
hash_cost.c
Description: Text document
pgptUOR2xfIHb.pgp
Description: PGP signature
|
