Static information storage and retrieval – Systems using particular element – Ternary
Reexamination Certificate
2001-12-21
2004-04-13
Lebentritt, Michael S. (Department: 2824)
Static information storage and retrieval
Systems using particular element
Ternary
C365S049130, C365S185070, C365S189020, C365S189070, C365S226000
Reexamination Certificate
active
06721202
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to semiconductor memory and, more particularly, to a ternary Content Addressable Memory (CAM) cell that uses a shared bit and compare line, and employs no more than sixteen transistors when implemented as an SRAM based memory cell.
2. Description of the Related Art
The following descriptions and examples are not admitted to be prior art by virtue of their inclusion within this section.
CAM is a memory device designed to accelerate any application that requires extremely fast searches of a database, list, pattern, image, or voice recognition stored within a computer or a communication network. Contrary to conventional memory devices, CAMs do not store data in any structured fashion. The locations at which data is stored within a CAM can be random, where the data can be written directly into the first empty location within the CAM. Once data is stored in CAM, it can be found by comparing every bit in the CAM memory with data placed in a comparand register. If a match exists for every bit stored in a particular word line location within the CAM corresponding to every bit in the comparand register, a match line is asserted. Accordingly, a CAM operates opposite that of a conventional memory device by receiving data and returning an address.
One advantage of a CAM is that extremely quick searches can be undertaken, whereby the entire array of CAM cells is searched in a single clock cycle. If a match is found, the address is returned. That address is then used to retrieve data associated with the search string. The address is typically used to retrieve associated data stored in a discrete memory specified by the result of the CAM search.
CAM devices are particularly well suited for handling packet protocols, such as TCP/IP protocols employed in packet processors that are used to route information across an intranet or internet. Attributable to an intranet or internet is a packet-forwarding engine, oftentimes referred to as a switch or router. The switch or router receives the incoming packet and then parses the packet header to assemble the information related to the enclosed data, or payload. Additionally, the forwarding engine must extract relevant fields of bits to determine where and how to send the accompanying payload. The process of extracting source address information and forwarding the payload to a destination address may require multiple lookups.
A packet may contain both a destination network field and a destination host field. Beginning with the network destination field, a lookup will be needed to determine if the forwarding engine resides on a particular destination network. Thereafter, the forwarding engine must determine if, within the destination network, it resides upon a destination host. Internet protocol version 4 (IPv4) specification has established certain classes of segmentation. For example, class C IPv4 addresses have an 8-bit network ID field and a 24-bit host ID field. As the use of the internet has increased, the number of IPv4 addresses has also increased. Segmenting the host and destination fields can oftentimes be inefficient if, for example, a user is barely within an upper class usage, resulting in his/ her inefficient use of the IP addresses allocated to that user. Accordingly, a classless IP addressing scheme, referred to as Classless Inter-Domain Routing (CIDR), has arisen. According to CIDR, a floating boundary exists between the destination network field and the destination host field. The network field indicates the “prefix length” of the CIDR address.
With the advent of CIDR, a need existed for producing a new generation of CAMs. The ternary CAM, or TCAM, is designed to take advantage of the CIDR addressing scheme. In the routing table of a TCAM, entries are ordered such that the CIDR address with the longest prefix (the greatest number of bits in the network field) may be located in the lowest numerical address of the TCAM. The TCAM, therefore, has a main memory cell array and a mask memory cell array, where the main memory cell is used to store, for example, the network destination address. The mask memory cell can store a masking bit. The array of masking cells are, therefore, used to mask certain bits from the lookup operation. For example, the masking bits could be those of the host field, such that faster lookup can occur on only the network field first, followed by unmasked host field lookup second.
While TCAMs prove helpful in speeding up the routing process, especially in CIDR addressing, TCAM cells can be quite large -resulting in large die sizes. While it is desirable to utilize the features of a TCAM, it is also desirable to minimize the size of a TCAM cell and, thus, the size of an array of TCAM cells within a TCAM device. The desired TCAM device should, therefore, be relatively small and not suffer the burden of using extra bit lines and compare lines of conventional cells. The desired TCAM cell of minimal size would not only be more cost effective to make, but also allow for a larger array of cells to accommodate the increasing size of routing tables contained therein. In addition, as the cell size increases, so does the die size, which may lead to issues with viable manufacturability (due to increased manufacturing defects and consequent low yields) especially at higher densities.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by an improved ternary content addressable memory (TCAM) device. A TCAM, in general, contains an array of main memory cells, mask memory cells, and compare circuits. In one feature of the present invention, further saving of area is achieved by encoding of the “value” and “mask” of the main memory cell and mask memory cell (in circuitry external to the memory array) and the resultant bit-encoded values are stored in what is hereinafter known as an “X” memory cell and a “Y” memory cell. A TCAM cell within the array employs a compare circuit interposed between the X memory cell and the Y memory cell.
For each TCAM cell, a single bit line/compare line conductor is used. The bit line/compare line conductor, or common conductor, is connected to the X memory cell, the Y memory cell, and the compare circuit. The common conductor can receive a voltage value to be stored in the X memory cell or the Y memory cell during a write operation, or to be read from the X memory cell or the Y memory cell, and can also receive a voltage value to be compared with the previously stored voltage value within the X and Y memory cells. The common conductor, therefore, can receive data to be written to or read from the X memory cell or the Y memory cell, or data to be compared with previously stored data in the X and Y memory cells.
A write operation can be encoded based on the value of a bit forwarded with a packet. The write operation indicates that a user is intending to change, for example, the routing tables within the TCAM cell. By writing a new voltage value at one or more X and Y memory cells, the user can change the packet-forwarding engine attributable to the TCAM. Thereafter, quick lookup can occur by performing a compare operation of subsequently sent packets with the network identification field or host identification field stored within the memory cell array. If the comparison indicates a match with all corresponding bits within a CAM word, then a match line will yield a logic value that is then presented to a priority encoder. In the case of a multiple match, the priority encoder will select the match line entry that has the lowest numerical address within the memory array (i.e., the address having the longest matching prefix).
The common conductor is therefore used not only during the write and read operations, but also during the compare operation based on the encoding of bits indicative of the operation being employed. Either the bit value being written to the memory cell or being read from the memory cell, or the bit value being compared with previously stored values are multiplexed onto a differential pa
Roge Manoj B.
Srikrishna Ajay
Conley & Rose, P.C.
Cypress Semiconductor Corp.
Daffer Kevin L.
Lebentritt Michael S.
Luu Pho M.
LandOfFree
Bit encoded ternary content addressable memory cell does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bit encoded ternary content addressable memory cell, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bit encoded ternary content addressable memory cell will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3260324