19 Sep
2023
19 Sep
'23
10 p.m.
On 19 Sep 2023, at 13:42, Noel Chiappa
<jnc(a)mercury.lcs.mit.edu> wrote:
That is a very interesting paper and it uses the same polynomial. The algorithm seems
different from the one that Perez published in 1983, but in the same general direction. So
it would seem that this “on-the-fly” method was not (well) known prior to 1983. By the
looks of it, it was not well known afterwards either.
You were part of the group that invented it and I’m telling you stuff you know better than
I do, but the adopted summation in TCP/IP had a lot of advantages: it could be efficiently
calculated on 36, 32 and 16 bit machines, it did not care about endianness and was
efficient on both two’s and one’s complement machines. I don’t think CRC had all those
properties.
I don’t think in 1978 the IEN group was aiming for the LAN use case, but as it turned out
a few years later the simple summation consumed 25% of a VAX-750 CPU to saturate 3 Mbps
ethernet. Even a 30% slowdown in checksumming would have been costly -- but you already
pointed out that speed was an important consideration.
From: Paul Ruizendaal
Any suggestions as to why the on-the-fly
algorithm did not catch on
more in the 1980's? Maybe it was simply less well known than I think?
I can't answer that directly, but I will point you at IEN-56, "CRC Checksum
Calculation", by Dave Reed (11-Sep-78):
https://www.rfc-editor.org/ien/ien56.pdf
Dave wanted the INWG to use a more powerful (in terms of detecting errors)
CRC, instead of the simple summation eventually adopted, in TCP and IP. So he
produced code to implement a particular CRC, to show people that it would not
be particularly expensive (whether in time, or space, I don't alas recall
definitively; speed would have been an important consideration, when
competing with the summation, though).
This would have been close to the leading edge of our knowledge at the time;
Dave liked playing around with math, and at about that time he did a very
fast DES implementation.
Noel