rhorn@infinet.UUCP (Rob Horn) (04/02/88)
There are sometimes good reasons to use CRC rather than just checksums,
especially when in the asynch world. We send a lot of data over hostile
links using asynch and we have found that one of the more anti-social failure
modes of port sharing devices and muxes is byte or buffer swapping. Checksums
don't catch these. CRC's do, and they cost relatively little. Our CRC
code compiles into only nine (9) instructions per byte, and could be cut
to seven (7) if we went to assembler. This is not as good as checksums, but
it is nothing when compared to the CPU cost of servicing the interrupts
for the comm device. I think that CRC's have gotten too much bad press
because people think they are expensive. So our CRC code (sans 512 byte table)
is attached at the end.
On the other hand, for reliable high speed links (like LANs) I think
Sun made the right decision to drop even checksums. With a typical 8
KB block, even if the checksum cost is down to 1 microsecond per byte
you have added 8 milliseconds to the response. This is a big portion
of the total response time for a disk on the same LAN, especially for
a cache hit. But Sun should have made checksumming a per mount
option, to accomodate those cases where the connection is slower or
less reliable than a LAN.
Rob Horn
...harvard!adelie!infinet!rhorn, ..!ulowell!infinet!rhorn
/*
* A simple table driven CRC calculator.
*/
extern BYTE CRC_TABLE [256] [2];
rx_crc(crc, buffer, len)
char crc[2];
char *buffer;
short len;
{
#define high 1
#define low 0
register BYTE *crcptr;
register char crclow;
register char crchigh;
register char *workptr;
register char *limit; /* This should only be a register on 68K or VAXen */
/* Not on Intel processors */
crclow = 0xff;
crchigh = 0xff;
limit = buffer + len;
workptr = buffer;
while( workptr < limit) {
crcptr = CRC_TABLE [(unsigned char) ( *workptr++ ^ crclow)];
crclow = crcptr[high] ^ crchigh;
crchigh = crcptr[low];
}
crc[low] = crclow;
crc[high] = crchigh;
}
--
Rob Horn
UUCP: ...harvard!adelie!infinet!rhorn
Snail: Infinet, 40 High St., North Andover, MA
(Note: harvard!infinet path is in maps but not working yet)mcc@ETN-WLV.EATON.COM (Merton Campbell Crockett) (04/04/88)
I seem to recall an article several years ago where cyclical reduncancy check (CRC), longitudinal redundancy check (LRC), and vertical redundancy check (VRC) were discussed. The thrust of the article was that they are, indeed, useful in detecting transmission errors; however, the difference in the ability of the CRC algorithm and the LRC algorithm to detect transmission errors was not that great. The error detection rates were something like 98% and 94%, respectively. A gut feel is that a VRC/LRC combination for error detection is just as reliable as a CRC for detection of errors *and* saves 5 instructions per byte assuming the use of a CRC table. Merton Campbell Crockett mcc@etn-wlv.eaton.com
zweig@uiucdcsp.cs.uiuc.edu (04/04/88)
I agree strongly with the point about checksums missing bugaboos like word-swaps. Especially with all the OSI hassling and with everyone from Apple to McDonald's (just kidding) brewing up TCP/IP code, the likelihood that byte-sex induced problems and weird buffer misuse errors will occur is increased. Another big overhead that often gets left out of the computation is this: how much CPU and man-time does it take to figure out what's going on and fix bugs (rare though they be) caused by _not_ having CRC's in the right places (i.e. over noisy asynch lines)?? If important files get bit rot and no- body notices for a long time, it can take many hours of travail to set things right -- this is a hidden cost of not using CRC's that needs to be taken into account when talking about bandwidth. A zillion bits per second won't buy you a thing if you have to go over the files with a fine-toothed comb to see if they have been munched. Johnny Zweig University of Illinois at Urbana-Champaign (standard disclaimer about being a grad-student and ignorant, etc., etc.)
rick@SEISMO.CSS.GOV (Rick Adams) (04/06/88)
places (i.e. over noisy asynch lines)?? If important files get bit The point I was trying to make and a lot of people missed is: An async line is not usually noisy. You do not have to automatically put a CRC on it. You probably don't use a CRC between your terminal and the TTY MUX on the host. That's because it's not necessary in 99% of the cases. The same holds true for async lines in general. They don't normally have a noise problem. If you have a serious noise problem, you shouldn't be using a simple async scheme. Buy a paid of decent modems and let them do the work. (E.g. today you can buy a pair of telebit trailblazers for $1345.) If you need a special case for your special environment, fine. However, don't claim that a protocol that doesn't have it is broken. No one seems to feel the need to put a CRC around the TCP/IP packet that is handed to the ethernet. Yet, given a broken ethernet board, you could be just as likely to have a corrupt packet as with SLIP without a CRC --rick
sandrock@uxc.cso.uiuc.edu (04/09/88)
RMS (Record Management Services) on VMS does a CRC on the entire file both before and after it is transfered. We found this out the hard way when we had a flakey UNIBUS adapter in our VAX/780 which caused most large DECnet file transfers out our DEUNA to fail with the message that the DAP level CRC check had failed. (DAP = Data Access Protocol). Would have had a lot of bad data around without this check, since the network itself was operating correctly and no other errors were ever reported. Mark Sandrock, (sandrock@b.scs.uiuc.edu)
philipp@LARRY.MCRCIM.MCGILL.EDU (Philip Prindeville [CC]) (04/10/88)
>>places (i.e. over noisy asynch lines)?? If important files get bit > >The point I was trying to make and a lot of people missed is: >>An async line is not usually noisy. You do not have to >>automatically put a CRC on it. You probably don't use a >>CRC between your terminal and the TTY MUX on the host. That's >>because it's not necessary in 99% of the cases. Of course the DCE/DTE wire does not need line error detection. It doesn't have 50 volt ring signals in adjacent copper pairs or have to travel through many relays, frequency boosters, or CODECs. And it is only a few meters long, not several kilometers. >>The same holds true for async lines in general. They don't >>normally have a noise problem. If you have a serious noise >>problem, you shouldn't be using a simple async scheme. Buy a >>paid of decent modems and let them do the work. (E.g. >>today you can buy a pair of telebit trailblazers for $1345.) When I was living in a dorm years ago, I had line noise every time the compressor is someones refrigerator started. Dial-up lines do indeed have noise. And I certainly didn't have $1300 to drop on a modem either (the one I had was an AJ rep's demo model). >If you need a special case for your special environment, fine. >However, don't claim that a protocol that doesn't have it is >broken. What the hell is wrong with a little robustness? I think we can all recount stories where a little builtin robustness has saved our butts at unexpected times. It might seem excessive now, but prove invaluable later. >No one seems to feel the need to put a CRC around the TCP/IP packet >that is handed to the ethernet. Yet, given a broken ethernet board, you >could be just as likely to have a corrupt packet as with SLIP without a >CRC > >--rick A computer's buss is hardly as hostile as a telephone line. A mile of copper pair is a great inductor in a thunderstorm... -Philip
gnu@hoptoad.uucp (John Gilmore) (04/11/88)
mcc@ETN-WLV.EATON.COM (Merton Campbell Crockett) wrote: > A gut feel is that a VRC/LRC combination for error detection is just as reliable > as a CRC for detection of errors *and* saves 5 instructions per byte assuming > the use of a CRC table. That would be nice for sending 8-bit data in 9-bit bytes, but we don't have the vertical check bit except on tapes and other 9-bit media (or when sending 7-bit data). If people are serious about fixing the checksums (sounds like a good idea), howabout adding an IP option for full-packet 32 bit CRC? Any site could ignore the option, but at least all the ones that used it would interoperate and check each others' checksums. The first site, gateway, or whatever that implemented the option would throw away a packet whose CRC was bad. That would not work when passed through gateways which modify the IP options (e.g. source routing) but don't implement the CRC option. Another option would be a CRC that protected only the user-data field, relying on the IP header checksum for the header. Not as good, but easier to retrofit. -- {pyramid,pacbell,amdahl,sun,ihnp4}!hoptoad!gnu gnu@toad.com I forsee a day when there are two kinds of C compilers: standard ones and useful ones ... just like Pascal and Fortran. Are we making progress yet? -- ASC:GUTHERY%slb-test.csnet