Technique for updating a content addressable memory

Details Technique for updating a content addressable memory Technique for updating a content addressable memory

2001-09-27

2003-03-11

Verbrugge, Kevin (Department: 2188)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C365S049130

Reexamination Certificate

active

06532516

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to content addressable memories and, more particularly, to a technique for updating a content addressable memory.
BACKGROUND OF THE INVENTION
The primary function of any network switch/router is to route a received packet to an appropriate destination. This primary function is made up of several different functions. For example, upon receiving the packet, the network switch/router functions to: 1.) determine the next hop node for the packet; 2.) provide buffer management for the packet; and 3.) provide quality of service to the packet. Function 1 requires a routing table lookup based primarily on a destination address field in a header of the packet. Functions 2 and 3 require classifying the packet to a “flow” based on fields in the packet header. Such fields that are typically used for packet classification include packet source and destination address fields, type of service (TOS) fields, etc.
A network processor typically performs the above-described functions. However, as link speeds and the size of the network increases, the time required for performing these functions decreases, while the size of the routing tables and the classification tables increases. For high-speed links and large networks, the network processor is not capable of performing lookups and classification at line rate.
A popular memory device used for performing fast routing table lookups and packet classification is a Content Addressable Memory (CAM). CAM's are attractive because of their inherent parallelism. A network processor builds a search key using packet header fields and sends the search key to a CAM. When a search key is presented to the CAM, a comparison of the search key happens in parallel with all of the entries in the CAM. If there are multiple matches, the CAM arbitrates among them and selects one of the entries. The network processor uses the index of the selected entry as an address to read a result from the associated memory. The result describes to the network processor the actions to be taken on the packet. Examples of such actions include replacing a field with a substitute field, decrementing a field, incrementing a field, etc.
Referring to
FIG. 1A
, there is shown a first example of a network switch/router
10
with a network processor (NP)
12
, a CAM
14
, and an associated memory
16
. In the network switch/router
10
of
FIG. 1A
, the network processor
12
directly accesses the CAM
14
and the associated memory
16
.
Referring to
FIG. 1B
, there is shown a second example of a network switch/router
20
with a network processor (NP)
22
, a CAM
24
, an associated memory
26
, and a bridge device
28
, which is located between the network processor
22
, the CAM
24
, and the associated memory
26
. In the network switch/router
20
of
FIG. 1B
, the bridge device
28
operates to reduce the load on the network processor
22
.
From a CAM perspective, both the first and second examples described above are equivalent and do not affect the internal design of the CAM.
The basic operations that are performed in a CAM are: 1.) addition of a key; 2.) deletion of a key; and 3.) search based on a key. Addition of a key occurs when a new routing entry or a flow classifier is learned by the network switch/router and has to be applied to the subsequent incoming packets (this event is also called a learning or update event). Deletion of a key could happen when a route or a flow classifier no longer exists, or when no packets with the key have arrived at the node for a long period of time (the latter event is called an aging event or a route delete event).
Referring to
FIG. 2A
, there is shown a 2-port CAM
30
having a search port
32
and a result port
34
. In the 2-port CAM
30
, CAM management (i.e., addition/deletion of keys) is multiplexed with searches through the search port
32
. Thus, in the 2-port CAM
30
, update latency can affect the search performance of the CAM.
Referring to
FIG. 2B
, there is shown a 3-port CAM
40
having a search port
42
, a result port
44
, and an update port
46
. In the 3-port CAM
40
, CAM management occurs through the update port
46
. Thus, in the 3-port CAM
40
, updates happen independent of searches.
While 2-port CAM's are fairly ubiquitous in the market, only a single vendor presently offers a 3-port CAM (i.e., Sibercore). However, it is anticipated that more vendors will soon begin to offer 3-port CAM's. Accordingly, because it is likely that both 2-port CAM's and 3-port CAM's will soon be widely available in the market, it would be desirable to provide a new CAM management technique to minimize the update time in both 2-port and 3-port CAM's.
SUMMARY OF THE INVENTION
According to the present invention, a technique for updating a content addressable memory is provided. In one exemplary embodiment, wherein the content addressable memory has a plurality of entries, and wherein each of the plurality of entries has a prefix field, a prefix length field, and an associated index identifier, the technique is realized by determining a first set of index identifiers, wherein each index identifier in the first set of index identifiers is associated with a respective entry in a first set of the plurality of entries, and wherein each entry in the first set of entries has a respective prefix with a respective prefix length that is greater than a third prefix length of a third prefix to be added to the content addressable memory. A second set of index identifiers is also determined, wherein each index identifier in the second set of index identifiers is associated with a respective entry in a second set of the plurality of entries, and wherein each entry in the second set of entries has a respective prefix with a respective prefix length that is less than the third prefix length of the third prefix to be added to the content addressable memory. Based upon the first set of index identifiers and the second set of index identifiers, a third index identifier is determined. The third index identifier is associated with a third of the plurality of entries where the third prefix with the third prefix length may be added to the content addressable memory. The third index identifier is located in one of or between the first set of index identifiers and the second set of index identifiers.
In accordance with other aspects of this exemplary embodiment of the present invention, each entry in the first set of entries is beneficially a member of a common prefix chain. Each entry in the second set of entries is also beneficially a member of the common prefix chain. Further, all members of the common prefix chain are beneficially sorted according to their respective prefix lengths.
In accordance with further aspects of this exemplary embodiment of the present invention, determining the first set of index identifiers beneficially comprises searching the content addressable memory for entries having prefixes with prefix lengths which match the third prefix having the third prefix length. For example, searching the content addressable memory may beneficially comprise generating a compare array having a plurality of compare array entries corresponding to the plurality of entries in the content addressable memory, wherein each of the plurality of compare array entries has a compare array prefix and an associated index identifier corresponding to the index identifier of a respective entry in the content addressable memory. Searching the content addressable memory may also beneficially comprise extending the third prefix length of the third prefix to obtain an extended third prefix with an extended third prefix length. Searching the content addressable memory may further beneficially comprise comparing the extended third prefix to the plurality of compare array prefixes so as to identify index identifiers associated with compare array prefixes which match the extended third prefix, wherein each identified index identifier corresponds to a respective entry in the content addressa

Affiliated with

Also associated with

Rating

Technique for updating 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 Technique for updating a content addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for updating a content addressable memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3016162