System and method of fast adaptive TCAM sorting for IP longest prefix matching

Abstract

A system and method are provided for sorting IP routing table entries in a TCAM for longest IP prefix matching LPM of destination IP addresses. The IP routing table is divided into logical blocks, for each block an associated routing entry IP prefix length. Each block is of a respective size whose proportion of the total size of the routing table is determined by the associated IP prefix length. The blocks are ordered so that the TCAM returns an LPM when queried. Starting block sizes can be initialized to proportions which reflect actual expected numbers by proportion of routing entries by IP prefix length. The blocks also grow and shrink as entries are added and deleted so as to more closely mirror real-world populations of expected entries having the IP prefix length in question.

Dependencies are inferred from the claim text.