Patent Document ID: 10026039
Application ID: 14497720
Patent Flag: 1

Claim One:
1. A method for generating a decision tree for packet classification, the method comprising: generating, by an apparatus, an encoded rule set according to a rule set, wherein the rule set comprises multiple rules, each rule is a string that comprises 0, 1 or a wildcard, and the strings of any two rules are not the same, the encoded rule set comprises multiple encoded rules, and the strings of any two encoded rules are not the same, each of the multiple encoded rules corresponds to at least one of the multiple rules, and each of the multiple rules corresponds to one of the multiple encoded rules, an encoded rule corresponding to a first rule is obtained by encoding the first rule according to a first function, the first rule is any one of the multiple rules, the first function is used to replace multiple segments in the first rule with multiple code segments to obtain a first encoded rule, the first rule comprises the multiple segments, each segment comprises at least one character, the first encoded rule comprises the multiple code segments, each code segment is a bit, the multiple segments are in one-to-one correspondence to the multiple code segments, a position of a first segment in the first rule is consistent with a position of a first code segment in the first encoded rule, the first segment is any one of the multiple segments, the first code segment is a code segment, corresponding to the first segment, in the multiple code segments, the first rule is a variable of the first function, the first encoded rule is a value of the first function, the first function is further used to calculate the first code segment according to the first segment, wherein in a scenario where the first segment comprises at least two characters, if the number of wildcards in the first segment is greater than or equal to N, the first code segment is 1, and, if the number of wildcards in the first segment is less than N, the first code segment is 0, wherein N is an integer greater than or equal to 1 but less than or equal to M, M is the number of symbols in the first segment, and each wildcard represents a single character, and wherein the apparatus comprises a network processor configured with a traffic classifier; generating, by the apparatus, a first weighted undirected graph, wherein the first weighted undirected graph comprises multiple vertices, the multiple vertices are in one-to-one correspondence to the multiple encoded rules, and each of the multiple vertices corresponds to a rule subset, the rule subset corresponding to a first vertex comprises all rules corresponding to the first encoded rule in the multiple rules, the first vertex is any vertex in the first weighted undirected graph, and the first encoded rule is an encoded rule, corresponding to the first vertex, in the multiple encoded rules; calculating, by the apparatus, a weight of each side in the first weighted undirected graph, wherein a side that connects any two vertices in the first weighted undirected graph is a side of the first weighted undirected graph, a weight of a first side is a value of a second function that uses a second encoded rule and a third encoded rule as variables, two vertices of the first side correspond to the second encoded rule and the third encoded rule respectively, the first side is any side in the first weighted undirected graph, and the second function is used to perform a bitwise operation for the second encoded rule and the third encoded rule and calculate the number of is in a result of the bitwise operation, wherein the number of is in the result of the bitwise operation is a value of the second function; if a weight of a side with a maximum weight in the first weighted undirected graph is greater than a first threshold, performing, by the apparatus, generation operations cyclically until a weight of a side with a maximum weight in a newly generated weighted undirected graph is less than or equal to the first threshold, wherein the first threshold is an integer greater than or equal to 0 but less than or equal to X−1, and X is the number of bits in the first encoded rule, wherein the generation operations comprise generating a new vertex according to the side with the maximum weight in the last generated weighted undirected graph among weighted undirected graphs that are generated, and generating a new weighted undirected graph according to the new vertex, wherein the new weighted undirected graph comprises the new vertex and all vertices of the last generated weighted undirected graph except two vertices of the side with the maximum weight among the weighted undirected graphs that are generated, and encoded rule corresponding to the new vertex is a value of a third function that uses a fourth encoded rule and a fifth encoded rule as variables, the fourth encoded rule and the fifth encoded rule correspond to the two vertices of the side with the maximum weight respectively in the last generated weighted undirected graph among the weighted undirected graphs that are generated, the third function is used to perform a bitwise AND operation for the fourth encoded rule and the fifth encoded rule, a result of the bitwise AND operation is a value of the third function, a rule subset corresponding to the new vertex comprises all rules in rule subsets that correspond to the two vertices of the side with the maximum weight respectively in the last generated weighted undirected graph among the weighted undirected graphs that are generated, a weight of a second side in the new weighted undirected graph is a value of a fourth function that uses a sixth encoded rule and a seventh encoded rule as variables, two vertices of the second side correspond to the sixth encoded rule and the seventh encoded rule respectively, the second side is any side in the new weighted undirected graph, and the fourth function is used to perform a bitwise operation for the sixth encoded rule and the seventh encoded rule and calculate the number of is in a result of the bitwise operation, wherein the number of is in the result of the bitwise operation is a value of the fourth function; generating, by the apparatus, a decision tree for a rule subset corresponding to each vertex respectively in the newly generated weighted undirected graph; storing, in a non-transitory memory of the apparatus, the decision tree; receiving, by a network device, an internet protocol packet, and matching, by the apparatus, a rule of the stored decision tree with a field of the received internet protocol packet; and performing an action, by the apparatus, the action corresponding to the determined rule that matches the field of the internet protocol packet, the action corresponding to passing, discarding, traffic limiting, or bandwidth guaranteeing, the internet protocol packet.