Checksum generator with minimum overflow

Details Checksum generator with minimum overflow Checksum generator with minimum overflow

2001-09-28

2003-07-08

Moise, Emmanuel L. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Error/fault detection technique

C714S799000

Reexamination Certificate

active

06591397

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to computer networks and, more specifically, to a method and apparatus for efficiently calculating checksums to detect data transmission errors.
BACKGROUND OF THE INVENTION
In computer network systems, data is often encapsulated into data messages and transmitted among various entities of the system. A sending entity, for example, may formulate one or more data messages and transmit them across the network for receipt by a receiving entity. The receiving entity captures the data messages and retrieves the data. During transmission, however, errors can be introduced into the data. Accordingly, error control has become an integral part of computer network systems. One of the primary methods to control data transmission errors is known as error detection. With error detection, a receiving entity examines captured data messages to determine whether an error exists. If so, the receiving entity typically discards the data and requests its retransmission.
One of the more well-known error detection techniques is to calculate and append a checksum valve to each data message. Typically, an agreed-upon algorithm (e.g., a parity check, 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.) is applied to the contents of the message prior to its transmission so as to generate a corresponding checksum. The generated checksum is then appended to the data message by the sending entity and the message is transmitted across the network. Upon receipt of the message, the receiving entity applies the same, agreed-upon algorithm to the contents of the message and determines whether its calculation of the checksum matches the checksum contained in the message. If so, the receiving entity concludes that no errors were introduced into the message during its transmission and, therefore, continues processing the data. If the two values do not match, the receiving entity assumes that errors are present in the data and the message is typically discarded.
FIG. 1
is a block diagram of a conventional network data message
100
. Message
100
, which corresponds to the well-known Transmission Control Protocol (TCP), includes a plurality of fields, including a source port field
102
, a destination port field
104
, a sequence number (SEQ. NO.) field
106
, an acknowledgment number (ACK. NO.) field
108
, a header length field
110
, a window size field
112
, a 16-bit checksum field
114
, a pointer (PTR.) field
116
, an options field
118
and a variable length data field
120
containing the contents of the message being transmitted. To calculate the checksum value pursuant to the TCP protocol, the checksum field
114
is initially set to zero and the data field
120
is padded with an additional zero byte if its length is an odd number. Next, the sending entity adds up all of the 16-bit portions of the message
100
in
1
's complement and then the
1
's complement of the sum is taken. In other words, all of the 16-bit portions of the message
100
are summed and the carry over values are added back into the sum. The 16-bit result is loaded into the checksum field
114
and the message
100
is transmitted across the network.
Checksum calculations can either be performed in software by the sending entity's central processor unit (CPU) or in a hardware circuit designed to calculate checksums. Several hardware circuits are known for calculating checksums. In a first checksum generation circuit, two 16-bit registers are used with an adder circuit. In operation, the first register is zeroed and the first 16-bit word of the message
100
is fetched into the second register. The two registers are then added together and result placed in the first register. The carry bit resulting from the add operation is then added into the first register and the circuit is ready for the next 16-bit word of the message
100
, which is processed in the same manner. After the last 16-bit word has been processed and the carry bit added back to the first register, the first register will contain the checksum value for loading into the checksum field
114
.
In another known checksum generation circuit, two 32-bit registers and a corresponding adder circuit are used. Here, the first register is zeroed and the first 32-bits of the message
100
are fetched into the second register. The two registers are then added together and the result placed in the first register. The carry bit resulting from the add operation is then added into the first register and the circuit is ready for the next 32-bit segment of the message
100
, which is processed in the same manner. After the last 32-bit segment of the message
100
has been processed and the carry bit added to the first register, the low order 16 bits of the register are added to the high order 16 bits and the result loaded into the low order 16 bits of the first register. The carry bit from this last addition is then added back to the low order 16 bits, which represent the final checksum.
U.S. Pat. No. 5,663,952 entitled CHECKSUM GENERATION CIRCUIT AND METHOD to Gentry, Jr., is directed to a checksum generation circuit using two 16-bit adder circuits to generate checksums on a 32-bit data stream. Here, the data stream is split into two 16-bit words and each adder circuit processes a respective 16-bit segment. Each adder circuit also adds back the carry bit for each add cycle and stores the result in a corresponding 16-bit register. After the last 32-bit segment has been processed, three additional steps are performed to obtain the final 16-bit checksum value. First, the 16-bit results produced by each adder circuit are added together along with the last remaining carry bit from the first adder circuit. Second, the last remaining carry bit from the second adder circuit is added back. Third, any carry bit resulting from the second step is added back in, thereby generating the checksum value. The final 16-bit checksum may then be loaded into the respective message.
By operating on two 16-bit words in parallel, the checksum generator of the '952 patent purportedly speeds up the calculation of checksums. It nonetheless has several disadvantages. First, each addition step creates a resulting carry bit. This carry bit, moreover, must be added back in with the next addition step. Furthermore, the creation of any carry bit during the final processing must also be added back in to the final sum. Since most processors typically handle additions sequentially, the adding back of each carry bit requires an additional step consuming processor resources and time. Accordingly, a need has arisen to develop a checksum generator which can operate more efficiently.
SUMMARY OF THE INVENTION
Briefly, the present invention is directed to a method and apparatus for generating a checksum that minimizes the creation and manipulation of carry bits by allowing a “running sum” to expand into a register having a larger capacity than the size of the message segments being processed. In particular, a checksum generator includes at least one adding circuit for processing a given message in segments. Associated with the adding circuit is a register for temporarily holding the running sum that is being calculated by the adding circuit. According to the invention, the register is configured to hold a running sum that is larger than the message segments being added by the adding circuit. Preferably, the register is twice the size of the message segments being processed and is segregated into a high order portion and a low order portion. For example, the adding circuit may be configured to process 16-bit message words and the register may be configured to store a 32-bit running sum and segregated into a high order 16-bit portion and a low order 16-bit portion. By coupling the adding circuit to a register that is larger than the corresponding message segments, the adding circuit can allow the running sum to expand into the register, thereby eliminatin

Affiliated with

Also associated with

Rating

Checksum generator with minimum overflow does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Checksum generator with minimum overflow, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Checksum generator with minimum overflow will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3090156