Re: Hashing function for PSAMP

[Maurizio Molina <maurizio.molina@dante.org.uk>]

Saverio Niccolini wrote:

> Dear all,
> I would like to ask a simple question to the list.
> As you have seen in the "Sampling and Filtering Techniques for IP Packet
> Selection" draft we have tried to give suggestions on which is the best
> hash function in order to do packet sampling.
>
> Hash Functions Suitable for Packet Selection
> 1. IPSX
> (2. BOB)
>
> Hash Functions Suitable for Packet Digesting
> 1. CRC-32
> (2. BOB)
>
> Thinking about it and doing some additional tests it turned out that:
> 1) IPSX can only accepts 16 bytes as input --> it is not useful for IPv6
> packets.
> Do we want to stay with IPSX that is 7 times faster than BOB but can not
> be used with IPv6 packets? What is the list feeling about this? 
>  
One thing to clarify is if IPSX cannot really be extended.
by looking at its (very simple) description,

          1.    v1 = f1 ^ f2; 
          2.    v2 = f3 ^ f4;   
          3.    h1 = v1 << 8; 
          4.    h1 ^= v1 >> 4; 
          5.    h1 ^= v1 >> 12;  
          6.    h1 ^= v1 >> 16; 
          7.    h1 ^= v2 << 6; 
          8.    h1 ^= v2 << 10; 
          9.    h1 ^= v2 << 14; 
          10.   h1 ^= v2 >> 7; 

where f1, f2, f3 and f4 are the four 32 bit input words,  my guess would 
be that  for  extending it to six 32 bit input word it would be 
necessary to select other two 32 bit word from the packet (say f5 and 
f6) and add four other shifting and XOR steps.
That is:

          11.   v3 = f5 ^ f6; 
          12.   h1 ^= v3 << N;
          13.   h1 ^= v3 >> M;
		............

The point is to understand what is the rationale of the choice of the number of shift positions and their direction in steps 3 to 10.
Is there is a "rule" this can be extended to other steps? Or was more or less a "random choice"? or is there any reason for which an extension should not work?
I think we need Nick's opinion on that...

Maurizio  

> 2) BOB is faster than CRC-32 (on software implementation) and achieves
> as good collision probability as CRC-32.
> Do we still want to recommend CRC-32 because we believe that hardware
> implementation of CRC-32 are already out or we just would like to
> promote BOB to recommended and CRC-32 as optional?
>
> I am asking this because we are going to submit a new version of the
> draft and we would definitely like to fix this issue.
>
> Thanks in advance for your comments,
> Saverio
>
> ============================================================
> Dr. Saverio Niccolini
> Research Staff Member
> Network Laboratories, NEC Europe Ltd.
> Kurfuerstenanlage 36, D-69115 Heidelberg
> Tel.     +49 (0)6221 90511-18
> Fax:     +49 (0)6221 90511-55
> e-mail:  saverio.niccolini@netlab.nec.de
> ============================================================
>
>
> --
> to unsubscribe send a message to psamp-request@ops.ietf.org with
> the word 'unsubscribe' in a single line as the message text body.
> archive: <http://ops.ietf.org/lists/psamp/>
>  


--
to unsubscribe send a message to psamp-request@ops.ietf.org with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/psamp/>