Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
2000-11-30
2003-11-04
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S807000
Reexamination Certificate
active
06643821
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to digital computing and communication systems, and more particularly to a method for computing incremental checksums for a data packet such as for processing communication packets of information.
2. Description of Related Art
Modern computing systems typically operate using error detection mechanisms such as checksums to maintain integrity of data words. This is particularly important for the higher error rates of network communication systems including wired and wireless communication systems. Communication systems, such as used in wired networks, the Internet, and wireless communication, process information that is typically organized as data packets and that needs to have data integrity checking. Devices in a communication system, such as network routers, repeaters, and relay stations, normally must quickly analyze received data packets to determine the integrity of the data packets. Additionally, if the devices make any changes to bits of information in the data packets then the device has to update the checksum information for such data packets. A common way to change the checksum information corresponding to a data packet is known as an incremental checksum. This incremental checksum process is often a software-based task. The task has to be performed at nearly the speed of the communication channel to maintain a throughput in a communication system. In a very high speed communication system, for example such as the Internet, the data packets may be processed at up to 30 million packets per second. A bit rate of 10 gigabits per second is not uncommon in processing data packets in such a network.
Accordingly, it is imperative that any operation on the bits of any data packet in such a high speed communication system must be very fast and efficient to keep up with the communication bit rate for such data packets. The speed of computing the incremental checksum, therefore, must be kept to nearly the bit rate of the communication of the data packets to minimize the impact on the speed of communication of the data packets across the network.
The incremental checksum operation is considered an integrated part of any networking system. One of the most widely used applications utilizing such checksum operation is IP Forwarding. An IP packet, for example, contains within it a checksum field, typically in its IP Header. This checksum field is used to help detect bit errors in data packets, due typically to unwanted noise in a communication medium. Understanding the fact that an IP router processes approximately 30 million packets per second on a high speed network link, one can see the importance of verifying the checksum value for each packet as they arrive. Once the checksum value is verified, an IP router may choose to edit part of an IP Header. Such a change requires the IP router to re-compute the checksum field. The incremental checksum operation is considered an optimal solution for such a problem. See, for example, the publication RFC 1071 “Computing the Internet Checksum,” R. Braden, 1988, A description of this well known incremental checksum operation follows.
(1) Consider a packet P with a checksum value of C, in its IP Header.
(2) Now lets say that a router changes part of IP Header X to X′.
(3) Incremental checksum states that, in order to compute new checksum value C′—one would subtract old information X from the checksum value C and then add in the new information X′, in order to acquire the new checksum value, NC. Please note that all additions are considered to be one's complement additions.
This means that a computing system has to perform an addition and a subtraction for every time a packet passes through an IP router. Conventionally, this operation is performed with the assistance of two software instructions. Below is a sample assembly code for a computing device to operate the Incremental Checksum.
Assume the following usage of registers:
(1) R
1
=old checksum
(2) R
2
=new checksum
(3) R
3
=old information
(4) R
4
=new information
sub R
1
, R
1
, R
3
add R
2
, R
1
, R
4
Assuming that each of these instructions above takes one processor cycle to complete, performing the incremental checksum algorithm will take two processor cycles. However, due to the data dependency on register R
1
, one needs to stall for an extra cycle—resulting in 3 cycles to complete the incremental checksum operation. One could try to avoid this extra cycle penalty by performing data forwarding in order to resolve any data dependency issues. We know that a high speed IP router processes 30 million packets per second. This means that every second it executes (30 million packets/second * 2 cycles/packet)=60 million cycles per second. In order to perform IP Forwarding at near “wire speed”, it is necessary to cut down the number of processor cycles used to perform the checksum operation.
Thus, there is a need to overcome the disadvantages of the prior art, such as discussed above, and in particular to improve the processing speed of incremental checksum operations in computing systems such as required for high speed communication of data packets.
REFERENCES:
patent: 4712215 (1987-12-01), Joshi et al.
patent: 5500864 (1996-03-01), Gonia et al.
patent: 5630054 (1997-05-01), Trang
patent: 5663952 (1997-09-01), Gentry, Jr.
patent: 5701316 (1997-12-01), Alferness et al.
patent: 5826032 (1998-10-01), Finn et al.
patent: 5912909 (1999-06-01), McCoy
patent: 6343306 (2002-01-01), Lo
Braden, R., RFC 1071 “Computing the Internet Checksum”, 1988.
Karim Faraydon O.
Talsania Kartik V.
Wass Vincent E.
Bongini Stephen
Jorgenson Lisa K.
STMicroelectronics Inc.
Ton David
LandOfFree
Method and device for computing incremental checksums 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 device for computing incremental checksums, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for computing incremental checksums will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3145546