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