Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-12-17
2002-12-31
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06502163
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to content addressable memories (CAMs) and more particularly to approaches for ordering entries in a ternary CAM.
BACKGROUND OF THE INVENTION
Information network systems continue to proliferate. In a typical network system, data can transferred in data structures referred to as “packets.” A packet can travel through network according to information included in a portion of the packet referred to as a “header.” Network switches and/or routers can receive packets, extract information from the packet header, and process the packet according to the extracted information. Network header information can establish, to name just a few possible examples, the destination of a packet and/or the manner in which a packet should be transmitted.
Packet routing and/or switching typically utilizes a matching function. In a matching function, a header field will be compared to a number of entries. In the event the field (or a portion of the field) matches an entry, a match indication will be generated. The match indication can be used to generate particular processing information for the packet.
Routing and switching functions can be performed by general-purpose processors that run a routing algorithm. Such an approach can result in limited throughput of data packets, be expensive in terms of component cost, and require considerable area to implement when implemented as one or more integrated circuits.
One way to address the need for faster routers is to fabricate an integrated circuit that is specialized to perform routing/switching tasks. Such application specific integrated circuits (ASICs) are designed to perform particular routing functions such as a matching function in conjunction with a random access memory (RAM). Unfortunately, because ASICs are custom manufactured products, they can also be expensive to manufacture.
One type of device that is particularly suitable for matching functions is a content addressable memory (CAM) (sometimes referred to as an “associative memory”). A CAM can include a number of data storage locations, each of which can be accessed by a corresponding address. The order in which the data values are stored varies according to the type of CAM. As just one example, in a typical “binary” CAM, data can be stored in the first available “empty” location. Empty locations can be distinguished from “full” (or valid) locations by a status bit associated with each storage location.
Valid locations in a binary CAM can be addressed according to the contents (data values) that they store. In a typical binary CAM matching function, a comparand value (which can be a header field or a portion thereof) can be loaded into a comparand register. The comparand value can then be compared to the data values within each valid location of the conventional binary CAM. In the event the value within the comparand register matches a value of a storage location, a match signal for the matching storage location will be generated. In the event there is more than one match, one match from the multiple matches may be selected according to predetermined priority criteria. The match indication can then be used to access other information (such as routing or packet processing information, as just two examples).
By providing for the simultaneous comparison of a comparand word value (a row of comparand bit values) with a number of data words, a rapid match function can be accomplished with a binary CAM. One drawback to conventional binary CAMs is that matching functions are typically performed on data values having a fixed number of bits. Unfortunately, many routing and switching functions can require matching a comparand value to data values having variable bit lengths. This type of matching function is often referred to as “longest prefix matching.”
An example of a longest prefix matching operation will now be described. Referring now to
FIG. 10
, an example of five CAM entries are illustrated. The five CAM entries occupy CAM addresses
0
FF
0
to
0
FF
4
. Each entry stores a binary data value having a non-masked portion that can be compared to an applied comparand value. Such non-masked portions are shown as zeros and ones in FIG.
10
. In addition, each data value includes a masked portion that is not compared to an applied comparand value. The masked portions are represented by a series of Xs in FIG.
10
. It is understood that each X could be a 0 or 1, but is represented by an X because the digit is “masked” according to a mask value.
Data values can be masked by providing corresponding mask data. In one particular arrangement, a mask bit can be provided for each data bit. Thus, the mask data for the first twenty bits (going from left to right) of the data value at
0
FF
0
can have mask bits of one value (1, for example), while the remaining twelve bits can have mask bits of another value (0, for example). A conventional ternary CAM can include memory cells that store a mask bit alongside a data bit.
FIG. 10
also illustrates a comparand value CMP. As shown in the figure, the non-masked portions of entries
0
FF
0
and
0
FF
2
match corresponding portions of the comparand value. Thus, when the comparand value is applied, entries
0
FF
0
and
0
FF
2
can generate match indications.
In a longest prefix matching operation, match indications are prioritized to select the entry having the longest non-masked portion. Thus, in the example of
FIG. 10
, entry
0
FF
0
provides the longest prefix match. Conventionally, priority between variable prefix data values can be established according to the order of entries within the CAM. Thus, data values are stored in the order of prefix length. The values with the most unmasked bits can be stored as entries at the lowest addresses. An entry having a lower address will have a higher priority.
Priority between multiple match indications is typically accomplished with a priority encoder circuit. The single match indication having the highest priority may then be applied to a memory to generate an index value. In one particular conventional approach, a prioritized match indication can be applied to a read only memory to generate an associated index value. The index value may then be used to access a random access memory which can store the rest of the associated data.
The ternary CAM approach described above can provide rapid matching operations, and so can be very useful when utilized in packet processing devices.
An important issue in CAM applications, particularly for CAMs used in packet processing devices, arises when a new data value must be added to a ternary CAM. Such operations are often referred to as “table updates.” In a conventional table update, new data must be stored in a location according to its prefix length.
An example of a table update is set forth in
FIGS. 11A
to
11
C.
FIGS. 11A
to
11
C show the same ternary CAM at different stages in a table update operation.
FIG. 11A
shows the CAM prior to a table update operation. The CAM is designated by the general reference character
1100
and can include consecutive entry groups
1102
-
1
to
1102
-
5
. Each consecutive group (
1102
-
1
to
1102
-
5
) stores data values of the same prefix length. Overall, the data values are arranged in an order within the CAM
1100
, with the longest prefix being at the top of the CAM
1100
and the shortest prefix being toward the bottom. Masked portions of the data values are shown by diagonal hashing lines.
In the example of
FIGS. 11A
to
11
C, a new data value is added that has the same prefix length as the data values of consecutive group
1102
-
2
. Because prefix length order must be maintained, a location must be made available so that the new data value can be added as another entry to consecutive group
1102
-
2
. This is shown in FIG.
11
B.
In
FIG. 11B
, a location is made available by shifting data values having shorter prefixes down by one location. Consequently, the former first entry of consecutive group
1102
-
3
is turned into an available location to store
1104
.
The new
Kim Matthew
Lara Technology, Inc.
Sako Bradley T.
Tran Denise
LandOfFree
Method and apparatus for ordering entries in a ternary... 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 and apparatus for ordering entries in a ternary..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for ordering entries in a ternary... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2982289