Subject: Re: [Tsvwg] [SCTP checksum problems]

From: Craig Partridge <[email-masked]>
Date: Wed, 18 Apr 2001 10:08:05 -0400

Hi Julian:

I read your ID quickly and may have more comments later.

I think the bit error study is flawed.  The key issue here is that
the TCP, and Fletcher checksum (and I think Adler) will catch all
1 bit errors.  Indeed, the TCP checksum will catch up to 16 distinct
bit errors, provided that the bit offsets are all distinct, modulo 16.

Expressing this simply, assuming my system did its Poisson calculations
right:

    * we don't have to worry about single bit errors in a chunk of
      data, the checksum will always catch it.

    * the probability of 2 bit errors occuring in a single 1KB packet
      is about 1 in 3* 10^15.  The probability that the two bits will
      have the same offset mod 16 is around .008 (if I did the distribution
      right) and the chance is 50% that the two bits will offset each other
      (i.e. they'll flip opposite ways).  Ergo, your chance of an
      undetected error is about 1 in 8*10^17.  I believe (without having
      done all the match) that is as good or better than you'll get for
      CRC32 in almost all cases.  Since the checksums are cheaper to compute,
      they're a win.

    * more than 2 bit errors per chunk is so rare we probably don't care

So the big issue is burst errors (and, incidentally, burst erasures).

Thanks!

Craig

_______________________________________________
tsvwg mailing list
[email-masked]
http://www1.ietf.org/mailman/listinfo/tsvwg

---

From: Jonathan Stone <[email-masked]>
Date: Wed, 18 Apr 2001 08:50:24 -0700

Julian, 

I skimmed your i-d late last night.  

I have not gone through the analysis of different CRCs. I'd like to
compare it to Raj Jain's analysis of the IEEE 802 CRC-32 in
http://www.cis.ohio-state.edu/~jain/papers/xie1.html; which I think
speaks to the siglne-bit-error point Craig has already raised.

The question I'd raise is a more fundamental one: whether link-level
bit and burst error rates are the appropriate model for an Internet
transport-level sum in the first place.

Craig Partridge and I examined that in our SIGCOMM 2000 paper.  
We monitored packets at a number of points in the Internet, and looked
for packet with checksum mismatches-- packets where recomputing the
checksum did not match the content of the checksum field.  We also
looked for transport-level (TCP) retransmissions of the damaged
packets.

Let's  call packets where a recomputation of the TCP (or UDP) checksum
does not match the contents of the checksum field a "mismatch". 

We observed mismatch rates of roughly 1 in 4,000 (average); best-case
around 1 in 30,000.  that's 5 or 6 orders of magnitude higher than the
link-level error rates you cite.  By comparing the checksum-mismatches
against a TCP-level retransmission, we were able to estimate how much
damage occured to the mismatches.  Keep in mind that these errors were
caught at the TCP layer: they have already passed a link-level CRC
check, usually the 802.3 CRC-32. The very high observed error rate
suggests thet these errors  occur outside the protection of the
MAC-layer CRC. 

For the iSCSI analysis, a fair synopsis is that half the packets were
so thoroughly curdled we couldn't even guess at what caused thenn
damage. there are more details in the SIGCOMM paper.
(There, I focused more on analyzing how the standard TCP sum would fare.
I am in the midst of recomputing total burst length and hamming
distances, for a polynomial-xor description of the errors rather
than the `minimum edit distance'.)

That characterization of errors is very different to the independent
bit-error and correlated-burst-error models used in the ID.

I think our data supports three conclusions relevant to this
discussion. (You may of course disagree.)

First, the Internet contains a variety of error sources above the
MAC-level:i between two MAC-layer interface cards inside a router; or
inside an end-host, between its MAC-layer card and its TCP (or SCTP,
or UDP, or other transport protocol).  

Second, error rates from these sources occur at rates several
orders of magnitude higher than current link-level errors.

Third, the damage done by these error sources  just does not match
the individual-bit/ single-burst model common in coding theory,
and often used to characterize link errors.

While we did observe a (very) few single-bit errors and short bursts,
we also observed a lot of much longer bursts. Approximately half the
damaged packets were so thoroughly curdled that more than half the
bytes were incorrect.  (We also found similar rates and patterns in
packet traces from Vern Paxson; those are included in our SIGCOMM 2000
paper.)

It may be helpful to think of *some* of these errors as due to (for
example) a single-bit error affecting a DMA pointer: flipping an
address bit can cause a large change in the data stream going to or
from the network interface. If the bit position flipped is high
enough, it could even skip to another packet altogether.

Its not clear how the analysis and conclusions in your draft stand up,
if instead of a link-level single-bit/burst error model, we
ed substitute the error characteristics and rates we observed in 
`in the wild' Internet traffic-- that is, error rates some 5 or
6 orders of magnitude higher, and where the errors cause either multiple
bursts per packet, or (if modeled as a single polynomial) vary from a few
dozen bits, up to a substantial fraction of the packet length.

The order-of-magnitude changes in error rate will obviously have an
impact.  I haven't thought in detail about whether the conclusions
about specific CRC polynomial choices hold up.

One final point is the computational cost of software CRCs.

If you buy our conclusion that the Internet contains very significant
error sources outside of "network interface cards". Then, outboard
acceleration of either checksums or CRCs is somewhat suspect:
error checks done inside the network card simply doesn't cover those
error sources.  Software CRC calculations are typically much slower than
either ones-complement, Fletcher, or Adler sums: Dave Feldmeier's
paper suggests roughly four times slower, for a total 32-bit check,
even for generator polynomials selected to minimze nonzero
coefficients (i.e,. few taps).  For the IEEE 802 CRC, its
faster to do a table-lookup, which is slower again.
I dont know whether the iSCSI community has considered that
issue, or where they/you stand on it.