Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-06-07
2003-09-02
Ellis, Kevin L. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S156000, C711S212000, C711S214000, C711S217000, C365S049130, C707S793000
Reexamination Certificate
active
06615311
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to content addressable memory (CAM) and more particularly to a method and system for updating a CAM such that CAM entries are prioritized within the CAM according to their associated prefix lengths.
BACKGROUND OF THE INVENTION
Internet protocol (IP) routing involves transmitting packets from a source to a destination through a series of hops. Determining the next hop of a packet involves looking up the destination address of the packet in a route lookup table. The speed with which route lookups are performed is one factor that determines the throughput of a router. Traditional routers have used RAM and software based lookups to determine the next hop of packets, however, RAM and software based lookups have become a bottleneck in newer high speed routers.
CAM arrays are now being used as a way to speed route table lookups. Specifically, “ternary” or “tertiary” CAMs are being used to perform route table lookups in networks that require longest prefix matching, such as networks that utilize Classless Inter Domain Routing (CIDR). Ternary CAMs can perform compare operations on bits that are “0”, “1”, or “don't care”. In order to accomplish compare operations on bits that are “0”, “1”, or “don't care”, ternary CAMs store a prefix mask word in addition to a CAM entry word. The prefix mask word associated with each CAM entry indicates the number of significant bits that must be matched in each CAM entry. That is, the prefix mask word identifies the bits that fall into the “don't care” category.
CIDR specifies longest prefix matching and because multiple matches may occur in a route lookup, the longest prefix match must be determined from the multiple matches. The most common technique for determining the longest prefix match from multiple matches involves prioritizing all of the route entries in a lookup table by prefix length, with the longest prefix length having the highest priority and the shortest prefix length having the lowest priority. The longest prefix match is determined by selecting the matching entry with the highest priority among all of the matching entries.
Prioritizing the route entries within a CAM array involves sorting the route entries by prefix length and then storing the sorted route entries in indexed CAM locations. The priority order of the route entries must be maintained within the CAM array even as the CAM array is updated. Updating the CAM array in a manner that maintains the priority order of the route entries is time consuming and can offset the efficiencies that are gained by utilizing CAMs because the CAM array cannot be looked up by the hardware while it is being updated.
One technique for managing route entries within a CAM array involves leaving free locations within the CAM array at each prefix level so that new route entries can be written into the free locations without effecting the priority order of the other route entries. While leaving free locations at each prefix level works well to maintain the priority order of the CAM entries, it reduces the density of route entries that are stored within the CAM.
Another technique for updating a CAM array involves moving a block of the CAM entries in order to free a location for a new entry or to delete an existing entry. Moving large blocks of CAM entries is undesirable because each move consumes processor cycles that could be allocated to other critical operations.
Still another technique for updating a CAM array involves maintaining a bitmap or linked list of the free locations in the memory of a central processing unit (CPU) in order to find free locations. Maintaining a bitmap or linked list could involve significant CPU memory and hence is not desirable.
In view of the benefits provided by CAMs and the problems involved with updating CAM arrays to maintain the priority order of route entries within a CAM array, what is needed is an efficient technique for updating a CAM array that maintains the priority order of CAM entries.
SUMMARY OF THE INVENTION
A method and system for updating a CAM involves identifying a new entry that is to be added to the CAM, identifying a free location in the CAM that is the fewest number of prefix levels away from the prefix level of the new entry, moving an existing CAM entry into the free location to create a newly freed location that is a fewer number of prefix levels away from the prefix level of the new entry, repeating the move process until a free location is created at the desired prefix level of the new entry, and then adding the new entry into the newly freed location. The specific algorithm for moving entries to free a location in the desired prefix level is a function of whether the prefix level of the first free location is above or below the prefix level of the new entry.
If the prefix level of the first free location is above the prefix level of the new entry, then the technique involves moving the bottom entry from a prefix level that is one prefix level below the prefix level with the free location to the bottom most free location of the prefix level with the free location, thereby consuming the bottom most free location in the prefix level with the free location and creating a newly freed location in a prefix level that is a fewer number of prefix levels away from the desired prefix level. The process is repeated until a free location is created at the desired prefix level.
If the prefix level of the first free location is below the prefix level of the new entry, then the technique involves moving the entry at the top of the prefix level with the free location to the first free location in the same prefix level, thereby creating a free location at the bottom of the next prefix level above. The process is repeated until a free location is created at the desired prefix level.
If free locations exist above and below the desired prefix level and the number of prefix levels above and below the desired prefix level is the same, then moves are made as if the prefix level of the first free location is above the prefix level of the new entry.
The technique for updating a CAM involves creating a free location, sequentially one prefix level at a time, from the initial prefix level to the desired prefix level and the technique requires only one move within each prefix level that separates the desired prefix level from the prefix level with the first free location. Because of the sequential nature of the moves, the priority order or the CAM entries is maintained and the number of moves is minimized. In addition, because the technique does not involve maintaining a bitmap or a linked list of free locations in CPU memory, CPU memory is conserved.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.
REFERENCES:
patent: 5920886 (1999-07-01), Feldmeier
patent: 6052683 (2000-04-01), Irwin
patent: 6081440 (2000-06-01), Washburn et al.
patent: 6134135 (2000-10-01), Andersson
patent: 6154384 (2000-11-01), Nataraj et al.
patent: 6289414 (2001-09-01), Feldmeier et al.
patent: 6539455 (2003-03-01), Khanna et al.
Music Semiconductors, Application Brief AB-N12, “Using the MU9C1965A/L LANCAM MP in LAN-ATM Edge Switches,” pp 1-4, Sep. 30, 1998.*
Music Semiconductors, Application Brief AB-N13, “VPI/VCI Translation and Cell Tagging in ATM with the MU9C4320L ATMCAM,” pp 1-12, Sep. 30, 1998.*
Music Semiconductors, Application Brief AB-N15, “Using the MUSIC ATMCAM,” pp 1-20, Sep. 30, 1998.*
Netlogic Microsystems, Application Note NCS05, Revision 1.5, “CIDR Longest Prefix Matching in Network Search Engines,” pp 1-4, Mar. 2001.*
McAuley et al., “Fast Routing Table Lookup Using CAMs,” pp 1382-1391, IEEE, 1993.*
Music Semiconductors, What Is A CAM (Content-Addressable Memory)?, Application Brief AB-N6, Sep. 30, 1998, Rev. 2a.
Music Semiconductors, Advantage of CAM in ASIC-Based Network Address Processing, Application Brief AB-N11, Sep.
Ellis Kevin L.
Elmore Stephen
Riverstone Networks, Inc.
Wilson Mark
LandOfFree
Method and system 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 Method and system for updating a content addressable memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for updating a content addressable memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3038692