Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2002-03-28
2004-06-01
Moazzami, Nasser (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06745280
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to the field of memory devices and, more particularly, to content addressable memory (CAM) devices and methods of operating same.
In many memory devices, including random access memory (RAM) devices, data is typically accessed by supplying an address to an array of memory cells and then reading data from the memory cells that reside at the supplied address. In content addressable memory (CAM) devices, however, data within a CAM array is not accessed by initially supplying an address, but rather by initially applying data to the array and then performing a compare operation to identify one or more locations within the array that contain data equivalent to the applied data and thereby represent a “match” condition. In this manner, data may be accessed according to its content in addition to being accessible by its address. Upon completion of the compare operation, the identified location(s) containing equivalent data is typically encoded to provide an address at which the equivalent data is located. If multiple locations are identified in response to the compare operation, then priority encoding operations may be performed to identify a best or highest priority match. Such priority encoding operations frequently use the physical locations of multiple matches within the CAM array to identify a highest priority match. Exemplary CAM cells and CAM memory devices are more fully described in U.S. Pat. Nos. 5,706,224, 5,852,569 and 5,964,857 to Srinivasan et al. and U.S. Pat. Nos. 6,101,116, 6,256,216 and 6,128,207 to Lien et al., assigned to the present assignee, the disclosures of which are hereby incorporated herein by reference.
CAM cells are frequently configured as binary CAM cells that store only data bits (as “1” or “0” logic values) or as ternary CAM cells that store data bits and mask bits. As will be understood by those skilled in the art, when a mask bit within a ternary CAM cell is inactive (e.g., set to a logic 1 value), the ternary CAM cell may operate as a conventional binary CAM cell storing an “unmasked” data bit. When the mask bit is active (e.g., set to a logic 0 value), the ternary CAM cell is treated as storing a “don't care” (X) value, which means that all compare operations performed on the actively masked ternary CAM cell will result in a cell match condition regardless of the value of the applied data bit versus the stored data bit. Thus, if a logic 0 data bit is applied to a ternary CAM cell storing an active mask bit and a logic 1 data bit, the compare operation will indicate a cell match condition. A cell match condition will also be indicated if a logic 1 data bit is applied to a ternary CAM cell storing an active mask bit and a logic 0 data bit. Accordingly, if a data word of length N, where N is an integer, is applied to a ternary CAM array having a plurality of entries therein of width N, then a compare operation will yield one or more entry match conditions whenever all the unmasked data bits of a word stored in the ternary CAM array are identical to the corresponding data bits of the applied word. This means that if the applied data word equals {1011}, the following stored words will result in an entry match condition in a CAM comprising ternary CAM cells (i.e., a ternary CAM): {1011}, {X011}, {1X11}, {10X1}, {101X}, {XX11}, {1XX1}, . . . , {1XXX}, {XXXX}.
Applications using CAMs include database management, disk caching, pattern and image recognition and artificial intelligence. CAMs are also well suited for use in routing network traffic, such as in network address lookup or packet switching. For example,
FIG. 1
illustrates a simplified view of a network switch
100
. The network switch
100
may communicate with a network through a plurality of network ports, shown as ports zero through seven. The switch
100
may receive network traffic on one port and determine to which of its other ports that traffic should be routed. As will be understood by those skilled in the art, the network traffic may include a packet stream of data containing a leading destination address. The network switch
100
may select a leading portion of the packet stream and provide it to a ternary CAM
102
. The CAM
102
may contain entries that include predetermined routing information, with the CAM address of each of these entries designating a port of the network switch
100
. When the portion of the packet stream is applied as data to the CAM
102
during a compare operation, the CAM
102
may return a CAM address. This CAM address may correspond to the location of an entry within the CAM
102
that matches the applied portion of the packet stream. This returned CAM address may then be used by the network switch
100
as a pointer to acquire routing information from a second memory device to direct the packet stream to a desired port that will enable the packet stream to reach its destination address.
Referring now to
FIG. 2
, a conventional network routing application may also use a switch controller
200
that receives network packets from an external source and routes the network packets through a switch
206
. The switch controller
200
may provide a portion of a destination address within a packet to an accompanying CAM
202
. In response, the CAM
202
may perform a compare operation and generate an address of a matching entry. This generated address may be used as a pointer to acquire network address translation information or other routing information contained within a RAM
204
. The information provided by the RAM is then conveyed to the controller
200
for use in routing the packet through the switch
206
. In this manner, a CAM
202
may be used to provide a mechanism for locating address translation and routing information for network packet addresses.
In the event multiple matches (i.e., multiple matching entries) are detected during a compare operation, conventional physical priority encoding techniques may be used to identify a best or highest priority match (i.e., a highest priority matching entry) that should be used to perform the routing of the packet stream in a preferred manner. This highest priority match is frequently referred to as a longest prefix match (LPM), where the prefix may be defined as a first portion of a network packet address. A conventional technique for identifying an LPM will now be described with reference to the entries illustrated within the CAM
102
of FIG.
1
. If the destination address within the packet stream is a bit sequence equal to {01100010}, then a compare operation within the CAM
102
of
FIG. 1
will result in three matches. These three matches correspond to the entries at address
0
, designating port
0
, address
3
, designating port
3
, and address
6
, designating port
6
. As illustrated by the entries within the CAM
102
, the match corresponding to the entry at address
0
may be treated as the highest priority match because it is the entry with the largest number of unmasked data bits that are equivalent to the applied destination address. The detection of this highest priority match can be relatively simple if the entries within the CAM
102
are presorted according to priority or are arranged within sectors, with each sector containing entries having the same number of unmasked bits and being physically arranged according to priority. As described herein, sectors within a CAM may have the same or different number of entries therein.
As illustrated by
FIG. 1
, entries having no masked bits may be stored in a first sector (illustrated as spanning addresses
0
-
2
within the CAM
102
) and entries having only one masked bit may be stored in a second sector (illustrated as spanning only address
3
within the CAM
102
). Entries having a greater number of masked bits are also stored in respective lower priority sectors within the CAM
102
. By intentionally arranging all entries having the same number of masked bits wit
Darnell Brian Scott
Fowler John
Integrated Device Technology Inc.
Moazzami Nasser
Myers Bigel & Sibley & Sajovec
LandOfFree
Content addressable memories having entries stored therein... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Content addressable memories having entries stored therein..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memories having entries stored therein... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3363706