The present invention relates generally to content addressable memories and, more particularly, to a technique for updating a content addressable memory.
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 xe2x80x9cflowxe2x80x9d 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.
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 addressable memory that is a member of the common prefix chain.
In accordance with still further aspects of this exemplary embodiment of the present invention, determining the second 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 addressable memory that is a member of the common prefix chain.
In accordance with still further aspects of this exemplary embodiment of the present invention, the third prefix with the third prefix length is beneficially added to the content addressable memory in the third entry associated with the third index identifier.
In accordance with still further aspects of this exemplary embodiment of the present invention, the plurality of entries in the content addressable memory are beneficially bounded by a minimum index identifier (INDEXMIN) and a maximum index identifier (INDEXMAX), the plurality of entries in the content addressable memory beneficially comprise a plurality of free space entries each having an unused prefix field and an unused prefix length field, the plurality of free space entries are beneficially located in a middle portion of the content addressable memory bounded by a low free space index identifier (FREELOW) and a high free space index identifier (FREEHIGH), entries in the content addressable memory having prefixes with prefix lengths that are greater than a threshold prefix length (THRESHOLD) beneficially have associated index identifiers that are greater than or equal to INDEXMIN and less than FREELOW, and entries in the content addressable memory having prefixes with prefix lengths that are less than or equal to THRESHOLD beneficially have associated index identifiers that are greater than FREEHIGH and less than INDEXMAX.
In accordance with still further aspects of this exemplary embodiment of the present invention, a subset of entries of one of the first set of entries and the second set of entries is beneficially moved up to create the third entry into which the third prefix with the third prefix length may be added if the third index identifier is determined to be less than FREELOW. If such is the case, FREELOW is beneficially incremented by one if the third index identifier is determined to be less than FREELOW.
In accordance with still further aspects of this exemplary embodiment of the present invention, a subset of entries of one of the first set of entries and the second set of entries is beneficially moved down to create the third entry into which the third prefix with the third prefix length may be added if the third index identifier is determined to be greater than FREEHIGH. If such is the case, FREEHIGH is beneficially decremented by one if the third index identifier is determined to be greater than FREEHIGH.
In accordance with still further aspects of this exemplary embodiment of the present invention, a fourth prefix with a fourth prefix length may beneficially be deleted from a fourth entry having an associated fourth index identifier. If such is the case, a free space indicator in the fourth entry may beneficially be set. Also, if such is the case, a block of entries may beneficially be moved down by one from the plurality of free space entries into the fourth entry if the fourth index identifier is less than FREELOW. Further, FREELOW may beneficially be decremented by one if the fourth index identifier is less than FREELOW. Additionally, a free space indicator in the entry associated with index identifier FREELOWxe2x88x921 may beneficially be set after decrementing FREELOW by one. Alternatively, if such is the case, a block of entries may beneficially be moved up by one from the plurality of free space entries into the fourth entry if the fourth index identifier is greater than FREEHIGH. Further, FREEHIGH may beneficially be incremented by one if the fourth index identifier is greater than FREEHIGH. Additionally, a free space indicator in the entry associated with index identifier FREEHIGH+1 may beneficially be set after incrementing FREEHIGH by one.
The present invention will now be described in more detail with reference to exemplary embodiments thereof as shown in the appended drawings. While the present invention is described below with reference to preferred embodiments, it should be understood that the present invention is not limited thereto. Those of ordinary skill in the art having access to the teachings herein will recognize additional implementations, modifications, and embodiments, as well as other fields of use, which are within the scope of the present invention as disclosed and claimed herein, and with respect to which the present invention could be of significant utility.