Data integrity verification in a switching network

DATA INTEGRITY VERIFICATION IN A SWITCHING NETWORK

CROSS-REFERENCE TO RELATED APPLICATIONS

Φ This application claims the benefit of U.S. Provisional Patent Application 60/152,849, filed September 8, 1999, and of U.S. Provisional Patent Application 60/175,339, filed January 5 10, 2000, which are incorporated herein by reference.

FIELD OF THE INVENTION

The present invention relates generally to systems and methods for high-speed data transfer, and specifically to methods and devices for verifying the integrity of data and detecting data faults in such a system.

י BACKGROUND OF THE INVENTION

Error-checking is an integral element of high-reliability data transfer systems. To ensure reliable operation, it is necessary to check all data and control paths for bit ettors, which may occur due to noise, cosmic rays or other causes. One of the most common, standard methods for error checking is based on Cyclic Redundancy Codes (CRCs), which are computed by 15 applying a predefined polynomial to each block of transmitted data. Typically, before sending a data packet over a network or other communication link, the transmitting device, such as a source node, computes the CRC for the bits in the packet and appends it to the packet. Upon receiving the packet, the receiving device recomputes the CRC and compares it to the transmitted CRC. A discrepancy indicates that an error has occurred.

In switch fabrics and other complex networks, it is generally desirable not only to detect erroneous packets, but also to determine at what point the error in the packet was introduced, in order to take remedial action. Since a packet typically makes multiple hops through the network between its source and its destination, multiple CRC checks are required. It is therefore necessary to check the CRC at every input of every device in the network. An 25 approach of this sort has been adopted in the InfiniBand network architecture, which has been advanced by a consortium led by a group of industry leaders (including Intel, Sun, Hewlett Packard, IBM, Compaq, Dell and Microsoft). This approach does not provide a complete solution to the problem of error location, however, since the CRC check at the device input is 1 incapable of distinguishing between network link errors and device errors that occurred in 30 devices along the packet ׳ s path.

WO 01/18974

PCI7IL00/00539

Fig. 1 is a block diagram that schematically illustrates a switching device 20, as is known in the art, offering a solution to the problem of error location. Device 20 comprises a plurality of input circuits 22 and output circuits 26, interconnected by a switching core 24. Each of the input circuits comprises a CRC checker 30, typically a logic circuit, which 5 computes the CRC of the bits in each received packet and compares it to the CRC transmitted with the packet by the preceding device on the packet׳ s route. In order to distinguish internal errors from external errors, a parity generator 32 computes a parity bit and attaches it to each unit of data to be conveyed through the device. The data, together with the associated parity bits, are then stored in a buffer 34 while awaiting the attention of switching core 24. Output 10 circuits 26 may include additional or alternative data buffers, as is known in the art.

A parity checker 40 recomputes the parity of each data unit passed to output circuit 26 by switching core 24. A discrepancy in the parity bit indicates that an error has occuaed in data storage or transfer within device 20. Routing logic 42 modifies the header of the data packet, typically in order to indicate the source and destination that the packet is to take over 15 its next hop. A CRC calculator 44 computes a new CRC for the packet, reflecting the change in the packet header, and the packet is then transmitted to the next device over the network. The separation of CRC and parity functions enables device 20 to distinguish internal from external data errors. Addition of the parity bit, however, requires additional data lines and storage capacity inside the device. When the data unit size is one byte, this overhead is greater 20 than 10%.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide improved devices and methods for verifying data integrity in a data transmission system.

It is a further object of some aspects of the present invention to provide devices and 25 methods for distinguishing between internal device errors and external link errors, with reduced overhead relative to approaches known in the art.

In preferred embodiments of the present invention, a switching device in a network comprises CRC checking logic both in its input circuits and in its output circuits. For each block of data passing through the device, typically in the form of a data packet, the CRC is thus 30 checked twice: once as it enters the device and once before it exits. A discrepancy between the entry and exit CRCs indicates that a fault has occurred inside the device. Otherwise, when both

ר

WO 01/18974 PCT/IL00/00539 the entry and exit CRCs are erroneous, the fault can be identified as having occurred in a link or other device before the packet reached the current device. Internal and external faults are thus distinguished without the added overhead of using a parity bit.

Preferably, when a CRC error is detected in a packet, the packet header information is 5 reported to a network management entity, referred to herein as a fabric manager, together with an identification of the fault as internal or external. Alternatively, only internal errors, only external errors, or neither internal nor external errors are reported in this manner. The fabric manager uses the header information to identify the route that the packet has taken through the network, so as to diagnose the fault and to take corrective action as appropriate.

While preferred embodiments are described herein with reference to particular switching devices in packet-switched networks, the principles of the present invention are equally applicable to other types of data transmission devices and systems. Furthermore, although these embodiments are based on CRCs, other methods of error checking, as are known in the art, may similarly be used.

There is therefore provided, in accordance with a preferred embodiment of the present invention, a data transmission device, including:

input circuitry, configured to receive a block of data over a network, the block containing an error-checking code, the input circuitry including input error-checking logic, which is adapted to detect a discrepancy between the data and the error-checking code and to 20 generate a first error signal indicating whether the discrepancy was detected in the input circuitry;

output circuitry, configured to transmit the block of data, received by the input circuitry, over the network, and including output error-checking logic, which is adapted to detect the discrepancy between the data and the error-checking code and to generate a second 25 error signal indicating whether the discrepancy was detected in the output circuitry; and a comparator, coupled to receive and compare the first and second εσοτ signals, so as to identify a source of the discrepancy.

Preferably, the error-checking code includes a Cyclic Redundancy Code (CRC).

Further preferably, when the error signals indicate that the discrepancy was detected in the output circuitry but not the input circuitry, the comparator identifies the source of the discrepancy as being in the device. Most preferably, when the error signals indicate that the

WO 01/18974 PCT/ILOO/00539 ’discrepancy was detected in both the input circuitry and the output circuitry, the comparator identifies the source of the discrepancy as being external to the device.

Preferably, the data block includes a packet including routing information, and the device includes a buffer, which is coupled to receive the routing information and to transfer the 5 routing information to a processor responsive to one or more of the error signals.

In a preferred embodiment, the input and output circuitry respectively include multiple input and output ports, and the input and output error-checking logic include error checkers associated respectively with the multiple ports, and the device includes a switching core, coupled to transfer the block of data from one of the input ports that receives the block to a 10 designated one of the output ports.

There is also provided, in accordance with a preferred embodiment of the present invention, a method for error detection in a device having an input and an output, including:

receiving a block of data at the input of the device, the block including an error-checking code;

checking the block so as to detect a discrepancy between the data at the input and the error-checking code;

generating a first error signal indicating whether the discrepancy was detected at the input;

conveying the data through the device, checking the block after conveying the data through the device so as to detect the discrepancy between the data and the eaor-checking code at the output of the device;

generating a second error signal indicating whether the discrepancy was detected at the output; and comparing the first and second error signals so as to identify a source of the 25 discrepancy.

Preferably, the data block includes a packet including routing information, and the method includes extracting the routing information responsive to one or more of the error signals. Most preferably, the device belongs to a network, and the method includes locating a fault in the network responsive to the one or more of the error signals and to the extracted 30 routing information.

WO 01/18974 PCT/IL00/00539

The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings in which: φ BRIEF DESCRIPTION OF THE DRAWINGS

Fig. 1 is a block diagram that schematically illustrates a switching device with error 5 detection capabilities, as is known in the art;

Fig. 2 is a block diagram that schematically illustrates elements of a switching device with error detection capabilities, in accordance with a preferred embodiment of the present invention; and

Fig. 3 is a flow chart that schematically illustrates a method of error detection and 10 diagnosis, in accordance with a preferred embodiment of the present invention.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT

Reference is now made to Fig. 2, which is a block diagram that schematically illustrates elements of a switching device 50, in accordance with a preferred embodiment of the present invention. Device 50 comprises input circuits 52 and output circuits 56, linked by switching 15 core 24 as in Fig. 1. Preferably, device 50 is a switch in a network, most preferably in a switching fabric, such as an InfiniBand fabric. Thus, device 50 typically comprises multiple inputs and outputs, like device 20 shown in Fig. 1; but for the sake of simplicity of illustration, only one input circuit 52 and one output circuit 56 are shown in Fig. 2.

CRC checker 30 checks packets received by input circuits 52 of device 50. For each 20 packet, the CRC checker generates an error signal, preferably by attaching an error bit to the packet. This action is schematically equivalent to placing an appropriate error bit in a first-in-first-out (FIFO) register 58, as shown in Fig. 2. The value of the error bit indicates whether the CRC code matched the data in the packet or not, with the value. 1 indicating that a discrepancy was detected, for example. The packets are placed in buffer 34 to await 25 transfer to the output circuits by switching core 24, and the packet headers are held in a header buffer 54 for later reference. Preferably, device 50 is configured for high-speed operation, wherein the switching core may begin transferring the packet to output circuits 56 even before the CRC check is completed.

Packets received by the output circuits are passed to routing circuitry 42 and CRC 30 calculator 44, for transmission to .the next element in the switching fabric. At the same time, the packets are again checked for CRC errors by a second CRC checker 60. Error bits

WO 01/18974

PCT/ILOO/OOS39 generated by checker 60 are passed to a comparator 66, which compares the error bit from checker 60 to the corresponding error bit stored in FIFO 58 for each of the packets passed from input circuits 52 to output circuits 56. When predetermined error conditions occur, such as when CRC checker 60 detects an error in a packet that was not detected by CRC checker

30, comparator 66 preferably generates an interrupt to a central processing unit (CPU) 68.

Output circuits 56 also comprise a packet header buffer 64, which is read by the CPU in order to find the source of the erroneous packet. Although comparator 66 is shown in Fig. 2 as a separate element from CPU 68, the function of the comparator may also be carried out by a software process running on the CPU, depending on considerations of design convenience and 10 processing speed needed to carry out this function. Alternatively or additionally, an identification of the error source (internal or external) is held in a status register (not shown), where it can be accessed either by CPU 68 or by a processor external to device 50 or by both.

Fig. 3 is a flow chart that schematically illustrates a method for detecting and diagnosing errors in device 50, in accordance with a preferred embodiment of the present 15 invention. The method is initiated when CRC checker 60 reports to comparator 66 that an error has been detected in a packet in output circuits 56, at an error detection step 70. The comparator then checks the error bit corresponding generated by CRC checker 30, at an error checking step 72. The error bit from checker 30 indicates, at a decision step 74, whether the fault that gave rise to the CRC error occurred in device 50 or along the path of the packet 20 through the fabric (or other network) before it reached device 50. If this error bit indicates that CRC checker 30 also detected an error in this packet, then the comparator determines that the error occurred before the packet reached device 50, at a prior error step 76. On the other hand, when the error bit indicates that CRC checker 30 found no prior error in this packet, the comparator notifies the CPU that a possible fault has occurred in device 50, at an internal error 25 step 78.

When a possible fault is detected in device 50, CPU 68 preferably halts the normal operation of the device while it collects diagnostic information and decides how to proceed. While the operation is halted, the CPU reads the header information of the faulty packet from buffer 54 and/or 64, at a header reading step 80. (Because the error detection and error 30 handling process runs in parallel with normal switching operation of device 50, the header information may have already been flushed from buffer 54 and may be available only in buffer

WO 01/18974

PCT/ILOO/O0539 . On the other hand, if the error is detected by CRC checker 30 before the packet was switched through to output circuits 56, the packet is typically discarded by input circuits 52, so that the header information never reaches buffer 64.) After receiving all of the necessary error φ information, the CPU may once again allow the device to continue operating. At a reporting 5 step 82, the CPU preferably informs a processor or other network management entity, such as an InfiniBand fabric manager, of the details of the detected fault in device 50. Optionally, the fabric manager is also informed when an error prior to device 50 was detected at step 76.

Based on the error report from the CPU, the fabric manager diagnoses the fault and, as appropriate, initiates corrective measures, at a remedial action step 84. The header information 10 reported by the CPU enables the fabric manager to determine the route that the packet took through the network, and hence through device 50, so that the location of the fault can be found. The fabric manager is thus able to distinguish device errors from faults occurring in network links between the devices. The corrective measures typically include shutting down a faulty link or a faulty device and rerouting network traffic around the faulty element. 15 Preferably, the fabric manager generates an alarm or otherwise notifies an operator of the network that the fault has occurred.

While the preferred embodiment described with reference to Figs. 2 and 3 is built around a particular switching device in a packet-switched fabric, the principles of the present invention are equally applicable to other types of data transmission devices and systems. 20 Furthermore, although this embodiment makes use of CRCs, other methods of error checking, as are known in the art, may similarly be used. It will thus be appreciated that the preferred embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and subcombinations of the various features 25 described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art.