Subject: Re: [Tsvwg] [SCTP checksum problems]

From: Jonathan Wood <[email-masked]>
Date: Mon, 16 Apr 2001 16:10:55 -0700 (PDT)

As an SCTP implementor and someone who will want to get the hardware folks to 
help with checksumming, I wholeheartedly agree with Randy. Remember that SCTP is 
just a proposed standard, and is as such not all that far along the 
standardization process. We should still be able to make changes like this if 
necessary.

Jon

>
>Q:
>
>The only problem with an additional "CRC chunk" is that
>it makes hardware assistance to error correction much
>more difficult. It is better (I think) to just realize
>we made a mistake. Get the opinions of the experts as to
>what checksum to use... i.e.:
>
>- CRC-32
>- Modified Adler-32 (16 bit word sums)
>- Fletcher-32
>- ???
>
>And then go with this as a replacement... Admit we were wrong
>and fix the problem..
>
>This way you have ONE and only ONE checksum algorithm making
>hardware designers life much easier...
>
>R
>
>Qiaobing Xie wrote:
>> 
>> Another solution could be (I think I mentioned this to Randy and a few
>> others at last IETF):
>> 
>> - Define a CRC-32 (or other strong checksum) control chunk and when the
>> sender wishes to use a stronger checksum protection, in addition to the
>> Adler-32 in the common SCTP header it includes this CRC-32 chuck in the
>> outbound packet. When the packet arrives, the receiver will do the
>> Adler-32 first, and then if the receiver supports the CRC-32 and sees
>> the presence of the CRC-32 chunk in the packet it will further verify
>> the CRC-32.
>> 
>> We could also use a bit pattern in the chunk type of the CRC-32 chunk so
>> that if the receiver doesn't understand the CRC-32 chunk it would drop
>> it with a report back to the sender.
>> 
>> -Qiaobing
>> 
>> _______________________________________________
>> tsvwg mailing list
>> [email-masked]
>> http://www1.ietf.org/mailman/listinfo/tsvwg
>
>-- 
>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: Tue, 17 Apr 2001 06:30:43 -0500

Jonathan:

I will make sure everyone at the bakeoff is aware of the upcoming
"checksum" change... Now one of the big questions yet is
what checksum should we use?

I kinda lean towards crc-32 myself (but of course I have no technical
basis for this and need to keep silent on which one to use anyway :->),
but do we have other candidates besides fletcher-32 and possibly
modified 
Adler-32 (i.e. 16 bit adds instead of 8)??

I will take the above 3 and do a bit of performance work this
week and post some numbers... thats about all I can do i.e.  tell
how much time the options I know of take... 

If you have some other candidates let me know and I can possibly get
some performance numbers on these as well...

As far as which is the best... I encourage all of you check-sum
experts out there to please join the thread :)

Oh, I know Jonathan Stone's paper will NOT be ready until sometime
in May.. so we may want to proceed slowly so that Craig Partridge and
he can have some cycles to add to this dicussion :)

R

---

From: "La Monte Henry Piggy Yarroll" <[email-masked]>
Date: Tue, 17 Apr 2001 07:55:44 -0500

As an implementor, I'd like to echo Jonathan's sentiments.  A
flash-cut is the best solution.  The installed base is currently small
enough that a change of this magnitude is still possible.

Jonathan Wood <[email-masked]> writes:
> As an SCTP implementor and someone who will want to get the hardware
> folks to help with checksumming, I wholeheartedly agree with
> Randy. Remember that SCTP is just a proposed standard, and is as
> such not all that far along the standardization process. We should
> still be able to make changes like this if necessary.
>
> Jon
> 
> >
> >Q:
> >

---

From: "La Monte Henry Piggy Yarroll" <[email-masked]>
Date: Tue, 17 Apr 2001 08:26:28 -0500

---

From: Craig Partridge <[email-masked]>
Date: Tue, 17 Apr 2001 09:24:28 -0400

>Adler-32 (i.e. 16 bit adds instead of 8)??

The other obvious choice is to define a TCP-32 (i.e. add in 32-bit
chunks with the carry wrapped).

>how much time the options I know of take... 

We have a fairly optimized CRC-32 running around that we can likely
send you.  I think Sklower had an optimized fletcher-32 in his paper
(though it may have only been fletcher-16 but regardless, you can
figure out how to do a faster fletcher-32 by reading his work and
much of it applies to Adler-32 as well).  Remember to test in both
endians (which is a nuisance, e.g. our CRC-32 was only done for big
endian) but it matters.

Craig

---

From: Jonathan Stone <[email-masked]>
Date: Tue, 17 Apr 2001 11:21:39 -0700

In message <[email-masked]>,

>chunks with the carry wrapped).

which requires either a 64-bit machine, or a mod-(2^32-1) reduction
for each 32-bit input word.

There's also the Reed-Solomon codes known as Weighted Sum Codes (WSC),
  http://www.acm.org/pubs/citations/journals/ton/1994-2-1/p16-mcauley/
  http://www.acm.org/pubs/citations/journals/ton/1995-3-2/p222-farkas/
but CRC-32 seem to give slightly better error detection, and is
currently better studied.

>send you.

Our code was really optimized for computing CRCs of `splices' of ATM
cells; so we could compute the CRC remainders of 48-byte ATM cell
payloads, `shift' the 48-byte cells around in a splice, and combine
the remainders.  Those techniques are from Dave Feldmeier; similar in
spirit, iirc, to
http://www.acm.org/pubs/citations/journals/ton/1995-3-6/p640-feldmeier.pdf

Our acutal CRC-32 core was a mundane four-bit-at-a-time lookup table:
a Google search finds several variants, plus the code in *BSD, and
(I assume) Linux kernels.

>  I think Sklower had an optimized fletcher-32 in his paper
>much of it applies to Adler-32 as well).

at http://www.cs.berkeley.edu/~sklower/cksumosi.ps.
Note the Fletcher terminology invites confusion: a `16-bit Fletcher
sum' has two 16-bit acumulators, giving a 32-bit error code (like
adler32 and CRC-32).

>Remember to test in both

Or see Dave Feldmeiere's paper for Fletcehr and CRC-32 implementation
techniques on a Sparc LX.  Sklower and Nakassis' papers measured
performance on vax/68020 generation machines using the pcc compiler.

On more modern machines and compilers, with fast CPUs and relatively
slow memory, the impact of loop unrolling, cache blocking, deferring
modulus operations, and (for a "TCP-32") presence/absence of
(depending on word size) add-with-carry or 64-bit adds, will likely
be more significant than optimizations between different VAX
addressing  sequences (auto-increment addressing vs "movaw".)

Getting realistic measurements is a thorny problem, too.