Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-07-02
2003-01-07
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C712S224000, C365S049130
Reexamination Certificate
active
06505270
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to content addressable memories (CAMs) and more particularly to a novel CAM architecture that allows for a longest prefix matching function.
BACKGROUND OF THE INVENTION
Information network systems continue to proliferate. Typically network data is 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) (also 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.
An example of longest prefix matching operation will be described below. Two data values (data
0
and data
1
) are set forth. The data values (data
0
and data
1
) are binary values having portions that can be compared to a comparand value (shown as either a 0 or 1). In addition, the data values (data
0
and data
1
) have portions that do not have to be matched. These “non-match” portions are represented by a series of Xs. It is understood that each X could be a 0 or 1, but is represented by an X because the digit should not be compared with a comparand value.
11110000
10XXXXXX
XXXXXXXX
XXXXXXXX
(data 0)
11110000
10010101
100XXXXX
XXXXXXXX
(data 1)
For the example of the data values set forth above, if the following comparand value is applied:
11110000
10010101
10010000
11010001
(comparand).
Both data values can result in a match indication. It is preferred that the data
1
value match indication have priority as it provides the longest prefix match.
One type of device that can be particularly suitable for longest prefix matching is a “ternary” or “tertiary” CAM. In a conventional ternary CAM, a mask bit is provided for each data bit. When the mask bit has a first predetermined value (a logic low, for example) its corresponding data bit will be masked from a compare operation. When a data bit is masked, it will not be compared with an applied comparand value. Ternary CAM entry values are set forth below for the two examples previously described.
11110000
10XXXXXX
XXXXXXXX
XXXXXXXX
(data 0)
11111111
11000000
00000000
00000000
(mask 0)
11110000
10010101
100XXXXX
XXXXXXXX
(data 1)
11111111
11111111
11100000
00000000
(mask 1)
To better understand the present invention, and to more clearly distinguish the described embodiments from conventional CAM approaches, a conventional ternary CAM is cell is set forth in FIG.
16
. The conventional ternary CAM cell is designated by the general reference character
1600
, and is shown to include data register
1602
, a compare circuit
1604
, a mask register
1606
, and a mask circuit
1608
. Data values can be entered into the data register
1602
by placing data values on a bit line pair (B and /B) and activating a data word line DWL. Similarly, mask values can be entered into the mask register
1606
by placing data values on a bit line pair (B and /B) and activating a mask word line MWL. It is understood that the word lines (DWL and MWL) can be commonly coupled to a row of CAM cells and the bit line pair (B and/B) can be commonly coupled to a column of CAM cells.
The compare circuit
1604
can receive the data value stored within the data register
1602
by way of complementary data lines D and /D and a complementary comparand values by way of compare lines C and /C. The compare circuit
1604
compares the data value and comparand value, and in the event the values are different, activates a match indication on match line M. In the particular conventional example of
FIG. 16
, the compare circuit
1604
is an exclusive OR (XOR) or exclusive NOR (XNOR) circuit.
Unlike a conventional binary CAM cell, which would couple comparison results of a compare circuit directly to a match line, in the conventional ternary CAM cell
1600
, comparison results can be masked by the mask circuit
1608
. In the event the mask register
1606
includes an active mask data bit (M), the mask circuit
1608
can prevent a comparison result from affecting the match line “MATCH.”
FIG. 17
illustrates an example of a conventional register that may be used in a CAM (as item
1602
or
1606
in
FIG. 16
, as just one example). The register is designated by the general reference character
1700
. Complementary stored data values stored within register
1700
are provided at data nodes
1702
-
0
and
1702
-
1
. Data values can be set within the register
1700
by driving a bit line pair (B and /B) to complementary data values and activating a corresponding word line WL.
FIG. 18
sets forth a conventional compare circuit
1800
that may be used in a CAM (as item
1604
in
FIG. 16
, as just one example). The compare circuit
1800
can receive complementary data values (D and /D) and complementary comparand values (C and /C). An indication node
1802
can be precharged to a high logic level at the beginning of a compare operation. A data value (D and /D) and com
Ramankutty Jayan
Voelkel Eric H.
Anderson Matthew D
Kim Matthew
Lara Technology, Inc.
Sako Bradley T.
LandOfFree
Content addressable memory having longest prefix matching... 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 longest prefix matching..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory having longest prefix matching... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3047050