Multiple entry matching in a content addressable memory

Details Multiple entry matching in a content addressable memory Multiple entry matching in a content addressable memory

2000-09-21

2001-07-10

Nelms, David (Department: 2818)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S189070

Reexamination Certificate

active

06259620

ABSTRACT:

BACKGROUND
The present invention relates to computer memory devices, and more particularly to content addressable memories.
A conventional Content Addressable Memory (CAM)
101
is illustrated in
FIG. 1. A
CAM
101
can be viewed as a computer accessible storage device having an inverse type of access compared with typical addressable memories. For example, a typical Random Access Memory (RAM) is accessed by means of an address port. One supplies an address to the address port, and the RAM supplies at its output the data value that is stored at the memory location designated by the address. By contrast, one accesses a CAM
101
by supplying data of interest (referred to as a “comparand”) at a comparand input port
103
. The comparand is represented as a ternary value for each bit: “0”, “1”or “*”, the last one interpreted as a wild card. Each storage entry
105
in the CAM
101
includes, or is otherwise associated with, logic that compares the value stored in the entry
105
with the comparand. (Any value is considered to match a value of “*”.) The resulting signals, each indicating whether a match occurred, are supplied to a priority encoder
107
, which generates an address
109
that indicates one of the matching entries (e.g., the lowest address associated with a matching entry
105
).
CAMs are increasingly used to implement massively parallel searches over a large number of data. For example, in the Internet Protocol (IP), the forwarding and classification of packets each require a search of a large to massive data base. IP forwarding lookup is the problem of using the destination address of an incoming packet to find a matching one from among tens of thousands of routing table entries. Once a best matching entry is found, it is used to determine the next hop for the packet. The routing table may contain several matching entries, where the one with the least number of “wild cards” is considered the best match.
IP classification is the more general problem of using selected parts of the IP and higher level headers of an incoming packet to find a matching one from among a hundred to a thousand classification entries. Once a highest priority entry is found, it is used for different purposes, such as filtering, IP security selection and virtual routing.
The IP forwarding lookup problem can be addressed by extending the basic CAM principle to allow the bits of stored data entries to take on wild card values. CAMs extended in this manner are called ternary CAMs. With such an extended CAM, the routing table entries are stored directly in the CAM, one after another. The destination address of the packet is simply presented as a comparand (without wild cards) to the CAM, which performs the matching in a single access. The address generated by the CAM is used to read further (non-associative) routing data from a standard RAM.
The task of updating the CAM is simple, since each data directly corresponds to a routing entry. The only consideration is that entries should be stored in order based on the number of wild cards. Hence, relocation can be necessary when updates are made.
The IP classification problem is improved, but not fully addressed by conventional CAMs. Considering all possible matching strategies, for the moment, it is apparent that the trivial method of matching against every table entry by reading them one after another will not achieve performance requirements. Hence, several methods using tree representations have been used. More particularly, the routing table may be compiled into a tree, which is stored in a RAM. The tree is traversed from the root to the leaves. In every node, a subfield of the destination address is used together with node specific data to decide what branch of the tree to select as the next step. The routing entries are associated with some nodes or leaves in the tree. Eventually, a best match will be found.
The problem with these methods is that, depending on implementation choices, they either require a large number of cycles to traverse the tree or alternatively are a huge waste of memory (several magnitudes more than needed for the entries). This problem is particularly acute with respect to the classification problem because the matching criteria are quite general and the number of bits to match very high. One possible solution is to split the problem into a multidimensional search problem, with each or a number of fields in the headers representing one dimension. Multiple simpler searches are then performed in each dimension and the results are combined in some way in a second step. However, different classification entries will overlap each other when projected to a dimension, generating extra complexity to both steps of the problem.
Applying a conventional CAM to the Ip classification problem simplifies the search in each of the dimensions. However, the use of conventional CAMs does not provide a straightforward solution to combining the results in the above-described second step of the multidimensional matching problem.
Like ordinary memories, a conventional CAM is arranged as number of entries, each holding a data word of a fixed width. Matching is limited to this width. Conventional CAMs offer no general and fast way to make matches to a comparand greater than the width of a cell.
SUMMARY
In accordance with one aspect of the present invention, the foregoing and other objects are achieved in a content addressable memory that comprises a matrix of cells having (n+1) columns and m rows, wherein n and m are each integers greater than or equal to 1, and wherein each row of cells comprises: n data storage cells, a carry storage cell, word compare logic, and carry write logic.
Each of the n data storage cells comprises: storage logic for storing a respective one of n data signals; an input for receiving a respective one of n comparand data signals; and bit compare logic that generates a bit compare signal that indicates whether the stored one of the n data signals matches the received one of the n comparand data signals.
The carry storage cell comprises: a first input for receiving a carry data signal; storage logic for storing the carry data signal; a second input for receiving a carry comparand data signal; and carry compare logic that generates a carry compare signal that indicates whether the stored carry data signal matches the received carry comparand data signal.
The word compare logic generates a word compare signal that indicates whether each of the bit compare signals in the row indicates that the stored one of the n data signals matches the received one of the n comparand data signals and that the carry compare signal in the row indicates that the stored carry data signal matches the received carry comparand data signal.
The carry write logic generates a carry storage cell write signal only if the word compare signal generated by the word compare logic in a previous row of cells indicates that each of the bit compare signals in the previous row indicates that the stored one of the n data signals matches the received one of the n comparand data signals and that the carry compare signal in the previous row indicates that the stored carry data signal matches the received carry comparand data signal.
In another aspect of the invention, each of the n comparand data signals and the carry comparand data signals may be a ternary value selected from a group of values consisting of “0”, “1” and “don't care”; and the “don't care” value matches any of the ternary values.
In yet another aspect of the invention, the carry write logic further comprises a write input port for receiving a carry write signal, and the carry write logic generates the carry storage cell write signal only if the carry write signal is asserted and the word compare signal generated by the word compare logic in a previous row of cells indicates that each of the bit compare signals in the previous row indicates that the stored one of the n data signals matches the received one of the n comparand data signals and that the carry compare signal in the previo

Affiliated with

Also associated with

Rating

Multiple entry matching in a content addressable memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multiple entry matching in a content addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple entry matching in a content addressable memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2506637