Re: [tsvwg] New Version Notification for draft-touch-tsvwg-udp-options-05.txt

["C. M. Heard" <[e-mail]>]

On Sat, Mar 25, 2017 at 3:06 PM, Joe Touch <[e-mail]> wrote:
> On 3/25/2017 6:26 AM, C. M. Heard wrote:
> > On Wed, Mar 22, 2017 at 10:43 PM, Joe Touch <[e-mail]> wrote:
> >>> In section 5.4, was a decision made as to what the CRC16 is? Details
> >>> will be needed in order to ensure interoperability.
> >> That's on my to-do list (I was a bit distracted by these other issues).
> >> There are three obvious possibilities:
> >>
> >> CRC-16-CCITT            used by Bluetooth, X.25, HDLC (4 terms - 0x1021)
> >> CRC-16-IBM               used by USB (4 terms -- 0x8005)
> >> CRC-16-CDMA2000    used by CDMA  mobile nets (8 terms - 0xC867)
> >>
> >> There are other analyses that point to other polynomials:
> >> https://users.ece.cmu.edu/~koopman/crc/
> >>
> >> Any suggestions?
> > Both the CRC-16-CCITT and CRC-16-IBM polynomials factor into the product
> > of x+1 times a primitive polynomial of degree 15 (*op in Koopman's notation)
> > and are in a sense optimal for random error patterns. They detect all triple
> > errors (and all error patterns of odd weight) for data lengths of 4093 bytes
> > or less. The CRC-16-CDMA2000 has a single factor, which is a primitive
> > degree 16 polynomial (*p in Koopman's notation), and it will detect all
> > double errors for data lengths of 8189 bytes or less. By data length I
> > mean of course the length of the data protected by the CRC (not
> > including the CRC itself).
> >
> > There are generic fast table lookup algorithms for all CRC-16 polynomials,
> > including automated methods for generating the lookup tables, so that is
> > not really a factor in choosing a polynomial.
>
> I that case should we go with CRC-16-CDMA2000?
>
> Or is there a better/stronger one from the table that's more useful?

Actually, CRC-16-CCITT or CRC-16-IBM (which are theoretically equivalent)
are ***stronger** than CRC-16-CDMA2000  for datagram payloads up to 32751
bits (i.e., CRC + data length = 32767 bits), when errors are random. For
datagrams of that exact length It can be proven (again for random errors)
that the undetected error rate is no worse than 1/65536, and for lesser
lengths simulations bear this out (see, for example,
http://doc.utwente.nl/64267/1/schiphorst.pdf). The only reason I can see
to choose CRC-16-CDMA2000 would be to provide protection for datagrams
longer than 4K bytes, in which case a better choice would be a 32-bit CRC.
The standard Autodin/Ethernet/ADCCP/HDLC CRC-32 polynomial is

x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^1+1

Although it is a primitive polynomial (without a factor of x+1) it will
protect against all triple error patters for datagram lengths of 11450
bytes, according to simulations that I ran about 14 years ago, and
its undetected error rate (for random errors) can be expected to be
under 2^-32. So that's what I would be inclined to recommend.

Regards,

Mike Heard