Subject: RE: Hashing function for PSAMP

From: <[email-masked]>
Date: Fri, 28 Jan 2005 13:29:23 -0500

Andy,

Note that distinct hashes are required for selection and digesting. This
could be achieved using a single parameterizable hash function, i.e.,
using different parameters to get different hashes. Both CRC32 and BOB
have initial vectors that could be used for this purpose. 

Any choice of initial vectors should be evaluated to determine whether
they work (i.e. produce two sufficiently random and mutually independent
hashes). Users will want to be able to set and change these parameters,
and keep them private in order to keep prevent subversion of the hash.
Is there any need to standardize the parameters? Perhaps it is useful to
recommend one pair of parameters that works (in the above sense).

Are router development folks happy with the computational requirement
for BOB (or CRC32) to be computed on every packet, if it is used as the
selection hash? 

It seems there is still some benefit to having IPSX available for
selection.

(i) IPSX is fast so could more easily be used by psamp devices with
lower computational abilities. 

(ii) IPSX is independent of the other hash functions under consideration
(BOB and CRC32) 

(iii) IPSX is very simple, so there is not much more overhead it making
it available; 

(iv) IPSX could be simply extended to take input for IPv6 (either more
input, or just a different 16 bytes). Or if we already have one IPv6
capable selection hash function standardized (say BOB), does any
additional standardized hash function also need to be IPv6 capable, or
is IPv4 sufficient?

Nick

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On
Behalf
> Of Andy Bierman
> Sent: Friday, January 28, 2005 8:42 AM
> To: Juergen Quittek
> Cc: [email-masked]
> Subject: Re: Hashing function for PSAMP
> 
> At 05:37 AM 1/27/2005, Juergen Quittek wrote:
> >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?
> 
> 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.)
> 
> 
> >Thanks,
> >
> >   Juergen
> 
> Andy
> 
> 
> >--
> >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
> >
> >
> >--On 24.01.2005 16:56 Uhr +0100 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?
> >>
> >>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/>

--
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: Stewart Bryant <[email-masked]>
Date: Mon, 31 Jan 2005 15:41:24 +0000

> for BOB (or CRC32) to be computed on every packet, if it is used as the

The short answer is NO ):

A lot depends on where you imagine this will be deployed.
On a pure s/w edge router there will be a measurable
headline performance hit with either of these, but perhaps
that does not matter in that environment. On a hardware
/microcoded core router, I would say that the chances
of getting either in the main path of existing hardware
are for all practical purposes zero.

If you were thinking that they would be run after
some primary sampler at a relatively low packet rate
in the export process, then there is less of an issue.

You canot use the existing CRC32 hardware to perform the
hash. So both BOB and CRC32 would need new hardware or
would need to be performed in software/microcode.

Software CRC32 implementations trade lookup table space
for compute cycles. Both of these resources are in
critically short supply on a high-end forwarder.
Even if you did find the resources (and on many
implementations they would simply not be available)
the result would be a crippling hit on headline
forwarding performance.

I have not done a detailed comparison of BOB and CRC32
execution speeds, but my first impression is that BOB
takes even more cycles to execute than CRC32 although
perhaps not if you take into account the cache stalls
in doing the table fetch.

- Stewart