Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-10-27
2004-10-12
Padmanabhan, Mano (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S128000, C711S170000, C711S172000, C711S173000, C365S049130
Reexamination Certificate
active
06804744
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to content addressable memories (CAMs) and more particularly to CAMs having configurable options.
BACKGROUND OF THE INVENTION
Information networks, including the Internet, can operate under various networking protocols. Data packets within a network can be processed according to a protocol “stack” having different layers. A data packet will typically include a header with various fields corresponding to various layers of a protocol stack.
Network hardware for processing data packets, such as a router or network switch, can include tables that store data corresponding to various network layers. When a packet arrives to a router and/or network switch, one or more fields in the packet header can be compared to corresponding tables. The packet can then be processed according to the comparison results. Content addressable memories (CAMs), also referred to as “associative memories,” can provide rapid matching functions often needed in routers and network switches.
A complicating factor in packet processing can be the variable length of the various fields in a protocol stack. Such variable length fields can result in routers or network switches having a CAM dedicated to each particular field length. Consequently, when multiple fields are processed, multiple CAM devices are utilized. This can increase the size and/or cost of the resulting network hardware.
A typical CAM can store a number of data values in a CAM cell array. In a compare (i.e., match) operation, the data values can be compared to a comparand value (also referred to as a “search key”). A data value that matches the comparand value can result in a match indication. Match indications can be prioritized by a priority encoder and be utilized to generate associated data. One example of associated data can be “next hop” information in the case of a connectionless network structure.
CAMs can be synchronous and/or asynchronous. A synchronous CAM can perform matching functions on applied comparand values according to a periodic timing signal (such as a system clock, as one example). An asynchronous CAM can perform matching functions on applied comparand value according a non-periodic timing signal (such as an applied comparand value, as just one example).
It is often desirable for synchronous CAMs to operate according to particular timing specifications. As just one example, it is desirable to have a CAM that can receive a comparand value on a certain clock edge, and then provide a compare result a predetermined number of clock cycles later. Such configurations can allow data values to be “pipelined,” which can generate compare results every clock cycle.
CAMs can include “binary” CAMs in which a multi-bit comparand value must match with every bit of a data value to generate a match indication. CAMs can also include “ternary” CAMs in which multi-bit comparand values can be compared with “maskable” data values. A maskable data value can have one or more bits that can be masked from the compare operation. A masked data value bit will not generate a mismatch indication even if the masked data value bit is different than the corresponding comparand value bit.
A conventional CAM will now be described to better understand the various disclosed embodiments of the present invention.
Referring now to
FIG. 9
, a block diagram is set forth illustrating a conventional CAM. The conventional CAM is designated by the general reference character
900
, and is shown to include CAM cell array
902
, a comparand register
904
and a priority encoder
906
. A CAM cell array
902
can include a number of entries, shown as “ENTRY m” through “ENTRY
0
.” Each entry can store a data value that is compared to an applied comparand value. Further, each entry has the same number of bits. In the arrangement of
FIG. 9
, each entry can include “n+1” bits. In many CAMs an entry corresponds to a row of CAM cells.
One way to conceptualize a CAM cell array
902
is to describe it as having a particular width and depth. A width can be the size of the data values stored and a depth can be the total number of data values that can be stored. Accordingly, in the example of
FIG. 9
, the CAM cell array
902
has a depth of m+1 and a width of n+1.
A comparand register
904
can store a comparand value that is to be compared with data values in the CAM cell array
902
. In the arrangement of
FIG. 9
, a comparand will typically have the same width as the CAM cell array
902
.
A CAM cell array
902
can receive a comparand value by way of compare lines
908
. Resulting match results (which may be a “match” or “no match,” for example) can be provided by way of match lines
910
. Typically, one match line can be associated with each entry of the CAM cell array
902
.
The priority encoder
906
can encode match indications into corresponding index values INDEX. Further, if more than one of the match lines
910
indicates a match, a priority encoder
906
can generate one INDEX value according to predetermined criteria (such as entry position, as but one example).
Referring now to
FIG. 10
, a typical ternary CAM array row is illustrated in a schematic diagram. The CAM array row is designated by the general reference character
1000
, and is shown to include “n+1” ternary CAM cells
1002
(m,n) to
1002
(m,
0
). The ternary CAM cells (
1002
(m,n) to
1002
(m,
0
)) of the row are commonly connected to a match line
1004
. Each ternary CAM cell (
1002
(m,n) to
1002
(m,
0
) is further connected to a corresponding comparand line (
1006
-n to
1006
-
0
).
Each ternary CAM cell (
1002
(m,n) to
1002
(m,
0
) includes a data store
1008
, a mask store
1010
, and a maskable compare circuit
1012
. A data store
1008
can store a data value portion (such as a bit). A mask store
1010
can store a mask value portion (such as a bit). A maskable compare circuit
1012
can compare a data value portion to a comparand portion on a compare line. The results of the compare operation can be masked (or not masked) according to a mask value portion.
In one particular arrangement, a match line
1004
can be precharged (or predischarged) to a particular potential, and then be discharged (or charged) when one or more CAM cells (
1002
(m,n) to
1002
(m,
0
) indicates a mismatch (i.e., no match between a comparand portion and stored data value portion).
A ternary CAM can advantageously provide specialized match functions, such as a longest prefix match. A longest prefix match can provide a match indication for a data value having the largest number of leading consecutive bits that match a comparand value. Longest prefix matching can be a valuable function in many types of network hardware.
To provide a match function for multiple layer fields, multiple CAMs, such as that set forth in
FIG. 9
can be used, with one or more CAMs being dedicated to a particular field length.
It would be desirable arrive at some way of providing match functions for multiple fields that includes fewer system components.
SUMMARY OF THE INVENTION
According to the disclosed embodiments, a content addressable memory (CAM) can include a number of CAM cells formed in an array and arranged into two or more sections. Each section can have an independently configurable width.
According to one aspect of the embodiments, a CAM can include a number of entries that each provide an entry match indication that can provide match results between comparand and data values of a first size. Multiple entry match indications can be combined to provide match indications between comparand and data values of a second size that is larger than the first size.
According to another aspect of the embodiments, a CAM can include two or more sections having independently configurable widths and a configuration register. The sections can be configured according to configuration information stored in the configuration register.
According to another aspect of the embodiments, a CAM can include two or more sections, each having at least two sub-sections. Each section can be configu
Lara Technology, Inc.
Padmanabhan Mano
Sako Bradley T.
Song Jasmine
LandOfFree
Content addressable memory having sections with... 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 sections with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory having sections with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3297333