Searching memory for a search key

#Ternary content addressable memory (TCAM) devices are often used to support packet forwarding and classification operations in network switches and routers. A TCAM device can be instructed to compare a search value, typically formed from one or more fields within the header of an incoming packet, with entries within an associative storage array of the TCAM device. If the search value matches an entry, the TCAM device generates an index that corresponds to the location of the matching entry within a storage array, and asserts a match flag to signal the march. The storage array addressed by the index may be either within or separate from the TCAM device. The entry retrieved from the storage array includes, for example, routing or classification information for the packet.

#A TCAM is typically organized as an array with multiple TCAM rows, where each row comprises multiple TCAM cells. When a search value is searched for in the TCAM it is simultaneously compared against all the values stored in the different rows. When all the TCAM cells in a row matches the search value, a row match signal for the row is generated. All match signals are connected to a match logic block. The match logic block generates a match address that corresponds to the match signal of the row.

#A TCAM cell is typically implemented using two SRAM cells and comparison logic. The first SRAM cell contains a data bit and the second SRAM cell contains a mask bit. Each SRAM cell requires 6 transistors. The comparison logic requires 4 transistors. All together a TCAM cell requires 16 transistors to store one bit of data, which results in large die area per storage bit.

#FIG. 1 is a simplified block diagram of a hash content addressable memory (HCAM) system used by multiple clients in accordance with an implementation.

#FIG. 2 is a simplified block diagram showing that the HCAM system of FIG. 1 has multiple HCAM blocks in accordance with an implementation.

#FIG. 3 is a simplified block diagram of a hash content addressable memory (HCAM) block in accordance with an implementation.

#FIG. 1 illustrates a hash content addressable memory (HCAM) device 600 used by multiple clients. In FIG. 1, multiple clients are illustrated by a client 51, a client 52 and a client 53. While FIG. 1 shows three clients, the number of clients will vary dependent upon design criteria, performance criteria and so on.

#Each client interacts with HCAM device 600 through a key bus, an operation (op) bus and a priority (prio) bus dedicated to that client. As shown in FIG. 1, client 51 uses a key bus 5301, an op bus 5101 and a prio bus 5291. Client 52 uses a key bus 5302, an op bus 5102 and a prio bus 5292. Client 53 uses a key bus 5303, an op bus 5103 and a prio bus 5293.

#On its dedicated op bus, each client places operations (instructions) for HCAM device 600. For example, an operation could be to search a specified table, or write to a specified table. On its dedicated key bus, the client places data associated to the operation. For example, if the operation is a write operation, the address and data for the write operation is placed on the key bus. If the operation is search a specified table, the search key to search for in the specified table is placed on the key bus. On the priority bus dedicated to the client, the responding HCAM device 600 places response information for the client.