Longest prefix match (LPM) algorithm implementation for a...

Details Longest prefix match (LPM) algorithm implementation for a... Longest prefix match (LPM) algorithm implementation for a...

2011-07-19

2011-07-19

Robinson, Greta L (Department: 2169)

Data processing: database and file management or data structures

Database and file access

Search engines

C711S100000, C707S713000, C707S781000

Reexamination Certificate

active

07984038

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 et al.
patent: 5430874 (1995-07-01), Kumazaki et al.
patent: 5438628 (1995-08-01), Spitz et al.
patent: 5546390 (1996-08-01), Stone et al.
patent: 5692173 (1997-11-01), Chew et al.
patent: 5696836 (1997-12-01), Yoshino et al.
patent: 5704060 (1997-12-01), Del Monte et al.
patent: 5737594 (1998-04-01), Williams et al.
patent: 5757869 (1998-05-01), Sands et al.
patent: 5781249 (1998-07-01), Hwang et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5867527 (1999-02-01), Ziv et al.
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 6012061 (2000-01-01), Sharma
patent: 6052683 (2000-04-01), Irwin et al.
patent: 6067574 (2000-05-01), Tzeng et al.
patent: 6112198 (2000-08-01), Lohman et al.
patent: 6208993 (2001-03-01), Shadmon
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6243720 (2001-06-01), Munter et al.
patent: 6266706 (2001-07-01), Brodnik et al.
patent: 6396842 (2002-05-01), Rochberger et al.
patent: 6404752 (2002-06-01), Allen et al.
patent: 6522632 (2003-02-01), Waters et al.
patent: 6567408 (2003-05-01), Li et al.
patent: 6631419 (2003-10-01), Greene
patent: 6647004 (2003-11-01), Allen et al.
patent: 6658482 (2003-12-01), Chen et al.
patent: 6735179 (2004-05-01), Teplitsky et al.
patent: 6836771 (2004-12-01), Brown
patent: 6975631 (2005-12-01), Kastenholz et al.
patent: 7107265 (2006-09-01), Calvignac et al.
patent: 7130847 (2006-10-01), Waters et al.
patent: 7139753 (2006-11-01), Bass et al.
patent: 2001/0043602 (2001-11-01), Brown et al.
patent: 2001/0046205 (2001-11-01), Easton et al.
patent: 2002/0048270 (2002-04-01), Allen et al.
patent: 2002/0061022 (2002-05-01), Allen et al.
patent: 2002/0196796 (2002-12-01), Ambe et al.
patent: 2006/0173920 (2006-08-01), Adler et al.
patent: 9906926 (1999-02-01), None
“Proceeding of 13th International Conference on Pattern Recognition”, Vienna Austra, Date: Aug. 25, 1996-Aug. 29, 1996, (pp. 1-13).
Young et al. Static Correlated Branch Prediction. ACM TOPLAS, vol. 21, Issue 5 (Sep. 1999), pp. 1028-1075.

Affiliated with

Also associated with

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2691040