Internet Draft V. Cavanna Agilent Technologies Expires September 2001 March 2, 2001 iSCSI Digests û CRC or Checksum? Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Copyright Notice Copyright (C) Agilent Technologies (2001). All Rights Reserved. 1. Abstract The iSCSI working group is currently considering the method of protecting iSCSI messages from errors. This I-D presents a proposal to use the Fletcher-32 checksum algorithm or some variant of it rather than Adler-32; if we must use CRC, to make it CRC32 (or CRC32Q) rather than CRC64. 2. Introduction The iSCSI I-D proposes using a 64 bit CRC to protect the header and payload of the iSCSI message. The overhead and complexity of a 64 bit CRC seems inappropriate for the type of errors from which the iSCSI message needs protection. In fact a 32-bit checksum seems adequate for our purposes. This document proposes using a 32 bit Fletcher-32 checksum rather than a 64 bit CRC and offers some justification. Cavanna [Page 1] Internet-Draft iSCSI û CRC or Checksum March 2001 3. Brief description of the algorithms CRC-32, Fletcher-32, Adler-32 3.1. CRC-32 (of Ethernet and FDDI fame) CRC-32 treats the data as binary coefficients of a polynomial in x and divides, using mod2 division, by the CRC polynomial P(x) (after multiplication by x^32 to make room for adding CRC bits to the low order bits of the shifted data without affecting the data). The coefficients of the remainder polynomial are then used as the CRC bits. The CRC register is initialized to a value other than zero to detect extra or missing leading zeroes. The CRC field is actually complemented before being transmitted in order to detect extra trailing zeroes in the case where the transmitted CRC would otherwise be zero. 3.2. Fletcher-32 checksum Fletcher-32 checksum has two sums, S1 and S2 which are initially zero. The sums can be ones complement (modulo 2^16-1) or twos complement (modulo 2^16). S1 is a 16 bit sum of the data taken 2 bytes at a time. S2 is a 16 bit sum of the data multiplied by the position of the data from the end of the packet. No multiplication is actually required in the algorithm. The multiplication effect results from the way the sum is accumulated. S2 accumulates values of S1 after S1 is updated; so a given data word appears multiple times in S2. The number of times a word appears in S2 depends on its position from the end of the packet. 3.3. Adler-32 checksum Adler-32 checksum has two sums S1 and S2. S1 is a 16 bit sum of the data taken one byte at a time and modulo 65521. S2 is a 16 bit sum, modulo 65521, of the data taken one byte at a time multiplied by its position from the end of the packet, and the sequence length. The sequence length enters the picture because of the initial value of 1 for S1. No multiplication is actually required in the algorithm. The multiplicative effect results from the way the sum is accumulated as described above in section 3.2. Adler-32 is essentially the same as Fletcher-32 except S1 is initialized to 1 instead of 0 and the sum is modulo 65521. Another difference which has implications on the burst detection capability of Adler-32, as I explain later, is that Adler-32 is defined to sum data one byte at a time whereas Fletcher- 32 is defined to handle data 2 bytes at a time. Cavanna [Page 2] Internet-Draft iSCSI û CRC or Checksum March 2001 4. What a CRC-n polynomial, P(x), can protect from? Assuming n check bits, we can claim the following error detection properties without placing much restrictions on the form of P(x). 4.1. Individual bit errors o All single bit errors provided p(x) has two or more terms and regardless of record length. o All double bit errors provided p(x) has a factor with 3 or more terms and record length less than the period of p(x). o The period of P(x) depends on its form (specifically the cycle length of the primitive polynomial that is usually one of the factors) and for most standard polynomials is within a factor of 4 of 2^n-1. Even for n=32 this number is much larger than the record length (4.3 billion bits). o All triple bit errors and odd number of errors provided p(x) contains the factor x^c+1 where c is an integer and regardless of record length. Most CRC polynomials (but not CRC-32) contain the factor x+1. This makes the hamming distance 4! o Most occurrences of more than three single bit errors regardless of record length. Thus most CRCs, with few restrictions on their form, will detect all possible 3 bit errors (Hamming distance is 4) in practical record lengths, and most occurrences of more than three single bit errors. CRC-32 used in Ethernet and FDDI and that I refer to in this document is prime and does not have x+1 as a factor. The implication is that it does not detect ALL odd number of errors (in particular 3) regardless of record length. Cavanna [Page 3] Internet-Draft iSCSI û CRC or Checksum March 2001 4.2. Burst errors o All single bursts of length up to and including n, regardless of record length, provided P(x) has an x^0 term. A burst is a range of bits in which at least the first and last bit are in error. The size of the burst is the number of bits including the first and last bits. o 1-1/2^(n-1) * 100 % of single bursts of length n+1 if all errors patterns are equally probable. The only pattern that is undetected is that which corresponds to the coefficients of P(x). o 1-1/2^(n) * 100 % of single bursts of length greater than n+1 if all errors patterns are equally probable. For n=32 this is 99.9999999767% of all single bursts. o If P(x) has (x^c+1) as a factor it will also detect double bursts such that the length of the shorter burst does not exceed the degree of p(x) and the sum of the lengths of the two bursts does not exceed c+1, provided the record length including check bits does not exceed the period of p(x). A double burst consists of two bursts separated by an arbitrary number of bits. o Most of remaining bursts. By picking a polynomial with a factor x+1 we guarantee a hamming distance of 4 (without this term hamming distance is at most 3 as long as P(x) has two or more terms and a factor with 3 or more terms). By picking the other factor to be a primitive poly we maximize the cycle length and thus increase our coverage of errors for which the coverage depends on cycle length, such as for double bit errors and for burst detection. Burst detection allows more bits to change than the hamming distance would imply but the bits must be close together. If all error patterns are equally probable the form of the polynomial is unimportant and only the number of check bits matters. Cavanna [Page 4] Internet-Draft iSCSI û CRC or Checksum March 2001 5. CRC-64 is overkill Protection length increases to 2^64 or 1.8 x10^19 bits. This increased protection length is not needed for iSCSI. The fraction of errors that are detected when all errors are equally probable is 1- 1/2^64. When all errors are equally probable the fraction detected by CRC-32, 1-1/2^32 or 99.9999999767%, is large enough. The size of single burst that is always detected is 64 whereas for CRC-32 it is 32 that is, CRC-64 will catch ALL single bursts of size 64 whereas CRC32 will only catch MOST such bursts. Many more errors are, of course, detected by CRC64 than by CRC32. Note that a checksum with 64 bits will detect the same fraction as CRC-64 ,1-1/2^64 û when all errors are equally probable [ref3]. Since we want to detect errors in buses that are wider than 64 bits the burst protection of CRC-64 is not sufficient to guarantee 100% detection. 6. What Fletcher-32/Adler-32 Checksum can protect from? Assume 2s complement sum. We can claim the following protection [ref 1]: o All single bit errors. o For Fletcher-32 and for Adler-32 modified to handle 2 bytes at once, all single bursts of less than 31 bits (possibly 32 for Adler-32). o Most other errors. o 1-1/2^32*100 % of all errors when all errors are equiprobable. This is the same as CRC-32 [ref 3] o Adler-32 checks the sequence length so a separate check is not necessary. Cavanna [Page 5] Internet-Draft iSCSI û CRC or Checksum March 2001 7. Adler vs. Fletcher for iSCSI. The only comparison (RFC-1950) I have seen between Fletcher and Adler involved Fletcher-16 (ones complement version) vs. Adler-32 and Adler-32 seemed better but, for the type of errors we are trying to protect from, is primarily due to the increase in the number of check bits rather than the change in algorithm û my opinion. If we compare Adler-32 to 32 bit Fletcher there are only two differences, both of which are minor in the context of error protection for iSCSI. Adler-32 differs in: o Initial value for S1 is 1 to make the length of the sequence part of S2 so extra or missing bytes with a value of zero will produce a different checksum. Since the length of the data record is easily verifiable by other means this is not a significant benefit. o Modulo is 65521 (a prime number) to avoid (according to RFC 1950) a possible large class of two-byte errors from going undetected. RFC 1950 was referring to ones complement Fletcher-16 which has the blind spot for 16 bit bursts due to its two representations for zero which produce the same checksum. Ref 1 also claims that Fletcher-16 guarantees detection of only 15 bits. My belief is that Fletcher-32 detects all bursts of 31 bits and may have a similar blind spot as Fletcher-16, but for 4-byte errors. Presumably Adler-32, which handles one data byte at a time, guarantees detection of all 2-byte bursts but I am not sure. Presumably Adler-32 if modified to handle two bytes at a time would catch all bursts of 32 bits. Again I am not positive of this but will confirm and report my conclusion. Cavanna [Page 6] Internet-Draft iSCSI û CRC or Checksum March 2001 8. Example of errors that are not detected by Adler-32, Fletcher-32, CRC-32. 8.1. [Ref2] shows some patterns that Fletcher and Adler will not detect but that CRC-32 will detect by virtue of its single burst detection capability. Adler-32 will not detect a change in 3 consecutive bytes from x,y,z to xÆ,yÆ,zÆ when the bytes are related as follows: zÆ-z= -(xÆ-x)-(yÆ-y) and 2xÆ+yÆ=2x+y For example the 3 byte sequence consisting of 4,2,1 is changed to 5,0,2 and the checksum is the same. This is only a 3 byte burst. Why is it not detected by Adler-32 when Fletcher-32 detects all bursts of 31? Because Adler-32 has been defined to handle one byte of data at a time. In this respect Adler- 32 is inferior to Fletcher-32 which is defined to handle 2-bytes of data at a time. I suppose Adler-32 can easily be modified to handle 2 bytes of data at a time. Note that this change involves 5 bits and requires invocation of the burst detection (since the bits are close together) properties of the Adler-32 checksum as it would of CRC-32 which has a hamming distance as low as 4. 8.2. CRC-32 will not detect any error pattern consisting of its coefficients nor any multiple of it (sum of shifted versions). The shortest such pattern is 33 bits. I should point out that the patterns that get by Adler-32 may be easily expressed in a short equation but are not necessarily more likely to occur than the patterns that get through the CRC-32. Cavanna [Page 7] Internet-Draft iSCSI û CRC or Checksum March 2001 9. Classes of errors to protect against Note that iSCSI is not the primary level of protection. In particular we do not need to protect from link type of errors. o Errors introduced at layers below iSCSI by sending or receiving node. o Software errors (buffer mismanagement). o DMA hardware that fails to DMA all the data or DMAs more data than it should, or corrupts the data. o Errors introduced by middle boxes that recomputed checksums for layers below iSCSI after introducing intentional and perhaps unintentional changes. o Unintentional changes in middle boxes and end nodes o Memory errors (random or pattern dependent) o Bus errors (widths: 16,32,64,128) o Fifo overruns and underruns o Summarizing probable error patterns o Missing data in chunks of 16, 32, 64, 128 bits o Extra data in chunks of 16, 32, 64, 128 bits o Changed data in chunks of 1, 16, 32, 64, 128 bits o Periodic single bit errors every 16 or 32 or 64 or 128 bits. Cavanna [Page 8] Internet-Draft iSCSI û CRC or Checksum March 2001 10. How good is our coverage of such errors? o When a single chunk is modified a 32 bit checksum and a 32 bit CRC both provide complete coverage for chunk sizes less than 32 bits. CRC-32 provides complete coverage for chunk sizes of 32. o CRC-64 provides complete coverage up to chunk size of 64 bits. o None provide complete coverage for chunk sizes of greater than 64 bits. o For single bit errors all provide complete coverage. o CRC-32 provides complete coverage for 2 and good coverage for 3 single bit errors. 11. Comparing CRC with Checksum o CRC algorithm uses division rather than addition. o A small change in input affects many bits of the CRC. o The number of bits is most important. o The form is not so important for the types of errors that we need to detect o CRCs are more sensitive to the bursty nature of communication line noise and will detect ALL bursts shorter than the size of the CRC. This is not the job of the iSCSI CRC but of the frame level CRC. The ones complement sum is not insensitive to these error patterns, it is just not especially sensitive to them. The extra sensitivity of a CRC to burst errors comes at the expense of lessened sensitivity to other bit pattern errors since the total fraction of errors detected remains the same. See Ref [3] o CRC is more likely to detect error patterns displaying regularity such as periodic single bit errors but this comes at the price of decreased sensitivity to other types of errors since the total fraction of error patterns detected, when all are equiprobable, for a given number of check bits is the same for CRC or a checksum. o For small enough number of errors CRC is guaranteed to catch ALL patterns as explained in a previous section and thus, if error patterns with small number of errors are more common, then CRC provides better error coverage. Again, this comes at the expense of decreased sensitivity to other error patterns although such patterns tend to be irregular and presumably less common. Cavanna [Page 9] Internet-Draft iSCSI û CRC or Checksum March 2001 o CHECKSUM, by contrast has more holes for error patterns with small number of errors, but CHECKSUM compensates by catching errors that CRC will miss. Again, the total fraction of error patterns detected only depends on the number of check bits [ref3]. o In a physical link where the primary source of errors is random noise it is very attractive to use an error protection scheme which guarantees complete protection for the most common errors which are single, double and triple individual bits or bursts (because of group encoding). For example if the bit error rate is low enough that the probability of 3 or more bits in error within a data record is so low that, at the link bit rate, the probability of 3 or more bits is negligible, then the CRC offers practically complete protection. However, to reiterate, it is the function of the link CRC to provide this protection, not the iSCSI message check sequence. o For group-encoded data, detecting all occurrences of 2 bits or less implies detecting all occurrences of two bursts of size that depends on the group encoding. For example for 8B:10B encoding, the bursts are 8 bits wide. CRCs can be easily designed to guarantee 100% protection from 2 bursts of 8 bits or less occurring anywhere within a record (of practical length). In fact CRC-32 will catch all double bursts of size 9 for code length up to 13000 [ref4]. This is not as easy to implement with checksums. o We need to characterize the types of errors that we need to protect from and confirm that CHECKSUM provides sufficient protection. 12. Checksum partials easier to handle When an iSCSI message is composed of multiple blocks that arrive at different time and perhaps out of sequence, the receiver needs to accumulate partial digests (CRC or checksum) from the blocks. Combining the partial digests appears to be significantly cheaper and faster for checksums than for CRCs. Cavanna [Page 10] Internet-Draft iSCSI û CRC or Checksum March 2001 13. Recommendation Fletcher-32 is my first choice. It is cheaper to implement than CRC- 32 and probably provides adequate protection from the expected errors. Unless Adler-32 is modified to handle 2 bytes at a time Fletcher-32 has superior single burst detection performance. There is not sufficient benefit in Adler-32 to justify the additional complexity of the mod 65521 arithmetic. CRC-32 is my second choice. There is not sufficient benefit in CRC- 64 to justify the additional complexity and overhead. Cavanna [Page 11] Internet-Draft iSCSI û CRC or Checksum March 2001 14. References [1] Performance of Checksums and CRCÆs over Real Data by Jonathan Stone, Michael Greenwald, Craig Partridge. IEEE/ACM Transactions on Networking, Vol. 6, no. 5, October 1998 [2] On Fletcher and Adler codes, and classic CRCs. email from Dr. Dafna Sheinwald from the IBM Haifa Research Lab to iSCSI group via Julian Satran of IBM circa 1/25/01. [3] FITS Checksum Proposal by R.L. Seaman and W.D. Pence 24 August 1995. http://rosat.gsfc.nasa.gov/docs/heasarc/ofwg/docs/general/checksum/n ode18.html [4] Toru Fujiwara, Tadao Kasami, Shu Lin. Error Detecting Capabilities of the Shortened Hamming codes adapted for error detection in IEEE standard 802.3. IEEE Transactions on Communications, vol. 37, no.9, 1989, pp. 986-989 15. Authors' Addresses Vicente Cavanna 1101 Creekside Ridge Drive Suite 100 Roseville, CA 95661-9051 USA Phone: 916-788-5797 Email: vince_cavanna@agilent.com Matt Wakeley 1101 Creekside Ridge Drive Suite 100 Roseville, CA 95661-9051 USA Phone: 916-788-5670 Email: matt_wakeley@agilent.com Expires September 2001 Cavanna [Page 12]