Patent ID: 6633548
Filing Date: 2003-10-14
Classification: H04L

Abstract:
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.