Patent ID: 7792120

Claim:
A computer network packet classification method for use on a network data processing unit for classification of an input packet in accordance with a predefined rule database, wherein the input packet contains a number of header fields, and the rule database specifies a number of rules corresponding to particular values of the header fields of the input packet; the computer network packet classification method comprising: building a projected-interval-to-encoded-bit-vector lookup table which predefines a mapping relationship of projected areas to encoded bit vectors, and which is constructed based on a nonoverlapping rule group encoding scheme which maps all the rules in the rule database onto a first one-dimensional Euclidean space and defines a number of projected intervals and a number of nonoverlapping rule groups over the first one-dimensional Euclidean space, and further define a number of encoded bit vectors corresponding to the projected intervals and the nonoverlapping rule groups; building an encoded-bit-vector-to-nonoverlapping-rule-group lookup table, which predefines a mapping relationship of encoded bit vectors to nonoverlapping rule groups based on the nonoverlapping rule group encoding scheme; during actual operation, reading the input packet for the value of each classification-related field, and then using each field value as an index to find corresponding projected interval and encoded bit vector from the projected-interval-to-encoded-bit-vector lookup table; retrieving a number of probable rule sets from the encoded-bit-vector-to-nonoverlapping-rule-group lookup table by using a number of indexes obtained by segmenting each encoded bit vector into a number of parts corresponding to the nonoverlapping rule groups associated with each classification related field; and performing an intersection operation on all probable rule sets to find a common rule included in all the probable rule sets as classification result.