Electrical computers and digital processing systems: multicomput – Computer network managing – Network resource allocating
Reexamination Certificate
2004-05-26
2008-08-26
Barot, Bharat N (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer network managing
Network resource allocating
C709S237000, C709S245000, C370S235000, C370S235100, C370S395100, C707S793000
Reexamination Certificate
active
07418505
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.
REFERENCES:
patent: 6658482 (2003-12-01), Chen et al.
patent: 6956858 (2005-10-01), Hariguchi et al.
patent: 7031320 (2006-04-01), Choe
patent: 7089240 (2006-08-01), Basso et al.
patent: 7246231 (2007-07-01), Tariq et al.
patent: 7304994 (2007-12-01), Dubnicki et al.
Chung Yeo-jin
Lim Hyesook
Barot Bharat N
EWHA University - Industry Collaboration Foundation
Oblon & Spivak, McClelland, Maier & Neustadt P.C.
LandOfFree
IP address lookup using either a hashing table or multiple... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with IP address lookup using either a hashing table or multiple..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and IP address lookup using either a hashing table or multiple... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4005969