Subject: Re: [e2e] Re: [Tsvwg] Really End-to-end or CRC vs everything else?

From: "Jonathan Stone" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:04 -0700

In message <[email-masked]>,
"David P. Reed" writes:

>Not to belabor this, but just passing the check-function test is not
>sufficient.  It must also pass a variety of other tests to be accepted in
>the context of a protocol (correct sequence number, correct address, ...).
>
>So the simple combinatoric argument  you sketch below doesn't quite
>work.  You can't synthesize just any datagram that passes the checksum.  It
>also has to meet the other constraints.

Oh, sure Thanks for pointing it out; I never meant it to be taken
that literally.  (In fact the next chapter of my dissertation talks
about this; I went through it in gory detail in in the ATM simulations
I did with Michael Greenwald, Jim Hughes, and Craig Partridge.)

You can interpret the result as applying to a check over just the
payload.  Or you an apply the result to all the bits at a give layer,
by sitting down and counting how many bits of information are check by
the syntactic check at a given layer.  Provided the ``check'' is a
function, not a relation, the proof still holds. (And yes, I did the
work to show how to extend it to a relation, though I didn't address
the specific example of TCP's window.)

The insight that we really cannot rank error-check functions _in
vacuo_, without reference to some error model[*]
(in the sense I use the phrase) is still valid.

[*] Or with reference to some input distribution, if you
buy the information-maximization story.

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

---

From: "Jonathan Stone" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:04 -0700

In message <[email-masked]>,

"Christopher Forsythe" writes:

>The information that is being stated seems to be all about either hardware,
>or software checksumming. The pro of hardware checksumming, as stated in
>earlier messages, is to speed up the total time of processes. The con (as
>stated earlier) is that once placed into the hardware, it cannot be fixed
>easily if broken.
>
>Software checksumming seems to have the exact opposite effect. It doesn't
>seem to affect hardware performance. But it can be fixed if the software
>doesn't seem to be working properly.
>
>The question is.... why couldn't the two be combined?

Not to speak for David Reed or Vern Schryver, but that isn't how I see it.

What I've been trying to say is that after spending person-years
analyzing traces of damaged packets, the best model I have is that
errors at the IP or TCP/UDP/SCTP layers aren't due to line noise.
They're primarily due to memory glitches in packet-buffer memory, or
to glitches in the packet-transfer engines which move packets between
packet-buffer memory (including end-host source and sink buffers) and
the MAC/PHY-layer hardware.

I'm not worried about bugs in the outboard checksuming hardware per se.
The issue is that once the checksum computation is moved outboard,
it covers less of the end-to-end path --- and it misses part of the
path which (according to the absurldy tiny data samples which are all
we have) is an important source of packet-level errors: the path
between end-host memory and the end-host NIC.

Yes, there are good market drivers to use outboard checksumming.
What I'd ask for is a knob toy turn outboard checksums off or on,
and that the knob be off by default. That way, after an undetected error
has pervasively curdled your filesystem *and* your recent backups, you
have no-one to blame but the guy who turned the knob on.

---

From: "Douglas Otis" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:02 -0700

Craig,

Adding to that, if errors were only due to random noise, then a summation
would be okay.  If the errors are not random and are the result of a weak
bus driver as example, then these errors will find a considerable weakness
in a summation that has the same patterns as the errors.  Hardware related
errors may not be random in nature, so any assumption that errors are random
becomes incorrect in these cases.  The source of random errors on the serial
line is prevented by CRC, so remaining errors move more into the area of
hardware related.

Doug

> In message
> <[email-masked]>, "Michael
> A. Ramalho" writes:
>
> >I know of no other easily proven statement for
> >bit "stuckedness" for Alder (or even other statistical
> >or frequency based checking/detection algorithms).
>
> The TCP checksum catches all error patterns that are 15-bits longer or
> less and all but one 16-bit long error.  If you did the TCP checksum as
> a 32-bit checksum (32-bit adds instead of 16) you'd have the same
> property.  If single bit errors are the error pattern, CRC is overkill.
>
> Key point here is we need an error model that is realistic to determine
> what checksum to use.
>
> [Side point -- Jonathan apologies if this steals your thunder -- but
> Jonathan has a nice little proof that, if all error patterns are equally
> likely, that a checksum that just includes a fixed size constant to each
> packet is just as effective as any stronger check -- the moral here is, if
> you don't know the error pattern, you don't know which checksum
> to choose].
>
> Craig
>

---

From: "Douglas Otis" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:04 -0700

Jonathan,

You can't be suggesting a simple summation is worth using in the face of
router memory errors.  You have detected these in the wild and noted their
positions within a 32 word.  You have statistics that indicate there are
more bits in error than others suggesting there may be a weak bus driver
being seen.  From the simple tests that I have run, a simple summation is
extremely weak in this area.  A CRC still does well even when the entire
packet is corrupted including the CRC itself.  There is no need for the CRC
to be affected to improve the performance of the algorithm.  I can say that
Fletcher-16 2^n should be avoided altogether due to this extremely weak
memory bus performance.  It is no where near 2^32 in preformance.  It is
closer to 2^6.  The only reason for placing a mandatory chunk at the end of
the packet would be to ensure against truncation which a good check should
catch.  If there is only one checksum type allowed, then placing this at the
end of the packet has the advantage of minimizing the potential passes this
packet needs in preparation.  Adler-32 suffers the Fletcher problem if the
packet is small or mostly zero.

Doug

> To: Craig Partridge; David P. Reed
> Cc: [email-masked]; end2end
> Subject: Re: [e2e] Re: [Tsvwg] Really End-to-end or CRC vs everything
> else?
>
> In message <[email-masked]>Craig Partridge writes
> >
> >In message <[email-masked]>,
> "David P. Reed"
> >
> >writes:
>
>
>
> >I think you've missed the point.  In a prior note, you suggested
> a line of
> >thinking of assume an adversary.  Implicitly, that's an error model.
> >
> >So what if traffic doesn't match that error model -- that is to
> say, errors
> >are not ones an adversary would pick -- then the checksum chosen is the
> >wrong one.
>
> Craig,
>
> To be fair, there are several points kicking around here, and being
> made to (or intended for) different audiences.  The tsvwg folks are
> under time pressure to (re-)decide on a check function.  The e2e
> folks can take a longer, or at least a middle-vision, view.
>
> The way I'd put it to the tsvwg folks choosing a checksum is this:
> if you start appealing to catching all but 1 in 2^32 errors (or
> more accurately, 1 in 65521^2), then you have fallen into a fallacy.
>
> You have just conflated a purely combinatoric result, about the ratio
> of sizes of the domain and range of the error-check function, with a
> probabilistic statement about how likely *in practice* you are to
> catch errors.  What should give you a serious wake-up call,is to hear
> that even the constant function -- some constant 32-bit integer-- will
> catch the same fraction of all errors.  There's no grounds for
> labelling *any* function (in the mathematical sense) as stronger than
> another, unless we know something about the distribution of the
> errors, or how well some particular function does against some
> particular distribution.    CRCs are not any stronger  than
> checksums, *unless* we happen to know that the distribution of
> acutal errors tends to favour low Hamming-weight errors.
> (the data I and Craig have, is that it doesn't.)
>
>
> The point to Dave Reed is that the combinatoric argument is very
> general and applies to any function, whether the constant function, or
> a cryptographic hash, or a shared-secret key, provided we define
> "error check bits" to properly measure the fraction of bit
> combinations which are accepted, versus those which are
> rejected.
>
>
> One further thing I've mentioned in email is that I recently
> re-analyzed the captured error datasets which I and Craig and Vern
> gathered, and I did find one pattern which could be exploited here.
>
> The pattern is that the errors we found can be broadly characterized
> into two classes: either single-bit or short, low-hamming weight
> errors; or as errors where some prefix of the packet is bad; the
> packet is subjected to an error; and the error continues all the way
> to the end of the packet. The ratio of errored bits within that
> damaged `tail' of packet is very close to 0.5.
>
> That suggests an error model where we model packet-level errors as due
> to either signle-bit errors, memory-readout errors which affect a
> single word or cache line; or due to `stateful' errors in the
> hardware/software finite-state engines which move packets between
> packet- buffer memory, and the hardware which implements some specific
> media layer. (think of errors due to an under-run in a hardware FIFO,
> or a bad bit in a DMA pointer register.)
>
> There's two things to take away from that.  The first is that the
> errors we've acutally observed, in the only study of in-the-wildn
> packet-level errors I know of, the errors are so heavy that, on
> average, they affect more than R bits, for any R that's a plausible
> error-check. That says we're only going to catch errors stochastically.
> The second is that, since the errors seem to be stateful, putting the
> error-cheeck information at the end of the packet rather than in a
> fixed header field doesn't hurt, and (for the reasons we analyzed to
> death in our 98 ToN paper) will acutally help, for the kinds of
> nonuniform data we find in filesystems.
>
> If there's anything i can recommend to the tsvwg, its to pick even a
> 32-bit extension of the TCP checksum, rather than Adler32; and to
> think seriously about moving the error-check bits to the end.  Not to
> help hardware, but to make whatever error-check you use more resilient
> against errors in packet-processing engines which (once an error does
> hit) trash the remainder of the packet.
>
>

---

From: "David P. Reed" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:11 -0700

At 06:57 PM 6/11/01 -0700, Christian Huitema wrote:
>What is at stake here is whether we want a safety belt or an alarm bell.

I would argue that the current TCP isn't a very good alarm bell, because it
doesn't detect too-smart-for-their-own-good, friendly "adversaries" (such
as NATs that recompute the entire checksum correctly after making serious
changes to the contents) that inadvertently weaken the detection.
  Note that, if you really follow the e2e argument, this
>is OK: the only way to be certain that the back-up went well is by
>computing a strong checksum over the whole volume, not by trusting TCP.

Indeed.  But then the IETF ought to spread the gospel to the folks who are
responsible for FTP and SMTP, for example.  These poor souls typically
believe that TCP provides a *reliable* stream, where the word reliable is
implicitly defined as *perfect*.

>In fact, it is all a matter of probabilities and arbitrations. The
>transmission system should be good enough that the backup is OK most of
>the time, so that the e2e checksum (volume) only fails rarely, so that
>the cost of correction is acceptable...

I assume you mean by transmitting the whole file again.

- David
--------------------------------------------
WWW Page: http://www.reed.com/dpr.html

---

From: "Randy Bush" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:13 -0700

> please remove my name from this mailing list.

*NEVER* send requests to be added to or removed from a mailing list to the
address used to send messages to recipients of the list.  It annoys them,
and they can't handle your request.

If you don't remember how you subscribed to the list originally, or someone
just gave you the list address, try:

1) <listname>-request

  Many lists provide such a mailbox for list "administrivia", as this type
  of request is called.

  If the list address is [email-masked], try sending your request to:

      [email-masked]

2) Automated list manager

  Many lists are managed by automated list managers.  If <listname>-request
  doesn't work, try sending the message "help" to each of the above
  addresses.

  If the list address is [email-masked], try sending to:

      [email-masked]
      [email-masked]
      [email-masked]

3) Postmaster

  As a last resort, you can write to the postmaster on the list system
  and ask how to get your request processed.

  If the list address is [email-masked], try sending to:

      [email-masked]

Good luck!

---

From: "Luigi Fratta" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:12 -0700

Thanks

lf

>I assume you mean by transmitting the whole file again.
Prof. Luigi Fratta
Dipartimento di Elettronica e Informazione
Politecnico di Milano
Piazza Leonardo da Vinci, 32
20133  MILANO
Tel.+39-02-2399-3578   Fax.+39-02-2399-3413
email.  [email-masked]

---

From: "Christian Huitema" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:15 -0700

> From: David P. Reed [mailto:[email-masked]]
>
> I would argue that the current TCP isn't a very good alarm bell,
because
> it

As Vernon pointed out, this is exactly what SSL/TLS gives you: a strong
checksum on top of TCP. It is actually commonly used in the
"continuously running applications" that Julo mentioned in his message.
I would expect these applications to do something smart when the SSL/TLS
checksum fails.

> I assume you mean by transmitting the whole file again.

That, or some form of divide and conquer. It is again a matter of
probabilities and arbitrations, whether or not you want to "optimize the
error cases."

-- Christian Huitema

---

From: "Dennis Ferguson" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:18 -0700

> At 04:52 PM 6/10/01 -0700, Dennis Ferguson wrote:
> >Choices which are really good under some sets of circumstances are really
> >bad under others.  For link-by-link protection from transmission errors we
> >have the luxury of crafting the error detection to match the characteristics
> >of the link, and even of changing it if the original choice is proven wrong,
> >but end-to-end checksums are long-lived and are supposed to be able to treat
> >the network stuff in between the ends as an ever-changing black box.  I
> >have no idea how you design for this.
>
> The traditional way to deal with this kind of non-statistical uncertainty
> is pretty straightforward.  What you do is assume that the error process is
> an *adversary* that knows everything about the protocol that can be known,
> and who *wins* the game if they can corrupt the data with a high enough
> probability.
>
> The result of this thinking is that cryptographic message authentication is
> the appropriate answer.  A "key" chosen out of sight of the adversary, at
> random, is used to select from a range of functional transformations which
> are diverse enough so that without knowledge of the key, one cannot
> transform the datagram into an acceptable one.
>
> For this, you don't need an "error model".

Actually what you seem to be doing is changing the problem from error
detection to something that is a bit different.  If we maintain focus
on the error detection problem, however, it is still the case that you've
suggested a solution for end-to-end error detection which I shouldn't
have precluded, that being "brute force".

If MD5 is a good example, then the two properties which make a good
cryptographic checksum seem to be

(1) they carry around a lot of bits in the packet, more than we're
    usually willing to spend for error detection, and

(2) the computation of the checksum has a certain irreducible complexity
    (to avoid brute force attack even with custom hardare), and the
    algorithm is analytically opague.

There is no reason to expect a cryptographic checksum to be any better
at detecting (unintentional) errors of any particular nature than any
other checksum occupying the same number of bits in the packet, in fact
it is reasonable to suspect it is worse at some things since for a
cryptographic checksum this is only a secondary property.  The real
reason you can get by without an "error model" (which you couldn't use
anyway because of (2) above) is that whether the 128-bit cryptographic
checksum fails to detect 1 in 2**130 of the errors which occur, or only
1 in 2**110, doesn't really matter much since both of those are really
small fractions.  The primary property that makes MD5 a good error
detection algorithm is sufficient brute force to make one comfortable
that it should always be strong enough.

So while (2) is, in fact, usually considered an undesirable property for
an error detection algorithm, (1) is always good if you have the luxury
of ignoring cost and MD5 uses enough bits that everything else matters
less.  Since error detection is usually considered an unfortunately
necessary overhead we usually try hard to do more with less, but if
you are willing to throw packet bits and compute cycles at it you can
always be assured of getting satisfactory performance even if it isn't
optimal for error detection in any theoretical sense.

With respect to the later arguments about computation cost and moving
checksums off-board, however, in a strange way I think you've been arguing
the wrong side of that dispute with Craig since the nature of MD5 might
actually decrease the probability that moving the checksum to off-board
hardware would be desirable.  MD5 is computationally complex (see (2))
but looks good despite this when you compare it to other things in CPU
benchmarks since it requires what current CPUs are good at; it does a lot
of computing per memory reference.  Off-board silicon is usually pretty
crappy compared to the way CPUs are designed, you get speed from this
compared to a CPU only on problems where the computation is fundamentally
bit-diddling (e.g. a CRC), or a datapath problem,  or a problem where
you can find a lot of things to compute in parallel.  MD5 really wants
a high clock rate and fast math, which general-purpose CPUs are still
king-of-the-hill at providing, so the bang-for-the-buck of moving it
off-board is probably minimized.

In any case, I was wrong.  If cost is no object you can always design
an acceptable end-to-end error check.

Dennis Ferguson

---

From: "Christian Huitema" <[email-masked]>
Date: Thu, 21 Jun 2001 17:03:05 -0700

What is at stake here is whether we want a safety belt or an alarm bell.
The current TCP checksum is the latter. It will detect "most" errors
with a good probability, which is enough to detect a faulty board. It
will not provide sufficient protection for guaranteeing a complete
absence of glitches in the 5 terabyte backup of a multinational
commercial bank. Note that, if you really follow the e2e argument, this
is OK: the only way to be certain that the back-up went well is by
computing a strong checksum over the whole volume, not by trusting TCP.
In fact, it is all a matter of probabilities and arbitrations. The
transmission system should be good enough that the backup is OK most of
the time, so that the e2e checksum (volume) only fails rarely, so that
the cost of correction is acceptable...

-- Christian Huitema

> -----Original Message-----
> From: Douglas Otis [mailto:[email-masked]]
> Sent: Monday, June 11, 2001 4:41 PM
> To: Jonathan Stone; Craig Partridge; David P. Reed
> Subject: RE: [e2e] Re: [Tsvwg] Really End-to-end or CRC vs everything
> else?
>
> Jonathan,
>
> packet is corrupted including the CRC itself.  There is no need for
the
> CRC
> closer to 2^6.  The only reason for placing a mandatory chunk at the
end
> of
> catch.  If there is only one checksum type allowed, then placing this
at
> the