Method and apparatus for ternary content addressable memory (TCAM) table management

An apparatus, comprising:

• logic to insert a new route into a ternary content-addressable memory (TCAM) table at an available location using a first index, the new route having a mask length, the new route grouped in a Patricia tree (P-tree) having one or more routes having the same mask length;
• logic to find a route having a common prefix with the new route, the route having the common prefix grouped in a P-tree having a different mask length than the new route, the route having the common prefix placed in a second index in the TCAM table, wherein the route having the common prefix is grouped in a chain of one or more routes having the same common prefix, the routes in the chain sequenced in an order such that a route having a longer prefix is located at a lower index in the TCAM table than a route having a shorter prefix, wherein a route in the chain at a lowest index is the route with the longest prefix;
• and
• logic to insert the new route into the chain based on the mask length of the new route and based on the first index such that the chain maintains the order such that that a route having a longer prefix is located at a lower index in the TCAM table than a route having a shorter prefix.

An apparatus comprising:

• means for inserting a new route into a ternary content-addressable memory (TCAM) table at an available location using a first index, the new route having a mask length, the new route grouped in a Patricia tree (P-tree) having one or more routes having the same mask length;
• means for finding a route having a common prefix with the new route, the route having the common prefix grouped in a P-tree having a different mask length than the new route, the route having the common prefix placed in a second index in the TCAM table, wherein the route having the common prefix is grouped in a chain of one or more routes having the same common prefix, the routes in the chain sequenced in an order such that a route having a longer prefix is located at a lower index in the TCAM table than a route having a shorter prefix, wherein a route in the chain at a lowest index is the route with the longest prefix;
• and
• means for inserting the new route into the chain based on the mask length of the new route and based on the first index such that the chain maintains the order such that that a route having a longer prefix is located at a lower index in the TCAM table than a route having a shorter prefix.

A computer readable medium having stored thereon sequences of instructions which are executable by a digital processing system, and which, when executed by the digital processing system, cause the system to perform a method comprising:

• inserting a new route into a ternary content-addressable memory (TCAM) table at an available location using a first index, the new route having a mask length, the new route grouped in a Patricia tree (P-tree) having one or more routes having the same mask length;
• finding a route having a common prefix with the new route, the route having the common prefix grouped in a P-tree having a different mask length than the new route, the route having the common prefix placed in a second index in the TCAM table, wherein the route having the common prefix is grouped in a chain of one or more routes having the same common prefix, the routes in the chain sequenced in an order such that a route having a longer prefix is located at a lower index in the TCAM table than a route having a shorter prefix, wherein a route in the chain at a lowest index is the route with the longest prefix;
• and
• inserting the new route into the chain based on the mask length of the new route and based on the first index such that the chain maintains the order such that that a route having a longer prefix is located at a lower index in the TCAM table than a route having a shorter prefix.