[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Hashing function for PSAMP



Saverio Niccolini wrote:

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


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

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?


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.


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.


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




-----Original Message-----
From: owner-psamp@ops.ietf.org [mailto:owner-psamp@ops.ietf.org] On Behalf Of Derek Chiou
Sent: Tuesday, February 01, 2005 7:03 AM
To: Stewart Bryant
Cc: duffield@research.att.com; abierman@cisco.com; Juergen Quittek; psamp@ops.ietf.org
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 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/>



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