Patent ID: 7116663

Claim:
In a packet classification process, a method of determining whether a target bit pattern matches at least one of a plurality of filter bit patterns, each bit pattern being composed of a specific sequence of element bits, each element bit in said target bit pattern having a value of either 1 or 0 and each element bit in said filter bit pattern having a value of 1, 0, or x where x can be matched by any value of an element bit the method comprising: a) generating a target vector from said target bit pattern; b) generating a filter array from said plurality of filter bit patterns, each filter bit pattern corresponding to a row in said filter array; c) generating at least one intermediate array based on said filter array; d) selecting specific columns from said at least one intermediate array based on bit values of said target vector; e) generating a final array from columns selected in step d); and f) generating a match vector from said final array, each vector element of said match vector being a result of a bitwise AND operation on a row of said final array, wherein each vector element in said match vector having a value of 1 indicates a match between said target bit pattern and a filter bit pattern corresponding to a row in said filter array having the same row number as said vector element.