Better "hash_packet6"

[Luigi Rizzo]

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