Patent ID: 7782868

Claim:
A two-stage 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 wherein the rule database specifies a number of rules corresponding to particular values of the header fields of the input packet; the two-stage computer network packet classification method comprising: establishing a decision tree data structure, which includes one root node and a plurality of leaf nodes linked to the root node, and wherein the decision tree data structure is established by mapping the field-to-rule correspondence defined in the rule database onto an N-dimensional Euclidean space, and using a predefined Euclidean space cutting scheme to cut each classification-related header field into a number of segments which are mapped to the N-dimensional Euclidean space to define a number of cut regions which divide all the rules into a number of groups, with each rule group being assigned to a unique identifier; and wherein the decision tree is used for storing a rule-group specifier which specifies each rule group that corresponds to the input packet; establishing a bit-vector lookup table data module, which is used for storing a field-segment information node lookup table module and a bit-vector lookup table cluster data module; wherein the field-segment information node lookup table module is used to define a set of field-segment information nodes associated with the rule-group specifiers retrieved from the decision-tree data module, with each field-segment information node being used to store a field-segment specifier which specifies a mapping of field segments to each rule group specified by the rule-group specifier; and wherein the bit-vector lookup table cluster data module is established by firstly organizing the rules in the rule database into a number of groups, and secondly generating a lucent bit vectors for each segment of each classification-related field in reference to each rule group; during actual operation, performing a first-stage of operation, which reads the input packet for the value of each classification-related field for use as a search key for retrieving from the decision-tree data structure a corresponding rule-group specifier; and performing a second-stage of operation, which firstly uses the rule-group specifier retrieved from the decision-tree data module as a key for retrieving a corresponding field-segment information node corresponding from the field-segment information node lookup table module; secondly reads the input packet for the values of the field-segments specified by the field-segment information node; thirdly performs a modulo operation on each field-segment value to thereby obtain a set of lookup keys for inquiring the bit-vector lookup table data module for a set of bit vectors; and finally performs an intersection operation on the bit vectors to obtain a matched rule as classification result for the input packet.