Low power, hash-content addressable memory architecture

#The present invention is directed to memory devices and, more particularly, to content addressable memories (CAMs).

#A CAM includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information, i.e., either logic zero or logic one. The bits stored within a row of memory cells constitute a CAM word. During compare operations, a comparand word is received from an input bus and then compared with all the CAM words. For highest performance, conventional CAM architectures simultaneously compare all of their pattern entries with the input bus. For each CAM word that matches the comparand word, a corresponding match line sipal is asserted to indicate a match condition. When there is a match condition, the index or address of the matching CAM word is read from the CAM. Associative information stored in, for instance, an associated RAM, may also be provided. Because CAMs provide a mechanism that enables matches to be quickly located, CAMs have come to be used in devices, such as routers.

#Routers are used in interconnected computer networks, such as the Internet, to couple networks together. Such a computer network router is typically connected to two or more distinct networks. For a message sent from one network to another destination network, the router receives the message, in the form of data packets, from one of the networks to which the router is connected and searches a database of routing information to determine to which of the connected networks the data packet should next be sent so that the data packet can reach the destination network. The database of routing information can be quite large in networks composed of many different interconnected networks, such as the Internet. Within each router, routing information received from neighboring routers is used to update its own routing table. That table is then used to control how packets are routed from one neighboring router to another on the network. Because CAMs use dedicated parallel hardware for comparisons, they are ideal for use in routers and other high performance systems.

#For the present invention to be easily understood and readily practiced, the present invention will now be described, for purposes of illustration and not limitation, in conjunction with the following figures, wherein:

#FIG. 1 illustrates a circuit architecture implementing the present invention;

#FIG. 2 illustrates one of the hash/SRAM circuits of FIG. 1;

#Referring to FIG. 1, FIG. 1 illustrates a circuit architecture implementing the present invention. The architecture illustrated in FIG. 1 is constructed around a TCAM. An n-bit comparand word is input to an input node 22. For example, if the circuit architecture of FIG. 1 is to be used to process address information in a routing device, the n-bit comparand word input at node 22 may be, for example, a 128-bit word. The comparand word is input, in parallel, to a plurality of hash/SRAM circuits 24(1)-24(n). Each of the hash/SRAM circuits 24(1)-24(n) produces information (as discussed more fully in conjunction with FIG. 2) which is input to bank enable logic 26. The bank enable logic 26 produces enable signals (as discussed more fully in conjunction with FIG. 3) which are input to TCAM 20 to enable, or precharge, portions of the TCAM 20. The TCAM 20 also receives the n-bit comparand word which may be input to the TCAM 20 through a delay circuit 28. The TCAM 20 compares the comparand word input through the delay circuit 28 to the enabled or precharged portions of the TCAM 20. If there is a match, the matched word is output to, for example, an output memory 30, which may be implemented by a RAM. The output memory 30 may be used to store information associated with each of the words stored in the TCAM 20. For example, output port information may be stored in output memory 30 so that an output port may be identified upon a match being found by TCAM 20.

#As seen in FIG. 1, the routing of the n-bit comparand word is such that it is sent in parallel to each of the hash/SRAM circuits 24(1)-24(n), one circuit for each prefix length. However, for an Internet-addressing scheme using 128-bit 113v6 addressing, small prefix lengths up to, for example 16, may be handled in an input memory device 32 which may be implemented by an SRAM. If prefixes 1 through 16 are handled by input memory device 32, then 128 minus 16 equals 112 prefixes to be processed by TCAM 20. Accordingly, one hundred and twelve hash/SRAM circuits 24(1)-24(112) are required. Each hash/SRAM circuit deals with a different prefix length, so the first hash/SRAM circuit 24(1) processes a prefix length of 17 bits, the next hash/SRAM circuit 24(2) processes a prefix length of 18 bits, and so on until the last hash/SRAM circuit 24(112) which processes the full 128 bits.

#The architecture of FIG. 1 includes a switch 34 which is responsive to both the input memory 32 for small prefix lengths and the output memory 30 for port information. If a match (e.g. a non-zero port value) is output from memory 30, then the switch connects ports Y and A so that the output port information is available at an output port 36. Otherwise, port Y is connected to port B, and the port information from memory device 32 is available at output port 36.