Techniques for segmented CRC design in high speed networks

• US 8,037,399 B2
• Filed: 07/18/2007
• Issued: 10/11/2011
• Est. Priority Date: 07/18/2007
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Foundry Networks LLC (Broadcom, Inc.)
• Inventors: Zhang, Hui, Wong, Yuen
• Primary Examiner(s): Alphonse; Fritz
• Application Number:
  US11/779,778
• Publication Number:
  US 20090282322A1
• Time in Patent Office: 1,546 Days
• Field of Search: 714/807, 714/207, 714/821, 714/758, 714/756
• US Class Current: 714/807
• CPC Class Codes: H03M 13/091 Parallel or block-wise CRC computation
• CPC Class Codes: H04L 1/0043 Realisations of complexity reduction techniques, e.g. use of look-up tables
• CPC Class Codes: H04L 1/0061 Error detection codes

Abstract

Embodiments of the present invention provide techniques for efficient generation of CRC values in a network environment. Specific embodiments of the present invention enable CRC processing circuits that can generate CRC values at high data throughput rates (e.g., 100 Gbps or greater), while being capable of being implemented on currently available FPGAs. Accordingly, embodiments of the present invention may be used in network devices such as routers, switches, hubs, host network interfaces and the like to support high speed data transmission standards such as 100G Ethernet and beyond.

Claims

1. A method comprising:

receiving, by a network device, a set of one or more data lines, each data line in the set of data lines having a width and comprising a portion of a message, wherein at least one data line in the set of data lines is a residue line containing a portion of the message that is smaller than the width of the residue line;

shifting, by the network device, the portion of the message in the residue line from a first boundary of the residue line to a second boundary of the residue line;

generating, by the network device, a data line CRC value for each data line in the set of data lines; and

generating, by the network device, a message CRC value for the message based on the data line CRC values.

2. The method of claim 1 wherein generating a message CRC value for the message based on the data line CRC values comprises aggregating the data line CRC values with a logical operator.

3. The method of claim 2 wherein the logical operator is an XOR operator.

4. The method of claim 1 wherein generating the message CRC value comprises:

for one or more data lines in the set of data lines excluding the residue line;

retrieving a first transformation matrix for each of the one or more data lines, wherein the first transformation matrix is dependent on the position of the data line relative to the other data lines in the set of data lines; and

multiplying a CRC value for the data line by the first transformation matrix to generate a transformed CRC value for the data line;

generating a partial accumulated message CRC value by aggregating the transformed CRC values for the data lines in the set of data lines excluding the residue line;

retrieving a second transformation matrix, wherein the second transformation matrix is dependent on a size of the portion of the message in the residue line;

multiplying the partial accumulated message CRC value by the second transformation matrix to generate a transformed partial accumulated message CRC value; and

generating the message CRC value by aggregating the transformed partial accumulated message CRC value with the CRC value of the residue line.

5. The method of claim 4 further comprising storing the first transformation matrix and the second transformation matrix in a memory accessible to the network device, wherein retrieving the first transformation matrix and the second transformation matrix comprises reading the first transformation matrix and the second transformation matrix from the memory.

6. The method of claim 1 wherein generating a data line CRC value for each data line in the set of data lines comprises:

splitting the data line into a plurality of sublines;

concurrently calculating a CRC value for each subline; and

generating a data line CRC value for the data line based on the subline CRC values.

7. The method of claim 6 wherein generating a data line CRC value for the data line based on the subline CRC values comprises:

if the subline is not the last subline in the data line;

retrieving a transformation matrix for the subline, wherein the transformation matrix is dependant on the position of the subline relative to the other sublines of the data line;

multiplying a CRC value for the subline with the transformation matrix retrieved for the subline to generate a transformed subline CRC value; and

aggregating the transformed subline CRC values and the CRC value for the last subline to generate the data line CRC value.

8. The method of claim 7 wherein aggregating the transformed subline CRC values and the CRC value for the last subline comprises combining the transformed subline CRC values and the CRC value for the last subline using a logical operator.

9. The method of claim 8 wherein the logical operator is an XOR operator.

10. The method of claim 7 further comprising storing the transformation matrix for the subline in a memory, wherein retrieving a transformation matrix for each subline comprises reading the transformation matrix for the subline from the memory.

11. A method comprising:

receiving, by a network device, a set of one or more data lines, each data line in the set of data lines having a width and comprising a portion of a message, wherein at least one data line in the set of data lines is a residue line containing a portion of the message that is smaller than the width of the residue line, and wherein each data line in the set of data lines has a data granularity of X bits;

calculating, by the network device, a CRC value for each data line in the set of data lines using a set of CRC generators, each CRC generator in the set of CRC generators being configured to calculate a CRC value for an input, wherein the input for each CRC generator is larger than X bits in size; and

generating, by the network device, a CRC value for the message based on the data line CRC values.

12. A method comprising:

receiving, by a network device, a set of one or more data lines, each data line in the set of data lines having a width and comprising a portion of a message, wherein at least one data line in the set of data lines is a residue line containing a portion of the message that is smaller than the width of the residue line;

calculating, by the network device, a CRC value for each data line in the set of data lines using a set of CRC generators, each CRC generator in the set of CRC generators being configured to calculate a CRC value for an input, wherein the input for each CRC generator is the same size; and

generating, by the network device, a CRC value for the message based on the data line CRC values.

13. A method comprising:

receiving, by a network device, a set of one or more data lines, each data line in the set of data lines comprising a portion of a message;

calculating, by the network device, a CRC value for each data line in the set of data lines using a set of CRC generators, the calculating being independent of the position of the data line relative to the other data lines in the set of data lines; and

generating, by the network device, a CRC value for the message based on the data line CRC values.

14. The method of claim 13 wherein the calculating a CRC value for each data line is performed concurrently.

15. The method of claim 14 wherein at least one data line in the set of data lines is a residue line containing a portion of the message that is smaller than a width of the residue line.

16. A method comprising:

receiving, by a network device, a set of one or more data lines, each data line in the set of data lines having a width of X bits and comprising a portion of a message, wherein at least one data line in the set of data lines is a residue line containing a portion of the message that is smaller than the width of the residue line, and wherein each data line in the set of data lines has a data granularity of Y bits;

calculating, by the network device, a CRC value for each data line in the set of data lines using a set of CRC generators, the number of CRC generators in the set of CRC generators being less than X divided by Y; and

generating, by the network device, a CRC value for the message based on the data line CRC values.