Patent ID: 6564211
Filing Date: 2003-05-13
Classification: G06F,Y10S

Abstract:
A process for selecting a subprefix having a longest match to a search prefix, comprising steps of:a) providing a search tree containing a plurality of vertices arranged in a plurality of levels such that a bottom level contains a plurality of bottom vertices each containing a plurality of prefixes, a top level contains a root vertex defining an input to the tree, and at least one intermediate level contains a plurality of hierarchy vertices, each hierarchy vertex having a plurality of child vertices in a next lower level and each bottom vertex being a child to a respective hierarchy vertex in a lowest intermediate level, each hierarchy vertex defining at least a portion of a path that extends through the respective level between the root vertex and a bottom vertex, each hierarchy vertex containing a prefix from a plurality of respective child vertices; b) input a search prefix into the root vertex; c) comparing the search prefix to the prefixes in a selected vertex of a hierarchy level; d) setting a bit in a search mask based on a least significant bit of a bit string in the search prefix that matches a longest bit string in a prefix in the selected vertex; e) repeating steps (c) and (d) for at least one vertex of each remaining hierarchy and bottom level; and f) selecting the longest matching subprefix.