Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!sdi.polaroid.COM!HORN%HYDRA
From: HORN%HYDRA@sdi.polaroid.COM
Newsgroups: comp.protocols.tcp-ip
Subject: Re: Fletcher Checksum
Message-ID: <0CEC4873D71F21B02A@sdi.polaroid.com>
Date: 13 Dec 89 14:27:00 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The Internet
Lines: 40

Adding a checksum option with expanded size checksum (32, 64, ...
bit) seems to be a reasonable way to start experimenting with error
control algorithms for high speed networks.  A similar experimental
option for VMTP also seems reasonable.

As transmission speeds increase I think that we will need to look
more and more to forward error correction (FEC) techniques to
replace ARQ techniques.  With TCP, 64Kbit effective bandwidth, 250
msec end-to-end delays the ARQ impact on response time is modest and
the buffering demands are low.  At high bandwidth you have many
megabytes in flight with corresponding major buffering demands.  I
would not be surprised to see the buffers move to disk or
re-computation in some cases, with the result that a single ARQ has
a very large performance impact.

FEC techniques are improving steadily and are now in widespread use
both within modems (typically convolution codes) and in
media like CDROM (Reed Solomon codes).  For the non-error case,
there are table lookup approaches to RS (and some other) codes that
reduce the computation load to 10-20 instructions per byte for a
code that can withstand 0.001 ber.  The computation needed to repair
an error is much larger.  These approaches only minimize the cost of
generating and verifying checkwords.

One of the important aspects of using FEC is a good characterization
of the error modes of the telemetry system.  This may be the most
difficult aspect of introducing it into any large network.  You do
need to understand how errors occur, what are typical error burst
sizes, deletion and insertion modes, etc.

Examination of the system level tradeoffs would be worthwhile.  FEC
costs somewhat more CPU (rapidly getting cheaper) and uses a
controllable percentage of the bandwidth (typically a few percent)
while drastically reducing the needs for buffers at both ends.  The 
extra cost for FEC at CDROM rates (about 1Mbit/s) is a few hundred
dollars at most (retail pricing).  FEC can always retreat to ARQ for
cases beyond its ability to repair.


R Horn    horn%hydra@polaroid.com