Facilitating error detection for content addressable memory

One embodiment of the disclosures made herein is an apparatus adapted to facilitate error detection for Content Addressable Memory (CAM) modules. The apparatus includes an input error detection module and an output error detection module. The input error detection module includes a parity word generator that generates a key-based parity word after receiving a key. The key-based parity word and the key jointly define a comparand that is provided to the CAM module. The output error detection module includes a protection word generator that generates a key-based protection word after receiving the key and memory. The output error detection module includes a comparator connected to the protection word generator and to the memory. The comparator enables the predetermined protection word to be compared with the key-based protection word for facilitating issuance of an output error indication when the predetermined protection word is different than the key-based protection word.

BACKGROUND OF THE INVENTION

CAM is memory that provides an address on its output bus when read. The address corresponds to the storage location of data provided at its input bus. The data (e.g., a data word) is known as a comparand or a key. Addresses in CAM are searched in parallel and produce the address storing associated data. The associated data is typically stored in separate, discrete memory in a storage location specified by the result of the CAM search. In this manner, CAM search functionality enables extremely quick searches of content.

CAM is used in ATM switches for connection identifier compression, whereby a 28-bit VPI/VCI (virtual path identifier/virtual circuit identifier) connection identifier is translated into an 18-bit connection identifier. This translation is necessary when a linecard in the switch can only support 256K connections (18-bit identifier) as compared to the 256 M connections supported by the 28-bit VPI/VCI connection identifier specified by the ATM standard.

Conventional implementations of CAM are limited in that they do not offer adequate error detection to provide indication of when an error occurs on the input bus, storage array or output bus of the CAM. Accordingly, conventional implementations of CAM are limited in their ability to facilitate data retrieval in a manner that is required by a carrier-class ATM switch. Therefore, method and equipment adapted for providing error detection in conventional implementations of CAM would be useful.

DETAILED DESCRIPTION OF THE INVENTION

The disclosures made herein relate to methods and apparatuses adapted for facilitating data error detection associated with conventional Content Addressable Memory (CAM) modules. Such methods and apparatuses are referred to hereinafter as disclosed CAM error detection methods and disclosed CAM error detection apparatuses, respectively, which provide corresponding disclosed CAM error detection functionality. Conventional CAM modules are defined herein to include off-the-shelf CAM modules that are not specially configured or specifically configured for facilitating error detection of a CAM module storage array, a CAM module input bus and/or a CAM module output bus.

Disclosed CAM error detection methods and disclosed CAM error detection apparatuses provide CAM error detection functionality for the CAM module storage array, the CAM module input bus and the CAM module output bus. Providing error detection on input data and output data of conventional CAM modules is more cost-effective than designing and implementing non-conventional CAM modules, particularly when means for providing such disclosed CAM error detection functionality is less costly than implementing non-conventional CAM modules.

Unlike conventional implementations of CAM error detection functionality, disclosed CAM error detection functionality enables conventional CAM modules to be used for Connection Identifier (CI) compression in a manner that meets requirements of carrier-class ATM switches. Because disclosed CAM error detection functionality enables carrier-class ATM switches to be manufactured with conventional CAM modules, which are cost-effective, switches incorporating disclosed methods and/or disclosed apparatuses are advantageous with respect to cost and performance of conventional switches. Hence, the competitiveness of ATM switches incorporating disclosed CAM error detection functionality is improved.

It will be appreciated that application of disclosed CAM error detection functionality is not limited to ATM switches. A skilled person will find that disclosed CAM error detection functionality is useful in numerous applications where reliable use of CAM storage retrieval of information is desirable and/or necessary.

Turning now to specific drawing figures,FIG. 1depicts a method100adapted for facilitating data error detection for CAM modules in accordance with an embodiment of the disclosures made herein. An operation102is performed for generating a parity word based on a key (i.e., key-based parity word). The key is received from a requesting system entity. The parity word comprises one or more bits. The value of the one or more bits is a function of the key. The parity word may be obtained using known error detection techniques (e.g., cyclical redundancy check, bit interleaved parity generating, etc.) A 28-bit VPI/VCI word is an example of a basis for the key in ATM applications. The key and the key-based parity word jointly define a comparand.

After generating the key-based parity word, an operation104is performed for searching storage of a CAM module for an address containing data corresponding to the comparand after the comparand is provided to the CAM module. If a data error (e.g., a bit error) has occurred anywhere in the comparand, an address containing data corresponding to the comparand will not be found in the storage of the CAM module. In response to a failure in making a comparand match in the storage of the CAM module at an operation105, an operation106is performed for issuing an input error indication. The input error indication means that a data error has occurred somewhere in the comparand, or that the original key was not found in the CAM.

In response to a comparand match being made in the storage of the CAM module at the operation105, an operation108is performed for accessing a predetermined protection word that corresponds to the address containing data corresponding to the comparand. Searching memory including a plurality of predetermined protection words and finding the predetermined protection word is an example of accessing the predetermined protection word. In response to a comparand match being made in the storage of the CAM module or prior to searching the storage of the CAM module for the address containing data corresponding to the comparand, an operation110is performed for generating a protection word based on the key (i.e., key-based protection word).

After generating the key-based protection word and after the predetermined protection word is accessed, an operation112is performed for comparing the predetermined protection word with the key-based protection word. In response to determining that the predetermined protection word is different than the key-based protection word at an operation113, an operation114is performed for facilitating (e.g., issuing) an output error indication. The output error indication means that the address from the CAM has not accessed a matching protection word in the memory and, hence, the address is corrupt. In response to determining that the predetermined protection word matches the key-based protection word at the operation113, an operation116is performed for providing the address to the requesting system entity.

An input error detection process for detecting errors on an input bus on a CAM module comprises generating the key-based parity word, searching storage of the CAM module and issuing the input error indication. An output error detection process for detecting errors on an output bus of a CAM module comprises accessing the predetermined protection word, generating the protection word based on the key (i.e., key-based protection word), comparing the predetermined protection word with the key-based protection word and issuing the output error indication.

FIG. 2depicts an embodiment of an apparatus200capable of carrying out the method100ofFIG. 1. An ATM switch is an example of the apparatus200. Carrying out the method100via the apparatus200enables CAM error detection functionality in accordance with an embodiment of the disclosures made herein.

The apparatus200includes a Connection Manager (CM)202connected to a CAM module204. The CM202includes a parity word generator206, a protection word generator208, memory210and a comparator212. The CAM module204includes a storage array214. The parity word generator206is connected to the storage array214. The protection word generator208and the memory210are connected to inputs of the comparator212. The memory210is connected between the output of the storage array214and one of the inputs of the comparator212.

The parity word generator206is adapted for generating a parity word upon being provided a key216(i.e., a key-based parity word218). The key-based parity word218and the key216jointly define a comparand, which is provided to the storage array214of the CAM module204. The storage array214of the CAM module204is searched in an attempt to access an address220containing data that corresponds to the comparand.

An appropriate portion of the CAM module204(not specifically shown) provides an error notification222to the CM202if a data error (e.g., a bit error) has occurred in the comparand. A data error in the comparand prevents the address220containing data that corresponds to the comparand from being accessed in the storage array214of the CAM module204. The error notification222is provided to the CM202for enabling an input error indication224to be issued. An input error detection module comprises the parity word generator206and means (not specifically shown) of the CM202adapted for issuing the input error indication224.

The protection word generator208generates a protection word from the key216(i.e., a key-based protection word226). A device capable of generating a cyclical redundancy code or a bit interleaved parity word is an example of the protection word generator208. A plurality of predetermined protection words (e.g., 4 bit protection words) is stored in the memory210of the CM202. When the address220containing data that corresponds to the comparand is accessed in the storage array214of the CAM module204, the memory210of the CM202is searched for accessing a predetermined protection word228corresponding to the address220assessed from the storage array214of the CAM module204.

The comparator212compares the key-based protection word226with the predetermined protection word228. When the key-based protection word226is different than predetermined protection word228(i.e., when inputs of the comparator208are not equal), the address220from the CAM module204has not accessed a matching predetermined protection word in the memory210. Hence, the address220is corrupt and the comparator212facilitates issuance of an output error indication230.

An input error detection module capable of detecting errors on an input bus on a CAM module comprises the parity word generator206and means (not shown) of the CM202adapted for issuing the input error indication224. An output error detection module capable of detecting errors on an output bus on a CAM module comprises the protection word generator208, the memory210and the comparator212.

A data processor program in accordance with an embodiment of the disclosures made herein controls at least a portion of the operations associated with facilitating disclosed CAM error detection functionality. Such a data processor program is processible by a data processor of an apparatus in accordance with an embodiment of the disclosures made herein for carrying out operations of a method in accordance with an embodiment of the disclosures made herein. Furthermore, such a data processor program may be resident on one or more data processing modules (e.g. a card including the data processor) or may be accessible by the data processor from an apparatus such as a diskette, a compact disk, a network storage device, a component of the network system or other suitable apparatus. The term data processor program refers to computer software, data processor algorithms or any other type of/sets of instruction code capable of controlling operations associated with a data processor.

A microprocessor, an application specific integrated circuit (ASIC), a field-programmable gate array (FPGA) and other types of programmable logic devices (PLDs) are examples of data processors capable of facilitating disclosed CAM error detection functionality. For example, it is contemplated herein that a FPGA may be used to generate parity and protection words, with appropriate software being used to configure the FPGA appropriately and to report any detected errors.

A data processor program accessible from an apparatus by a data processor is defined herein as a data processor program product. A read-only memory (ROM), a programmable read-only memory (PROM), an erasable programmable read-only memory (EPROM), an electrically erasable programmable read-only memory (EEPROM), an electrically alterable programmable read-only memory (EAPROM), a flash memory, other non-volatile memory (NVM), a compact disk (CD/CDR/CDRW), or a digital video disk (DVD/DVDR/DVDRW) having a data processor program adapted for carrying out disclosed CAM error detection functionality are examples of a data processor program product.

In the preceding detailed description, reference has been made to the accompanying drawings that form a part hereof, and in which are shown by way of illustration specific embodiments in which the invention may be practiced. These embodiments have been described in sufficient detail to enable those skilled in the art to practice the invention, and it is to be understood that other embodiments may be utilized and that logical, mechanical, chemical and electrical changes may be made without departing from the spirit or scope of the invention. To avoid detail not necessary to enable those skilled in the art to practice the invention, the description omits certain information known to those of skill in the art. The preceding detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims.