Patent ID: 6526055
Filing Date: 2003-02-25
Classification: H04L

Abstract:
A method, performed by a data processing system, of finding a longest match for a piece of target data against a group of comparison values, comprising:creating a plurality of padded prefixes by padding each prefix for which a router has an associated port both with zeros and with ones to a length one longer than the target data; sorting the padded prefixes, using masks of the padded prefixes to determine order when there are ties; eliminating duplicate padded prefixes by keeping a zero-padded duplicate prefix having a longest mask and keeping a one-padded duplicate prefix having a shortest mask; accessing at least one of a plurality of entries in a comparison data structure, each entry in the data structure having at most kâˆ’1 comparison values and k addresses of a next data structure entry, where 2<=k<=N, and where N is the total number of comparison values; and comparing kâˆ’1 comparison values in the at least one of the data structure entries to the target data, in parallel, to determine a longest matching value.