Re: Optimizing cutting paths - The proof

At 12:32 02/09/2001 +0000, you wrote:

> >I probably shouldn't pick this nit, but the protocols do not guarantee
> >correct delivery to an absolute degree. They do guarantee that all
> >data that passes the CRC tests will be accurate to one part in 65,536
> >because the checksum is only 16-bits. Actually, the error could be
> >even more likely, if the error had a particular pattern to it related to
> >the simple way the checksum is calculated. But, it seems pretty reliable,
> >anyway.
> >
>
>Naturally, there are no real guarantees. The TCP/IP checksum is quite
>weak but the lower level protocols are likely to use relatively good CRC
>algorithms that will detect all single bit errors, all odd number of bit
>errors and most if not all double bit errors as well as error bursts of
>length less than the length of the CRC polynomial. The probability of
>errors propagating, end-to-end, undetected is very small. Their
>calculation is left as an exercise for the reader.

...And a non-trivial exercise it is too!

To give an example of just how effective CRC error detection procedures can
be, the IEEE 802.3 standard (known colloquially as Ethernet - this is the
LAN technology most commonly used in modern computer installations) makes
use of a 32-bit CRC check in its transmitted data frames, which can carry
up to 1500 bytes of data, in order to meet a *worst-case* probability of
less than 1 in 13.3 billion that a data frame is delivered with an
undetected error. (And before somebody gets tempted into an argument over
the numbers, I had better point out that I am paraphrasing here part of the
2001 revision of IEEE Standard 802, the overall architecture standard for
LANs, which was developed by a working group for which I am currently the
Chairman.) The low-level protocols used to carry wide area data traffic in
"The Internet" use similar mechanisms and offer similar guarantees of
reliability - indeed, Ethernet is itself starting to be deployed as a wide
area carrier technology.

Regards,
Tony