Subject: RE: Hashing function for PSAMP

From: "Saverio Niccolini" <[email-masked]>
Date: Tue, 1 Feb 2005 14:18:34 +0100

Dear all,
what you are saying applies to BOB, CRC32 or IPSX as to other hash
functions.
Then your suggestions are just NOT to use a hash function as selection
method...
This is understandable but it is not what the question was about.

I think what it is important here is to think:
IF we are going to use a hash packet based sampling, are you happy with 
BOB (or CRC32) or would you prefer to see IPSX in the RFC?

And this leads us to the question from Juergen Quittek:
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.

Looking at your answer it seems to me that you can easily say:
I prefer (2).
Since one function or another is anyway not good for what you have in
mind,
the option number (2) gives you the chance of implementing only one hash
function
(instead of two) that you are not going to use anyway.

Regards,
Saverio

P.S.: from the software implementation that we have tested, we saw that
CRC32
is 4 times slower than BOB (86 ns of execution time for BOB against 320
ns for CRC32).
The absolute numbers are relative to our PC characteristics but the
relative numbers
should be right.

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Derek Chiou
> Sent: Tuesday, February 01, 2005 7:03 AM
> To: Stewart Bryant
> Cc: [email-masked]; [email-masked]; Juergen 
> Quittek; [email-masked]
> Subject: Re: Hashing function for PSAMP
> 
> Happy is a difficult thing to say.
> 
> I agree with Stewart.  In general, if a router doesn't 
> support it today, it won't.  Hardware cannot be changed and 
> NP resources in extant boxes are already stretched to the limit.
> 
> That said, CRC32 is not a big deal in new hardware; my 
> expectation is that the same is true for BOB (I'm not 
> familiar with it.)  Thus, if it's a real requirement that 
> router manufacturers see it as a serious differentiator that 
> sells boxes, you will see it in future products.
> 
> 
> Stewart Bryant wrote:
> 
> >
> >> 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?
> >
> >
> > 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
> >
> >
> >
> >
> >
> > --
> > 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: Tue, 01 Feb 2005 14:05:14 +0000

> Then your suggestions are just NOT to use a hash function as selection

We were answering the exact question that we were asked :)

> BOB (or CRC32) or would you prefer to see IPSX in the RFC?

 From a pure forwarding point of view, we need an algorithm that
is easy to imlement in harware, and easy to execute in a
typical microcode engine.

Typical forwarding microcode engines have fast access to a
tiny fraction of the packet. A very simple instruction set.
A tiny register set. A massive cost of fetching anything
else from memory.

> The absolute numbers are relative to our PC characteristics but the

Timing the execution on a PC is interesting, but does not tell you
much about execution performance on a forwarder. The environments
are very different. Also you need to specify the CRC32 algorithm
that you were using, and assuming that you were using a table
algorithm, the table size needs to be stated.

- Stewart