Scope In Decision Trees

• US 20160071016A1
• Filed: 10/26/2015
• Published: 03/10/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Bullis, Kenneth A.
• Granted Patent: US 10,460,250 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/045 Explanation of inference; Explainable artificial intelligence [XAI]; Interpretable artificial intelligence

Abstract

A root node of a decision tree data structure may cover all values of a search space used for packet classification. The search space may include a plurality of rules, the plurality of rules having at least one field. The decision tree data structure may include a plurality of nodes, the plurality of nodes including a subset of the plurality of rules. Scope in the decision tree data structure may be based on comparing a portion of the search space covered by a node to a portion of the search space covered by the node'"'"'s rules. Scope in the decision tree data structure may be used to identify whether or not a compilation operation may be unproductive. By identifying an unproductive compilation operation it may be avoided, thereby improving compiler efficiency as the unproductive compilation operation may be time-consuming.

Claims

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 rule portion of the search space covered by each rule intersecting 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 a node scope value indicating a node portion of the search space covered by the node, wherein computing the node scope value includes computing a node field scope value for each at least one field covered by the node portion of the search space and summing each node field scope value computed to compute a total node scope value for the node.

3. The method of claim 1 wherein computing the scope factor includes computing a rule scope value indicating the rule portion of the search space covered by 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 each rule intersecting the node and summing each rule field scope computed to compute a total rule scope value for each rule.

4. The method of claim 1 wherein computing the scope factor for the node includes averaging a ratio of a total rule scope value computed for each rule to a total node scope value computed for the node.

5. 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.

6. The method of claim 5 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.

7. The method of claim 5 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.

8. 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.

9. The method of claim 8 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.

10. 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 rule portion of the search space covered by each rule intersecting 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.

11. The apparatus of claim 10 wherein to compute the scope factor, the processor is further configured to compute a node scope value indicating a node portion of the search space covered by the node, wherein to compute the node scope value, the processor is further configured to compute a node field scope value for each at least one field covered by the node portion of the search space and sum each node field scope value computed to compute a total node scope value for the node.

12. The apparatus of claim 10 wherein to compute the scope factor, the processor is further configured to compute a rule scope value indicating the rule portion of the search space covered by 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 each rule intersecting the node and sum each rule field scope computed to compute a total rule scope value for each rule.

13. The apparatus of claim 10 wherein to compute the scope factor for the node, the processor is further configured to average a ratio of a total rule scope value computed for each rule to a total node scope value computed for the node.

14. The apparatus of claim 10 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.

15. The apparatus of claim 14 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.

16. The apparatus of claim 14 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.

17. The apparatus of claim 10 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.

18. The apparatus of claim 17 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.

19. 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 rule portion of the search space covered by each rule intersecting 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.

20. The non-transitory computer-readable medium of claim 19 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.