Patent ID: 7289979
Filing Date: 2007-10-30
Classification: H04L,Y10S

Abstract:
1. A method of searching a LPM (longest prefix match) to perform a single search in a database which holds a plurality of prefixes in groups and defines an initial search area made up of a plurality of ranges, comprising steps of: (a) performing a round of binary LPM searches by executing a plurality of search instances in parallel, each search instance searching in a different range of the initial search area; (b) in response to the last round of binary LPM searches, defining a new search area by eliminating, from further searches, one or more ranges; (c) performing a further round of binary LPM searches to perform the single search by executing the plurality of search instances in parallel, each search instance searching in a different sub-range of the new search area; (d) in response to the last round of binary LPM searches, defining further a new search area by eliminating, from further searches, one or more sub-ranges; (e) storing a longest match found in a round of binary LPM searches, and (f) if necessary, repeating steps (c) to (e) to further narrow the new search area until either one of the search instances finds a longest matching prefix or all the search areas have been searched, in which case the last longest match becomes the longest matching prefix.