RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt

[julian_satran@il.ibm.com]

Doug,


There is no lookup in CRC computation.

A table entry (indexed by the code) is used in computation.

I would appreciate if you would not spread confusion.

Julo



"Douglas Otis" <dotis@sanlight.net> on 04/03/2001 18:58:27

Please respond to "Douglas Otis" <dotis@sanlight.net>

To:   ips@ece.cmu.edu
cc:
Subject:  RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt




Julian,

Errors being detected are not created by a media defect or an impulse on a
serial line.  CRC serial burst error detection will be in place on the
serial medium so focus on burst errors seems misplaced.  Also, CRC requires
a relatively expensive lookup compared to an algorithm that only accesses
data being checked.  I would not be surprised the difference running 2:1
for
most architectures.  The suggestion by John Howard sounds interesting for
small regions of less than 512 bytes.

Doug

> John,
>
> We all due respect I disagree with both your statements:
>
> - CRC is not expensive in software if you are willing to spend some
memory
> for tables
>    and literature about how to do it is abundant.
>
> - Adler and Fletcher are weak and there is no theory behind your
> distribution statements, nor any simulation results as far as I know.  We
> found that on very simple sequences the Hamming distance gets
> down to 2 (or
> lower) and the burst protection is probably not better than 16 bit.
There
> is even a simple formula for what sequences will get you false codes (see
> bellow for a reference)
>
> - CRC gets you alway a 32 bit burst protection and that makes for a very
> low probability for undetected burst and a guaranteed Hamming
> distance of 3
> (or higher blocks up to 2k). There seems to exist also a class of
> CRCs that
> are excellent for very long blocks with distances higher than 4.
>
> Computing the undetected error probability was never published
> for Adler or
> Flletcher and adding thhis to the lack of theoretical background make it
a
> very poor choice for a data storage platform.
>
>
> If you want some theory background please read:
>
> http://www.haifa.il.ibm.com/satran/ips/draft-sheinwald-iSCSI-CRC-00.txt
>
>
> You will find there both theoretical references and CRC implementation
> references that include even code.
> We are planing to update it with some newer CRCs.
>
> Regards,
> Julo
>
>
> John H Howard <jhh@sun.com> on 02/03/2001 15:42:25
>
> Please respond to John H Howard <jhh@sun.com>
>
> To:   Douglas Otis <dotis@sanlight.net>
> cc:   IPS Reflector <ips@ece.cmu.edu>
> Subject:  Re: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt
>
>
>
>
>
> CRC-32 is very expensive in software; it may require hardware assist in
> fast networks.  Is iSCSI really intended to be a hardware only protocol?
>
> Fletcher-32 has a serious flaw:  it does not distinguish between an
> input halfword of all ones (FFFFx) and an input halfword of all zeros
> (0000x).  Both are equal to zero under ones' complement addition.
> [Stone, J., Greenwald, M., Partridge, C., & Hughes, J., "Performance of
> Checksums and CRC's over Real Data", IEEE/ACM Trans. on Networking,
> Vol., 6, No. 5, October 1988] gives several examples of situations in
> which this is important.
>
> Adler-32 avoids this problem by adding 8-bit inputs into its 16-bit
> sub-sums.  It also uses a prime modulus (2**16-15) rather than ones'
> complement's 2**16-1.  Using 8 bit rather than 16 bit inputs doubles the
> number of additions Adler-32 performs compared to Fletcher-32.  A more
> subtle problem is that the high-order bits of the sums are not uniformly
> distributed until the block size becomes very large.  I estimate that
> this causes Adler-32 to lose one or two bits worth of resolving power.
> Still, a 30 bit checksum is still quite strong.
>
> An alternative worth consideration is Fletcher-32 modified to use the
> prime modulus 2**16-15.  It's fast, doesn't have the 0000=FFFF problem,
> detects permutations, and distributes all result bits uniformly.  It
> does confuse an input halfword of 0 with 2**16-15 (and similarly for
> 1..14), but I think this only a minor problem because the potentially
> confused inputs are unlikely.  By definition every checksum confuses
> many inputs.  If you are going to argue from bad examples you really
> should estimate how likely your bad examples are.
>
> John Howard
> Sun Microsystems
>
>
>
>