Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
1998-11-20
2001-01-30
De Cady, Albert (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S746000, C714S052000
Reexamination Certificate
active
06182267
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a system and method for use in detecting errors in data transmission, and more specifically, to a system and method for ensuring accurate checksumming of data transferred via at least one pre-fetchable bus.
2. Brief Description of Related Prior Art
In modern computer systems, data is transferred among various processing/communications modules of the system. Errors may be introduced during transmission of the data. Consequently, error control has become an integral part of the design of such computer systems.
In order for the system to be able to control data transmission errors, it must be able to accurately determine when such errors occur. A checksum procedure is one conventional technique for determining when errors have been introduced into a data stream (e.g., a data block or packet). In a typical checksum procedure, a numerical value (“checksum” or “checksum value”) is generated by the sender (“the sender's checksum”) of the packet in the system by applying a computational algorithm (e.g., a parity or cyclic redundancy check, hashing function, summation of the number of bits in the packet equal to “1”, summation of the numerical values represented by the data, etc.) to the contents of packet. This value is then sent with the packet when the packet is transmitted. After the recipient receives the packet, the recipient computes a new checksum value (“the recipient's checksum”) by applying the same algorithm to the received data packet, and compares the recipient's checksum to that transmitted with the data packet. If the two checksums match, it is assumed that transmission of the packet was successful (i.e., no errors were introduced into the packet during transmission). Alternatively, if the two values do not match, it is assumed that errors where introduced into the packet during its transmission, and the recipient typically undertakes action (e.g., requesting that the packet be re-transmitted by the sender) to remedy the situation.
In order to speed data transfer and reduce software processing overhead in the system, it is often desirable to calculate the sender's checksum using a checksum system that is substantially or entirely hardware, and wherein, as portions of the data block to checksummed are transmitted to the recipient, they are substantially simultaneously presented to the checksum logic, in parallel with their transmission to the recipient. Each time a portion of the data block is presented to the checksum logic, the checksum logic generates a new subtotal checksum by essentially accumulating checksums of the data block portion being presented (using a predetermined checksum algorithm implemented by the checksum logic) and a subtotal checksum of those portions of the data block previously presented to the checksum logic. Once the final portion of the data block has been presented to the checksum logic, the resulting total accumulated checksum of the data block is generated, and transmitted to the recipient, which then uses this total checksum to determine whether the transmission of the data block was successful.
Unfortunately, problems can arise in accurately calculating the sender's checksum using the above-described technique, if the data block is transmitted from the sender to the recipient via a pre-fetched bus system. As used herein, a bus system is said to be “pre-fetched” if data latency may exist between different portions of the bus. Such data latency may arise, e.g., if the bus (1) comprises one or more bus controllers (or other data buffering devices) through which data transmitted via the bus from the source must pass before it can reach the recipient, and/or (2) the bus permits the recipient to command that data be transmitted from the source to the recipient via a “burst mode” data transfer operation (e.g., via direct memory accessing (DMA) of the data source wherein the source is commanded to transmit data to the recipient, starting with portions of the data associated with a memory location specified in the DMA command, and continuing during subsequent bus read cycles, with portions of the block associated with subsequent sequential memory locations, until assertion of the transfer command terminates, and without specification in the command of the total amount of data that is to be provided to the recipient from the source in the transfer operation). One example of a prefetched bus, as that term is used herein, is a conventional Peripheral Component Interconnect (“PCI”) bus.
As a result of the data latency that may exist in a pre-fetched bus system wherein data checksummed in parallel with its transmission to the recipient, if the total length of the data packet exceeds the maximum data word length that can be transferred via the bus in a single bus data transfer operation cycle (i.e., the “bus width”) and the transfer operation is terminated prior to receipt of all of the portions of the data block transmitted by the source, portions of the data block to be checksummed may be transmitted from the source via the bus, but not received by the recipient. Thus, in this type of system, repeated transmission of identical portions of the data block may be required in order for the recipient to receive the entire data block.
Unfortunately, since in this type of system the data is checksummed by the source's checksum logic in parallel with its transmission to the recipient, portions of the data block that undergo repeated transmission to the recipient also undergo repeated checksumming by the checksum logic. This causes the data block's total checksum as generated by the checksum logic to be invalid, and likely results in unnecessary retransmission of the entire data block from the source to the recipient.
Partial solutions to these problems may involve (1) clearing and recalculating of the checksum logic's subtotals after repeated transfers of the same data from the source, or (2) calculating the checksum of the entire data block in a separate checksum operation prior to transmitting any of the data block to the recipient. Disadvantageously, these partial solutions decrease overall data transfer speed, and increase data processing overhead.
SUMMARY OF THE INVENTION
In accordance with the present invention, a system and method are provided that overcome the aforesaid and other disadvantages and drawbacks of the prior art. More specifically, the system and method of the present invention ensures that an accurate total checksum is generated of a data block being transmitted via a prefetched bus, by ensuring that only portions of the data block that have yet to undergo checksumming are checksummed by checksum logic, in parallel with their transmission via the bus, despite repeated transmissions of identical portions of the data block.
Advantageously, the present invention permits only those portions of the data block that have not yet been previously checksummed by the checksumming logic to be so checksummed, despite repeated transfers of the same portions of data from the data source. Advantageously, this ensures that an accurate total checksum of the entire data block is generated, despite repeated reads of identical memory locations in the block, and without requiring either the clearing of the checksum logic and restoring of the block's previously calculated partial checksum after such repeated reads, or a separate checksum calculation operation (i.e., wherein the checksum of the entire block would be calculated prior to being transferred to the recipient). Thus, the present invention is able to generate an accurate total checksum of a data packet being transferred via a prefetchable bus, without decreasing data transfer speed or substantially increasing data processing overhead.
These and other features and advantages of the present invention will become apparent as the following Detailed Description proceeds, and upon reference to the Drawings, wherein like numerals depict like parts, and in which:
REFER
Jennings William E.
Kidd Jeffrey W.
Cady Albert De
Cesari and McKenna LLP
Chase Shelly A
Cisco Technology Inc.
LandOfFree
Ensuring accurate data checksum does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Ensuring accurate data checksum, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ensuring accurate data checksum will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2500605