Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-05-30
2003-02-04
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06516383
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to memory management schemes for use in data communications, specifically packet routing.
2. Description of the Related Art
Within routers and switches today, the process whereby the routing function is carried out is well known in the art. Part of that process is the step of determining whether or not a router is aware of the corresponding next hop destination for packet routing. This typically uses a lookup of certain elements of the packet or cell header in a table to determine packet routing, such as a longest Internet Protocol (IP) prefix match for a destination address derived from the packet header. Many systems exist for determining such matches, both in the context of Internet Protocol routing as well as other forms of routing and switching (such as those employed with the asynchronous transfer mode [ATM] communications). See for example, U.S. Pat. No. 5,809,501 to Noven, entitled
Method and System of Database Management and an Asynchronous Transfer Mode (ATM) Environment
and U.S. Pat. No. 5,884,297 also to Noven, entitled
System and Method for Maintaining a Table in Content Addressable Memory Using Hole Algorithms.
Both of these patents are incorporated herein by reference in their entireties.
As is well-known in the art, a content addressable memory (CAM) lookup outputs an exact match: either the parameter to be looked up (i.e., the lookup key) is in the CAM table or it is not. If the key is found in the table, an exact match exists and the address in the CAM table where the entry was found is provided as the output of the lookup. Ternary CAMs (TCAMs) differ from CAMs in that a TCAM allows the user to mask off bits such that a lookup key is said to match a TCAM entry even if all bits in the key do not match the entry. In other words, by masking out certain bits in the TCAM as “don't care” bits, more than one lookup key can be said to match a TCAM entry. If several TCAM entries match the lookup key, the top-most one (i.e., the entry having the lowest address) is returned. This feature is useful in supporting the longest IP prefix lookup function because the object of the search is only to find the longest prefix match, not to find all exact matches of the entire key. Commonly, the mask function of the TCAM is used to remove (mask off) non-prefix bits in the TCAM so that the lookup speed is increased in a longest prefix match lookup.
Longest prefix lookups are commonly implemented using a TCAM by placing the prefix entries in the TCAM in descending order, sorted by the length of the prefix in each entry.
FIG. 1
illustrates a prior art TCAM-implemented lookup table
100
containing sorted prefix entries
110
. The non-prefix bits of the IP address in the TCAM are generally masked off at the time of lookup. For Internet Protocol version 4 (IPv4), the IP addresses are 32 bits long: sorting these addresses into a TCAM thus creates a table having 32 different regions (not shown), where each region
1
consists of entries of a prefix length i, i being the number of unique prefix bits in an entry. (Note that in the upcoming standard Internet Protocol version 6 (IPv6), the IP address is 128 bits. IPv6 will thus necessitate a TCAM having 128 distinct IP prefix length regions.)
FIG. 1
shows a representative prior art TCAM containing a number of entries
110
. Entries
110
that are empty (i.e., not having a prefix stored therewithin) are labeled as “holes”
120
. (Entries having a prefix stored therewithin are labeled “130”.) The highest address entry is
110
-A, here containing a prefix
130
. The lowest address entry (in the bottom-most position) in TCAM table
100
is
110
-Z, here containing a hole
120
.
Although a TCAM addressing scheme having the lowest address at the “bottom” of the memory array is described, those skilled in the art will realize that such an organization is merely conceptual and that other conceptualizations and/or physical content-addressable memory layouts can be used. Accordingly, the present invention is not limited to any particular address ordering. Both the “lowest address on top” and “lowest address on bottom” orderings can be used with appropriate adaptations of the methods and apparatus described herein. Such adaptation is well within the skill of one of ordinary skill in the art and requires no undue experimentation.
Furthermore,
FIG. 1
is only a representative illustration of a portion of a TCAM configured for longest prefix match lookups. One of ordinary skill in the art will readily understand that TCAMs, and CAMs generally, having widths greater than 32 bits are commonly used and that the “depth” (i.e., the number of available entries) of the TCAM can vary.
In operation, lookup key
105
is compared to every entry
110
in TCAM
100
. The comparison of key
105
to all entries in TCAM
100
is done simultaneously by a bit-wise NOT(XOR) with every unmasked bit in every entry. If an AND function of the results of all of the NOT(XOR) operations for an entry
110
is TRUE, the all bits of that entry
110
match key
105
. The address of the highest addressed (and therefore longest prefix) entry is provided to the TCAM output.
Although the ability of the TCAM to rapidly produce longest prefix lookup matches is advantageous, it complicates the task of inserting and deleting new prefixes within the TCAM table. This is so because the TCAM table must be maintained in a prefix length sorted order. Though TCAM updates (inserts and deletes) are infrequent, a time consuming update mechanism steals valuable processor resources and potentially results in a dropping of packets. Such deleterious effects must be avoided if high packet switching/routing speeds are to be maintained. The problem is only exacerbated by the expected industry switch to the IPv6 architecture with its longer addresses.
An insert of a prefix of length i can be accomplished in one TCAM write cycle if there is a vacant entry (hole) in the i
th
region (i.e., the region containing all entries of equal length i), otherwise the TCAM write may need to move a vacant entry from a neighboring region in order to expand the space in the i
th
region. In particular, if up to k regions on either side of the i
th
region have no holes, then one would need to perform k moves to provide a hole. Since the cost of a move (involving both reading and writing the entry) is much higher than that of a lookup, it is desirable to minimize the number of moves involved in TCAM updates.
In one prior art method commonly used, a “naïve” algorithm for TCAM updates is employed. The naïve (or “lazy”) algorithm moves TCAM entries only when it needs to. A delete in a given region creates a hole in that region. Conversely, an insert in a region requires the presence of a hole in that region in which to insert the entry. A region is referred to as a “full” (or “congested”) region when it does not have any holes and thus an insert into a full region requires moving a hole into that region from the nearest non-full region. This may necessitate moving entries in adjoining regions as well, in order to make room. It is desirable that the number of moves required to supply a hole to a full region is minimized. Indeed, it is preferable to have some holes in each region to facilitate updating.
Consider a TCAM with a certain maximum number of entries. One can readily see that some routing applications could use enough IP prefixes to result in a TCAM occupancy rate of 90% or more. In fact, such occupancy rates are commonly seen in the art today. A 90% occupancy rate implies that 10% of the TCAM entries are holes. A “good distribution” of these holes is one where they are almost equally distributed among the 32 regions (in an IPv4 system, which has a maximum prefix length of 32 bits) so that one does not encounter a full region during any insert. Obviously, a “bad distribution” is one where several full regions occur contiguously, resulting in the requirement for a number of moves in order to provide a hole to support an
Panigrahy Rina
Patra Abhijit
Sharma Samar
Campbell III Samuel G.
Campbell Stephenson Ascolese LLP
Cisco Technology Inc.
Moazzami Nasser
Yoo Do Hyun
LandOfFree
Techniques for efficient location of free entries for TCAM... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Techniques for efficient location of free entries for TCAM..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Techniques for efficient location of free entries for TCAM... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3127968