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-06-03

Verbrugge, Kevin (Department: 2188)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C365S049130

Reexamination Certificate

active

06574701

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 combined update/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 combined update/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 index identifier associated with a first of the plurality of entries, wherein the first entry has a first prefix with a first prefix length that is greater than a third prefix length of a third prefix to be added to the content addressable memory. A second index identifier associated with a second of the plurality of entries is also determined, wherein the second entry has a second prefix with a second 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 index identifier and the second index identifier, 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 at one of or between the first index identifier and the second index identifier.
In accordance with other aspects of this exemplary embodiment of the present invention, the first entry is beneficially a member of a prefix chain having at least one other member entry each having a respective prefix with a respective prefix length, wherein the first prefix length is less than the lengths of all other prefixes in other entries that are members of the prefix chain whose prefix lengths are greater than the third prefix length.
In accordance with further aspects of this exemplary embodiment of the present invention, the second entry is also beneficially a member of the prefix chain, wherein the second prefix length is greater than the lengths of all other prefixes in other entries that are members of the prefix chain whose prefix lengths are less than the third prefix length.
In accordance with still further aspects of this exemplary embodiment of the present invention, all members of the prefix chain are beneficially sorted according to their respective prefix lengths.
In accordance with still further aspects of this exemplary embodiment of the present invention, determining the first index identifier beneficially comp rises 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 f

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-3111502