Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-02-23
2003-08-12
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S156000, C370S392000
Reexamination Certificate
active
06606681
ABSTRACT:
TECHNICAL FIELD
This invention relates generally to packet switched communication systems.
BACKGROUND
With reference to computing systems, memory refers to a place where the computing system holds information, such information able to be accessed and worked on as appropriate. Random Access Memory (RAM) can be used in a personal computer to temporarily store data that is currently being accessed or worked on. Read-only memory can be used for storage of information that does not change. A conventional memory structure includes a memory space of data that includes a plurality of entries, each identifiable by a specific location in the memory space. Each entry has a name (the address) that serves to locate the contents within the memory space.
An associative memory element, more commonly referred to as content addressable memory (CAM), includes a different structure. CAM element objects are selected based on their contents, not based on their location in the memory space. Each CAM element includes a key and associated data. Examples of associative memory elements include a hash table and set-associative table. A content addressable memory is searched (searching of the keys in the CAM memory space) and returns a data value (data word) upon detecting a valid match condition for a given key. The CAM contains all keys to be compared during a search operation. In a conventional CAM, each key (i.e., entry) in the CAM is associated with a single data word. The association can be by location, that is, entries in the CAM can map directly to data stored in a RAM. As such, the associative data portion of the CAM can be of the form of an actual data word or a pointer to the data word that is associated with the corresponding key.
In use, a CAM is searched whenever the information associated with a key is needed. A search is performed in the valid portion of the CAM. If a match is detected, a data word associated with the matching key is returned. Where the association is by location, the address of the key is obtained when a match is detected. Using the returned address, data can be read from, for example, a RAM that is used to store the associated data words.
An example of a conventional CAM including associated RAM for storing data words is shown in
FIG. 1
a.
The CAM
100
includes a plurality of entries
102
, each including a valid bit
104
and a key
106
. The valid bit is set for each valid entry in CAM
100
. Not shown, but associated with each entry in the CAM
100
, is an address for a given entry. Data words are stored in an external RAM
108
. Data words are located in RAM
108
in accordance with the addresses associated with the given entries (keys) in CAM
100
. An external search engine
110
provides keys to be searched for in the information space associated with CAM
100
. Thereafter, the valid portion of the CAM
100
(all valid entries) is searched. The address of a matching key is obtained upon detection of a match. The address is in turn forwarded to control logic
111
. Control logic
111
uses the address to access the appropriate data word stored in the RAM
108
(the data word associated with the key being searched).
Another example of a conventional CAM is shown in
FIG. 1
b,
which is used to make forwarding decisions of packets in a router or switch. Each entry
102
in CAM
150
can include a tag
112
. The tag
112
is used to designate the entry as being either a source address or destination address. Accordingly, the same key can be stored multiple times in CAM
150
as a source address and as a destination address. Depending on whether the search invoked by search engine
110
is for a destination address or source address, different hits will result in CAM
150
for the same key. The number of entries or blocks in CAM
150
is equal to the sum of the number of source addresses and destination addresses that are to be searched.
CAM memory tends to be expensive (relative to RAM). As the information base associated with a CAM grows, such as when multiple copies of the same key are included in the CAM, costs rise. What is desired is a means to be able to minimize the CAM size while still realizing the benefits derived from an associative memory structure.
SUMMARY
In one aspect, the invention provides a content addressable memory including an associative memory portion including N entries, each entry including a key. The content addressable memory further includes a random access memory portion. The random access memory portion includes K*N entries where a single key stored as an entry in the associative memory portion is mapped to K entries in the random access memory portion, where K is greater than 1.
Aspects of the invention can include one or more of the following features. Each entry in the random access memory portion can be associated with a single key and can include information based on the key type. The type can be a source or destination address. The type can be a MAC address or an MPLS label. Each entry can include an M-bit type indicator, where M is greater than 1. The number of types can be two, source and destination addresses. The content addressable memory can be configured such that K=M.
In another aspect the invention provides a content addressable memory including an associative memory portion including N entries, each entry including a key and an M-bit type indicator, where M is greater than 1. The content addressable memory further includes a random access memory portion. The random access memory portion includes N entries including K portions where a single key stored as an entry in the associative memory portion is mapped to a single entry in the random access memory including the K portions, where K is greater than 1.
In another aspect, the invention provides a content addressable memory for storing MAC addresses and MPLS labels and includes an associative memory portion including N entries. Each entry includes a key and an M-bit type indicator, where M is greater than 1. Each key is of the form of a MAC address or MPLS label or both as indicated by the type indicator. The content addressable memory further includes a random access memory portion. The random access memory portion including K*N entries where a single key stored as an entry in the associative memory portion is mapped to up to K entries in the random access memory portion, where K is greater than 1.
In another aspect, the invention provides a method for storing MAC addresses in a content addressable memory. The content addressable memory includes an associative portion and a random access portion. The associative portion includes one or more entries each including an address. The random access portion is operable to store information relevant to each address. The method includes associating a single address with plural entries in the random access memory when the single address is maintained in the associative portion of the content addressable memory for two different contexts, one dependent on whether the address is a source address and one dependent on whether the address is a destination address.
In another aspect, the invention provides a method for storing MAC addresses in a content addressable memory. The content addressable memory includes an associative portion and a random access portion. The associative portion includes one or more entries each including an address. The random access portion is operable to store information relevant to each address. The method includes determining if an address is present in the associative portion for a first context, either as a source address or destination address. If the address is present, marking the address in the associative portion to indicate that the address is to be associated with a second context. Information relevant to the second context and associated with the address is added to the random access portion including mapping the address to relevant information stored in the random access portion associated with the first context and the second context.
In another aspect, the invention provides a method
Choi Woo H.
Cisco Systems Inc.
Kim Matthew
The Law Office Kirk D. Williams
LandOfFree
Optimized content addressable memory (CAM) does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimized content addressable memory (CAM), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimized content addressable memory (CAM) will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3121849