SEGMENTED CRC DESIGN IN HIGH SPEED NETWORKS

• US 20090282148A1
• Filed: 07/18/2007
• Published: 11/12/2009
• Est. Priority Date: 07/18/2007
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Foundry Networks Incorporated (Broadcom, Inc.)
• Inventors: Wong, Yuen, Zhang, Hui
• Granted Patent: US 8,271,859 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• 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 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

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

a port configured to receive a data stream comprising one or more messages; and

a processing component configured to calculate a CRC value for each message in the one or messages, the calculating comprising 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.

16. The network device of claim 15 wherein the network device is a network switch.

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

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

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

20. 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 CRC value for each data line in the set of data lines, the calculating being independent of the position of the 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.

21. The network device of claim 20 wherein the network device is a network switch.

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

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

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

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

26. The network device of claim 20 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.