Scope in decision trees

• US 9,195,939 B1
• Filed: 03/15/2013
• Issued: 11/24/2015
• 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.
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): FINK, THOMAS ANDREW
• Application Number:
  US13/840,867
• Time in Patent Office: 984 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 successively smaller subsets of the plurality of rules with increasing depth in the decision tree data structure;

for each node of the decision tree data structure, (a) computing a node scope value indicating a node portion of the search space covered by the node;

(b) for each rule intersecting the node, computing a rule scope value indicating a rule portion of the node portion covered by the rule;

(c) comparing the node portion of the search space covered by the node to an amount of the node portion covered by rules intersecting the node by computing a scope factor for the node based on the node scope value computed and the rule scope value computed for each rule; 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 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;

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; and

computing the scope factor for the node includes averaging a ratio of the total rule scope computed for each rule to the total node scope value computed for the node.

3. The method of claim 1 wherein the node scope value increases as the node portion of the search space covered by the node increases, the node scope value decreases as the node portion of the search space covered by the node decreases, the rule scope increases as the rule portion of the node portion covered by the rule increases, and the rule scope decreases as the rule portion of the node portion covered by the rule decreases.

4. The method of claim 1 wherein computing the node scope value includes determining a 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.

5. The method of claim 1 wherein computing the rule scope value includes:

intersecting each at least one field of the rule with the node portion of the search space covered by the node to identify non-intersecting portions of the rule;

trimming the non-intersecting portions identified from each at least one field of the rule; and

determining a number of bits for enumerating all values of the search space covered by each at least one field of the rule trimmed and setting the rule scope value to a sum of the number of bits determined for each at least one field.

6. The method of claim 1 wherein computing the scope factor for the node based on the node scope value computed and the rule scope value computed for each rule represented by the node includes:

computing a ratio of the rule scope value computed for each rule represented by the node to the node scope value computed; and

determining an average value for the ratios computed.

7. The method of claim 1 further comprising:

grouping same fields of the at least one field of the plurality of rules; and

enabling access to multiple same fields grouped in a single access by storing together the same fields grouped, wherein same fields grouped have same field dimensions and are fields of different rules.

8. The method of claim 1 further comprising:

for each node of the decision tree data structure, (d) determining a number of cuts for a selected one or more fields of the at least one field, the number of cuts being based on the scope factor computed for the node;

(e) 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. The method of claim 8 further including:

for each node of the decision tree data structure, (f) traversing a list of rules represented by the node in a single sweep;

(g) assigning one or more rules from the list traversed in the single sweep to each of the child nodes created based on the one or more rules being within regions of the search space bounded by the child nodes created as a function of the cutting of the node.

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

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

13. The method of claim 11 wherein the plurality of rules have an associated priority and the search 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.

14. The method of claim 1 further comprising:

receiving an incremental update for the decision tree data structure compiled;

determining one or more updates to the decision tree data structure compiled based on the incremental update received; and

incrementally adjusting the scope factor computed for at least one node of the plurality of nodes based on the one or more updates determined.

15. The method of claim 1 wherein the compiler operation includes cutting at least one node of the plurality of nodes and the method further comprises:

creating a plurality of scope factor ranges and associating each scope factor range with a unique cutting range and a unique maximum replication factor;

for each node of the decision tree data structure, (h) identifying a scope factor range including the scope factor computed for the node;

(i) identifying the unique cutting range associated with the scope factor range identified;

(j) iteratively selecting a number of cuts from the unique cutting range identified, computing a total number of rules based on cuts of the node using the number of cuts iteratively selected, and setting a desired number of cuts to the number of cuts iteratively selected based on a comparison of the total number of rules computed divided by a number of rules represented by the node to the unique maximum replication factor associated with the scope factor range identified, wherein the desired number of cuts set is a maximum value within the unique cutting range selected based on the comparison; and

cutting the node into children using the desired number of cuts set.

16. The method of claim 15 including storing each of the plurality of scope factor ranges with an associated unique cutting range and a unique maximum replication factor, wherein iteratively selecting the number of cuts includes accessing an entry of a lookup table (LUT) associated with the scope factor range identified.

17. The method of claim 1 further including:

associating a node bitstring with the node, the node bitstring enabling enumeration of all possible values of the node, wherein the node bitstring includes zero or more don'"'"'t care bits;

for each rule of the node, associating a rule bitstring with the rule, the rule bitstring enabling enumeration of all values of the rule, wherein the rule bitstring includes zero or more don'"'"'t care bits;

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, wherein the node field scope value for each at least one field is based on a number of the zero or more don'"'"'t care bits included in the node bitstring;

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, wherein each rule intersecting the node has zero or more don'"'"'t care bits in the rule bitstring associated with the rule in a same location as a don'"'"'t care bit in the node bitstring associated with the node, and further wherein the rule scope value computed is based on the number of bit positions in which both the rule bitstring and the node bitstring have don'"'"'t-care bits; and

computing the scope factor for the node includes averaging a ratio of the total rule scope computed for each rule to the total node scope value computed for the node.

18. 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 successively smaller subsets of the plurality of rules with increasing depth in the decision tree data structure;

for each node of the decision tree data structure, (a) compute a node scope value indicating a node portion of the search space covered by the node;

(b) for each rule intersecting the node, compute a rule scope value indicating a rule portion of the node portion covered by the rule;

(c) compare the node portion of the search space covered by the node to an amount of the node portion covered by rules intersecting the node by computing a scope factor for the node based on the node scope value computed and the rule scope value computed for each rule; 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.

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

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; and

to compute the scope factor for the node the processor is further configured to average a ratio of the total rule scope computed for each rule to the total node scope value computed for the node.

20. The apparatus of claim 18 wherein the node scope value increases as the node portion of the search space covered by the node increases, the node scope value decreases as the node portion of the search space covered by the node decreases, the rule scope increases as the rule portion of the node portion covered by the rule increases, and the rule scope decreases as the rule portion of the node portion covered by the rule decreases.

21. The apparatus of claim 18 wherein to compute the node scope value, the processor is further configured to determine a number of bits to enumerate all values of the search space covered by the node on a per field basis and set the node scope value to a sum of the number of bits determined for each at least one field.

22. The apparatus of claim 18 wherein to compute the rule scope value, the processor is further configured to:

intersect each at least one field of the rule with the node portion of the search space covered by the node to identify non-intersecting portions of the rule;

trim the non-intersecting portions identified from each at least one field of the rule; and

determine a number of bits to enumerate all values of the search space covered by each at least one field of the rule trimmed and set the rule scope value to a sum of the number of bits determined for each at least one field.

23. The apparatus of claim 18 wherein to compute the scope factor for the node based on the node scope value computed and the rule scope value computed for each rule intersecting the node, the processor is further configured to:

compute a ratio of the rule scope value computed for each rule intersecting the node to the node scope value computed; and

compute an average value for the ratios computed, wherein the scope factor for the node is a function of the average value computed.

24. The apparatus of claim 18 wherein the processor is further configured to:

group same fields of the at least one field of the plurality of rules; and

enable access to multiple same fields grouped in a single access by storing together the same fields grouped, wherein same fields grouped have same field dimensions and are fields of different rules.

25. The apparatus of claim 18 wherein the processor is further configured to:

for each node of the decision tree data structure, (d) determine a number of cuts for a selected one or more fields of the at least one field, the number of cuts being based on the scope factor computed for the node;

(e) 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.

26. The apparatus of claim 25 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.

27. The apparatus of claim 25 wherein the processor is further configured to:

for each node of the decision tree data structure, (f) traverse a list of rules represented by the node in a single sweep;

(g) assign one or more rules from the list traversed in the single sweep to each of the child nodes created based on the one or more rules being within regions of the search space bounded by the child nodes created as a function of the cutting of the node.

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

29. The apparatus of claim 28 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.

30. The apparatus of claim 28 wherein the plurality of rules have an associated priority and to search for redundant rules at the at least one node the processor is further configured to:

determine 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;

omit 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

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

31. The apparatus of claim 18 wherein the processor is further configured to:

receive an incremental update for the decision tree data structure compiled;

determine one or more updates to the decision tree data structure compiled based on the incremental update received; and

incrementally adjust the scope factor computed for at least one node of the plurality of nodes based on the one or more updates determined.

32. The apparatus of claim 18 wherein the compiler operation includes cutting at least one node of the plurality of nodes and the processor is further configured to:

create a plurality of scope factor ranges and associating each scope factor range with a unique cutting range and a unique maximum replication factor;

for each node of the decision tree data structure, (h) identify a scope factor range including the scope factor computed for the node;

(i) identify a unique cutting range associated with the scope factor range identified;

(j) iteratively select a number of cuts from the unique cutting range identified, compute a total number of rules based on cuts of the node using the number of cuts iteratively selected, and set a desired number of cuts to the number of cuts iteratively selected based on a comparison of the total number of rules computed divided by a number of rules intersecting the node to the unique maximum replication factor associated with the scope factor range identified, wherein the desired number of cuts set is a maximum value within the unique cutting range selected based on the comparison; and

cut the node into children using the desired number of cuts set.

33. The apparatus of claim 32 wherein the processor is further configured to store each of the plurality of scope factor ranges with an associated unique cutting range and a unique maximum replication factor, wherein to iteratively select the number of cuts the processor is still further configured to access an entry of a lookup table LUT associated with the scope factor range identified.

34. The apparatus of claim 33 wherein the processor is further configured to:

associate a node bitstring with the node, the node bitstring enabling enumeration of all possible values of the node, wherein the node bitstring includes zero or more don'"'"'t care bits;

for each rule of the node, associate a rule bitstring with the rule, the rule bitstring enabling enumeration of all values of the rule, wherein the rule bitstring includes zero or more don'"'"'t care bits;

compute 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 sum each node field scope value computed to compute a total node scope value for the node, wherein the node field scope value for each at least one field is based on a number of the zero or more don'"'"'t care bits included in the node bitstring;

compute 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, wherein each rule intersecting the node has zero or more don'"'"'t care bits in the rule bitstring associated with the rule in a same location as a don'"'"'t care bit in the node bitstring associated with the node, and further wherein the rule scope value computed is based on the number of bit positions in which both the rule bitstring and the node bitstring have don'"'"'t-care bits; and

compute the scope factor for the node includes averaging a ratio of the total rule scope computed for each rule to the total node scope value computed for the node.

35. 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 successively smaller subsets of the plurality of rules with increasing depth in the decision tree data structure;

for each node of the decision tree data structure, (a) compute a node scope value indicating a node portion of the search space covered by the node;

(b) for each rule intersecting the node, compute a rule scope value indicating a rule portion of the node portion covered by the rule;

(c) compare the node portion of the search space covered by the node to an amount of the node portion covered by rules intersecting the node by computing a scope factor for the node based on the node scope value computed and the rule scope value computed for each rule; 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.

36. The non-transitory computer-readable medium of claim 35 wherein:

to compute the node scope value the sequence of instructions further causes the processor 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;

to compute the rule scope value, the sequence of instructions further causes the processor 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; and

to compute the scope factor for the node the sequence of instructions further causes the processor to average a ratio of the total rule scope computed for each rule to the total node scope value computed for the node.

37. The non-transitory computer-readable medium of claim 35 wherein the node scope value increases as the node portion of the search space covered by the node increases, the node scope value decreases as the node portion of the search space covered by the node decreases, the rule scope increases as the rule portion of the node portion covered by the rule increases, and the rule scope decreases as the rule portion of the node portion covered by the rule decreases.

38. The non-transitory computer-readable medium of claim 35 wherein to compute the node scope value, the sequence of instructions further causes the processor to determine a number of bits to enumerate all values of the search space covered by the node on a per field basis and set the node scope value to a sum of the number of bits determined for each at least one field.

39. The non-transitory computer-readable medium of claim 35 wherein to compute the rule scope value, the sequence of instructions further causes the processor to:

intersect each at least one field of the rule with the node portion of the search space covered by the node to identify non-intersecting portions of the rule;

trim the non-intersecting portions identified from each at least one field of the rule; and

determine a number of bits to enumerate all values of the search space covered by each at least one field of the rule trimmed and set the rule scope value to a sum of the number of bits determined for each at least one field.

40. The non-transitory computer-readable medium of claim 35 wherein to compute the scope factor for the node based on the node scope value computed and the rule scope value computed for each rule intersecting the node, the sequence of instructions further causes the processor to:

compute a ratio of the rule scope value computed for each rule intersecting the node to the node scope value computed; and

compute an average value for the ratios computed, wherein the scope factor for the node is a function of the average value computed.

41. The non-transitory computer-readable medium of claim 35 wherein the sequence of instructions further causes the processor to:

group same fields of the at least one field of the plurality of rules; and

enable access to multiple same fields grouped in a single access by storing together the same fields grouped, wherein same fields grouped have same field dimensions and are fields of different rules.

42. The non-transitory computer-readable medium of claim 35 wherein the sequence of instructions further causes the processor to:

for each node of the decision tree data structure, (d) determine a number of cuts for a selected one or more fields of the at least one field, the number of cuts being based on the scope factor computed for the node;

(e) 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.

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

44. The non-transitory computer-readable medium of claim 42 wherein the sequence of instructions further causes the processor to:

for each node of the decision tree data structure, (f) traverse a list of rules represented by the node in a single sweep;

(g) assign one or more rules from the list traversed in the single sweep to each of the child nodes created based on the one or more rules being within regions of the search space bounded by the child nodes created as a function of the cutting of the node.

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

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

47. The non-transitory computer-readable medium of claim 45 wherein the plurality of rules have an associated priority and to search for redundant rules at the at least one node, the sequence of instructions further causes the processor to:

determine 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;

omit 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

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

48. The non-transitory computer-readable medium of claim 35 wherein the sequence of instructions further causes the processor to:

receive an incremental update for the decision tree data structure compiled;

determine one or more updates to the decision tree data structure compiled based on the incremental update received; and

incrementally adjust the scope factor computed for at least one node of the plurality of nodes based on the one or more updates determined.

49. The non-transitory computer-readable medium of claim 35 wherein the compiler operation includes cutting at least one node of the plurality of nodes and the sequence of instructions further causes the processor to:

create a plurality of scope factor ranges and associate each scope factor range with a unique cutting range and a unique maximum replication factor;

for each node of the decision tree data structure, (h) identify a scope factor range including the scope factor computed for the node;

(i) identify a unique cutting range associated with the scope factor range identified;

(j) iteratively select a number of cuts from the unique cutting range identified, compute a total number of rules based on cuts of the node using the number of cuts iteratively selected, and set a desired number of cuts to the number of cuts iteratively selected based on a comparison of the total number of rules computed divided by a number of rules represented by the node to the unique maximum replication factor associated with the scope factor range identified, wherein the desired number of cuts set is a maximum value within the unique cutting range selected based on the comparison; and

cut the node into children using the desired number of cuts set.

50. The non-transitory computer-readable medium of claim 49 wherein the sequence of instructions further causes the processor to store each of the plurality of scope factor ranges with an associated unique cutting range and a unique maximum replication factor, wherein to iteratively select the number of cuts, the sequence of instructions still further causes the processor to access an entry of a lookup table (LUT) associated with the scope factor range identified.