Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-11-16
2003-11-11
Sparks, Donald (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S128000, C711S158000, C365S049130, C365S189070
Reexamination Certificate
active
06647457
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to content addressable memories (CAMs) and more particularly to CAMs having indicators for showing when an entry is occupied or unoccupied.
BACKGROUND OF THE INVENTION
Due to the increasing importance of data networks, including the Internet, the prevalence of content addressable memories (CAMs) has continued to proliferate. CAMs, also referred to as “associative memories,” can provide rapid matching functions that are often needed in certain packet processing hardware devices, such as routers and network switches, to name just two. In a typical packet processing operation, a device can receive a packet. The packet can include a “header” that includes various data fields that indicate how the packet should be processed. The device can use a matching function, provided by a CAM, to compare one or more header fields to “look-up” tables stored in the CAMs.
As just one example, a router can use a matching function to match the destination of an incoming packet with a “forwarding” table. The forwarding table can provide “nexthop” information that can allow the incoming packet to be transmitted to its final destination, or to another node on the way to its final destination.
The look-up tables in packet processing devices (which are typically stored in a CAM) are rarely static. That is, the entries with such a table may be constantly updated with different information. This may be particularly true in routers, which can update forwarding tables thousands of times a second.
A typical CAM can store the data values of a look-up table in one or more CAM cell arrays. The CAM cell arrays can be configured into a number of entries, each of which can provide a match indication. In a compare (i.e., match) operation, the data values stored within the entries can be compared to a comparand value (also referred to as a “search key”). In a typical packet processing device, the comparand value can include a field extracted from a data packet header. If a data value matches an applied comparand value, the corresponding entry can generate an active match indication. If a data value does not match an applied comparand value, the corresponding entry can generate an inactive match indication (signifying a “mismatch”) condition.
Because the data values within a CAM may be continuously updated, some conventional CAMs can include a “status” bit (sometimes referred to as a “valid/invalid” or “occupied/unoccupied” bit). A status bit can be stored in one or more CAM cells in an entry. A status bit can have a “valid” logic state that can indicate an entry that stores usable data. A status bit can also have an “invalid” logic state that can indicate that the data stored within contains data that should no longer be used in a compare operation.
The use of a valid/invalid bit may be best understood by an example. Referring now to
FIG. 8
, an example of a CAM having entries with status bits is set forth in a table form. The CAM is designated by the general reference character
800
, and is shown to include eight entries, labeled
0
to
7
. Each entry can include 68 bits, labeled “C” to
67
. Bit
0
(the “C” bit) can be a status bit. Also shown in
FIG. 8
is a 68-bit comparand value. Each entry can generate a match indication in response to the application of a comparand value.
For many CAM applications it can be desirable to have entries arranged with a predetermined priority. In the event two or more match indications are activated in response to an applied comparand value, one of the match indications can be selected according to the location of its corresponding entry. As just one example, in the particular arrangement of
FIG. 8
, lower numbered entries can have priority over higher numbered entries. Thus, if the application of a comparand value resulted in entries
1
and
4
both activating a match indication, the match indication of entry
1
would have priority over that of entry
4
.
In the particular example of
FIG. 8
, bit
0
is a status bit. When the status bit is “1”, the entry is “valid” (or occupied), and thus stores data that can be compared with a comparand value. When the status bit is “0”, the entry is “invalid” (or unoccupied), and thus stores data that should not be compared with a comparand value. To prevent an invalid entry from generating a possibly erroneous active match indication, the bit
0
of all applied comparands is set to “1.” In this way, all invalid entries can be forced to generate a mismatch indication in response to a comparand value.
Thus, in the particular arrangement of
FIG. 8
, entries
2
,
3
and
6
will generate a mismatch indication regardless of what other data values are stored within the entries.
In a table update operation, various operations can occur within a CAM. Existing “valid” data values may be placed into an invalid state by writing into at least the status bit and changing it from a valid to an invalid state. In addition, new data values may be written into available entries. Available entries can be those entries with “invalid” status bits.
In many applications, it can be desirable to write new data values into the “next free” entry. A next free entry can be the lowest number entry that is invalid. In the particular arrangement of
FIG. 8
, entry
2
can be considered the next free entry.
One way to write data into a “next free” entry is to employ duplicate storage registers to maintain a record of which entries are valid (such as a “shadow register”). A lowest entry number can then be determined from these values. The next free location can then be used as a write address for a subsequent data value write.
Approaches that utilize duplicate storage registers can have a number of drawbacks. Testing may become more complicated as data stored in the entry and the data in duplicate registers must both be tested to ensure that they both store the same data.
Approaches with “shadow registers” can also result in defective operation if either the entries or the duplicate registers contain a defect. Still further, such approaches can consume additional area on an integrated circuit, in addition to the area consumed by the registers themselves. Still further, additional circuitry can be included to write data into and read data out of the duplicate registers as well as ancillary support circuitry. Still further, other circuitry may be included to select the next free location from the shadow register information.
It would be desirable to arrive at some way of identifying a next free location in a CAM that is less complicated and/or consumes less circuit area than other conventional approaches.
SUMMARY OF THE INVENTION
According to disclosed embodiments, a content addressable memory (CAM) includes a number of entries that can store data values. In response to an applied comparand value, each entry can generate a match indication. The match indications can be received by a priority encoder that can select and output the address of one active match indication from multiple active match indications. Each entry can also include associated status data. Status data can indicate whether the data stored within an entry is valid or not. The priority encoder can further receive status data, and select a next free address location from the status data.
According to one aspect of the embodiments, a CAM can include a number of entries that each provide a match indication and include a CAM cell that stores status data. Match indications and status data from the CAM cells can be applied to the same priority encoder.
According to another aspect of the embodiments, a CAM can include a switch circuit that couples either match indications or status data to a priority encoder. In response to match indication, the priority encoder can generate a highest priority match indication which is output as an address. In response to status data, the priority encoder can generate a next free address. According to another aspect, a switch circuit can include multiplexer circuits.
According to another aspect of the embodiments, a CA
Sywyk Stefan P.
Voelkel Eric H.
Cypress Semiconductor Corporation
Sako Bradley T.
Song Jasmine
Sparks Donald
LandOfFree
Content addressable memory having prioritization of... 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 memory having prioritization of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory having prioritization of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3126269