rfc3385.txt

一个学习iSCSI协议的文档

   explored 47000 polynomials (not all the possible ones).  The best
   they found has d=6 up to block lengths of 5275 and d=4 up to 2^31-1
   (bits).

   The investigation was done in 1993 with a special purpose processor.

   By comparison, the IEEE-802 code has d=4 up to at least 64,000 bits
   (Fujikura stopped looking at 12,144) and d=3 up to 2^32-1 bits.





Sheinwald, et. al.           Informational                      [Page 6]

RFC 3385                iSCSI CRC Considerations          September 2002


   CRC32/4 (we will refer to it as CRC32C for the remainder of this
   memo) is 11EDC6F41;  IEEE-802 CRC is 104C11DB7, denoting the
   coefficients as a bit vector.

   [Stone98] evaluated the performance of CRC (the AAL5 CRC that is the
   same as IEEE802) and the TCP and Fletcher checksums on large amounts
   of data.  The results of this experiment indicate a serious weakness
   of the checksums on real-data that stems from the fact that checksums
   do not spread the "hot spots" in input data.  However, the results
   show that Fletcher behaves by a factor of 2 better than the regular
   TCP checksum.

4. Probability of Undetected Errors - Burst Error

4.1 CRC32C (Derivations from [Wolf94j])

   Wolf [Wolf94j] found a 32-bit polynomial of the form g(x) = (1+x)p(x)
   for which the conditional probability of undetected error, given that
   a burst of length 33 occurred, is at most (i.e., maximized over all
   possible channel bit error probabilities within the burst) 4 * 10^-
   10.

   We will now figure the probability of undetected error, given that a
   burst of length 34 occurred, using the result derived in this paper,
   namely that for a given code, for all b in the range 32 < b < n, the
   conditional probability of undetected error for the (n, n-32) code,
   given that a (b:p) burst occurred, is equal to the probability of
   undetected errors for the same code (the same generating polynomial),
   shortened to block length b, when this shortened code is used with a
   binary symmetric channel with channel (sporadic, independent) bit
   error probability p.

   The approximation formula for Pud of sporadic errors, if the weights
   Ai are distributed binomially, is:

   Pud(C, epsilon) =~= Sigma[for i=d to n] ((n choose i) / 2^r )*(1-
   epsilon)^(n-i) * epsilon^i .

   Assuming a very small epsilon, this expression is dominated by i=d.
   From [Fujiwara89] we know that for 32-bit CRC, for such small n,
   d=15.  Thus, when n grows from 33 to 34, we find that the
   approximation of Pud grows by (34 choose 15) / (33 choose 15) =
   34/19; when n grows further to 35, Pud grows by another 35/20.

   Taking, from Wolf [Wolf94j], the most generous conditional
   probability, computed with the bit error probability p* that
   maximizes Pub(p|b), we derive: Pud(p*|33) = 4 x 10^{-10}, yielding
   Pud(p*|34) = 7.15 x 10^{-10} and Pud(p*|35) = 1.25 x 10^{-9}.



Sheinwald, et. al.           Informational                      [Page 7]

RFC 3385                iSCSI CRC Considerations          September 2002


   For the density function of the burst length, we assume the Rayleigh
   density function (the discretization thereof to integers), which is
   the density of the absolute values of complex numbers of Gauss
   distribution:

      f(x) = x / a^2  exp {-x^2 / 2a^2 }     , x>0 .

   This density function has a peak at the parameter a and it decreases
   smoothly as x increases.

   We take three consecutive bits as the most common burst event once an
   error does occur, and thus a=3.

   Now, the probability that a burst of length b occurs in a specific
   position is the burst error rate, which we estimate as 10^{-10},
   times f(b).  Calculating for b=33 we find f(33) = 1.94 x 10^{-26}.
   Together, we found that the probability that a burst of length 33
   occurred, starting at a specific position, is 1.94 x 10^{-36}.

   Multiplying this by the generous upper bound on the probability that
   this burst error is not detected, Pud(p*|33), we get that the
   probability that a burst occurred at a specific position, and is not
   detected, is 7.79 x 10 ^{-46}.

   Going again along this path of calculations, this time for b=34 we
   find that f(34) = 4.85*10^{-28}.  Multiplying by 10^{-10} and by
   Pud(p*|34) = 7.15*10^{-10} we find that the probability that a burst
   of length 34 occurred at a specific position, and is not detected, is
   3.46*10^{-47}.

   Last, computing for b=35, we get 1*10^{-29} * 10^{-10} * 1.25*10^{-9}
   = 1.25*10^{-48}.

   It looks like the total can be approximated at 10^-45 which is within
   the bounds of what we are looking for.

   When we multiply this by the length of the code (because thus far we
   calculated for a specific position) we have 10^-45 * 6.5*10^4 =
   6.5*10^-41 as an upper bound on the probability of undetected burst
   error for a code of length 8K Bytes.

   We can also apply this overestimation for IEEE 802.3.

   Comment: 2^{-32} = 2.33*10^{-10}.







Sheinwald, et. al.           Informational                      [Page 8]

RFC 3385                iSCSI CRC Considerations          September 2002


5. Probability of Undetected Errors - Independent Errors

5.1 CRC (Derivations from [Castagnoli93])

   It is reported in [Castagnoli93] that for BER = epsilon=10^-6, Pud
   for a single bit error, for a code of length 8KB, for both cases,
   IEEE-802.3 and CRC32C is 10^{-20}.  They also report that CRC32C has
   distance 4, and IEEE either 3 or 4 for this code length.  From this,
   and the minimum distance of the code of this length, we conclude that
   with our estimation of epsilon, namely 10^{-11}, we should multiply
   the reported result by {10^{-5}}^4 = 10^{-20} for CRC32C, and either
   10^{-15} or 10^{-20} for IEEE802.3.

5.2 Checksums

   For independent bit errors, Pud of CRC is approximately 12,000 better
   than Fletcher, and 22,000 better than Adler.  For burst errors, by
   the simple examples that exist for three consecutive values that can
   produce an undetected burst, we take the factor to be at least the
   same.

   If in three consecutive bytes, the error values are x, -2x, x then
   the error is undetected.  Even for this error pattern alone, the
   conditional probability of undetected error, assuming a uniform
   distribution of data, is 2^-16 = 1.5 * 10^-5.  The probability that a
   burst of length 3 bytes occurs, is f(24) = 3*10^-14.  Together:
   4.5*10^-19.  Multiplying this by the length of the code, we get close
   to 4.5*10^-16, way worse than the vicinity of 10^-40.

   The numbers in the table in Section 7 below reflect a more "tolerant"
   difference (10*4).

6. Incremental CRC Updates

   In some protocols the packet header changes frequently.  If the CRC
   includes the changing part, the CRC will have to be recomputed.  This
   raises two issues:

      - the complete computation is expensive
      - the packet is not protected against unwanted changes
        between the last check and the recomputation

   Fortunately, changes in the header do not imply a need for completed
   CRC computation.  The reason is the linearity of the CRC function.
   Namely, with I1 and I2 denoting two equal-length blocks of
   information bits, CRC(I) denoting the CRC check bits calculated for
   I, and + denoting bitwise modulo-2 addition, we have CRC(I1+I2) =
   CRC(I1)+CRC(I2).



Sheinwald, et. al.           Informational                      [Page 9]

RFC 3385                iSCSI CRC Considerations          September 2002


   Hence, for an IP packet, made of a header h followed by data d
   followed by CRC bits c = CRC(h d), arriving at a node, which updates
   header h to become h', the implied update of c is an addition of
   CRC(h'-h 0), where 0 is an all 0 block of the length of the data
   block d, and addition and subtraction are bitwise modulo 2.

   We know that a predetermined permutation of bits does not change
   distance and weight statistics of the codewords.  It follows that
   such a transformation does not change the probability of undetected
   errors.

   We can then conceive the packet as if it was built from data d
   followed by header h, compute the CRC accordingly, c=CRC(d h), and
   update at the node with an addition of CRC(0 h'-h)=CRC(h'-h), but on
   transmission, send the header part before the data and the CRC bits.
   This will allow a faster computation of the CRC, while still letting
   the header part lead (no change to the protocol).

   Error detection, i.e., computing the CRC bits by the data and header
   parts that arrive, and comparing them with the CRC part that arrives
   together with them, can be done at the final, end-target node only,
   and the detected errors will include unwanted changes introduced by
   the intermediate nodes.

   The analysis of the undetected error probability remains valid
   according to the following rationale:

   The packet started its way as a codeword.  On its way, several
   codewords were added to it (any information followed by the
   corresponding CRC is a codeword).  Let e denote the totality of
   errors added to the packet, on its long, multi-hop journey.  Because
   the code is linear (i.e., the sum of two codewords is also a
   codeword) the packet arriving to the end-target node is some codeword
   + e, and hence, as in our preceding analysis, e is undetected if and
   only if it is a codeword by itself.  This fact is the basis of our
   above analysis, and hence that analysis applies here too.  (See a
   detailed discussion at [braun01].)

7. Complexity of Hardware Implementation

   Comparing the cost of various CRC polynomials, we used a tool
   available at http://www.easics.com/webtools/crctool to implement CRC
   generators/checkers for various CRC polynomials.  The program gives
   either Verilog or VHDL code after specifying a polynomial, as well as
   the number of data bits, k, to be handled in one clock cycle.  For a
   serial implementation, k would be one.





Sheinwald, et. al.           Informational                     [Page 10]

RFC 3385                iSCSI CRC Considerations          September 2002


   The cost for either one generator or checker is shown in the
   following table.

   The number of 2-input XOR gates, for an un-optimized implementation,
   required for various values of k:

   +----------------------------------------------+
   | Polynomial  | k=32     | k=64     | k=128    |
   +----------------------------------------------+
   | CCITT-CRC32 | 488      | 740      | 1430     |
   +----------------------------------------------+
   | IEEE-802    | 872      | 1390     | 2518     |
   +----------------------------------------------+
   | CRC32Q(Wolf)| 944      | 1444     | 2534     |
   +----------------------------------------------+
   | CRC32C      | 1036     | 1470     | 2490     |
   +----------------------------------------------+

   After optimizing (sharing terms) and in terms of Cells (4 cells per 2
   input AND, 7 cells per 2 input XOR, 3 cells per inverter) the cost
   for two candidate polynomials is shown in the following table.

   +-----------------------------------+
   | Polynomial  | k=32     | k=64     |
   +-----------------------------------+
   | CCITT-CRC32 | 1855     | 3572     |
   +-----------------------------------+
   | CRC32C      | 4784     | 7111     |
   +-----------------------------------+

   For 32-bit datapath, CCITT-CRC32 requires 40% of the number of cells
   required by the CRC32C.  For a 64-bit datapath, CCITT-CRC32 requires
   50% of the number of cells.

   The total size of one of our smaller chips is roughly 1 million
   cells.  The fraction represented by the CRC circuit is less than 1%.

8. Implementation of CRC32C

8.1 A Serial Implementation in Hardware

   A serial implementation that processes one data bit at a time and
   performs simultaneous multiplication of the data polynomial by x^32
   and division by the CRC32C polynomial is described in the following
   Verilog [ieee1364] code.






Sheinwald, et. al.           Informational                     [Page 11]

RFC 3385                iSCSI CRC Considerations          September 2002


   /////////////////////////////////////////////////////////////////////
   //File: CRC32_D1.v
   //Date: Tue Feb 26 02:47:05 2002
   //
   //Copyright (C) 1999 Easics NV.
   //This source file may be used and distributed without restriction
   //provided that this copyright statement is not removed from the file
   //and that any derivative work contains the original copyright notice
   //and the associated disclaimer.
   //
   //THIS SOURCE FILE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS
   //OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
   //WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
   //
   //Purpose: Verilog module containing a synthesizable CRC function
   //* polynomial: (0 1 2 4 5 7 8 10 11 12 16 22 23 26 32)
   //* data width: 1
   //
   //Info: [e-mail] (Jan Decaluwe)
   //http://www.easics.com
   /////////////////////////////////////////////////////////////////////
   module CRC32_D1;
   // polynomial: (0 1 2 4 5 7 8 10 11 12 16 22 23 26 32)
   // data width: 1
   function [31:0] nextCRC32_D1;