Patent ID: 7418505

Claim:
An IP address lookup method comprising: (a) establishing a hashing table with an SRAM, the hashing table including a plurality of main tables and a plurality of sub-tables corresponding to prefix lengths of the IP address, entries being stored in the main tables and the sub-tables; (b) performing a hashing process on an incoming IP address based on the prefix lengths to generate a prefix of the incoming IP address that is shorter than the incoming IP address by using a hashing hardware unit, wherein the hashing hardware unit is constructed based on the prefix lengths of the IP address; (c) comparing prefixes, each of which is stored at a location in a main table pointed by a hashing value with the prefix of the incoming IP address, searching entries of the main table having a prefix matched with the prefix of the incoming IP address, and forwarding information on prefix-matched entries; (d) if there is no prefix-matched entry as a result of Step (c), searching entries of a sub-table having the prefix matched with the prefix of the incoming IP address starting from a location in the sub-table pointed by a pointer of the main table, and forwarding information on prefix-matched entries; and (e) selecting an entry having a longest-matched-prefix among the prefix-matched entries by using information forwarded in Steps (c) and (e).