Subject: RE: [Tsvwg] SCTP and Checksums

From: [email-masked]
Date: Wed, 9 May 2001 04:01:04 -0400

Ok, here's the objection you were expecting ...

As Jim Wendt has pointed out, iSCSI is currently
specifying error recovery (retransmits,
timeouts, etc.) that wouldn't be necessary if
there was a good CRC in the transport.  We have
no choice for TCP (e.g., the alternate checksum
breaks NAT), but this approach will land SCTP
in the same situation as TCP - iSCSI will
need error recovery logic, and there may be
work on adding a shim with the CRC that
should have been in the base protocol.

Given SCTP's description as the
general purpose transport for the future,
and the work that's been done to realize
that, failing to get this CRC vs. checksum
issue right is a shame.  Given that the
results show software overheads in the
same ballpark for checksums and CRCs,
I think choosing a checksum solely
because it's slightly easier to
do in software is short-sighted.

In practice, while I appreciate the suggestions
for how this could be addressed by some sort
of optional chunk, if SCTP becomes a
ubiquitous part of operating systems, and
the CRC chunk is optional, it won't be there,
and there'll be the same resistance to tinkering
with SCTP implementations as we have run into
on tinkering with TCP implementations.
At best, this optional chunk approach might
make putting in a CRC shim easier, but it won't
eliminate any of the error recovery
mechanisms that wouldn't be necessary
if the transport detected its own errors.

In the absence of a compelling reason for
why things should play out in this fashion,
put me on the record as objecting.  The fact
that iSCSI will be able to cope with SCTP
getting this wrong shouldn't be an excuse
for not doing it right.

Thanks,
--David
 
---------------------------------------------------
David L. Black, Senior Technologist
EMC Corporation, 42 South St., Hopkinton, MA  01748
+1 (508) 435-1000 x75140     FAX: +1 (508) 497-8500
[email-masked]       Mobile: +1 (978) 394-7754
---------------------------------------------------

> -----Original Message-----
> From:	Randall Stewart [SMTP:[email-masked]]
> Sent:	Tuesday, May 08, 2001 10:05 AM
> To:	[email-masked]
> Subject:	[Tsvwg] SCTP and Checksums
> 
> Dear All:
> 
> I am not beginning the RFC2960bis work as Lyndon put out. The question
> then turns to the checksum. For a first draft of the bis I will
> use the Fletcher-16 (its a 32 bit sum.. aka RFC1145). Any pre objections
> please raise them ASAP since I am just now beginning the wade through
> of the document..
> 
> 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: Wed, 09 May 2001 08:38:51 -0500

David:

I understand your concern... and I had another
interesting comment (off-line) from Al Varney.
He sent me a CRC16 code CRC-CCITT to be percise.
This is the same code used by MT2P... which is
optimized for small messages.. Now, yeah, I know I know
two sums are bad but one could envision:

1) Use only the bottom 2 bytes of the current CRC.
2) Make the upper 2 bytes reserved/flags
3) Set one of the flags as a 'CRC-32' attached at end, not included
   in CRC-16 check.
4) Set one of the flags as a 'No-CRC-16' flag, i.e CC-field in
   header is 0x0000.

Now Jonathan Stone as told me that one of the most effective CRC's
you can have is a trailing one. This supposedly helps even more
I am not sure why but I am no expert.

I have often wondered if we did not make a mistake by not allowing
some flags "Reserved" for the future in the common header...

With the above 1-4 one could:

A) Set a '11' in the flags and turn off CRC-16 and do inline hardware
   CRC for say iSCSI.
B) Set a '00' for standard environement in software so that you hold
   the packet, copy out the 16 bit CRC and then run your standard
   CRC-CCITT algorithm**.
C) Set a '10' if you were really really paranoid and wanted both a
   CRC-16 AND a CRC-32.
D) Set a  '01' if you were completely trusting (or had some sort of
   application level error correction) and wanted to disable all
   CRC protection.

Now this is a radical idea and I need another cup of coffee and some
performance numbers as well... but I am thinking it might just
be viable... we could even change from say CRC-CCITT to the standard
IP checksum if folks prefered this to CRC-CCITT... I really am
non-descript
about it...

Jonathan, Craig could you comment on this radical idea please???

R

** Note: I will use Al's code and run performance comparison on this guy
today.. which
         means results will be ready early next week...

---

From: Randall Stewart <[email-masked]>
Date: Wed, 09 May 2001 10:59:15 -0500

David:

After a brief look at the crc16 that Al Varney sent me as well
as the original crc16 that was in the reference implementation
way back... yes we used to specify crc16 a ways back :/

I have found the following in a single pass... I am not sure
I am willing to invest in a 20 hour run for this one ... sigh...

1) The small table version Al sent me is really bad CPU wise... it is
   worse than any of the others ... sigh...in the order of 228us per
call.
   The table one drops to 185us .

2) The original CRC16 with a 512 byte table (not to unreasonable) is
better
   than the CRC32 on the PI but not the PII. The PII seems to do a lot
   better with the CRC32 algorithms (all of them) than any of my CRC16.

I am wondering if I should just go make a pass of the lot of them doing
say 5,000,000 packets but this time change my compile options to
"-g -pg" instead of the current "-O3 -pg" and see if we get a lot
differnt
results with this...  Maybe I will...

I am not necessarily convinced by any of the numbers really but I doubt
very much the wisdom of having options or negotiation. I side more
with Kacheong on this one... 

Should we drop back to a 16 bit check with flags? This might allow 
iSCSI to do something in the future.. I just don't know and would like
some other comments as well... I surely am not qualified to make the
decision.. I hope to get the bis finished up today and submitted.. For
now
I will leave in the fletcher-16 that I have crafted into it yesterday.
We
can change this has the debate on the BIS goes on (if that is the
best thing to do)..

R

---

From: Qiaobing Xie <[email-masked]>
Date: Wed, 09 May 2001 17:33:21 -0500

Randall Stewart wrote:
...
> with Kacheong on this one...

I couldn't agree with you more...

-Qiaobing

---

From: Qiaobing Xie <[email-masked]>
Date: Wed, 09 May 2001 17:30:52 -0500

But this approach won't address David's concern if the desired options
are not available in the OS. He will still need to "tinkering" with the
SCTP implementation or build his own shim:

> [David] ...if SCTP becomes a

But to require every implementation to support all options seems simply
making things worse since now you are paying the cost for implementing
multiple CRCs. 

-Qiaobing

---

From: "Douglas Otis" <[email-masked]>
Date: Thu, 10 May 2001 13:42:27 -0700

I have just created a draft that will define an additional Chunk for SCTP.
This chunk was placed at the end of the packet with the concept that if the
packet is truncated, a missing IA-Digest packet would act as a truncation
indicator.  Although not indicated is the possible use of this to include
CRC.

ftp://ftp.sanlight.net/pub/draft-otis-sctp-digest-00.txt

Doug

---

From: "Douglas Otis" <[email-masked]>
Date: Sat, 12 May 2001 10:25:06 -0700

All,

I made a quick simulation of a stuck bit error and the ability of either
Fletcher and Alder-Fletcher to detect this problem.  Think of this as a
memory cell within a router with a defective driver.  The results were
surprising so perhaps I made a mistake.

See: Errchk.c and Errchk.exe  (Windows compatible)
ftp://ftp.sanlight.net/pub/

The results indicated this significant error could not be detected 2% of the
time using Fletcher and yet the Adler-Fletcher algorithm failed detection
.1% of the time for a 20 times improvement.  The simulation code plays a few
tricks.  The SCTP header ensures any stuck bit induces an error.

The method of ensuring the Adler modulo used an integer with the C code but
this could be done using a 16 bit register if written in assembly to take
advantage of the carry flag.  This would avoid the modulo comparison in most
cases and would actually be faster.  The modulo technique should not be
viewed as more instructions to that of the traditional technique.  A 16 bit
add can exceed the modulo, the addition technique with a 16 bit register
ensures the upper sum remains within a Adler modulo.

I'll play around with other error techniques, but I thought this was
significant to provide this information sooner than later.

Doug

---

From: "Douglas Otis" <[email-masked]>
Date: Sun, 13 May 2001 21:38:59 -0700

Follow-up,

I have included Fletcher, Fletcher-Adler, Adler-32, and CRC-32 in a stuck
bit test.  The results are as follows:

On one drive, in 28,283,456 passes (42GB), failure to detect are:
Fletcher - 589,640 2% failure to detect
Fletcher-Adler - 51,804 0.18% failure to detect
Adler-32 - 7 0.000,024% failure to detect
CRC-32 - 0 0% failure to detect

Compared to Fletcher:
Fletcher-Adler is 11 times better,
Adler-32 is 84,000 times better.

On another drive, in 26,992,768 passes (40GB), failure to detect are:
Fletcher - 564,378 2% failure to detect
Fletcher-Adler - 39,272 0.15% failure to detect
Adler-32 - 2 0.000,007,4% failure to detect
CRC-32 - 0 0% failure to detect

Compared to Fletcher:
Fletcher-Adler is 14 times better,
Adler-32 is 280,000 times better.

To detect large errors with binary patterns, the apparent bits of randomness
are:
Fletcher = 6 bits
Fletcher-Adler = 10 bits
Adler-32 = 18 bits
CRC-32 = ~32 bits

The worst algorithm for detecting hardware failures, the type of errors not
protected by CRC, is Fletcher by a large amount.  It would appear to be a
major mistake to move from Adler-32 to Fletcher.  The only algorithm better
at detecting this type of error is CRC.  Even the Fletcher-Adler is not much
better although in theory it would be better for detecting burst errors than
Adler-32.  Burst errors should already be guarded by media CRC.

See: errchk_all.c, errchk_all.exe

Doug

---

From: "La Monte Henry Piggy Yarroll" <[email-masked]>
Date: Mon, 14 May 2001 08:46:18 -0500

Thanks very much!  This is precisely the sort of information I'd been
asking for.

---

From: Randall Stewart at work <[email-masked]>
Date: Mon, 14 May 2001 09:05:43 -0500

La Monte/Doug:

These are interesting results for sure... but I really
would like to get Craig Partridge and Jonathan Stone
to look over this simulation and results and comment before
we switch horses back :/

R

---

From: Craig Partridge <[email-masked]>
Date: Mon, 14 May 2001 10:28:46 -0400

I need to understand the test a bit better.

If there is only one stuck bit, Fletcher, Adler-32, and Fletcher-Adler
should all detect the error (which suggests the test is broken).  For
instance, just focusing on Fletcher, one of the two bytes of the Fletcher
sum is simply the sum of all the bytes.  A single stuck bit must cause
that sum to change...

Craig

---

From: "Douglas Otis" <[email-masked]>
Date: Mon, 14 May 2001 08:24:05 -0700

Craig,

See errchk_all.c at:

Based on an interface of 32 bits, if one of these bits were stuck (failed
signal driver) then what is the ability of these various algorithms to
detect this single failure?  This would not be a single bit, but potentially
a bit changed every four bytes.  Yes, this is an extreme but possible
failure.  As memory in middle devices increases into the giga-bytes often
without parity, buffers are likely to distribute widely over these many
memory devices.  If this defective device hammered one out of 16 packets,
the ability to detect this failure becomes significant.  There may be many
more cases of soft rather than hard failures, but I suspect this would not
change the results significantly, it would simply reduce the rate.  I used
this extreme case to expose the relative weakness.

Doug

> >> > To detect large errors with binary patterns, the apparent
> bits of randomne
> >> ss
> >> > are:
> >> > Fletcher = 6 bits
> >> > Fletcher-Adler = 10 bits
> >> > Adler-32 = 18 bits
> >> > CRC-32 = ~32 bits
> >> >
> >> > The worst algorithm for detecting hardware failures, the
> type of errors no
> >> t
> >> > major mistake to move from Adler-32 to Fletcher.  The only
> algorithm bette
> >> r
> >> > at detecting this type of error is CRC.  Even the
> Fletcher-Adler is not mu
> >> ch
> >> > better although in theory it would be better for detecting
> burst errors th
> >> an
> >> > > time using Fletcher and yet the Adler-Fletcher algorithm
> failed detectio
> >> n
> >> > > this could be done using a 16 bit register if written in
> assembly to tak
> >> e