Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-09-20
2005-09-20
Choules, Jack (Department: 2162)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C370S392000, C370S389000, C370S408000, C711S216000
Reexamination Certificate
active
06947931
ABSTRACT:
Novel data structures, methods and apparatus for finding the longest prefix match search when searching tables with variable length patterns or prefixes. To find the exact match or the best matching prefix, patterns have to be compared a bit at a time until the exact or first match is found. This requires “n” number of comparisons or memory accesses to identify the closest matching pattern. The trees are built in such a way that the matching result is guaranteed to be a best match, whether it is an exact match or a longest prefix match. Using the trail of all the birds and associated prefix lengths enables determination of the correct prefix result from the trail. By construction, the search tree provides the best matching prefix at or after the first compare during walking of the trail or tree.
REFERENCES:
patent: 5032987 (1991-07-01), Broder et al.
patent: 5051947 (1991-09-01), Messenger et al.
patent: 5053991 (1991-10-01), Burrows
patent: 5438628 (1995-08-01), Spitz et al.
patent: 5692173 (1997-11-01), Chew
patent: 5696836 (1997-12-01), Yoshino et al.
patent: 5737594 (1998-04-01), Williams
patent: 5757869 (1998-05-01), Sands et al.
patent: 5781249 (1998-07-01), Hwang
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5946676 (1999-08-01), Iggulden
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 5956721 (1999-09-01), Douceur et al.
patent: 5995971 (1999-11-01), Douceur et al.
patent: 6047286 (2000-04-01), Burrows
patent: 6404752 (2002-06-01), Allen et al.
patent: 6460120 (2002-10-01), Bass et al.
patent: 6526056 (2003-02-01), Rekhter et al.
patent: 6553002 (2003-04-01), Bremer et al.
patent: 6691218 (2004-02-01), Brown
patent: 2002/0184221 (2002-12-01), Ahmad et al.
patent: 2003/0126113 (2003-07-01), Brown
patent: 9906926 (1999-02-01), None
“Routing on Longest-Matching Prefixes”—Willibald Doeringer, Gunter Karjoth and Mehdi Nassehi—1996 IEEE (pp. 86-97).
“Pattern Matching in Trees”—Christoph M. Hoffmann and Michael J. O'Donnell—Journal of association for Computing Machinery, vol. 29, Jan. 1982, pp 68-95.
“Scalable High-Speed Prefix Matching”—Marcel Waldvogel, George Varghese, Jon Turner and Bernhard Plattner—ACM transactions on Computer Systems, vol. 19, No. 4, Nov. 2001, pp 440-482.
“Faster IP Lookups using Controlled prefix Expansion”—V. Srinivasan and george Varghese, 1996 ACM 0-89791-982-3/98/0006, pp 1-10.
Bass Brian Mitchell
Calvignac Jean Louis
Heddes Marco C.
Maragkos Antonios
Patel Piyush Chunilal
Choules Jack
Cockburn Joscelyn G.
Ly Anh
LandOfFree
Longest prefix match (LPM) algorithm implementation for a... 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 (LPM) algorithm implementation for a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Longest prefix match (LPM) algorithm implementation for a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3406197