Segmented CRC design in high speed networks

• US 8,271,859 B2
• Filed: 07/18/2007
• Issued: 09/18/2012
• Est. Priority Date: 07/18/2007
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Foundry Networks LLC (Broadcom, Inc.)
• Inventors: Wong, Yuen, Zhang, Hui
• Primary Examiner(s): Lim, Krisna
• Assistant Examiner(s): DESAI, MARGISHI V
• Application Number:
  US11/779,714
• Publication Number:
  US 20090282148A1
• Time in Patent Office: 1,889 Days
• Field of Search: 370/337, 345/531
• US Class Current: 714/781
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit

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 network device comprising:

a port configured to receive a set of one or more data lines, each data line in the set of data lines having a fixed 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 fixed width of the residue line; and

a processing component configured to;

shift 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;

generate a separate data line CRC value for each data line; and

generate a message CRC value for the message based on the data line CRC values.

2. The network device of claim 1 wherein the network device is a network switch.

3. The network device of claim 1 wherein the processing component is configured to support a data throughput of at least 10 gigabits per second.

4. The network device of claim 1 wherein the processing component is configured to support a data throughput of at least 100 gigabits per second.

5. The network device of claim 1 wherein the processing component is a Media Access Controller (MAC).

6. The network device 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.

7. The network device of claim 6 wherein the logical operator is an XOR operator.

8. The network device 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.

9. The network device of claim 8 wherein generating the message CRC value further comprises 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.

10. The network device 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.

11. The network device of claim 10 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.

12. The network device of claim 11 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.

13. The network device of claim 12 wherein the logical operator is an XOR operator.

14. The network device of claim 11 wherein generating a data line CRC value for the data line based on the subline CRC values further comprises 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.

15. The network device of claim 1 wherein the first boundary is a most significant bit (MSB) boundary of the residue line and wherein the second boundary is a least significant bit (LSB) boundary of the residue line.

16. The method of claim 1 wherein the set of data lines are ordered, and wherein the residue line is the last data line in the set of data lines.

17. A network device comprising:

a port configured to receive a data stream comprising one or more messages, each message being split into a set of data lines; and

a processing component configured to calculate a CRC value for each message by;

shifting a portion of the message in a residue line from a first boundary of the residue line to a second boundary of the residue line;

calculating a separate CRC value for each data line in the set of data lines; and

generate a CRC value for the message based on the data line CRC values.

18. The network device of claim 17 wherein the network device is a network switch.

19. The network device of claim 17 wherein the processing component is configured to support a data throughput of at least 10 gigabits per second.

20. The network device of claim 17 wherein the processing component is configured to support a data throughput of at least 100 gigabits per second.

21. The network device of claim 17 wherein the processing component is a Media Access Controller (MAC).

22. A network device comprising:

a port configured to receive a data stream comprising a set of one or more data lines, each data line in the set of data lines comprising a portion of a message; and

a processing component configured to;

calculate a separate CRC value for each data line in the set of data lines, the calculating being independent of the position of said each data line relative to the other data lines in the set of data lines; and

generate a CRC value for the message based on the data line CRC values.

23. The network device of claim 22 wherein the network device is a network switch.

24. The network device of claim 22 wherein the processing component is configured to support a data throughput of at least 10 gigabits per second.

25. The network device of claim 22 wherein the processing component is configured to support a data throughput of at least 100 gigabits per second.

26. The network device of claim 22 wherein the processing component is a Media Access Controller (MAC).

27. The network device of claim 22 wherein the calculating a CRC value for each data line is performed concurrently.

28. The network device of claim 22 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.

29. The method of claim 22 wherein calculating a separate CRC value for each data line in the set of data lines comprises:

concurrently calculating multiple subline CRC values for the data line, each subline CRC value corresponding to a portion of the data line; and

calculating the CRC value for the data line based on the multiple subline CRC values.