Patent ID: 7706375

Claim:
A method of managing a routing table of a Ternary Content Addressable Memory (TCAM) for longest IP prefix matching, the method comprising: dividing the routing table into a plurality of logical blocks wherein each logical block is associated with a respective IP prefix length and is for storing respective routing entries having said respective IP prefix length, and wherein each logical block is of a respective size whose proportion to a total size of the routing table is determined by the respective IP prefix length, and wherein said plurality of logical blocks are ordered in said routing table such that the TCAM returns a longest IP prefix match when passed an IP address; and adding a routing entry to a logical block of said plurality of logical blocks of said table, the step of adding comprising: inserting the routing entry into the center of the logical block if the logical block is empty, inserting the routing entry into an empty entry adjacent to a used portion of the logical block on a side of the used portion which has a greatest number of empty entries, if the logical block has non-empty entries and empty entries, and growing the logical block into an adjacent empty portion of a neighboring logical block, if the logical block is full, and inserting the routing entry into said adjacent empty portion in an empty entry adjacent to a used portion of the logical block.