Granted Patent B2

US 10,460,250 · App. 14/922,449 · Granted Oct 29, 2019

Abstract

Claims (43)

1. A method comprising:

compiling a decision tree data structure including a plurality of nodes using a classifier table having a plurality of rules representing a search space for packet classification, the plurality of rules having at least one field, the plurality of nodes each covering a portion of the search space by representing subsets of the plurality of rules;

for each node of the decision tree data structure, computing a scope factor for the node based on (a) a node scope value computed for the node, the node scope value indicating a node portion of the search space covered by the node, the node scope value computed by determining a minimum number of bits for enumerating all values of the search space covered by the node on a per field basis and setting the node scope value to a sum of the minimum number of bits determined for each at least one field, and (b) a rule scope value computed for each rule intersecting the node, the rule scope value indicating a rule portion of the node portion covered by the node; and

using the scope factor computed for at least one node of the plurality of nodes as an input parameter to a decision for performing a compiler operation at the at least one node.

2. The method of claim 1 wherein computing the scope factor includes computing the rule scope value for each rule intersecting the node, wherein computing the rule scope value includes computing a rule field scope value for each at least one field of the rule intersecting the node and summing each rule field scope computed to compute a total rule scope value for the rule intersecting the node.

3. The method of claim 1 wherein computing the scope factor for the node includes computing an average rule scope of the node by averaging the rule scope value computed for each rule and computing a ratio of the average rule scope to the node scope value computed for the node.

4. The method of claim 1 wherein the compiler operation includes searching for redundant rules at the at least one node and the decision for performing the compiler operation at the at least one node is based on a comparison of the scope factor computed to a given threshold.

5. The method of claim 4 wherein the comparison of the scope factor computed to the given threshold enables avoiding a time-consuming unproductive search for redundant rules at the at least one node.

6. The method of claim 4 wherein the plurality of rules have an associated priority and searching for redundant rules at the at least one node includes:

determining whether or not a given rule represented by the at least one node is covered by one or more other higher priority rules represented by the at least one node;

omitting the given rule from the at least one node and other nodes cut from the at least one node if the given rule is covered; and

populating one or more cover lists for the one or more higher priority rules to include the given rule omitted, the one or more cover lists each being associated with the at least one node.

7. The method of claim 1 further comprising:

for each node of the decision tree data structure:

determining a number of cuts for a selected one or more fields of the at least one field, wherein the number of cuts is based on the scope factor computed for the node;

creating child nodes by cutting the node on a selected one or more bits of the selected one or more fields based on the number of cuts determined; and

storing the decision tree data structure.

8. The method of claim 7 wherein the number of cuts determined increases as the scope factor computed decreases and the number of cuts determined decreases as the scope factor computed increases.

9. An apparatus comprising:

a memory;

a processor coupled to the memory, the processor configured to:

compile a decision tree data structure including a plurality of nodes using a classifier table having a plurality of rules representing a search space for packet classification, the plurality of rules having at least one field, the plurality of nodes each covering a portion of the search space by representing subsets of the plurality of rules;

for each node of the decision tree data structure, compute a scope factor for the node based on (a) a node scope value computed for the node, the node scope value indicating a node portion of the search space covered by the node, the node scope value computed by determining a minimum number of bits for enumerating all values of the search space covered by the node on a per field basis and setting the node scope value to a sum of the minimum number of bits determined for each at least one field, and (b) a rule scope value computed for each rule intersecting the node, the rule scope value indicating a rule portion of the node portion covered by the node; and

use the scope factor computed for at least one node of the plurality of nodes as an input parameter to a decision for performing a compiler operation at the at least one node.

10. The apparatus of claim 9 wherein to compute the scope factor, the processor is further configured to compute the rule scope value for each rule intersecting the node, wherein to compute the rule scope value, the processor is further configured to compute a rule field scope value for each at least one field of the rule intersecting the node and sum each rule field scope computed to compute a total rule scope value for the rule intersecting the node.

11. The apparatus of claim 9 wherein to compute the scope factor for the node, the processor is further configured to compute an average rule scope of the node by averaging the rule scope value computed for each rule and compute a ratio of the average rule scope to the node scope value computed for the node.

12. The apparatus of claim 9 wherein the compiler operation includes searching for redundant rules at the at least one node and the decision for performing the compiler operation at the at least one node is based on a comparison of the scope factor computed to a given threshold.

13. The apparatus of claim 12 wherein the comparison of the scope factor computed to the given threshold enables avoiding a time-consuming unproductive search for redundant rules at the at least one node.

14. The apparatus of claim 12 wherein the plurality of rules have an associated priority and searching for redundant rules at the at least one node includes:

determining whether or not a given rule represented by the at least one node is covered by one or more other higher priority rules represented by the at least one node;

omitting the given rule from the at least one node and other nodes cut from the at least one node if the given rule is covered; and

populating one or more cover lists for the one or more higher priority rules to include the given rule omitted, the one or more cover lists each being associated with the at least one node.

15. The apparatus of claim 9 wherein the processor is further configured to:

for each node of the decision tree data structure:

determine a number of cuts for a selected one or more fields of the at least one field, wherein the number of cuts is based on the scope factor computed for the node;

create child nodes by cutting the node on a selected one or more bits of the selected one or more fields based on the number of cuts determined; and

store the decision tree data structure.

16. The apparatus of claim 15 wherein the number of cuts determined increases as the scope factor computed decreases and the number of cuts determined decreases as the scope factor computed increases.

17. A non-transitory computer-readable medium having encoded thereon a sequence of instructions which, when loaded and executed by a processor, causes the processor to:

compile a decision tree data structure including a plurality of nodes using a classifier table having a plurality of rules representing a search space for packet classification, the plurality of rules having at least one field, the plurality of nodes each covering a portion of the search space by representing subsets of the plurality of rules;

for each node of the decision tree data structure, compute a scope factor for the node based on (a) a node scope value computed for the node, the node scope value indicating a node portion of the search space covered by the node, the node scope value computed by determining a minimum number of bits for enumerating all values of the search space covered by the node on a per field basis and setting the node scope value to a sum of the minimum number of bits determined for each at least one field, and (b) a rule scope value computed for each rule intersecting the node, the rule scope value indicating a rule portion of the node portion covered by the node; and

use the scope factor computed for at least one node of the plurality of nodes as an input parameter to a decision for performing a compiler operation at the at least one node.

18. The non-transitory computer-readable medium of claim 17 wherein the compiler operation includes searching for redundant rules at the at least one node and the decision for performing the compiler operation at the at least one node is based on a comparison of the scope factor computed to a given threshold, wherein the comparison of the scope factor computed to the given threshold enables avoiding a time-consuming unproductive search for redundant rules at the at least one node.

Assignments (6)