Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
2000-04-13
2003-07-29
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S748000
Reexamination Certificate
active
06601217
ABSTRACT:
BACKGROUND
This invention relates to the field of computer systems and communications. More particularly, a system and methods are presented for facilitating fast error correction for small communication packets and/or distinct portions of communication packets.
Communication packets exchanged between computer systems (e.g., through a network) usually include some form of error correction encoding in addition to whatever data, headers, trailers or other elements they may include. In particular, a packet may include an ECC (Error Correction Code), which may be calculated or computed using any of a variety of algorithms. The ECC or other error correction mechanism is generated by the entity (e.g., computer system) that sends the packet and is used by the packet recipient to determine whether the packet was received with any errors and to correct them, where possible. A Hamming code, for example, allows the recipient of a packet to correct a single bit error in an encoded packet or detect a multi-bit error.
Often the ECC is calculated for the entire contents of a packet, rather than just the data or other portion. In such a situation it becomes difficult to detect a single bit error on a line that is stuck or broken. For example, if one line of a communication link is stuck on, then every bit of the packet that traverses the line risks being transformed from a zero into a one. Decoding the ECC or applying error correction at the receiving entity may allow it to determine that a multi-bit error has occurred, but it may not be able to narrow that observation to determine that a line is broken or determine which line is broken.
The larger percentage of a packet that is covered by an ECC and the more types of errors to be protected from (e.g., single bit error, multiple bit errors, broken line), the more complicated the ECC algorithm may become. The more complex the error correction algorithm, the longer it takes for the recipient to decode the packet, detect any errors and, if possible, correct them. In particular, first the coded information must be received, then it must be decoded, or the ECC re-computed on what was received, in order to determine if there are any errors. If there is an error, it must then be corrected before the information can be acted on. Even if there is no error, however, the delay induced in order to check for errors may be non-trivial, thereby detracting from the performance of an application waiting for the packet.
Further, an end recipient or intermediate recipient of a packet (e.g., a router) may only need to access a small portion of the packet, such as a routing header. If this recipient is forced to decode the entire packet in order to access and/or verify the correctness of the routing information, the packet suffers what should be an unnecessary delay.
Thus, what is needed is a method of error correction for a small packet or a portion (e.g., routing header) of any size packet that decreases the time needed to check the packet or packet portion for errors and correct an error. It is also desirable to be able to retrieve or rebuild the packet or packet portion in the event of an error, even if one line of the communication or data link is broken. Further, by applying such a method of error correction to a specific portion of a packet, the packet may be processed faster by an entity requiring access only to that portion.
SUMMARY
In one embodiment of the invention a system and methods are provided for facilitating error correction of small packets or portions of any size packets. In this embodiment a packet or packet portion is divided into multiple segments and the packet or packet portion is repeated in such a way that the segments in each iteration are arranged in a different order. It may be sufficient to repeat the packet or packet portion twice, but additional repetition will allow correction of more errors at the receiving entity. Thus, if the error correction is to be applied to a routing header of a packet, the routing header is segmented and then multiple iterations of the header are included with the packet rather than a single copy. However, the segments of the routing header are arranged in different sequences among the multiple iterations and may therefore be transmitted over different elements of a communication link.
The entity that receives the packet or packet portion applies an error correction algorithm to each iteration of the packet or packet portion, each segment, the overall collection of multiple iterations, etc. This algorithm may differ from any error correction algorithm applied to another portion of the packet.
In this embodiment each segment of the packet or packet portion is received multiple times (e.g., twice), over different lines of the incoming communication link. As the packet or packet portion is received, each segment or iteration of the packet or packet portion can be checked for errors while a succeeding segment or iteration is being received. If an error is detected in one segment of one iteration, the segment can be retrieved from a different iteration. And, by comparing errors among the multiple iterations a broken line can be detected (e.g., a single bit error may be detected in each segment that uses the broken line).
By the time the final iteration of the packet or packet portion is received, the receiving entity, may have already determined whether a previous iteration or segment was received correctly. Thus, if an initial or early iteration is received without any detected errors, before the final iteration is received the receiving entity may begin passing the packet or packet portion forward for higher level processing, for use by a router, etc. If all preceding iterations have errors, then the final iteration may be passed forward immediately upon receipt.
In one particular embodiment of the invention multiple segments of routing data or other information are received in multiple iterations or versions, with the segments arranged in different sequences in each iteration. When a first iteration is received, each segment is checked for errors, possibly using a parity indicator (e.g., a parity bit or other error detection code) computed and set by the entity that sent the data. If an error is detected in a given segment of the first iteration, that segment may be retrieved instead from a different iteration. Because the segments are sent in different sequences in the different iterations, it is likely that at least one version will be received without errors.
REFERENCES:
patent: 5153920 (1992-10-01), Danner
patent: 5710798 (1998-01-01), Campana, Jr.
patent: 6170075 (2001-01-01), Schuster et al.
patent: 6345375 (2002-02-01), Kelkar et al.
patent: 6490705 (2002-12-01), Boyce
patent: 6516435 (2003-02-01), Tsunoda
patent: 410093659 (1998-04-01), None
Britt Cynthia
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
System and method for error correction in an electronic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for error correction in an electronic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for error correction in an electronic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3049336