Re: Question about tcp hash function tcp_hashfn()

On Wed, May 31, 2006 at 02:58:18PM +0400, Evgeniy Polyakov (johnpol@2ka.mipt.ru) wrote:

On Wed, May 31, 2006 at 03:51:24AM -0600, Brian F. G. Bidulock (bidulock@openss7.org) wrote:

quoted

Evgeniy,

On Wed, 31 May 2006, Evgeniy Polyakov wrote:

quoted

2. Compared Jenkins hash with XOR hash used in TCP socket selection code.
http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14

Two problems with the comparison:

  Port numbers can be collected into a 32 bit register in network
  byte order directly from the TCP packet without taking two 16 bit
  values and shifting and or'ing them.

They are.

u32 ports;

ports = lport;
ports <<= 16;
ports |= fport;

Using network or host byte order does not affect hash distribution,
that shifting was coded to simulate other types of mixing ports,
which actually never showed different results.

quoted

  Worse: he folded the jenkins algorith result with

   h ^= h >> 16;
   h ^= h >> 8;

  Destroying the coverage of the function.

It was done to simulate socket code which uses the same folding.
Leaving 32bit space is just wrong, consider hash table size with that
index.

quoted

I, for one, am not suprised that artifacts appeared in the comparison
as a result of this destruction of the coverage of the hashing function.

It is comparison of the approach used in TCP hashing code, it is not full 
mathematical analysis. And in that case jenkins hash already not good. 
I'm sure it can be tuned, but it does require a lot of iterations, while
XOR one "just works".

-- 
	Evgeniy Polyakov