Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-02-08
2002-03-12
Tu, Christine T. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C370S229000
Reexamination Certificate
active
06357032
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the data processing field, and more particularly, relates to a method and apparatus for implementing cyclic redundancy check calculation with receive data processing for data communications in a communications system.
DESCRIPTION OF THE RELATED ART
An Asynchronous Transfer Mode (ATM) network described in “ATM: Theory and Application” by David E.
McDysan and Darren L. Spohn, McGraw-Hill, 1994 is an internationally agreed upon technique for transmission, multiplexing and switching in a broadband network. ATM networks are designed to support the integration of high quality voice, video, and high speed data traffic. ATM networks use fixed size cells as a unit of transmission.
Ethernet is the original and still common name for the communications technique that has been standardized by the IEEE as some of the 802.x standards. 802.3 is the general Ethernet standard and 802.x are the link layer standards covering a variety of speeds.
In the face of emerging proprietary optical transmission protocols, SONET (Synchronous Optical Network) was provided as an open standard for synchronous data transmission on optical media. The standard was approved in 1988 by the predecessor to today's International Telecommunication Union, and in 1989 by the American National Standards Institute. SONET is widely deployed in the US. Using time division multiplexing, SONET works by dividing a fiber transmission path into multiple logical channels called tributaries. A tributary's basic unit of transmission is an STS-
1
(synchronous transport signal, level 1) or OC-
1
(optical carrier, level 1) signal. STS describes a transmission's signals while in an electrical state, and OC describes the same traffic after being converted into optical signals. STS-
1
and OC-
1
both operate at 51.84 Mbps. OC-
2
is twice as fast, OC-
3
is three times as fast, and so on. SONET is based on direct synchronous multiplexing, where separate signals are multiplexed directly into higher speed signals. For example, an OC-
12
circuit might carry traffic from four OC-
3
links. SONET line rates are currently operating up to OC-
192
(9.953 Gbps). This is considerably faster than ATM's maximum current rate of 622 Mbps or Ethernet's current rate of 1 Gbps.
Many network packets, for example, Ethernet packets and ATM AAL5 packets, have Cyclic Redundancy Checks (CRC) across the contents of the packet to help guarantee error free delivery. The transmitter generates the CRC and places it in the packet trailer. The receiver validates that the CRC matches the calculated CRC upon reception. The logic to generate and validate a CRC in each of the above environments is well known. The CRC logic typically is formed using a tree of XOR gates called a CRC tree. The logic takes a seed/residue and some amount data, for example, one or two data bytes and calculates a new CRC. This process is repeated over the entire data set. For serial data streams, the logic is somewhat different.
In Ethernet or in other packet networks, the calculation is simple because the CRC can be accumulated over the received stream with no interruption, and the calculation uses a fixed sized input to the CRC tree. The fixed sized input is some power of two, such as 1, 2, or 4 bytes. The number of input bytes is selected to evenly divide into the possible packet sizes. For example, an Ethernet packet is always mod
4
in length. This allows a single tree to be used.
In ATM, things are different due to the nature of the interleaved cells. The CRC needs to be calculated in a series of steps with one CRC calculation for each cell. The CRC remainder needs to be maintained between cells and used as a seed when the next cell arrives. This process is repeated until the packet is completely transmitted or received. In ATM, the data size is always mod
48
due to the cell payload size. Because the CRC is stored and loaded as state between cells, there is latency involved in the process. Due to this latency, the CRC tree typically takes more bytes as input than a packet network CRC requires. This is done so the CRC can be calculated very quickly to overcome the latency of loading the CRC seed.
When the above environments are combined in a single adapter, problems result. In a communications adapter that supports a Packet over SONET physical bus called POS-PHY both cell based protocols and packet based protocols are supported. In addition to both types of protocols, multiple physicals are attached to the bus. Also multiple cell sizes are supported. In these environments, it is necessary to calculate the CRC with a non-standard number of input bytes. For example, on the POS-PHY bus, packets are time multiplexed between physicals, different amounts of data may be received in different bursts. In some environments, it may be necessary to calculate CRC using different numbers of input bytes to the CRC tree for the same cell.
A different more general method is needed for implementing cyclic redundancy check (CRC) calculation with cell and packet processing for data communications in a communications system. A need exists for a mechanism for implementing cyclic redundancy check (CRC) calculation for use with a variety of modes for communications in a communications system.
SUMMARY OF THE INVENTION
A principal object of the present invention is to provide an improved method and apparatus for implementing cyclic redundancy check (CRC) calculation for data communications in a communications system. Other important objects of the present invention are to provide such method and apparatus for cyclic redundancy check (CRC) calculation for data communications for use with a variety of modes for communications and to provide such method and apparatus that overcome disadvantages of prior art arrangements.
In brief, a method and apparatus are provided for implementing cyclic redundancy check (CRC) calculation for data communications in a communications system. CRC calculation apparatus includes a CRC tree structure receiving a first CRC input, a data input of N−1 data input bytes; and a length input. The CRC tree structure includes a series of CRC trees. Each of the CRC trees has a seed CRC input, a fixed size data input and provides a CRC result output. The series of CRC trees are arranged in cascade with increasing data size inputs. A multiplexer control logic responsive to the length input selectively couples predefined data input bytes to predefined ones of the CRC trees. The multiplexer control logic responsive to the length input couples the first CRC input to a selected one of the CRC trees; and couples predefined CRC result outputs to predefined ones of the CRC trees.
REFERENCES:
patent: 5537403 (1996-07-01), Cloonan et al.
patent: 5568477 (1996-10-01), Galand et al.
patent: 5740075 (1998-04-01), Bigham et al.
patent: 5878057 (1999-03-01), Maa
patent: 5953344 (1999-09-01), Dail et al.
patent: 6122759 (2000-09-01), Ayanoglu et al.
patent: 6167049 (2000-12-01), Pei et al.
patent: 6167389 (2000-12-01), Davis et al.
patent: 6188699 (2001-02-01), Lang et al.
Plotz Kevin Gerard
Slane Albert Alfonse
Lamarre Guy
Pennington Joan
Tu Christine T.
LandOfFree
Method and apparatus for implementing cyclic redundancy... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for implementing cyclic redundancy..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing cyclic redundancy... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2821336