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



    
    
    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