Subject: Hashing function for PSAMP

From: "Saverio Niccolini" <[email-masked]>
Date: Mon, 24 Jan 2005 16:56:44 +0100

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?

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:  [email-masked]
============================================================

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

---

From: Maurizio Molina <[email-masked]>
Date: Mon, 24 Jan 2005 18:21:42 +0000

>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

---

From: Juergen Quittek <[email-masked]>
Date: Thu, 27 Jan 2005 14:37:15 +0100

Dear all,

Currently, the packet selection document has IPSX mandatory for packet
selection and CRC32 mandatory for packet digest.

The problem I see with this recommendation is that IPSX is not suitable
for IPv6.  It does not sound like a good idea to have it mandatory for
IPv6 systems.

Here are two alternatives:

1. Make IPSX mandatory for IPv4 packet selection and BOB mandatory
   for IPv6 packet selection.
   Then, with BOB implemented anyway, we should then replace CRC32
   with BOB for packet digest, because both perform similarly and
   there is no good reason for forcing implementors to support also
   a third hash function.

2. Just make BOB mandatory for packet selection and packet digest.
   This would simplify implementation, because only a single function
   is required.  For packet digest this should be OK, see 1.
   A disadvantage is that BOB is slower than IPSX by factor 7.
   An advantage is, that BOB is free of IPR, while IPSX is protected
   by a patent.

Does anybody have a preferences for 1., 2., or the current choice?

Thanks,

    Juergen
-- 
Juergen Quittek        [email-masked]       Tel: +49 6221 90511-15
NEC Europe Ltd.,       Network Laboratories        Fax: +49 6221 90511-55
Kurfuersten-Anlage 36, 69115 Heidelberg, Germany   http://www.netlab.nec.de

---

From: Andy Bierman <[email-masked]>
Date: Fri, 28 Jan 2005 05:42:12 -0800

>Does anybody have a preferences for 1., 2., or the current choice?

I prefer (2) because we can't ignore IPv6 and we are selecting
a hash algorithm for interoperability, so we really only need
one of them.  (Consider the extra expense for HW-assisted implementations.)

>   Juergen

Andy