Subject: [Tsvwg] SCTP and checksums

From: Randall Stewart <[email-masked]>
Date: Fri, 04 May 2001 09:10:00 -0500

Dear All:

I have just completed my study of the performance of various
sums and such. I had some interesting results, to say the least :)

Here is a summary of my findings, I can provide details for any
who would like (in the form of a starOffice spreadsheet or a
email with the results a bit less raw).

Summary:
-----------------------------------------------------------------
CRC-32 - Varies widly based on caching and type of algorithm and
         size of arrays. Generaly I saw anywhere from 3us - 128us
         per call on a PI running the receive side of my tests.

Adler-32 - Tended to take between 2-91 us on my PI. Not sure why the
           wide variance. Most of the results were around 60-70us
           per call.

ModAdler - Tended to be slightly faster than Adler-32 (as expected)
           ranging in the 40-60us per call range.

Fletcher - Was faster than either adler32 variant (using only 16 bit
           fletcher) ranged anywhere from 15us - 50us per call during
           my various test runs... but for the most part consistently
           lower time frames than either adler.

TCP32 - This was put forward in some early discussion by Craig Partridge
so
        I whipped up something along the lines of the IP sum only adding
        32 bits at a time. 1's compliment at the end and of course all
        of the wraps carried back in. I did this assuming a 32 bit 
        adder so that each addition needed to check for wrap and
maintain
        a wrap counter which was folded in at the end. This tended to
        always be slightly fast than Fletcher somewhere between 3-15us
        in all cases with no inconsistent results. 

Now after looking at these results I have reached the following
conclusion:

A) CRC-32 is to variable and will I think result in to much work for 
   small devices. If one assumes a device with a small cache you are
looking
   most likely in the higher end of my results and in the worse case it
can
   get pretty bad. 

B) Fletcher seems to do much better than Modifed adler in terms of
performance
   due to the smaller number of instructions needed to execute it. 

C) TCP32 did best of all but is completely new. I am hesitant to go down
   a path of a unknown-unexplored checksum that has not been studied
very
   well. Been there, done that, did not like the results :)

So I think the bottom line is we should shift SCTP into a 16 bit
Fletcher algorithm
which will:

1) Improve performance
2) Provide better checksum protection
3) Has been studied enough and is actually an alternative that
   TCP can use (but it seems does not).

I will begin working on the RFC2960Bis document today. I will try to
have it
out next week... I am thinking on  (urged by Lyndon) incorperating all
of the findings of the
bakeoff draft in this (except the last bakeoff... I need to write a
seperate
ID on this one so that I can get some help from the IPv6 community on
the 
only issue found... address scoping in V6 :>)

Anyway please comment to me ... throw things etc... it is helpful if you
make
sure I am copied .. since I still have the northpoint flu and my normal
IETF email is delayed quite a bit being batched once or so every day...

Comments and opinions would be most helpful...

PS: Lyndon can you please forward this to the sigtran wg since it won't
take
    my posts from my non-subscribed cisco account... thanks

Thanks

R
-- 
Randall R. Stewart
Systems & Solutions Engineering
Cisco Systems Inc.
[email-masked] 815-342-5222 or 815-477-2127

_______________________________________________
tsvwg mailing list
[email-masked]
http://www1.ietf.org/mailman/listinfo/tsvwg

---

From: Qiaobing Xie <[email-masked]>
Date: Fri, 04 May 2001 11:33:59 -0500

Another important thing to consider is the hardware implementation
complexity of those candidates, and my gut feeling is that anything
CRC-based will be a magnitude or more harder to put into hardware (e.g.
FPGA) than those sum-based. Can someone knows more about hardware
implementation chip in your opinion?

-Qiaobing

---

From: Andreas Jungmaier <[email-masked]>
Date: Fri, 4 May 2001 18:49:56 -0400

> implementation chip in your opinion?
Folks,

if I recall my lectures in technical computer science right, a CRC is
about the easiest thing to implement in hardware there is.
Bits are pushed through a simple register, being Xored with a generator 
polynomial function.
(therefore it is employed in checksumming Ethernet frames, too).
I might be wrong about the CRC-32, but in general it should work easy in
Hardware.
As with all other algorithms, the CRC is only computed after all bits have 
been pushed through the register, and must then be added to the CRC-field
of the SCTP header, which is not helpful for wire-speed forwarding
anyway. But that is a general SCTP problem, and applies to all 
algorithms equally.

Regards,

- -- 

Andreas Jungmaier

- ----------------------------------------------------------------------------
 \|/ _____ \|/    Andreas Jungmaier, Dipl.-Ing. 
 "@'/ , . \`@"    University of Essen           [email-masked]
 /_| \___/ |__\   -> Computer Networking        Tel. : +49 (0201) 183-7636
    \___U_/          Technology Group <-
- ----------------------------------------------------------------------------
PGP Public Key and Fingerprint: see http://www.exp-math.uni-essen.de/~ajung
- ----------------------------------------------------------------------------

---

From: Randall Stewart <[email-masked]>
Date: Fri, 04 May 2001 12:04:31 -0500

Andreas Jungmaier wrote:
> 
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 

And TCP and UDP has well..

R

> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.0.4 (GNU/Linux)
> Comment: For info see http://www.gnupg.org
> 
> iD8DBQE68zIed2Uw+xBvGUIRAkx3AKCIpVZ9OIvIjgsj7bySNGmrAKwkFACfXzS6
> sDtWq+pyG2K246FIh0Gnd6Y=
> =N1Vo
> -----END PGP SIGNATURE-----

---

From: Qiaobing Xie <[email-masked]>
Date: Fri, 04 May 2001 13:40:10 -0500

Andreas Jungmaier wrote:
....
> I might be wrong about the CRC-32, but in general it should work easy in

This sounds like a serial bit-wise implementation. But isn't this going
to take a lot more clock cycles to operate than a 32-bit parallel adder
that is basically what a sum-based algorithm needs? 

-Qiaobing

---

From: Michael Krause <[email-masked]>
Date: Fri, 04 May 2001 16:24:50 -0700

>email with the results a bit less raw).

Without a description of the tests, the execution environment, etc. it is 
unclear how to evaluate these results.  Clearly the wide variance of the 
results needs to be explained before any conclusions can be drawn.

Mike

---

From: Randall Stewart <[email-masked]>
Date: Sat, 05 May 2001 08:16:21 -0500

Michael:

just a couple of comments...

1) I will be glad to forward you more details on the test environment.
2) The widest differences appear to be in the crc32 measurements..
believe
   it or not. It is well known that caching of tables (or not) will 
cause
   such wide discrepancies. 
3) I think it is clear from my study that:
   a) crc-32 is more expensive if you do it in software, but can be
      not much more overhead than the others IF (and thats a big
      if) you have a hardware environment that is more friendly to
      it (i.e. big cpu cache and enough memory to keep a fairly
      large CRC table... aka 1k 32 bit words or so). 
    b) Since we want SCTP to run in all types of devices crc-32
       will be more expensive for small devices and may make it
       harder to put SCTP in those devices.

I don't see the value in moving to crc-32 due to its increased overhead
in small devices... I think it is quite clear that IPS will do there
own CRC no matter what SCTP does and besides... SCTP is a general
purpose protocol and thus needs to fit in the "all device catagory" even
though IPS would most likely run on more CRC-32 friendly environments...

I will send you a seperate email with more details on my results... I
did
not want to plague the list with excess information.. anyone else that
would
like more details please send me an email and I would be glad to share
the
info with you..

R