Patent ID: 7079542

Claim:
An Internet Protocol address look-up method, the method comprising the steps of: inputting a search key into a plurality of routing entries, each respective one of the routing entries having a data string that includes data of a respective prefix and having a mask string that includes a length of the respective prefix, each respective one of the routing entries being included in a ternary content addressable memory (CAM); detecting matching prefixes when a search key matches prefixes from among the prefixes of the routing entries; outputting the mask strings corresponding to the routing entries having the matching prefixes; and comparing lengths of the matching prefixes corresponding to the outputted mask strings to determine a longest prefix matching (LPM) entry, the longest prefix matching entry corresponding to the routing entry having the longest outputted mask string; said method further comprising the steps, after the outputting step, of: assigning an upper pointer to a most significant bit of the outputted mask strings; assigning a lower pointer to a least significant bit of the outputted mask strings; assigning a check pointer, intermediately positioned between the upper and lower pointers, to a bit of the outputted mask strings; and when more than one bit indicated by the check pointer corresponds to a prefix bit, reassigning the lower pointer to a new position corresponding to a position of the check pointer, and then reassigning the check pointer to a bit of the outputted mask strings intermediately positioned between the upper pointer and the reassigned lower pointer.