Longest prefix match lookup using hash function

Details Longest prefix match lookup using hash function Longest prefix match lookup using hash function

2006-08-08

2006-08-08

Corrielus, Jean (Department: 2162)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C370S335000, C370S392000

Reexamination Certificate

active

07089240

ABSTRACT:
A method and apparatus are used for finding the longest prefix match in a variable length prefix search when searching a direct table within a routing table structure of a network processor. The search through the routing table structure is expedited by hashing a first segment of an internet protocol address with a virtual private network number followed by concatenating the unhashed bits of the IP address to the result of the hash operation to form an input key. Patterns are compared a bit at a time until an exact match or the best match is found. The search is conducted in a search tree that provides that the matching results will be the best possible match.

REFERENCES:
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 6061712 (2000-05-01), Tzeng
patent: 6070246 (2000-05-01), Beser
patent: 6101499 (2000-08-01), Ford et al.
patent: 6173399 (2001-01-01), Gilbrech
patent: 6212183 (2001-04-01), Wilford
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6223172 (2001-04-01), Hunter et al.
patent: 6226710 (2001-05-01), Melchior
patent: 6226748 (2001-05-01), Bots et al.
patent: 6226751 (2001-05-01), Arrow et al.
patent: 6308220 (2001-10-01), Mathur
patent: 6311216 (2001-10-01), Smith et al.
patent: 6338078 (2002-01-01), Chang et al.
patent: 6404752 (2002-06-01), Allen et al.
patent: 6430184 (2002-08-01), Robins et al.
patent: 6434144 (2002-08-01), Romanov
patent: 6473846 (2002-10-01), Melchior
patent: 6539369 (2003-03-01), Brown
patent: 6631419 (2003-10-01), Greene
patent: 6633563 (2003-10-01), Lin et al.
patent: 6633880 (2003-10-01), Modelski et al.
patent: 6640220 (2003-10-01), Firlit et al.
patent: 6662184 (2003-12-01), Friedberg
patent: 6691218 (2004-02-01), Brown
patent: 6715081 (2004-03-01), Attwood et al.
patent: 6754832 (2004-06-01), Godwin et al.
patent: 6778532 (2004-08-01), Akahane et al.
patent: 6858455 (2005-02-01), Guillom et al.
patent: 2001/0043602 (2001-11-01), Brown
patent: 2001/0044876 (2001-11-01), Brown
patent: 2003/0126113 (2003-07-01), Brown
patent: WO 01/04802 (2001-01-01), None
“Using multiple hash functions to improve IP lookups” by Broder et al, INFOCOM 2001, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, vol. 3, pp. 1454-1463, Apr. 22-26, 2001.
“Hybrid direct table and LPM searches” Research Disclosure 443117, Mar., 2001, p. 456.

Affiliated with

Also associated with

Rating

Longest prefix match lookup using hash function does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Longest prefix match lookup using hash function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Longest prefix match lookup using hash function will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3645316