SORT BY:

LIST ORDER
THREAD
AUTHOR
SUBJECT


SEARCH

IPS HOME


    [Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

    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
    >
    >
    >
    >
    
    


Home

Last updated: Tue Sep 04 01:05:27 2001
6315 messages in chronological order