Subject: RE: Hashing function for PSAMP

From: <[email-masked]>
Date: Mon, 24 Jan 2005 15:19:35 -0500

Maurizio,

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On
Behalf
> Of Maurizio Molina
> Sent: Monday, January 24, 2005 1:22 PM
> To: Saverio Niccolini
> Cc: [email-masked]
> Subject: Re: Hashing function for PSAMP
> 
> 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...

The rationale was to exploit variability expected and/or found
empirically in different fields in the IPv4 packet header. A number of
other variants on this theme were evaluated. The final choice
represented a good combination of computational simplicity, and
quasi-randomness, observed in testing.

It is possible to extend the form to longer inputs, along the lines that
you suggest above. However, evaluation of different variants is
difficult in practice. Due to the comparatively small deployment of
IPv6, it is questionable whether IPv6 traces available today would be
representative (in terms of the variability of their fields) of what
could be expected in future. This is a problem for the evaluation of any
hash.

Nick

> 
> 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:  [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/>
> >
> >
> 
> 
> --
> 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/>

--
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: Tue, 25 Jan 2005 11:58:36 +0000

>could be expected in future. This is a problem for the evaluation of any
My idea, to start with, was to evaluate the "IPSX extension" on the IPv4 
traces.
Saverio did some tests (on traces of the of the MAWI project). His 
results showed that all hashes (BOB, CRC-32, IPSX, MMH) showed a poor 
uniformity (according to the Chi-square tests) with 16 input bytes. 
Moving from 16 input bytes to 20 (and then further to 24, 28, 32, etc), 
some of the hases (BOB, CRC-32) showed a big improvement in their 
uniformity behavior, while  MMH didn't. For IPSX, it was only possible 
to test it on 16 bytes, where it showed a poor uniformity behaviour as 
all the other functions. If we can have an IPSX variant, we'll be at 
least able to understand if moving from 16 to 20 input bytes (and then 
possibly to 24, 28, etc...) it will improve its behaviour (like BOB and 
CRC-32) or not (like MMH). This will already be an interestring result 
for PSAMP to give a reccomendation.
Maurizio