Masking parity information associated with a ternary content addressable memory

According to some embodiments, a parity check is provided for ternary content addressable memory. For example, it may be arranged for a read request to be transmitted to a ternary content addressable memory unit. Data content may then be received from the memory unit in response to the read request, a parity check may be performed on the data content. According to some embodiments, parity information may be masked when the memory unit is queried.

BACKGROUND

A parity check may be performed to verify information stored in a memory unit (e.g., to ensure that no soft error was introduced due to a failure of a cell in the memory unit). For example, an exclusive OR operation may be performed on data as it is stored into a Random Access Memory (RAM) unit. This parity information may be stored in the RAM unit along with the data. The data and parity information may then be verified when it is retrieved from the RAM unit (e.g., by re-performing the exclusive OR operation on the data and comparing the result to the retrieved parity information).

Because of the technology involved, information stored in a Ternary Content Addressable Memory (TCAM) unit has not traditionally required protection against soft errors. As the sizes of elements used in a TCAM unit are reduced, however, the memory cells may become more susceptible to soft errors.

DETAILED DESCRIPTION

In a typical RAM unit, a write instruction may store a particular set of data in a particular memory address (e.g., 01011011 might be stored into address512). Similarly, a read instruction may retrieve a particular set of data from a particular address (e.g., 01011011 might be retrieved from address512). If the address of a particular set of data needs to be determined, read instructions can be sequentially performed on addresses in the RAM unit (e.g., by reading from address3, address4, address5). The information retrieved from each address can then be compared to the desired set of data until a match is found.

In contrast, a Content Addressable Memory (CAM) unit can be used to directly determine the memory address associated with a particular set of data. In particular, a query instruction includes a “key” representing that set of data. The CAM unit responds to the query by indicating a memory address where that set of data is currently stored. Note that write and read instructions can also be used with a CAM unit (to write data into and to read data from particular addresses).

In a “Ternary” CAM (TCAM) unit, a bit can represent either a zero (“0”), a one (“1”), or a don't care value (“x”). For example, a TCAM may be used to find the first entry that is currently storing 001111xx (and the TCAM may respond by indicating a memory address where any of 00111100, 00111101, 00111110, or 00111111 are stored).

A don't care value might be supported using masks for each entry in the TCAM unit. For example, a TCAM entry might include:

TABLE Ib7b6b5b4b3b2b1b0data:00111100mask:00000011
In this case, a key of 10111100 would not match the entry, because the data's Most Significant Bit (MSB) does not match the key's MSB. A key of 00111101, on the other hand, would match the entry, because the Least Significant Bit (LSB) of the mask (i.e., “1”) indicates that the data's LSB of the data does not need to match the key's LSB. A don't care value could also be supported using a global mask that applies to all entries in the TCAM unit. Moreover, both per-entry and global masks could be supported.

A TCAM unit may be used in a communication device (e.g., a network switch or router). For example, Internet Protocol (IP) addresses may be stored in the TCAM unit. The memory address associated with the a portion of the IP address may then be determined using a query instruction.

TCAM Parity Check System

FIG. 1is a block diagram of a TCAM parity check system100according to some embodiments. The system100includes a TCAM unit110to store entries (e.g., entries that include a data portion and a mask portion). The TCAM unit110may be X bits wide and N entries deep (e.g., 16 bits wide and 1024 entries deep).

A requester120may provide write, read, and/or query requests for the TCAM unit110. For example, the requestor120might be a hardware, software, or firmware device that generates a read request for a particular memory address. The TCAM unit110would then respond to the read request with the data that is stored at that memory address. Although a single requestor120is illustrated inFIG. 1, the system100can include multiple requesters120.

Note that the typical approach to performing parity checks (e.g., creating parity information when data is stored into a RAM unit and checking the parity information when data is retrieved from the RAM unit) may not be practical for a TCAM unit. For example, a soft error in the TCAM unit110might not be detected. Assume that 00001111 is stored in a particular address, and a soft error in the MSB causes the data to become 10001111. If a requestor120generates a query having a key of 00001111, the TCAM unit110will not indicate the memory address in response to the query (and thus no parity check would be performed on the data that actually contains the error). Moreover, implementing hardware to check every cell in the TCM unit110(e.g., once each cycle) introduce a significant amount of area overhead.

According to some embodiments, a parity check engine130generates read requests for the TCAM unit110. For example, the parity check engine130may read data from a particular address in the TCAM unit110and perform a parity check on the data. Moreover, an arbiter unit140may facilitate read requests from the parity check engine130(along with requests from the requester120).

FIG. 2is a method that may be used to store data in the TCAM unit110according to some embodiments. The method may be performed, for example, by the requestor120when it performs a write instruction. The flow charts described herein do not necessarily imply a fixed order to the actions, and embodiments may be performed in any order that is practicable. Note that any of the methods described herein may be performed by firmware, hardware, software, or any combination of these techniques. For example, a storage medium may store thereon instructions that when executed by a machine result in performance according to any of the embodiments described herein.

At202, data content to be stored in the TCAM unit110is determined. For example, the requester120might determine that a particular set of data should be stored into the TCAM unit110.

At204, a parity function is executed on the data content to generate data parity information. For example, a hardware or software device could perform an exclusive OR operation on the data content to generate a single parity bit.

At206, the data content is stored in the TCAM unit110. According to some embodiments, the data parity information is also stored in the TCAM unit110. According to other embodiments, the data parity information is instead stored in a separate memory structure.

Similarly, mask content to be stored in the TCAM unit110may be determined, and a parity function may be executed on the mask content to generate mask parity information. The mask content can then be stored in the TCAM unit110(with or without the mask parity information).

According to some embodiments, it is arranged for the data and mask parity information to be masked during a subsequent query as described below with respect toFIGS. 3 and 4.

TCAM Data Structure that Supports Global Masking

FIG. 3illustrates a data structure300for a TCAM unit110that supports global masking according to some embodiments. Each of the N entries in the TCAM unit110includes a data portion310and a mask portion320.

Each data portion310is divided into a data content field and a data parity field (“DP”). If, for example, the TCAM unit110is sixteen bits wide and the data parity field is a single bit, then the data content field would contain fifteen bits. Similarly, each mask portion320is divided into a mask content field and a mask parity field (“MP”). Note that the data and mask parity fields do not need to be a single bit (e.g., two parity bits may be provided). Moreover, the data and mask parity fields do not need to be located at the LSB (e.g., they could instead be located at the MSB).

According to this embodiment, the bits in the global mask that correspond to the data and mask parity fields can be used to mask the parity information during a query. Consider, for example, an eight-bit wide entry having a single data parity bit and a single mask parity bit. The data portion310might use bit bo as the data parity field and bits b1through b7as the data content field. Similarly, the mask portion320might use bit b0as the mask parity field and bits b1through b7as the mask content field:

TABLE IIb7b6b5b4b3b2b1b0data portion:data contentDPmask portion:mask contentMPglobal mask:1
In this case, the LSB of the global mask may always be set to “1” when a query is performed and, as a result, the parity information stored in the TCAM unit110will be masked. Note that storing the data and mask parity portions in corresponding locations (e.g., b0) may increase the data and mask content that does not need to be masked.
TCAM Data Structure that does not Support Global Masking

FIG. 4illustrates a data structure400for a TCAM unit110that does not support global masking according to other embodiments. As before, Each of the N entries in the TCAM unit110includes a data portion410and a mask portion420.

Each data portion410includes a data content field and a data parity field (“DP”). Similarly, each mask portion420includes a mask content field and a mask parity field (“MP”). According to this embodiment, the mask parity field is located in a position other than the one occupied by the data parity field. Moreover, the position in the data portion410that corresponds to the position of the mask parity field is set to “1” and the position in the mask portion420that corresponds to the position of the data parity filed is set to “1.” If, for example, the TCAM unit110is sixteen bits wide and the data and mask parity fields are each a single bit, then the data content field would contain fourteen bits.

As before the data and mask parity fields do not need to be a single bit nor do they need to be located at any particular position (e.g., they could be separated).

According to this embodiment, the data and mask parity fields may be masked during a query. Consider, for example, an eight bit wide entry having a single data parity bit and a single mask parity bit:

TABLE IIIb7b6b5b4b3b2b1b0data:data contentDP1mask:mask content1MP
When a query is provided to the TCAM unit110, the data parity information is masked because of the “1” located in bit b1of the mask portion420. Moreover, bit b0in the query key can be set to “1” to mask the mask parity information (because that “1” will match bit b0of the data portion410). According to another embodiment, bit b0in the data portion410and the key are both set to zero to mask the mask parity information. In other words, as long as the corresponding locations in the data portion410and the key are the same, the mask parity information can be masked during a query. For example, if the mask parity information is four bits, the locations corresponding to those four bits in the data portion410and the key could both be set to “0101” to mask the mask parity information.
Parity Check Engine

FIG. 5is a method that may be performed, for example, by the parity check engine130according to some embodiments. At502, it is arranged for a read request to be transmitted to the TCAM unit110. For example, the parity check engine130may transmit the read request to the arbiter unit140(which can then forward the request to the TCAM unit110). According to another embodiment, the parity check engine130transmits a read instruction directly to the TCAM unit110(e.g., after receiving permission from the arbiter unit140).

The read request transmitted to the TCAM unit110includes a memory address associated with memory cells that will be checked by the parity check engine130. According to some embodiments, the parity check engine130selects the memory addresses sequentially. For example, the parity check engine130might start with the first memory address and increment the address after the memory cells are checked (and the memory address may wrap back to the first memory address after the memory cells associated with the last memory address are checked). According to another embodiment, parity check engine130instead starts with the last memory address and decrements the address. In yet another embodiment, the memory addresses are not selected sequentially (e.g., they may be selected randomly or pseudo-randomly).

At504, data content is received from the TCAM unit110in response to the read request. The data content may be received, for example, directly from the TCAM unit110or via the arbiter unit140

At506, a parity check is performed on the data content. For example, hardware or software associated with the parity check engine130may execute a parity function (e.g., an exclusive OR operation) on the data content to generate a parity result.

According to some embodiments, the parity check engine130also receives parity information (e.g., data parity information) from the TCAM unit110in response to the read request. According to another embodiment, the parity check engine130retrieves parity information associated with the memory address being checked from a separate data structure. In either case, the parity result generated by the parity check engine130can be compared to the parity information to determine if a soft error has occurred in the memory cells. If an error is detected (e.g., the parity result does not match the parity information), the parity check engine130may, for example, flag the error to a user or an application.

Similarly, the parity check engine130can receive mask content from the TCAM unit110in response to a read request and perform a parity check on the mask content (e.g., based on mask parity retrieved from the TCAM unit110or a separate memory structure).

Arbiter Unit

FIG. 6is a method that may be performed, for example, by the arbiter unit140according to some embodiments. At602, information is received indicating that the parity check engine130wants to transmit a read request to the TCAM unit110. At604, information is received indicating that another requestor120wants to transmit another request to the TCAM unit110. For example, the other requestor120might want to transmit a write request, another read request, or a query request to the TCAM unit110.

At604, the arbiter unit140arranges for the read request associated with the parity check engine130to be received by the TCAM unit110after arbitration between that request and the request from the other requestor. For example, the arbiter unit140might accept a read request from the parity check engine130only when there is no request from the other requestor120(e.g., read requests from the parity check engine130may only be accepted during cycles in which the TCAM unit110is otherwise free). According to another embodiment, the arbiter unit140may accept read requests from the parity check engine130periodically (e.g., every ten cycles—even if there is a request from the other requestor120).

Network Device

FIG. 7is a network device700, such as a network switch or router, according to some embodiments. The network device700may, for example, exchange packets of information via an Ethernet interface710in accordance with the Fast Ethernet Local Area Network (LAN) transmission standard 802.3-2002® published by the Institute of Electrical and Electronics Engineers (IEEE). In other embodiments, the network device700exchanges information in accordance with other communication protocols.

The network device700may include a network processor, such as a INTEL® IXP2400 or IXP2800 network processor. Moreover, the network device700may include any of the embodiments described herein. For example, the network device700may include a TCAM unit, a parity check engine, and an arbiter unit.

Additional Embodiments

The following illustrates various additional embodiments. These do not constitute a definition of all possible embodiments, and those skilled in the art will understand that many other embodiments are possible. Further, although the following embodiments are briefly described for clarity, those skilled in the art will understand how to make any changes, if necessary, to the above description to accommodate these and other embodiments and applications.

For example, although a separate parity check engine130and arbiter unit140were illustrated inFIG. 1, according to other embodiments the arbiter unit140performs the functions described with respect to the parity check engine130(e.g., selecting memory addresses and executing a parity function on data content received from the TCAM unit110). According to another embodiment, no arbiter unit140is needed (e.g., the parity check engine130may decide when a read request will be transmitted to the TCAM unit110).

In addition, although an exclusive OR parity function was described, other types of parity functions, including those that generate multi-bit results, may be used instead.

The several embodiments described herein are solely for the purpose of illustration. Persons skilled in the art will recognize from this description other embodiments may be practiced with modifications and alterations limited only by the claims.