HK1062340B - Method and apparatus for ternary content addressable memory (tcam) table management - Google Patents

Description

Method and apparatus for Ternary Content Addressable Memory (TCAM) table management

Technical Field

The present invention relates generally to the field of network addressing. In particular, the present invention relates to a method and apparatus for managing Ternary Content Addressable Memory (TCAM) tables.

Background

The Internet Protocol (IP) is a source-routed network that forwards based on a destination internet address. Address forwarding is performed on a per-station basis. The destination address is looked up in the routing table to determine where the next station is and then the packet is forwarded to the next station. Routing protocols are used to ensure that a packet transmitted over a network can eventually reach its destination.

The development of the internet has led to a faster development of routing tables than router technology. A router must maintain thousands of items in a database corresponding to thousands of computers on the internet. The lookup process of the destination address in the routing table is an important part of the IP forwarding process. One of the internet protocols is IP version 4 ("IPv 4"). The IPv4 address space is 32 bits wide. There are two IP address schemes in IPv 4. One IP address scheme is "classful", and the other scheme is "classless". Each IP or internet address includes a network ID and a host ID. The network ID identifies the network to which the host belongs. Sometimes the network ID refers to a network prefix. The host ID identifies a particular host on a given network. The classified IP address scheme includes a plurality of addresses: A. b, C, D, E are provided. For class a, the network ID is 8 bits wide and the host ID is 24 bits wide. For class B, the width of the network ID is 16 bits; for class C, the network ID is 24 bits wide. Each class is used to support different sized networks with different numbers of hosts. Network IDs of all 0's and all 1's are used for default routing and loopback functions, respectively. Class D is used for multicast and class E is saved. The classified IP address scheme cannot effectively accommodate networks of different sizes. Routers in "legacy" networks typically use a classed IP address scheme.

The classless IP address scheme is commonly referred to as CIDR ("classless inter-domain routing"). Basically CIDR can eliminate the concept of A, B, C-class networks and replace it with an IP address prefix. CIDR may be used to perform route aggregation where a single route may cover the address space of several "old" network numbers, replacing some old routes. CIDR enables more efficient use of the available address space and allows the internet to continue to expand uninterrupted. Newer routers use the CIDR address scheme.

IP packet forwarding is handled at each router. To speed up the lookup process, a set of address prefixes is stored instead of thousands of internet addresses. A route lookup using address prefixes is referred to as a longest prefix match. In the longest prefix match, each destination address is a 32-bit string. The forwarding decision depends on using the destination address and finding the entry with the longest prefix match. The destination address is compared to a set of address prefixes to find the next route to forward the packet. There may be multiple prefix matches, but the route with the longest prefix match will be selected. The longest match algorithm assumes that the host is part of the network with the longest prefix match.

Traditional lookup procedures are based on software using hashes and trees. There may be multiple lookups per packet. However, as the number of packets increases, a faster lookup procedure is required. One hardware lookup approach uses a high-speed Ternary Content Addressable Memory (TCAM). TCAMs are memory devices that provide fast searches, such as looking up entries in a routing table database. TCAMs allow the location where content can be retrieved given a portion of the content. Given a content (e.g., destination address), the TCAM can provide location information (e.g., routing) to the content. In addition, TCAM allows bit fields to be masked and thus can be used to determine the longest prefix match. Each TCAM memory location has a corresponding mask register. A "1" in the mask register forces a match to the corresponding bit in the TCAM memory location where the address of the next station for the next route is pre-stored. The prefixes are stored in a mask register.

Management of the TCAM memory ("TCAM table") is essential to provide the correct longest prefix match in the shortest time.

Disclosure of Invention

The invention discloses a method and a system for managing a TCAM table. The new route is inserted into the TCAM table using the prefix at one of the available locations. The new route is added to the Patricia tree organized by a mask length associated with the new route. Routes having a common prefix with the new route are searched in Patricia trees organized by longer mask lengths and Patricia trees organized by shorter mask lengths to locate links for the new route. The link of the new route aggregates multiple routes having a common prefix. The multiple routes in the link are ordered in a longer prefix first ordering such that the route on top of the link has the longest prefix. Switching of multiple routes within the link is performed to accommodate the new route and maintain the ordering of longer prefix precedence.

Other features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows.

Drawings

The invention is illustrated by way of example and not limited by the figures of the accompanying drawings. In the drawings, like numbering represents like elements.

FIG. 1 is an example of a longest prefix matching operation;

FIG. 2 is a table of an exemplary TCAM for longest prefix match;

FIG. 3 is an exemplary diagram of a TCAM;

FIG. 4 is an exemplary illustration of routing links;

fig. 5 is an exemplary flow chart illustrating a process for inserting a new route into a TCAM table according to one embodiment of the invention.

Detailed Description

Fig. 1 is an exemplary illustration of a longest prefix match operation. In this example, destination address 105(11.1.2.5) is compared to the three routes 110, 115, and 120 to find the route with the longest matching prefix. Each route is associated with a mask having a mask length. The binary representation of the destination address 105 and the mask is shown for bit comparison purposes. For example, the mask length for the route 110 is 24 bits. The mask length for route 115 is 16 bits and the mask length for route 120 is 8 bits. The first 8 bits of the destination address 105 match all three masks. The first 16 bits of the destination address match the mask of route 110 and route 115. The first 24 bits of the destination address only match the mask of route 110. Route 110 is selected because route 110 provides the longest prefix match with the destination address. It should be noted that in order to find a route with the longest prefix match, multiple comparisons are performed in this example. This may be inefficient when the number of entries or routes stored in the routing table is large. This has the advantage that the route with the longest prefix can be located in the minimum amount of time.

Fig. 2 is a typical TCAM table illustrating longest prefix matching. The routing table is stored in the TCAM. This routing table is called the TCAM table. TCAM table 200 includes a table for forwarding the destination IP address. TCAM allows the above comparison to be done in one step. A result is generated whenever the TCAM finds a prefix match under any circumstances.

Empty space exists in the TCAM table 200 and can be used to insert additional routes. The destination address 205 in this example is 192.19.112.135. As described above, each TCAM entry is associated with a mask (not shown). Typically, when destination address 205 is compared to each entry shown in TCAM table 200, the route associated with entry 215 is selected because it provides the longest prefix match. However, since the comparison of TCAMs is done in such a way that the first route with prefix match is taken as the result, the route associated with item 210 is selected. This would be an incorrect choice because the mask length associated with entry 210 is only 24 bits, while the mask length associated with entry 215 is 27 bits. In the case of a TCAM, the execution of the TCAM is correct since the first match is provided. However, since the software handling the route insertion into the TCAM table is erroneous, the result will not be able to satisfy the longest prefix matching requirement. One way to find the correct longest prefix match is to arrange the entries in the TCAM table so that the entry with the longest mask precedes the entry with the shorter mask. In this way, it is guaranteed that the first match found by the TCAM has the longest prefix. This property is referred to as longest prefix match precedence.

FIG. 3 is a representative illustration of a TCAM. The TCAM includes a Ternary Content Addressable Memory (TCAM) partition 305 and a memory partition 310. For a destination address 315, there may be one or more routing prefix matches in the TCAM partition 305. When a packet arrives, the destination address is extracted. TCAM 305 performs a lookup to retrieve the result 325. TCAM 325 uses a mask in the comparison operation to select or look for a result 325 with the longest prefix match. When there is no mask matching the destination address 315, the packet will not reach the route and will be discarded.

When there is a match, the result is checked 325. Results 325 need to be processed before they can be sent to an interface. The result 325 may be a direct result or an IP address. An access to the memory 310 is performed to find the meaning of the TCAM result 325. The access provides an action 330 to be performed by the TCAM result 325. Action 330 may include information such as an output port number, output type, output link number, layer 2 encapsulation information, and the like. For example, the action may entail dividing the packet into cells for ATM, adding a header for frame delay, dropping the results 325, and so on. Based on the action information, virtual machine 335 performs the action on packet 320 and sends result 340 to the interface. The result 340 may be a new packet for transmission or nothing, since the packet has been dropped. When this is a router, the result may be an IP address and the action indicates that the packet 320 is to be transmitted to the next station.

Since there is a direct relationship between the results 325 in the TCAM 305 and the actions 330 in the memory 310, it is important to manage the TCAM table so that the insert and delete operations performed against the TCAM table of the TCAM 305 do not cause any conflicts with the memory 310. Furthermore, the TCAM table needs to be arranged in an ordering so that the longest prefix matching requirement can be performed with minimum delay. Thus, when a new entry is added to the TCAM table, a corresponding entry is also added to the memory 310. Similarly, if an entry is deleted from the TCAM table, another corresponding entry will also be deleted from the TCAM table. The ordering of the insertion of items into the TCAM table and memory 310 is important to avoid conflicts.

Typically, for an insertion, the memory 310 is updated first, and then the TCAM table is updated. For deletion, the TCAM table is deleted first, and then the deletion of the memory 310 is optionally performed. However, when the insertion is made at a location of the TCAM table that is already occupied, a conflict occurs. When there is a conflict, several TCAM table entries need to be moved or exchanged. These swapping operations present a problem of potential mismatches or inconsistencies between the TCAM table and the entries of the memory 310.

Fig. 4 is an exemplary illustration of a routing link. The TCAM table includes addresses and their corresponding masks. Table 400 of fig. 4 lists addresses (routes) and their associated mask lengths. The mask length is determined according to the mask. Each route is identified by its index number. For example, index number 10 in TCAM table 400 is occupied by route 405.

The indices 30 and 32 correspond to slots in the TCAM table 400. In one embodiment of the invention, routes having the same prefix are grouped together in a link. For example, the first 8 bits of routes 405, 410, 420, and 430 have similar prefixes. The first 8 bits of routes 415 and 425 have similar prefixes. Thus, starting from the top of the table 400, the first link is R1 → R2 → R4 → R6, and the second link is R3 → R5, where the route in the link is selected from left to right. Thus, for the first link, R1 is selected before R2 and R2 is selected before R4. The linking may be implemented using a linked list data structure.

The two links are independent of each other. If there are only two links, the valid destination address will match a route in the first link or match a route in the second link. An invalid destination address will only match the route 435 and will be discarded. The first link is R1 → R2 → R4 → R6, even though R4 has a longer prefix match than R2, R2 still precedes R4. In one embodiment, the links need to maintain an ordering such that the longest prefix match can be selected with the first match. Thus, a better ordering of the first link would be R1 → R4 → R2 → R6. This will make the first match the longest prefix match.

The first link is 4 in length because it includes four routes. The second link is 2 in length because it has two routes. A link may have a maximum length of 32. This is because the prefix becomes shorter as the number of bits in the mask is increased one bit at a time. A link may have a minimum length of 1 where there are no other routes with a common prefix. Thus, a link may start with a route having a 32-bit prefix and end with a route having a one-bit prefix. All routes in a link have a common prefix of at least one bit. Thus, for the particular set of prefixes involved, a link is a routing sequence from the longest prefix to the shortest prefix. Note that when the TCAM is programmed with new routes, the route ordering in the link needs to be preserved to meet the longest prefix match requirement. Since it is known that a maximum of 32 routes can be made to a link, the time required to perform any reordering of the links will not exceed some fixed maximum. This is advantageous because the fixed maximum time can remain the same regardless of the size of the TCAM table. Thus, the link captures the maximum prefix matching order.

In one embodiment of the invention, each route in the TCAM table having the same mask length is associated with each other. For example, all routes associated with a mask length of 24 bits belong to one group, while all routes associated with a mask length of 16 bits belong to a different group. When the IP address length is 32 bits, there are 32 groups, each group being associated with a mask length from 1 bit to 32 bits. Likewise, when the IP address length is 128 bits (as in IP version 6), there are 128 groups, each group being associated with a mask length from 1 bit to 128 bits. Each group is represented as a Patricia ("Practical algorithm to retrieve alphanumeric information") tree or P-tree data structure. Thus, there is a maximum of 32P-trees. The P-Tree data structure is a compressed representation of a tree where all the children are merged with the parent. The tree stores a plurality of strings, here a node for each common prefix. These strings are stored in additional leaf nodes. Those skilled in the art are aware of the characteristics of the P-tree.

Using the P-tree data structure, P-tree-1 ("PT-1") contains all routes with a mask length of 1 bit; PT-16 contains all routes with a mask length of 16 bits, PT-32 contains all routes with a mask length of 32 bits, etc. Thus, referring to FIG. 4, route 410(R2) and route 415(R3) are in the same PT-16. Likewise, route 425(R5) and route 430(R6) are in the same PT-8. Route 405(R1) is in PT-32 and route 420(R4) is in PT-24.

In one embodiment, the routes in the same P-tree do not have any order. Thus, the P-tree captures all routes having the same mask length. In another embodiment, routes in the same P-tree are organized in lexical graphic order.

Fig. 5 is an exemplary flow chart illustrating the process of inserting a new route into a TCAM table of the present invention. This process allows the TCAM table to be updated so that consistency can be maintained between the routing data of the TCAM and the corresponding action information of the memory. The process begins at block 505 when a new route is to be inserted into the TCAM table. Each new route has an address ("a") and a mask data ("M"). The route ("R") is represented as a data pair (A/M, index), where the index is an index of a route entry in a TCAM table. Each position in the TCAM table is associated with an index. The same index of a location in the TCAM table is used to point to a corresponding location in memory. For example, the TCAM table may include the following routes in increasing index order:

R1：(1.1.1.1/32，10)

R2：(1.1.1.0/24，12)

R3：(1.1.0.0/16，30)

R4：(1.0.0.0/8，40)

where each route is represented as (address/mask-length, index in TCAM). In this example, one new route R5: (1.128.0.0/9, X) will be inserted into the TCAM table, where "X" is an unknown index position.

In one embodiment, the index of the slot in the TCAM is determined on the first available unused entry in the TCAM table. In another embodiment, the index is determined by first determining the previous prefix, and then determining the first available item before and after the item associated with the previous prefix or first available item.

At block 510, a slot in the TCAM table is located using the free index described above. The slot is used to store the route. Assume that the TCAM table location at index 11 is empty and a new route R5 is inserted into this location. The representation of the new route R5 is (1.128.0.0/9, 11). The insertion of the TCAM table is shown at block 515. TCAMs are represented by the following:

R1：(1.1.1.1/32，10)

R5：(1.128.0.0/9，11)

R2：(1.1.1.0/24，12)

R3：(1.1.0.0/16，30)

R4：(1.0.0.0/8，40)

as described above, a link is a routing sequence from the longest prefix to the shortest prefix for the particular set of prefixes involved. In this example, after inserting the new route R5, the link is: r1(1.1.1.1/32, 10) → R5(1.128.0.0/9, 11) → R2(1.1.1.0/24, 12) → R3(1.1.0.0/16, 30) → R4 (1.0.0.0.0/8, 40). All routes in the link have the same first 8 bits. However, the insert transaction cannot be counted to completion because the link is not located within the longest matching sequence. The current link has a new route R5 with a 9-bit mask length before routes R2 and R3, even though routes R2 and R3 have mask lengths of 24 and 16 bits, respectively.

To complete a route insertion transaction, the route links and P-tree must be updated so that the routing sequence in the links is correct. In one embodiment, TCAM insertion is not minimal. In this embodiment, the invalid bit is set to indicate that the newly inserted route is not immediately available. After all route entries are inserted, the invalid bit is reset to enable routing.

In one embodiment, the mask length is used to determine the appropriate P-tree to add the new route. For example, when the mask length of the new route is 16 bits, the new route is added to the PT-16 tree. At block 520, the route is inserted into the P-tree according to the mask length associated with the route. The route insertion can be expressed as: r (a, M) → PT (| M |), wherein R (a, M) is the route and | M | is the mask length.

At block 525, a route link is searched for prefixes that match the route. As described above, when the length of an IP address is 32 bits, there are up to 32P-trees. It is possible not to occupy all 32P-trees. As described above, the P-tree captures all routes having the same mask length. Thus, to find routes with longer prefixes than the new route, a search is performed with the P-tree having a higher ordering of mask bits. Also, to find a route with a shorter prefix than the new route, a search is done with the P-tree having a lower ordering of the mask bits. For example, when a route is to be added to TP-16, routes in PT-17 through PT-32 (i.e., (PT (| M |) +1) through PT-32) are searched for a matching prefix. Also, routes in PT-1 through PT-15 (i.e., PT (| M |) -1 through PT-1) are searched for matching prefixes. Thus, in this example, there are at most 31P-trees that look for routes with a common prefix.

For each route that has a common prefix with the new route, a decision is made to see if the ordering of the routes in the link matches the ordering of longest prefix match precedence. When this is not the case, the exchange of routes in the link and the exchange of routes in the TCAM table are performed, as shown in block 530. In the current embodiment, the mask for the new route R5 is 9 bits in length and is placed on index 11 of the TCAM table. The search for routes having a common prefix with the new route R5 is done with the help of P-trees (i.e., PT-1 to PT-8) having shorter mask lengths.

There is only one route (R4) with the shorter mask length (8) and located at index position 40. A comparison of the index positions of R5 and R4 is made to see if the two routes need to be switched. If R4 has a lower index position than R5, an exchange is made to maintain an increased index ordering, thereby maintaining the longest prefix match precedence ordering. In this example, since the index of R5(11) is lower than the index of R4(40), no swap is required. Thus, according to the increasing index ordering, the routes in the link are in the following ordering: r1(1.1.1.1/32, 10) → R5(1.128.0.0/9, 11) → R2(1.1.1.0/24, 12) → R3(1.1.0.0/16, 30) → R4 (1.0.0.0.0/8, 40).

The search for routes having a common prefix for the new route R5 is done with the P-trees having the longer mask lengths (i.e., PT-10 to PT-32). In the current example, route R3(16) has a longer prefix than the new route R5 (9). Since the prefix for route R3 is 30 and the prefix for new route R5 is 11, the two routes do not have to be ordered, and a switch is needed to maintain the longest prefix match ordering. After exchanging R3 and R5, the routes in the link are in the following order: r1(1.1.1.1/32, 10) → R3(1.1.0.0/16, 30) → R2(1.1.1.0/24, 12) → R5(1.128.0.0/9, 11) → R4(1.0.0.0/8, 40).

Further, route R2 has a longer mask length than route R3. The mask length for route R2 is 24, while the mask length for route R3 is 16. Therefore, the two routes R2 and R3 need to be switched to maintain the longest match precedence. After exchanging R2 and R3, the routes in the link are in the following order: r1(1.1.1.1/32, 10) → R2(1.1.1.0/24, 12) → R3 (1.1.0.0.0/16, 30) → R5(1.128.0.0/9, 11) → R4(1.0.0.0/8, 40). Route R3 is inserted into the TCAM table at new index position 12 and route R2 is inserted into the TCAM table at new index position 11.

The flow chart process of figure 5 ends at block 535. In the current example, the final routing sequence inserted into the transaction end point is: r1(1.1.1.1/32, 10) → R2(1.1.1.0/24, 11) → R3 (1.1.0.0.0/16, 12) → R5(1.128.0.0/9, 30) → R4(1.0.0.0/8, 40).

In the foregoing specification, the invention has been described in detail with reference to specific exemplary embodiments thereof. It will be evident that various modifications and changes may be made thereto without departing from the broader and intended spirit of the invention as set forth in the appended claims. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.

Claims (3)

1. A method for managing a ternary content addressable memory, comprising:

inserting new routes into a Ternary Content Addressable Memory (TCAM) table at available locations using a first index, the new routes having a mask length, the new routes grouped in Patricia trees (P-trees) having one or more routes with the same mask length;

finding routes having a common prefix with the new route, grouping the routes having the common prefix in a P-tree having a mask length different from the mask length of the new route, the routes having the common prefix being placed at a second index in the TCAM table, wherein the routes having the common prefix are grouped in links having one or more routes having the same common prefix, the routes in the links being ordered in an ordering such that the route having the longer prefix is located at a lower index in the TCAM table than the route having the shorter prefix, wherein the route at the lowest index in the links is the route having the longest prefix; and

inserting the new route into the link according to the mask length of the new route and according to the first index, the ordering of the links being maintained such that routes having longer prefixes are located at a lower index in the TCAM table than routes having shorter prefixes.

2. The method of claim 1, wherein finding a route having a common prefix with a new route comprises: routes in the P-tree are searched for which the mask length is longer and shorter than the mask length of the new route.

3. The method of claim 1, wherein inserting the new route into the link according to the mask length of the new route and according to the first index comprises: comparing a mask length of the new route to a mask length of the common prefix route, wherein the new route and a location of the common prefix route are exchanged in the TCAM table when the mask length of the new route is longer than the mask length of the common prefix route and the first index is higher than the second index.