Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-11-08
2002-10-15
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S128000, C711S206000, C365S049130, C365S168000, C365S189070
Reexamination Certificate
active
06467019
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to content addressable memories (CAMs), and more particularly to methods for updating search tables in CAMs.
BACKGROUND OF THE INVENTION
One type of device that has found wide application in the field of networking is the content addressable memory (CAM). Many networking applications can require a match function. To perform a typical match function, a CAM can include a number of entries that store data values. The data values stored in a CAM may be conceptualized as a “table.” Each data value can include match criteria that can be considered a “rule.”
An input value (a query or comparand) can be applied to the CAM and essentially simultaneously with the table of rules. If a rule matches the query a match indication can be generated. Typically, a CAM can include a priority encoder to select from among multiple match indications. Conventionally, a priority encoder establishes priority according to the data value position within a CAM. Data value position is typically a CAM address.
In the field of networking, CAMs can be used to process network packets. Network packets can include a header with a number of data fields. Selected data fields can be extracted from a header and applied to a CAM. The CAM can compare an extracted data field with its table data values essentially simultaneously. If a header field matches a data value within the CAM, a match indication can be generated. A CAM match indication can generate associated data that can be used to process a packet.
As but a few of the many applications, a CAM can be used to in route forwarding. According to match indications provided by the CAM, a packet can be transmitted from one network node to the next. A CAM may also be used in packet filtering. Match indications (or lack thereof) can be used to prevent a packet from being allowed into, or transmitted from, a network. Still further, a CAM can be utilized to establish flow classification. Match indications can be used to direct packets along particular predetermined data flow routes.
By providing rapid, parallel matching of data values to an applied input value (a comparand), a CAM can provide a rapid matching function.
CAMs can include binary CAMs and ternary CAMs. A conventional binary CAM can compare data values of fixed size to comparand values of the same size. While useful for straightforward match functions, conventional binary CAMs cannot provide more complex match functions. In particular, it is often desirable to provide a match function between a comparand value and portions of a data values within a table. These and other more complex matching functions can be accomplished with a ternary (or “tertiary”) CAM.
A ternary CAM can store data values that can be “masked.” In a conventional ternary CAM, data values can be masked on a bit-by-bit basis. Thus, a valid ternary CAM entry can include masked and unmasked bits. Conventionally, an unmasked bit can be a “1” or “0” that is compared to the 1 or 0 of a comparand bit to generate a bit match or no match. A masked bit, often identified as “X,” will provide a bit match regardless of its corresponding comparand bit value.
By masking a trailing portion of a data value, a conventional ternary CAM can provide a longest prefix match function. By masking various non-contiguous portions of a data value, a ternary CAM can provide a masked prefix match function. Longest and masked prefix matching can be important operations in a network hardware device.
A conventional ternary CAM, as noted above, can include a priority encoder that establishes priority according to position within a CAM.
While CAM priority encoders can allow for rapid match functions, such arrangements can have drawbacks. If data values stored in a CAM table remained static, matching functions could be undertaken without interruption and at high speed. Unfortunately, in most networking applications CAM data values can be continuously updated. As just a few examples, the data values in a route forwarding CAM may frequently change due to shortest path calculations of a routing protocol. Further, routers and/or switches in a network may be added or deleted, requiring a table update operation. Conventionally, if a new data value is added to a CAM, the new value must be placed within the CAM between those entries having a higher priority and those entries having a lower priority.
An example of a conventional CAM match and update operation will now be described. Referring now to
FIGS. 14A
to
14
B, a portion of a CAM table is set forth in a sequence of diagrams.
FIG. 14A
illustrates a CAM table prior to an update operation. The CAM table includes four locations,
0
to
3
, that store data values A to D. In the arrangement of
FIG. 14A
it is assumed that priority is established according to lowest location. Thus, if an applied comparand value indicates a match with data value A and data value D, the match with data value A will have priority.
FIGS. 14B and 14C
shown an update operation to the CAM table. The update operation includes the addition of a data value “Y” having a priority that is less than data values A and B, but greater than data values C and D. As shown by
FIG. 14B
, in order to ensure data value Y will have the desired priority, data values C and D must be moved to locations of lower priority. Thus, data values C and D are moved to locations
3
and
4
, respectively. As shown by
FIG. 14C
, by moving data values of lesser priority, the new data value Y can be written into location
2
.
CAM densities continue to increase. Currently, CAMs can include as many as 512 k entries. As densities increase CAMs may include millions of entries. Thus, conventional approaches to updating such large tables can be impractical. First, update operations for very large tables can consume processing resources. For example, if a CAM is utilized in conjunction with a central processing unit (CPU), the numerous copying operations required for some update operations can tie up the system CPU slowing down input/output operations in the system. Such slowdowns can be exacerbated because CAM data cannot typically be cached.
Conventional CAM update operations can also impact network device performance. For example, a router and/or network switch that includes a CAM can receive packets on a continuous basis. However, within a conventional CAM, the data and/or control paths that are used to perform a match function are not separate from those used to perform an update operation. Consequently, update operations of a CAM can prevent match functions from taking place, slowing down a network device's performance.
Nonconventional CAMs can include an intrinsic “block move.” A block move can allow a CAM to move data values without taxing CPU resources. Unfortunately, including block move capabilities in a CAM can add to the complexity and/or cost of a CAM. Further, while a block move can free CPU resources, update operations may still interfere with match functions.
It would be desirable to provide some way of managing data values within CAM that does not include the drawbacks of conventional arrangements. Such a method could preferably be used in conjunction with conventional ternary CAMs.
SUMMARY OF THE INVENTION
According to one embodiment, a CAM can receive input values as queries. Various entries within the CAM can be conceptualized as including a matching rule and a priority. A method for updating entries in a CAM can include determining if a new entry overlaps any existing rules in the CAM. Rules can overlap if a query exists that can results in a match to both rules. In the event there is no overlap between a new rule and existing rules, the new CAM entry can be written into a free location within the CAM.
According to one aspect of the embodiments, existing rules that overlap can be arranged into a graph group within the CAM. A graph group can indicate a particular order for the rules within the CAM according to priority. If a new rule overlaps an existing rule within a graph group, a preceding and succeeding rul
Juniper Networks, Inc.
Song Jasmine
Yoo Do Hyun
LandOfFree
Method for memory management in ternary content addressable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for memory management in ternary content addressable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for memory management in ternary content addressable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2996015