Subject: [tsvwg] Which CRC is best from transport layer view

From: Tom Herbert <[email-masked]>
Date: Tue, 27 Mar 2018 08:38:35 -0700

Hello,

The question of which CRC should be used in L3/L4 protocols for a
stronger data check than checksum came up in intarea meeting. The
context of this discussion was GUE for which we have defined an
alternate checksum extension that would allow a choice of CRC-32,
CRC-16, or CRC-16-CCITT that covers the GUE header and some specified
portion of the payload. The feedback was that multiple CRC variants
are not needed, and there was a suggestion that CRC-32C (iSCSI CRC)
would be better than Ethernet CRC.

This question might also be relevant to UDP options which currently
uses CRC16-CCITT for a check of UDP payload.

Any opinions?

Thanks,
Tom

---

From: Michael Tuexen <[email-masked]>
Date: Tue, 27 Mar 2018 17:41:04 +0200

> On 27. Mar 2018, at 17:38, Tom Herbert <[email-masked]> wrote:
> 
> Hello,
> 
SCTP uses the CRC32c.

Best regards
Michael

---

From: Randall Stewart <[email-masked]>
Date: Tue, 27 Mar 2018 09:03:20 -0700

And the reason we moved to it is it has one bit better hamming
distance as compared to CRC32. There is a large archive of email
discussions you can find on this in tsvwg history 😊

R

Sent from my iPhone

> On Mar 27, 2018, at 8:41 AM, Michael Tuexen <[email-masked]> wrote:
>

SCTP uses the CRC32c.

Best regards
Michael

---

From: Joe Touch <[email-masked]>
Date: Tue, 27 Mar 2018 09:06:51 -0700

I was hoping for something 16 but for UDP options for alignment reasons, but could include either or both 16- and 32-bit sizes. 

Otherwise, I don’t have any opinion. 

Joe

> On Mar 27, 2018, at 8:38 AM, Tom Herbert <[email-masked]> wrote:
> 
> Hello,
>

---

From: Pat Thaler <[email-masked]>
Date: Tue, 27 Mar 2018 10:05:21 -0700

First off, any credible CRC will be a large improvement over a checksum as
there are large classes of errors that a checksum misses.

Once you get down to debating which CRC, you are talking about smaller
differences.
A 16-bit CRC will detect 1 - 2^-16 errors (about 99.99847%). A 32-bit CRC
detects 1 - 2^-32 errors (99.999999977%).

Much of the analysis of which CRC is best for two CRC polynomials of the
same length is based on analyzing Hamming distance. It assumes that errors
occur as single bit errors with independent probability, If the assumption
is accurate and the probability of getting a single bit error is Pber << 1,
then the probability of getting 3 bit errors is Pber^3 and the probability
of getting 4 bit errors is Pber^4. The probability of an undetected error
is roughly
<probability that an error longer than Hamming distance occurs> *  2^-<CRC
length>
So, if the assumption is correct, then increasing Hamming distance greatly
decreases the probability of an undetected error.

The Ethernet CRC is a primitive polynomial (i.e. it has no factors) with a
Hamming distance of 4 out to at least 9 Kbytes (last time I looked at the
literature, that was the longest that has been checked, it hadn't been
determined where the first undetected 3-bit error occurs).

Polynomials such as CRC32c have two factors one of them being 1 + x. The
factor 1 + x is a parity check so such polynomials will detect all odd
numbers of bit errors giving them a Hamming distance of 4 out to the length
of the cycle. Nothing is free. They pay for this by halving their error
detection for even numbers of bit errors.

However, the assumption that bit errors occur as single bit errors with
independent probability is unrealistic. There are many types of errors that
occur as multi-bit errors - e.g. noise that causes burst errors and
physical layer line codes where a single error in the line code causes
multiple errors in the decoded bits.

Furthermore, there are other mechanisms operating that detect odd numbers
of bit errors - e.g. parity checks on memories (where independent single
bit errors are caused by some physical phenomena) and buses; line codes
that detect odd numbers of bit errors. As we move to higher speeds, it is
common to use FEC (Forward Error Correction) on the physical layer to
reduce the bit error rate from the physical layer. Such a code will correct
up to a certain number of bit errors. At that point the only errors that
get through are ones that were too long to correct

Therefore, an analysis of which CRC is better based on Hamming distance may
be an interesting academic exercise (as in part of RFC 3385), but it
doesn't reflect physical reality of which is best.

---

From: G Fairhurst <[email-masked]>
Date: Tue, 27 Mar 2018 18:28:01 +0100

I quite agree with comment on the error extension of PHY FEC, that has a 
huge impact on the error patterns that actually are passed to the CRC.

I do have a curiosity, that may, or may not, be relevant. Since most IP 
packets are carried on Ethernet bearers, there seems at least the 
possibility that an undetected error pattern for an Ethernet CRC could 
emerge as an input error pattern within a transport payload. If that is 
so, is there benefit in having different factors in the polynomial for 
the link and transport layers?

Gorry

On 27/03/2018, 18:05, Pat Thaler wrote:
> First off, any credible CRC will be a large improvement over a 
> checksum as there are large classes of errors that a checksum misses.
>
> A 16-bit CRC will detect 1 - 2^-16 errors (about 99.99847%). A 32-bit 
> CRC detects 1 - 2^-32 errors (99.999999977%).
>
> Much of the analysis of which CRC is best for two CRC polynomials of 
> the same length is based on analyzing Hamming distance. It assumes 
> that errors occur as single bit errors with independent probability, 
> If the assumption is accurate and the probability of getting a single 
> bit error is Pber << 1, then the probability of getting 3 bit errors 
> is Pber^3 and the probability of getting 4 bit errors is Pber^4. The 
> probability of an undetected error is roughly
> <probability that an error longer than Hamming distance occurs> *  
> 2^-<CRC length>
> So, if the assumption is correct, then increasing Hamming distance 
> greatly decreases the probability of an undetected error.
>
> The Ethernet CRC is a primitive polynomial (i.e. it has no factors) 
> with a Hamming distance of 4 out to at least 9 Kbytes (last time I 
> looked at the literature, that was the longest that has been checked, 
> it hadn't been determined where the first undetected 3-bit error occurs).
>
> Polynomials such as CRC32c have two factors one of them being 1 + x. 
> The factor 1 + x is a parity check so such polynomials will detect all 
> odd numbers of bit errors giving them a Hamming distance of 4 out to 
> the length of the cycle. Nothing is free. They pay for this by halving 
> their error detection for even numbers of bit errors.
>
> However, the assumption that bit errors occur as single bit errors 
> with independent probability is unrealistic. There are many types of 
> errors that occur as multi-bit errors - e.g. noise that causes burst 
> errors and physical layer line codes where a single error in the line 
> code causes multiple errors in the decoded bits.
>
> Furthermore, there are other mechanisms operating that detect odd 
> numbers of bit errors - e.g. parity checks on memories (where 
> independent single bit errors are caused by some physical phenomena) 
> and buses; line codes that detect odd numbers of bit errors. As we 
> move to higher speeds, it is common to use FEC (Forward Error 
> Correction) on the physical layer to reduce the bit error rate from 
> the physical layer. Such a code will correct up to a certain number of 
> bit errors. At that point the only errors that get through are ones 
> that were too long to correct
>
> Therefore, an analysis of which CRC is better based on Hamming 
> distance may be an interesting academic exercise (as in part of RFC 
> 3385), but it doesn't reflect physical reality of which is best.
>
> On Tue, Mar 27, 2018 at 9:03 AM, Randall Stewart <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     > On Mar 27, 2018, at 8:41 AM, Michael Tuexen
>     <[email-masked]
>     <mailto:[email-masked]>> wrote:
>     >
>
>     > On 27. Mar 2018, at 17:38, Tom Herbert <[email-masked]
>     <mailto:[email-masked]>> wrote:
>     >
>     > Hello,
>     >

---

From: Tom Herbert <[email-masked]>
Date: Tue, 27 Mar 2018 10:38:14 -0700

On Tue, Mar 27, 2018 at 10:05 AM, Pat Thaler <[email-masked]>
wrote:

> Therefore, an analysis of which CRC is better based on Hamming distance
> may be an interesting academic exercise (as in part of RFC 3385), but it
> Pat,

I would point out that Intel CPU has instructions for both CRC32 and
CRC32c, so either one will be sufficiently efficient for hosts to compute.
Also, I believed David Black mentioned that using something other than
Ethernet CRC might be stronger to avoid using the same algorithm twice over
the same data in a packet.

Do you see any negatives about only using CRC32c for GUE?

Thanks,
Tom

---

From: Michael Tuexen <[email-masked]>
Date: Tue, 27 Mar 2018 19:51:07 +0200

> On 27. Mar 2018, at 19:38, Tom Herbert <[email-masked]> wrote:
> 
> 
> 
> On Tue, Mar 27, 2018 at 10:05 AM, Pat Thaler <[email-masked]> wrote:
> First off, any credible CRC will be a large improvement over a checksum as there are large classes of errors that a checksum misses.
> 
> Once you get down to debating which CRC, you are talking about smaller differences. 
> A 16-bit CRC will detect 1 - 2^-16 errors (about 99.99847%). A 32-bit CRC detects 1 - 2^-32 errors (99.999999977%). 
> 
> Much of the analysis of which CRC is best for two CRC polynomials of the same length is based on analyzing Hamming distance. It assumes that errors occur as single bit errors with independent probability, If the assumption is accurate and the probability of getting a single bit error is Pber << 1, then the probability of getting 3 bit errors is Pber^3 and the probability of getting 4 bit errors is Pber^4. The probability of an undetected error is roughly 
> <probability that an error longer than Hamming distance occurs> *  2^-<CRC length>
> So, if the assumption is correct, then increasing Hamming distance greatly decreases the probability of an undetected error.
> 
> The Ethernet CRC is a primitive polynomial (i.e. it has no factors) with a Hamming distance of 4 out to at least 9 Kbytes (last time I looked at the literature, that was the longest that has been checked, it hadn't been determined where the first undetected 3-bit error occurs).
> 
> Polynomials such as CRC32c have two factors one of them being 1 + x. The factor 1 + x is a parity check so such polynomials will detect all odd numbers of bit errors giving them a Hamming distance of 4 out to the length of the cycle. Nothing is free. They pay for this by halving their error detection for even numbers of bit errors.
> 
> However, the assumption that bit errors occur as single bit errors with independent probability is unrealistic. There are many types of errors that occur as multi-bit errors - e.g. noise that causes burst errors and physical layer line codes where a single error in the line code causes multiple errors in the decoded bits. 
> 
> Furthermore, there are other mechanisms operating that detect odd numbers of bit errors - e.g. parity checks on memories (where independent single bit errors are caused by some physical phenomena) and buses; line codes that detect odd numbers of bit errors. As we move to higher speeds, it is common to use FEC (Forward Error Correction) on the physical layer to reduce the bit error rate from the physical layer. Such a code will correct up to a certain number of bit errors. At that point the only errors that get through are ones that were too long to correct 
> 
> Therefore, an analysis of which CRC is better based on Hamming distance may be an interesting academic exercise (as in part of RFC 3385), but it doesn't reflect physical reality of which is best. 
> 
> Pat,
> 
> I would point out that Intel CPU has instructions for both CRC32 and CRC32c, so either one will be sufficiently efficient for hosts to compute. Also, I believed 
On arm64 platforms there is also support for CRC32 and CRC32c.

Best regards
Michael
> David Black mentioned that using something other than Ethernet CRC might be stronger to avoid using the same algorithm twice over the same data in a packet.
>

---

From: Bob Hinden <[email-masked]>
Date: Tue, 27 Mar 2018 19:01:52 +0100

Gorry,

> On Mar 27, 2018, at 6:28 PM, G Fairhurst <[email-masked]> wrote:
> 
> I quite agree with comment on the error extension of PHY FEC, that has a huge impact on the error patterns that actually are passed to the CRC.
> 
> I do have a curiosity, that may, or may not, be relevant. Since most IP packets are carried on Ethernet bearers, there seems at least the possibility that an undetected error pattern for an Ethernet CRC could emerge as an input error pattern within a transport payload. If that is so, is there benefit in having different factors in the polynomial for the link and transport layers?

Good point.  The transport header protection should be there to detect link errors that the link protection didn’t catch or memory errors in a router.  I don’t know the answer, but as you point out, using a CRC that is similar to what is used on the link probably isn’t the best choice.

Bob

>> On Tue, Mar 27, 2018 at 9:03 AM, Randall Stewart <[email-masked] <mailto:[email-masked]>> wrote:
>>

---

From: Pat Thaler <[email-masked]>
Date: Tue, 27 Mar 2018 11:49:55 -0700

Yes, when applying more than one CRC over a message, there is an advantage
to using different CRC polynomial so that, as Gary mentioned above, if
there is an error pattern that goes through one CRC computation without
detection, the other CRC has a chance to detect it. In some physical layers
in Ethernet where we we don't need FEC but want more error protection, we
have used a 16-bit CRC at the physical layer to get the extra protection.

Do I see any negatives to using only CRC32c?
It's not a 16-bit CRC for those that believe that using a 16-bit CRC
instead of a 16-bit checksum is enough of an upgrade in protection. But do
any of the 16-bit CRCs have instructions supported in CPUs to make
computation more efficient? Does that matter? Computation by the CPU
requires putting the whole message through the CPU and even for checksum,
offload to the NIC is more efficient when possible.

As mentioned in my earlier post, once errors aren't independent single bit
error, there is a slight advantage to CRCs that protect as much against
even numbers of bit errors as they do against odd numbers of bit errors.
For even numbers of bit errors, a CRC32c is giving approximately 31-bits of
protection. That's a lot more than a 16-bit CRC so probably good enough. If
you expect payloads are protected by the Ethernet CRC most of the time at
layer 2, the advantage of using a different CRC from that used at the lower
layer perhaps outweighs that.

On a more esoteric side, there's a method that works for primitive
polynomials for calculating the update to the CRC of a message from the CRC
of a change in the header where the computation takes Log N steps where N
is the remaining message length. It takes a couple of extra steps to adjust
the computation if the CRC polynomial is (1 + x) times a primitive
polynomial.

Regards,
Pat

On Tue, Mar 27, 2018 at 10:38 AM, Tom Herbert <[email-masked]> wrote:

>> First off, any credible CRC will be a large improvement over a checksum
>> as there are large classes of errors that a checksum misses.
>>
>> The Ethernet CRC is a primitive polynomial (i.e. it has no factors) with
>> a Hamming distance of 4 out to at least 9 Kbytes (last time I looked at the

---

From: Tom Herbert <[email-masked]>
Date: Tue, 27 Mar 2018 13:44:39 -0700

Thanks for all the input. I've updated the GUE extensions draft to only use
CRC32-C ( https://tools.ietf.org/html/draft-ietf-intarea-gue-extensions-04 ).
That seems reasonable given the feedback.

Tom

On Tue, Mar 27, 2018 at 11:49 AM, Pat Thaler <[email-masked]>
wrote:

>>> numbers of bit errors - e.g. parity checks on memories (where independent
>>> single bit errors are caused by some physical phenomena) and buses; line
>>> codes that detect odd numbers of bit errors. As we move to higher speeds,
>>> it is common to use FEC (Forward Error Correction) on the physical layer to
>>> may be an interesting academic exercise (as in part of RFC 3385), but
>>> it doesn't reflect physical reality of which is best.
>>>
>>> Pat,
>>

---

From: Mikael Abrahamsson <[email-masked]>
Date: Sat, 31 Mar 2018 06:57:49 +0200 (CEST)

> the link and transport layers?

I would like to point out that some of my hardest to find networking 
problem of my career was a make/model of routers that due to bad memory 
would occasionally single-bitflip packets in transit and recalculate 
correct checksum.

So whatever we do, ew should put checksum/CRC in places so that the 
payload is protected from whatever the router actually has to look into, 
and we should also take into account what an L3/L4 device will have to do, 
and if it ever has to modify something as part of its normal operation 
(decrement TTL, perform MSS clamping, or any other similar duty) it should 
not have to recalculate any checksum/CRC values. Having occasional 
bitflips in these is a lot less problematic than having payload 
accidentially modified by devices like these.

-- 
Mikael Abrahamsson    email: [email-masked]