Incremental cyclic redundancy (CRC) process

Performing a constant time cyclic redundancy check (CRC) over an entire packet to obtain a constant time CRC value. A first CRC is performed on an original header of the packet and a second CRC is performed on a modified header of the packet. The size of the payload of the packet is obtained. An XOR operation is performed on the results of the first and second CRC to calculate a third result. An intermediate CRC value is obtained by performing a CRC on a number of zero values corresponding to the size of the payload using the third result as an initial value. The intermediate CRC value may be employed with other packets having a same size and same header as the packet. The constant time CRC value is obtained by performing an XOR operation on the intermediate CRC value and the original CRC value contained in the packet.

FIELD OF THE INVENTION

Embodiments of the invention relate to data verification performed on exchanged data packets.

BACKGROUND

Anytime data is converted from an analog format to a digital format, or vice-versa, there is a possibility that the conversion may inadvertently convert one or more bits of data incorrectly. In the transmission of digital data, it is sometimes necessary to convert digital data into analog signals to facilitate its propagation. To detect if any data has been inadvertently changed during transmission, an error-detecting code, such as a cyclic redundancy check (CRC), is often employed. When a system uses a CRC, a block of data is assigned a short check value, based on the remainder of a polynomial division of their contents. On retrieval of the block of data, the calculation is repeated and, in the event the check values do not match, corrective action can be taken against data corruption. CRCs can be used for both error correction as well as error identification.

The check value constituting a CRC is redundant in that it expands the message without adding information. The algorithm used to create the check value of a CRC is cyclic in that it is based on cyclic codes. CRCs are popular because they are simple to implement in binary hardware, easy to analyze mathematically, and particularly good at detecting common errors caused by noise in transmission channels.

Many software applications have a need to calculate a cyclic redundancy check (CRC) for processed Ethernet frames. For instance, this process is performed in software, rather than by hardware, when the packet is encapsulated several times after the CRC calculation. As a result, hardware may only need to append the CRC to the final Ethernet frame.

The calculation of a CRC can become a bottleneck for two reasons. First, the calculation of a CRC has a linear asymptotic complexity and depends on the number of bytes in the packet. Second, for software to calculate a CRC, the software requires access to the data carried by the packet (i.e., the “payload”), which is known to be a slow operation because such data should be loaded from memory to the CPU cache. Regardless of whether the payload is pre-fetched or loaded to the CPU cache to facilitate the calculation of the CRC, the CPU cache becomes clogged. This, in turn, leads to evicting other data from the cache, which further increases the latency in processing requests to access the other data evicted from the cache.

An approach for performing an incremental CRC update, as described by Mark Adler on the web site www <dot> stackoverlow <dot> com, involves calculating a CRC in logarithmic time. However, this technique discussed by Mark Adler suffers from the disadvantage in that it requires multiple matrix multiplications and extra CPU cache usage.

DETAILED DESCRIPTION OF THE INVENTION

Approaches for performing a cyclic redundancy check (CRC) on a data packet in constant time are presented herein. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the embodiments of the invention described herein. It will be apparent, however, that the embodiments of the invention described herein may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form or discussed at a high level in order to avoid unnecessarily obscuring teachings of embodiments of the invention.

Embodiments of the invention are directed towards performing a cyclic redundancy check (CRC) on a data packet. Advantageously, embodiments of the invention may perform an incremental CRC update upon a data packet in constant time. For this reason, the CRC value obtained by an embodiment may be referred to herein as a constant time CRC value. To achieve such CRC calculation performance, embodiments do employ the use of additional memory compared to prior approaches.

FIG.1Ais an illustration of a computer system60which may receive a plurality of packets, such as packet30, over network20according to an embodiment of the invention. Computer system60represents any type of computer system capable of receiving packets over network20, e.g., computer system60may correspond to a switch, a router, a firewall computer, a server, and the like. Software application50, executing on computer system60, broadly represents any type of software responsible for processing one or more packets, such as packet30. Network20, as broadly used herein, represents a wide variety of packet-based networks, including but not limited to, the Internet. As is well-understood in the art, computer system60will receive large numbers of packets over network20.

In the prior art, when a software application receives an Ethernet packet from the network, the packet will already possess a CRC value that has been appended to the end of the packet. In the prior art, a network interface controller (NIC) checks that CRC value and removes the CRC value from the packet before sending the packet up the network stack (i.e., to a different network protocol layer) for further processing. However, some modern NICs have an ability to leave the CRC value in the packet.

Computer system60ofFIG.1Acomprises network interface card (NIC)62in an embodiment. Embodiments of the invention make use of the CRC value that is present in the packet. Thus, network interface card (NIC)62is designed to not remove the CRC value from packet30upon receipt of packet30from network20. Consequently, when packet30is processed by software application50, packet30will comprise the CRC value.

Embodiments of the invention shall be discussed below with reference to software application50performing a cyclic redundancy check (CRC) on packet30in constant time. WhileFIG.1Adepicts a single packet, namely packet30, it should be understood that software application50may process each packet received by computer system60in the same manner as that described herein with reference to packet30.

To illustrate the process performed by embodiments upon packet30, different states of packet30are illustrated inFIGS.1B and1C, whereFIG.1Bis an illustration of packet30upon receipt by computer system60and prior to being processed by an embodiment of the invention, andFIG.1Cis an illustration of packet30after having an updated header processed to possess an updated CRC value in accordance with an embodiment of the invention.FIG.1Bdepicts packet30having a header160, a common payload140, and a CRC value150.FIG.1Cdepicts packet30having an updated header162, a common payload140, and an updated CRC value. Advantageously, common payload140is not changed during packet processing.

FIG.2is a flowchart illustrating the functional steps of performing a cyclic redundancy check (CRC) on a data packet in constant time according to an embodiment of the invention. As shown inFIG.2, step210involves a plurality of sub-steps, i.e., sub-steps212-220. In the performance of step210, software application50, software application50may perform certain processing on packet30and, thereafter, use the result of that processing to convert CRC value150to updated CRC value152in constant time to obtain the constant time CRC value. Thereafter, software application50may remove CRC value150from packet30and in its stead, insert the constant time CRC value, which is depicted inFIG.1Cas updated CRC value152. Packet30, once in possession of updated CRC value152, may then be forwarded to its next destination. Note that in the performance of the steps ofFIG.2, software application50will modify the destination MAC address110of packet30as appropriate and may strip VLAN tag130from packet30.

In an embodiment, initially in step212inFIG.2, a first cyclic redundancy check (CRC) is performed by software application50on a byte stream of header160of packet30as received. The state of packet30as received is shown inFIG.1B.FIG.1Bdepicts header160of packet30, common payload140of packet30, and a CRC value150for packet30.

Header160of packet30comprises a destination MAC address110, a source MAC address120, and potentially a VLAN tag130. VLAN tag130refers to a 802.1Q VLAN header under the IEEE standard IEEE 802.1Q-1998. Common payload140of packet30is not changed or altered during the processing of step210or any sub-step thereof.

Thereafter, in step214, a second cyclic redundancy check (CRC) is performed by software application50on a byte stream of updated header162of packet30. Updated header162is shown inFIG.1Cand comprises updated destination MAC address112and the source MAC address120. Updated destination MAC address112refers to the MAC address of the next destination to which packet30is to be sent over network20, while source MAC address120refers to the MAC address of the original sender of packet30. Software application50, or some other entity, may update packet30to possess updated header162before the performance of step214.

In step216, software application50determines a size of payload140of packet30. Step216may involve determine the number of bits comprising payload140in an embodiment.

In step218, software application50performs an XOR operation on the CRC value obtained in step212and the CRC value obtained in step214to generate a result.

Thereafter, in step220, software application50generates an Intermediate CRC value by performing a third cyclic redundancy check (CRC) on a number of zero values corresponding to the size of the payload that was determined in step16. The third CRC performed in step220uses the result obtained in step218as an initial value (also known as a CRC register) of the CRC algorithm.

Thereafter, in step222, software application50may generate updated CRC value152(which is the constant time CRC value) by performing an XOR operation on the Intermediate CRC value of step220and the CRC value150, which is the original CRC value contained within data packet30upon receipt by computer system60.

Once updated CRC value152is generated in step222, updated CRC value152may be appended to payload140in place of CRC value150for packet30as shown inFIG.1C, and thereafter, packet30may be sent over network20to a new destination.

Note that the calculation of the updated CRC value152in step222only depends upon (a) header160, (b) updated header162, and (c) the size of payload140determined in step216; however, the calculation of updated CRC value152does not depend on the contents of payload140. Since software application50will process a limited number of destination MAC addresses/VLANs, this means that software application50need only calculate certain Intermediate CRC values once for each combination of header160, updated header162, and payload size. Thereafter, once the Intermediate CRC value is known or calculated for packet30, then it may be reused without having to recalculate this value.

In step230, Intermediate CRC obtained in step220is employed in generating the updated CRC value152for one or more other packets having the same payload size and same header as packet30.

Note that in the above discussion, the steps of initial and final inverting of CRC register (which are required by Ethernet standard) are skipped, as these steps are not necessarily required in all CRC algorithms. Embodiments of the invention have broader applicability than just an Ethernet CRC only. In the given example above, the Ethernet header was modified. However, embodiments will work with IP header modifications. The only difference is that the length of these headers will change.

Embodiments of the invention enable a CRC value to be calculated for packet30by software application50in a manner that has constant asymptotic complexity. Further, embodiments of the invention will not overload CPU cache of computer system60because the inventive approach loads packet data only once in the calculation of updated CRC value152. Moreover, the processing of all network traffic with the same headers will then use this Intermediate CRC value to update the CRC value150.

Embodiments of the invention may consume additional memory as compared to other prior art approaches for calculating a CRC; for example, embodiments may consume an amount of memory as big as number of different headers multiplied by number of packet sizes. Nevertheless, the inventive approach discussed herein yields a significant performance gain over prior art approaches.

FIG.3is a block diagram that illustrates a computer system300, which may correspond to computer system50in an embodiment of the invention. In an embodiment, computer system300includes processor304, main memory306, ROM308, storage device310, communication interface318, and communications bus330. Computer system300includes at least one processor304for processing information. Computer system300also includes a main memory306, such as a random-access memory (RAM) or other dynamic storage device, for storing information and instructions to be executed by processor304. Main memory306also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor304. Computer system300further includes a read only memory (ROM)308or other static storage device for storing static information and instructions for processor304. A storage device310, such as a magnetic disk or optical disk, is provided for storing information and instructions.

The term “non-transitory computer-readable storage medium” as used herein refers to any tangible medium that participates in storing instructions which may be provided to processor304for execution. Non-limiting, illustrative examples of non-transitory computer-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, or any other magnetic medium, a CD-ROM, any other optical medium, a RAM, a PROM, and EPROM, a FLASH-EPROM, any other memory chip or cartridge, or any other medium from which a computer can read.

Various forms of non-transitory computer-readable media may be involved in carrying one or more sequences of one or more instructions to processor304for execution. For example, the instructions may initially be carried on a magnetic disk of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a network link320to computer system300.

Communication interface318provides a two-way data communication coupling to a network link320that is connected to a local network. For example, communication interface318may be an integrated service digital network (ISDN) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface318may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links or optical links may also be implemented. In any such implementation, communication interface318sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

Network link320typically provides data communication through one or more networks to other data devices. For example, network link320may provide a connection through a network to one or more other computer systems.

Computer system300can send messages and receive data, including program code, through the network(s), network link320and communication interface318. For example, a server might transmit a requested code for an application program through the Internet, a local ISP, a local network, subsequently to communication interface318. The received code may be executed by processor304as it is received, and/or stored in storage device310, or other non-volatile storage for later execution.