Subject: RE: [Tsvwg] SCTP and checksums

From: "Ong, Lyndon" <[email-masked]>
Date: Fri, 4 May 2001 09:37:33 -0700

Randy,

Any reason you suggest Fletcher-16 instead of Fletcher-32?

Vincente Cavanna's draft suggests that the main difference between
Fletcher-32 and Adler-32 is that Adler will catch changes in length due to
added or missing zero bytes at the ends of the message, and that can be
checked by looking at length indicators.  However, Fletcher-32 would
presumably be stronger than Fletcher-16.

Cheers,

Lyndon

-----Original Message-----
From: Qiaobing Xie [mailto:[email-masked]]
Sent: Friday, May 04, 2001 9:34 AM
To: Randall Stewart
Cc: [email-masked]; Ong, Lyndon
Subject: Re: [Tsvwg] SCTP and checksums

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

Randall Stewart wrote:
> 
> 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

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

---

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

Lyndon:

Second attempt at a reply.. I HATE dialup ... sigh...

> presumably be stronger than Fletcher-16.

Maybe I hae Fletcher-16 and 32 mixed up.

The function I used for fletcher is this:

**********************************************************************
unsigned int fletcher(const unsigned char *buf, int len)
{
  unsigned long s1 = 0;
  unsigned long s2 = 0;
  unsigned short *bufp;
  int n,nlen;
  nlen = len / 2;

  bufp = (unsigned short *)buf;
  for (n = 0; n < nlen; n++,bufp++) {
    s1 = ((s1 + *bufp) & 0x0000ffff);
    s2 = ((s2 + s1) & 0x0000ffff);
  }
  if(len > (nlen *2)){
    /* do the odd byte, we don't
     * expect this code to execute.
     */
    unsigned short x;
    x = buf[(len-1)] << 8 | 0;
    s1 = ((s1 + x) & 0x0000ffff);
    s2 = ((s2 + s1) & 0x0000ffff);
  }
  return ((unsigned int)(s2 << 16) + s1);
}
*************************************************************

If this is fletcher32 .. then my mistake.. if not please send me
a pointer to its method of implementation and I will rerun the
specific test and I will bet it is even better than the
Fletcher-16... and I would think we would want to go with that..

Note: I stripped sigtran off the reply all so it does not bounce and
      fool folks into thinking it went there... sigh..

R