Patent ID: 8732110

Claim:
A method for classifying a packet, the method comprising: receiving a packet; searching for a rule matching the packet in at least one created decision tree, wherein the decision tree is a decision tree created after an original rule set is divided based on a segmentation code; and classifying the packet according to a found rule; wherein before searching for the rule matching the packet in the at least one created decision tree, the method further comprises: dividing the original rule set into at least two sub-rule sets according to the segmentation code; and creating a decision tree for each of the sub-rule sets; and wherein dividing the original rule set into the at least two sub-rule sets according to the segmentation code comprises: using at least two bits of characters as a segment to segment each rule in the original rule set, and calculating a segmentation code corresponding to each rule; counting rules corresponding to a same segmentation code and obtaining the number of the rules, and sequencing segmentation codes according to a descending order of the numbers of rules; selecting a segmentation code corresponding to a largest number of the rules, performing, in sequence, a bit-by-bit AND operation on the selected segmentation code and each of other segmentation codes sequenced according to the numbers of the rules, using the number of ‘1’ a bit-by-bit AND result as a matching level to classify and sequence the segmentation codes; performing, in sequence, a continuous bit-by-bit AND operation on the segmentation codes of which the matching level is not 0 and that are sequenced according to the matching level, and when the number of ‘1’ in a continuous bit-by-bit AND result is less than a minimum matching level, sorting a last segmentation code participating in the continuous bit-by-bit AND operation into a type of which a matching level is 0; sorting rules corresponding to the segmentation codes of which matching levels are greater than 0 into a first sub-rule set; and when the number of the rules corresponding to the segmentation codes of which a matching level is 0 is less than or equal to a first threshold, sorting the rules corresponding to the segmentation codes of which the matching level is 0 into a second sub-rule set; and when the number of the rules corresponding to the segmentation codes of which the matching level is 0 is greater than the first threshold, re-selecting a segmentation code corresponding to a largest number of the rules from the multiple segmentation codes of which the matching level is 0, and repeating the above steps to continuously divide the segmentation codes of which the matching level is 0.