Ip address lookup using either a hashing table or multiple hash functions

Abstract

The present invention relates to an IP address lookup method and hardware architecture. There is provided an IP address lookup method using a hashing table, the hashing table being constructed with an SRAM, the hashing table including main tables and sub-tables corresponding to prefix lengths of the IP address, entries being stored in the main tables and the sub-tables, the method comprising steps of: (a) performing a hashing process on an incoming IP address based on the prefix lengths of the IP address by using a hashing hardware unit, wherein the hashing hardware unit is constructed based on the prefix lengths of the IP address; (b) comparing prefixes, each of which is stored at a location in the main table pointed by a hashing value with the prefix of the IP address, searching entries of the main table having the prefix matched with the prefix of the IP address, and forwarding information on prefix-matched entries; (c) if there is no prefix-matched entry as a result of Step (b), searching entries of the sub-table having the prefix matched with the prefix of the 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 (d) searching an entry having the longest-matched-prefix among the prefix-matched entries by using the information forwarded in Steps (b) and (c). Accordingly, it is possible to perform an IP address lookup process on all the prefixes in parallel by classifying prefixes based on the prefix lengths and constructing separate tables corresponding to the classified prefix lengths of the IP address. As a result, it is possible to easily apply a hashing process to the IP address and to reduce searching time.