RE: CRC vs CHKSUM presentation slides

["THALER,PAT (A-Roseville,ex1)" <pat_thaler@agilent.com>]

Vince,

Probably Fujiware, et al only examined the results for the Ethernet packet
length and shorter. The Ethernet CRC was also adopted for FDDI and 802.5
Token Ring. I know its protection was checked for 4-bit Hamming distance out
to their larger maximum packet sizes. I think Raj Jain would have been one
of the authors, but it would have been quite a while ago like early 80's.

Actually, the three bit coverage for Ethernet is still important for
protection against individual bit errors as might occur in a fiber optic
receiver. Ethernet uses two coding schemes at 10 Gbit/s. One is the 8B/10B
code. In that case, 3-bit error coverage of the polynomial is not important
because the code as it is used will detect any odd number of bit errors in a
packet. The other is the 64B/66B code. This code doesn't block code the
data. A single bit error in the data field causes a single bit error in the
received data. Packet delimiters and sync headers in this code are designed
to provide 4-bit Hamming distance for false delimiter creation. The code
relies on the CRC for protection against bit hits in the data field.

I'm not sure what is most important for protection under the ISCSI CRC (or
checksum). I think the supposition is that the data will be protected by
transmission system CRCs when it is on the wires and that the main purpose
of the ISCSI protection is for coverage while the packets are in switches,
routerrs, etc. There are several potential kinds of errors:

Random bit errors in data - Hamming distance matters here because
Pbe^Hamming_distance is a factor in the Pud calculation.

Individual wrong byte/word read/write error in memory - If this is a concern
and one expects byte wide structures in the memory, then a CRC like the
Ethernet CRC that detects any two errored bytes in a packet would be
desireable. If such errors are expected to be wider than a byte, then the
various 32-bit CRCs should be about equal. Fletcher is extremely weak for
this kind of error because many two byte hits exist that produce
undetectable errors. Adler avoids the 2 byte hit problem, but is weak for
hits beyond.

Random bit errors in buffer structure pointers - A broad class of
switch/router/end node architectures store packets in a series of buffers
with pointer lists. If there is an error in reading a pointer, the packet
error would be similar to the errors analyzed in Performance of Checksums
and CRC's over Real Data; Jonathan Stone, et al. Unfortunately, that paper
examined only the 16-bit TCP checksum and the AAL5 CRC.

Regards,
Pat
-----Original Message-----
From: CAVANNA,VICENTE V (A-Roseville,ex1) 
Sent: Friday, March 23, 2001 10:34 AM
To: THALER,PAT (A-Roseville,ex1); 'mbakke@cisco.com';
'jim.williams@emulex.com'; 'ips@ece.cmu.edu'
Cc: CAVANNA,VICENTE V (A-Roseville,ex1)
Subject: RE: CRC vs CHKSUM presentation slides


Pat and others,

I have not actually determined for myself the coverage of the ethernet poly
for 3 errors. All I know for sure, as I show in my slides, is that the
ethernet poly, because it does not have an x^c+1 term, cannot detect ALL
occurrences of an odd number of errors (including 3). I have therefore
quoted data from the widely referenced paper (which I have refereced many
times before) by Fujiware, Kasami and Lin on Error detecting capabilities of
hte ethernet polynomial . This paper claims the Ethernet poly has a Hamming
distance of 4 for lengths 3007 <= n <= 12144 and larger hamming distance for
smaller n. 

It seems quite a coincidence to me that 12144 happens to be the length of
the maximum IEE 802.3 frame (prior to VLAN tagging) and I can only assume
that the polynomial was either expressely designed for that coverage or the
coverage is actually larger than 12144 and the authors thought 12144 was
sufficient and did not bother to give the exact number. 

In any case, I don't think it is particularly important for the ethernet
poly to be able to catch ALL 3 bit errors since, due to the group encoding
used, 3 bit errors on the link will manifest themselves as 3 bursts for
which the ethernet poly most likely does not have complete coverage anyway.
At one time (prior to the use of group encoding) the ability to detect 3 bit
errors may have been important but not today. Same is true for Fiberchannel
which has even larger frame sizes and also uses group encoding.

Vince

|-----Original Message-----
|From: THALER,PAT (A-Roseville,ex1) 
|Sent: Friday, March 23, 2001 9:59 AM
|To: vince_cavanna@agilent.com; mbakke@cisco.com;
|jim.williams@emulex.com; ips@ece.cmu.edu
|Subject: RE: CRC vs CHKSUM presentation slides
|
|
|Vince,
|
|Your statement is correct except for the number 12144. 12144 
|bits is the length of the maximum IEEE 802.3 frame (before we 
|added 4 bytes for VLAN tagging). The polynomial was actually 
|checked for coverage of 3-bit errors out to the Token Ring and 
|FDDI maximum packet sizes which are about 3 times as long. I 
|don't know the length at which the first undetectable 3-bit 
|error occurs, but it is something beyond 32000 bits.
|
|I also have trouble with an argument based on leverage. 
|Hardware design of CRC generators and checkers is just not 
|that hard. It's a register plus a bunch of XOR's.
|
|Regards,
|Pat
|
|-----Original Message-----
|From: vince_cavanna@agilent.com [mailto:vince_cavanna@agilent.com]
|Sent: Thursday, March 22, 2001 4:10 PM
|To: vince_cavanna@agilent.com; mbakke@cisco.com;
|jim.williams@emulex.com; ips@ece.cmu.edu
|Subject: RE: CRC vs CHKSUM presentation slides
|
|
|To save Julian from having to write a memo I would like to add that the
|ethernet polynomial has a certain weakness for 3 bit errors 
|that the others
|don't. The ethernet polynomial is only guaranteed to catch all 
|combination
|sof 3 bit errors when the message length is up to 12144 bits. 
|For larger
|message lengths some 3 bit errors may get through. 
|Vince
|
|
||-----Original Message-----
||From: CAVANNA,VICENTE V (A-Roseville,ex1) 
||Sent: Thursday, March 22, 2001 3:42 PM
||To: 'Mark Bakke'; 'Jim Williams'; ips@ece.cmu.edu
||Cc: CAVANNA,VICENTE V (A-Roseville,ex1)
||Subject: RE: CRC vs CHKSUM presentation slides
||
||
||Mark and Jim,
||I think any of the 32 bit CRC polynomials that have been 
||proposed are more than good enough. My main reason for 
||recommending hte CCITT-CRC32 is that it is half the cost of 
||the others in terms of gate count - and unless you are doing a 
||serial divider, which would be too slow, the gate count is 
||very significant. Also, the leverage may not be as high as you 
||think unless we are willing to use the datapath width of 
||existing implementations. For 10 gig we will probably need to 
||have larger than normal datapath widths. If you change the 
||datapath width to handle, say, 64 bits at a time you change 
||the implementation. I would otherwise have no problem with 
||using the ethernet polynomial. I will try to explain later why 
||I am not concerned about using the same polynomial and 
||potentially giving up some cross-checking (I am not quite sure yet).
||Vince
||
|||-----Original Message-----
|||From: Jim Williams [mailto:jim.williams@emulex.com]
|||Sent: Thursday, March 22, 2001 1:30 PM
|||To: ips@ece.cmu.edu
|||Subject: Re: CRC vs CHKSUM presentation slides
|||
|||
|||From: "Mark Bakke" <mbakke@cisco.com>
|||To: "CAVANNA,VICENTE V (A-Roseville,ex1)" <vince_cavanna@agilent.com>
|||Cc: <ips@ece.cmu.edu>; <ipsan@rtl.rose.agilent.com>
|||Sent: Thursday, March 22, 2001 4:00 PM
|||Subject: Re: CRC vs CHKSUM presentation slides
|||
|||
|||> Vicente-
|||> 
|||> I just took another look through your slides after seeing the
|||> presentation on Monday.  They were very well-done.  I have
|||> one question, though.  If the CCITT-CRC32 is considered "good
|||> enough", then would the Ethernet CRC32 also be good enough?  The
|||> reason I ask is that every hardware vendor involved in building
|||> iSCSI stuff already has implementations of the Ethernet CRC, 
|||> which is used for both Ethernet and Fibre Channel.
|||> 
|||> The Ethernet poly has more terms than CCITT, and perhaps is
|||> not as good as CRC-32C (any thoughts?), but everyone has hardware
|||> and software for this, with proven interoperability (bit and
|||> byte order, etc).  Performance-wise, it will be there for
|||> 10Gb Ethernet, so it should be fast enough.
|||> 
|||> So if the Ethernet poly is deemed good enough (even if it's not
|||> the best), and fast enough (even if it's not the fastest), why
|||> not use it?  I think we would stand a much better chance of
|||> achieving interoperability in a short time.
|||> 
|||> Please let me know what you think of this; I realize that a few
|||> of my questions were speculative.
|||
|||Since the iSCSI messages will often be encapsulated in ethernet
|||packets, there is some value to using a different CRC.  Link
|||errors are double protected with two different CRCs.  If
|||ethernet and iSCSI use the same polynomial, there is little
|||additional coverage against link errors.  This point may not
|||be decisive, but all other things being equal or almost
|||equal, it is worth considering.
|||
||
|