|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txtJulian, 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 |