Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-06-18
2004-11-16
Lamarre, Guy J. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S801000
Reexamination Certificate
active
06820228
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of data processing. More specifically, the present invention relates to high speed cyclic redundancy check (CRC) generation, having special application to high speed network traffic routing, such as Gigabit Ethernet packet switching.
2. Background Information
Cyclic Redundancy Check (CRC) has long been employed as a metric to detect transmission errors. The technique is employed in a wide variety of data processing related disciplines, including in particular, networking. The underlying mathematics including the polynomial divisions involved in the generation of a CRC value for a data block is well understood among those ordinarily skilled in the art. Various hardware as well as software implementations are known. Examples of known hardware implementations include but are not limited to the implementations available from e.g. Actel of Sunnyvale, CA.
With advances in integrated circuit, microprocessor, networking and communication technologies, increasing number of devices, in particular, digital computing devices, are being networked together. Devices are often first coupled to a local area network, such as an Ethernet based office/home network. In turn, the local area networks are interconnected together through wide area networks, such as SONET, ATM, or Frame Relay networks, and the like. Of particular notoriety is the TCP/IP based global inter-networks, Internet.
As a result of this trend of increased connectivity, increasing number of applications that are network dependent are being deployed. Examples of these network dependent applications include but are not limited to, email, net based telephony, world wide web and various types of e-commerce. Successes of many of these content/service providers as well as commerce sites depend on high speed delivery of a large volume of data. As a result, high speed networking, which in turn translates into high speed CRC generation is needed.
Unfortunately, the current generation of CRC generators known in the art are generally unable to meet the speed requirement of the next generation IC based high speed network traffic routing devices. For these IC based devices, it is not only necessary for the CRC generation resource to be sufficiently fast to keep pace with the processing of a single network traffic flow, it is further desirable that the CRC generation resource to be sufficiently efficient and fast, such that it can be shared among the various flow processing units, thereby eliminating the need to have dedicated CRC generation resource for-each of the flow processing units.
Thus, a highly efficient approach to CRC generation is needed.
SUMMARY OF THE INVENTION
A CRC generation unit includes a number of CRC calculation assemblies to be selectively employed to incrementally calculate a CRC value for a sequence of N data bytes. The calculation is iteratively performed, one iteration at a time. Further, the selection of the CRC calculation assemblies is made in accordance with the group size of each of a number of data word groups of the N data bytes.
In one embodiment, the CRC calculation assemblies include a first assembly to incrementally calculate the CRC value for an iteration, whenever the group size for the iteration is n/2 bytes or less, and a second assembly to incrementally calculate the CRC value for an iteration, whenever the group size for the iteration is more than n/2 bytes.
In one embodiment, the CRC generation unit is a shared resource to multiple network traffic flow processing units of a network traffic routing IC.
In one embodiment, the network traffic routing device is disposed on a single integrated circuit.
REFERENCES:
patent: 4937828 (1990-06-01), Shih et al.
patent: 5103451 (1992-04-01), Fossey
patent: 5859859 (1999-01-01), Kim
patent: 5878057 (1999-03-01), Maa
Guido Albertengo and Ricardo Sisto, “Parallel CRC Generation”, IEEE Micro, 0272-1732/90/1000-0063501.00, Oct. 1990.*
“High-Speed Parallel Cyclic Redundancy Check Generator”, IBM Technical Disclosure Bulletin NN901051, vol. 33, Issue 5, pp 51-56, Oct. 1, 1990.
Lamarre Guy J.
Network Elements, Inc.
Schwabe Williamson & Wyatt P.C.
Trimmings John P.
LandOfFree
Fast cyclic redundancy check (CRC) generation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast cyclic redundancy check (CRC) generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast cyclic redundancy check (CRC) generation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3347480