RE: Hashing function for PSAMP

[<duffield@research.att.com>]

Maurizio,

> -----Original Message-----
> From: owner-psamp@ops.ietf.org [mailto:owner-psamp@ops.ietf.org] On
Behalf
> Of Maurizio Molina
> Sent: Monday, January 24, 2005 1:22 PM
> To: Saverio Niccolini
> Cc: psamp@psg.com
> 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:  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/>


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