Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
1998-11-05
2001-07-24
Tran, Andrew Q. (Department: 2824)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S189020, C365S189070, C365S190000
Reexamination Certificate
active
06266262
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to content addressable memories (CAMs) and more particularly to a novel CAM structure that allows for matching of variable length input data values.
BACKGROUND OF THE INVENTION
Computer networks continue to proliferate. As a result, data traffic among networks continues to increase, placing ever-increasing demands on the ability of network structures to transfer data between networks. Network data is usually transferred in data units referred to as “packets” (or datagrams) that are transmitted from a source machine and eventually received by a destination machine. While network data transfers may appear transparent to both the source machine and the destination machine, in actuality, the data packets are usually transferred between intermediate stages (referred to as “hops”) by machines referred to as “routers.” A router will receive a packet, examine destination information within the packet, and from this destination information, “forward” the packet to a “next” hop destination. In this manner, data is forwarded by one or more hops, and eventually arrives at the desired destination. The function of examining a destination address and determining next hop information is often referred to as “address matching.”
Routing functions rely on an underlying standardization in the data packet format and transmission method (protocols). One of the most prevalent protocols is the internet protocol (IP). IP serves to route a given packet from a source to a destination. To accomplish this function an IP data packet will include an initial portion (header) that includes, among other information fields, a source address and a destination address. As noted above, it is the destination address that is utilized by a routing machine to transfer a data packet to its next hop or final destination. To accomplish the routing function, a router will typically include a “look-up” table that includes next hop information corresponding to particular destination addresses. The router examines the destination address of an incoming packet, looks up the next hop information, and uses the next hop information to forward the packet onward toward its destination.
Routing 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.
One way to address the need for faster routers is to fabricate an integrated circuit that is specialized to perform routing tasks. Such application specific integrated circuits (ASICs) are designed to perform particular routing functions such as address matching. Unfortunately, because ASICs are custom manufactured products, they can also be expensive to manufacture.
One type of device that is particularly suitable for router address matching functions, is a content addressable memory (CAM), also referred to as an “associative memory.” A CAM includes 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 are distinguished from “full” (or valid) locations by a status bit associated with each storage location.
Valid locations can then be addressed according to the contents (data values) that they store. A data value is loaded into a comparand register. The value within the comparand register can then be compared to the data values within each valid location. In the event the value within the comparand register matches the 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 will be selected according to predetermined priority criteria. The address corresponding to the match location can then be made available.
Referring now to
FIG. 1
, a prior art “binary” CAM cell is set forth in block schematic diagram and designated by the general reference character
100
. The CAM cell
100
is shown to include a storage register
102
that stores a data value. The register
102
can be accessed (for a read or write operation) by activating a word line WL. In a write operation, data would be placed on a pair of complementary bit lines (B and /B) to force a logic value into the register
102
. In a read operation, the register
102
would place a data value on the bit lines (B and /B). It is understood that the word line WL is common to a number of other CAM cells within the same row, and the bit line pair (BL and /BL) is common to a number of other CAM cells within the same column.
As shown in
FIG. 1
, the CAM cell
100
also includes a compare circuit
104
that receives the data values stored within the register
102
by way of data lines D and /D. In addition, the compare circuit
104
also receives complementary comparand values, by way of compare lines C and /C. The compare circuit
104
compares the data line values and comparand values, and in the event the values are the same, activates a match indication on match line M. In the particular prior art example of
FIG. 1
, the compare circuit
104
is an exclusive OR (XOR) circuit.
Referring now to
FIG. 2
, a prior art register that may be used as the register
102
, is set forth in a block schematic diagram. The register is designated by the general reference character
200
and includes a pair of cross-coupled inverters I
200
and I
202
. The inverters (I
200
and I
202
) are “cross-coupled” in that the output of inverter I
200
is coupled to the input of inverter I
202
, and vice versa. The outputs of the inverters (I
200
and I
202
) provide the data values on lines D and /D. Thus, the node formed at the output of inverter I
202
and the input of inverter I
200
can be considered a data node. The inverters (I
200
and I
202
) provide the storage function of the register
200
, and are accessed by two n-channel pass transistors N
200
and N
202
. Transistor N
200
has a source-drain path coupled between bit line B and the input of inverter I
200
. Transistor N
202
has a source-drain path coupled between bit line /B and the input of inverter I
202
. The gates of transistors N
200
and N
202
are commonly coupled to a word line WL.
FIG. 3
sets forth a prior art compare circuit
300
that may be used as the compare circuit
104
set forth in FIG.
1
. The compare circuit is an XOR circuit that includes a first pair of n-channel transistors N
300
and N
302
arranged in series between a match node
302
and a ground voltage GND. The gate of transistor N
300
receives a comparand value C. The gate of transistor N
302
receives the complementary data value /D. The compare circuit
300
further includes a second pair of transistors N
304
and N
306
arranged in series between the match node
302
and the GND voltage. The gate of transistor N
304
receives a complementary comparand value /C and the gate of transistor N
306
receives a data value D. In the event the comparand values (C and /C) are different than the data values (D and /D, respectively), the match node
302
will be discharged to the GND voltage. However, in the event the comparand values (C and /C) are the same as the data values (D and /D), the match node
302
will remain at a precharged level, indicating a match.
As noted above, a binary CAM can provide a rapid look-up function for an IP address. However, this is only true when the look-up function is for IP addresses having the same number of bits. Unfortunately, IP addresses can have prefixes of variable length. For example, two addresses are set forth below. The prefix values that must be matched are shown as binary values (either 0 or 1). The remaining portion of the IP address that does not have to be matched is represented by a series of Xs.
11110000 10XXXXXX XXXXXXXX XXXXXXXX (address 1)
10101010 01010101 100XXXX
Medhekar Ajit K.
Ramankutty Jayan R.
Washburn James G.
Lara Technology, Inc.
Sako Bradley T.
Tran Andrew Q.
LandOfFree
Enhanced binary content addressable memory for longest... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced binary content addressable memory for longest..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced binary content addressable memory for longest... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2524960