Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-03-19
2001-06-26
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06253280
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to content addressable memories (CAMs) and more particularly to a CAM architecture that can provide multiple word matching capabilities.
BACKGROUND OF THE INVENTION
Content addressable memories (sometimes referred to as CAMs or associative memories) typically store a number of data word values. The data word values are compared with an applied input value (a comparand) to determine if the comparand matches any of the data word values. If a match occurs, a match indication is generated. The match indication can be used to index an output data value. Thus, each data word values typically indexes to an output data value.
CAMs can be used in a numerous applications. One particular application is that of data packet header processing. Data packets are typically used to transmit data over data network systems. A data packet will typically include an initial “header” portion and a subsequent data portion. A header will include various fields that include the information necessary for processing a data packet. As just one example, if a data packet is transmitted according to the “Internet Protocol” (IP), its header can include a source address, a source port, a destination address, and a destination port. Data packets within an IP network are transmitted from a source location to a destination location by way of a number of network nodes. A transmission of data from one node to the next is often referred to as a “hop.”
More straightforward IP packet processing applications involve simply “forwarding” a data packet according to a destination address. An IP network node will include hardware that “looks-up” the destination address within a packet to determine a “next hop” value. Such a look-up operation can be performed by a CAM. The CAM will store a number of destination addresses as data word values. Each data word value will index to a next hop value. An incoming destination address will be then be used as a comparand value for the CAM. Thus, if an incoming destination address matches a stored destination address, a next hop value will be output. This next hop value can then be used to forward the data packet to a next hop location.
While a conventional CAM can be appropriate for a straightforward destination address look-up, a conventional CAM is not suitable for more complex network functions. For example, the conventional forwarding operation described above will function properly for a comparand value and match data values of a fixed width (i.e., fixed number of bits). However, some network applications may require looking up values having a variable length. Accordingly, while a conventional CAM may be designed for comparing 64-bit values (words having a 64-bit width), it will not be capable of comparing 128-bit values.
Another more complex network function is that of multiple field matching. For example, certain types of IP data packet processing can essentially reserve a data channel that will be dedicated to a flow of data packets. Such an application can require lookups of more than one field within the packet header. For example, the destination address, source address, and source port may have to be examined to determine a particular flow.
To better understand the limitations of a conventional CAM architecture, a conventional CAM architecture will now be described. Referring now to
FIG. 1
, a conventional CAM is set forth in a block diagram and designated by the general reference character
100
. The conventional CAM
100
is shown to include a number of data word registers
102
-
0
to
102
-n. Data word registers (
102
-
0
to
102
-n) will each store a data word that is to be compared to an applied comparand value. A comparand register
104
stores a comparand value that can be applied to data word registers (
102
-
0
to
102
-n). Each data word register (
102
-
0
to
102
-n) provides a match value (MATCH0-MATCHn). A match value (MATCH0-MATCHn) will be active when its stored data word matches an applied comparand value.
Also included in
FIG. 1
is a “filter” circuit
106
. The filter circuit
106
receives the match values (MATCH0-MATCHn) and generates corresponding encode values (ENC0 to ENCn). A filter circuit
106
can be used to determine a priority in the event there is more than one active match value (MATCH0-MATCHn). Each encode value (ENC0 to ENCn) is applied to a corresponding output data register (
108
-
0
and
108
-n).
In operation, a comparand value that is stored in the comparand register
104
is applied to the data word registers (
102
-
0
to
102
-n). For each data word value in a data word register (
102
-
0
to
102
-n) that matches an applied comparand value, a match value (MATCH0-MATCHn) will be activated. For example, if the value stored in data word register
102
-
1
matches the comparand value stored in comparand register
104
, the MATCH1 value will be activated.
The filter
106
will filter the match values (MATCH0-MATCHn) to generate an active encode value (ENC0-ENCn). For example, the MATCH1 value can result in the ENC1 value being activated. The active ENC1 value will result in the data stored within output data value register
108
-
1
being provided as output data.
Thus, a conventional CAM architecture (such as that set forth in
FIG. 1
) can provide matches between a single, fixed-width comparand value and a number of data words of the same fixed width. However, such a conventional CAM architecture is not capable of providing match functions for words beyond the fixed width, or multiple words.
It would be desirable to provide a CAM that is capable of providing matching functions for multiple word widths. Such a CAM could provide matching capabilities for comparand values beyond a fixed width. Such a CAM could also provide multiple word matching capabilities that may be used in a multiple field matching operation.
SUMMARY OF THE INVENTION
According to the disclosed embodiments, a content addressable memory (CAM) is disclosed that can provide single word match results and multiple word match results.
According to one aspect of the embodiments, a CAM has a single word match mode and a two word match mode. In a single word match mode, comparand values are applied and single word match values generated. In a two word match mode, a first comparand value is applied, and the match results for first word values are stored. A second comparand value is then applied, and the match results for second word values are logically combined with the match results of the stored first word values to generate two word match results.
According to another aspect of the embodiments, a CAM includes a single word match mode and a two word match mode, as described above. In addition, the CAM includes a four word match mode. In a four word match mode, a first comparand value is applied to the CAM, and first match results are stored. A second comparand value is applied and second word match results are also stored. A third comparand value is applied and third word match results are then stored. Finally, a fourth comparand value is applied, and fourth word match results are logically combined with stored first, second and third match values to generate four word match results.
According to another aspect of the disclosed embodiments, a CAM includes a multiple match circuit having a first level circuit block that provides single word match values and a second level circuit block that provides two word match values. The CAM further includes a select circuit that provides either single word match values or two word match values.
According to another aspect of the disclosed embodiments, a CAM includes a multiple match circuit having a first level circuit block and second level circuit block as described above. The multiple match circuit also has a third level circuit block that provides four word match values. The CAM further includes a select circuit that provides either single word match values, two word match values, or four word match values.
REFERENCES:
patent: 4996666 (1991-02-01), Duluk et al.
patent: 5
Lara Technology, Inc.
Moazzami Nasser
Sako Bradley T.
Yoo Do Hyun
LandOfFree
Programmable multiple word width CAM architecture does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Programmable multiple word width CAM architecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable multiple word width CAM architecture will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2487326