Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-10-25
2004-01-27
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S757000, C714S772000
Reexamination Certificate
active
06684363
ABSTRACT:
BACKGROUND OF TIE INVENTION
1. Field of the Invention
The present invention relates generally to data communication networks and the transmission of data in those networks. More specifically, it relates to hardware and data encoding modifications for increasing the throughput and reliability of data networks.
2. Discussion of Related Art
As the use of data communication networks becomes increasingly widespread, the need for reliable data transmission through nodes in such networks, the Internet being one example, has become more important. In particular, increasing the amount of data that can be sent over an interconnect link between two nodes has always been a goal of data networks. Users expect networks to deliver data faster and at the same time more reliably. One way data can be delivered with higher throughput is ensuring that the payload portion of a data packet is carrying as much actual data as possible; that is, minimizing space taken up by various encoding and CRC bits found in most data packets. These various encoding bits are necessary for ensuring that data is delivered reliably and error-free.
Presently, a significant portion of the payload of a data packet is used for transmitting packet sequence numbers, necessary for ensuring that packets are received in order and that all expected packets are received.
FIG. 1
is a block diagram of a single -flit data packet excluding the packet's 11 inversion bits. Thus, only 77 of the 88 bits are shown. A typical single-flit packet has 47 bits available for carrying payload data and 30 bits used for CRC checking used for checking the accuracy of the data sent. Of the 47 bits that can be used for carrying actual data, eight bits are presently being used for transmitting a sequence number for the packet. This leaves only 39 bits, out of an 88-bit data packet for carrying payload data. By eliminating the need to transmit the sequence number data as part of the payload, the payload portion of the packet used for carrying data would increase by approximately 15%; eight extra bits in each packet.
As mentioned, each packet has 11 invert bits, one for each 8-bit word in an 88-bit packet. An invert bit indicates whether its corresponding seven bits should be inverted or left unmodified. Thus, if a single invert bit is corrupted during transmission over the link, seven other bits will appear at the receiving end as also being corrupted, when in fact they were transmitted accurately but “corrupted” at the receiving end because of the incorrect invert bit. However, the CRC check will show that all eight bits are corrupted. The CRC is presently not able to differentiate an inversion-bit (or 7-bit error) coding error as opposed to a real corrupt data error. As is known in the field, the CRC check is important; if the CRC check matches, the packet can be used, if not, the packet is considered corrupt and is dropped and resent.
Therefore, it would be desirable to increase the bandwidth of a link by utilizing the maximum number of bits in the payload segment of a data packet. This can be done by taking the sequence number of a data packet out of the payload segment and encoding it in the CRC section of a packet. It would also be desirable to have the CRC check account for various encodings in the data packet and be able to handle bursting errors on a single fiber. In addition is would be desirable to have the CRC checking performed at an increased speed.
SUMMARY OF THE INVENTION
Methods and systems for rapidly determining a CRC value for a message that takes into account encoded bits, such as DC inversion bits, to be sent on a link to a remote node is described. A system and method for rapidly calculating a CRC value for a message that takes into account encoded bits in the message, such as DC balance bits, is described. The techniques can be applied to single or multiple flit packets. A table of CRC values is used in combination with a logical grid to quickly determine an appropriate CRC value of a message. This determination is also made by taking into account the encoded inversion bits for DC balancing and prevents a burst of errors that can occur on parallel optical fiber links or from a corrupted inversion bit resulting the apparent error in its seven corresponding non-inversion bits (e.g., data bits).
In one aspect of the invention, a method of deriving a CRC value for a initial data packet having a first set of encoded bits and a sequence number is described. A first CRC value for the initial data packet having a first set of encoded bits is computed. A second CRC value for a subsequent data packet or flit having a second set of encoded bits, if the message is a multi-flit message, is computed. Both data packets are part of the same message but have different sequence numbers. The first CRC is used to modify or adjust the second CRC to take into account the encoded bits. A third CRC value for the sequence number is computed for the initial data packet. A final CRC value is calculated for the initial data packet which can be transmitted to a remote node, where the final CRC value accommodates the first set of encoded bits and the second set of encoded bits.
REFERENCES:
patent: 4720830 (1988-01-01), Joshi et al.
patent: 5426654 (1995-06-01), Hayashi et al.
patent: 5598424 (1997-01-01), Erickson et al.
patent: 5935268 (1999-08-01), Weaver
patent: 6038694 (2000-03-01), Swallow
patent: 6084888 (2000-07-01), Watanabe et al.
patent: 6173431 (2001-01-01), Rittle
patent: 6189124 (2001-02-01), Glaise
patent: 6252888 (2001-06-01), Fite, Jr. et al.
patent: 1035682 (2000-09-01), None
Stephen B. Wicker, “Error Control Systems for Digital Communication and Storage”, Prentice-Hall, 1995.
Cassiday Daniel R.
Moser Thomas J.
Rettberg Randall D.
Satterfield David L.
De'cady Albert
Sun Microsystems Inc.
Torres Joseph D.
LandOfFree
Method for detecting errors on parallel links 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 for detecting errors on parallel links, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for detecting errors on parallel links will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3198829