Duplication in decision trees

• US 9,208,438 B2
• Filed: 03/14/2013
• Issued: 12/08/2015
• Est. Priority Date: 08/02/2011
• 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., Billa, Satyanarayana Lakshmipathi
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Bharadwaj, Kalpana
• Application Number:
  US13/831,487
• Publication Number:
  US 20130232104A1
• Time in Patent Office: 999 Days
• US Class Current: 1/1
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

A packet classification system, apparatus, and corresponding apparatus are provided for enabling packet classification. A processor of a security appliance coupled to a network uses a classifier table having a plurality of rules, the plurality of rules having at least one field, to build a decision tree structure for packet classification. Duplication in the decision tree may be identified, producing a wider, shallower decision tree that may result in shorter search times with reduced memory requirements for storing the decision tree. A number of operations needed to identify duplication in the decision tree may be reduced, thereby increasing speed and efficiency of a compiler building the decision tree.

Claims

1. A method comprising:

building a decision tree structure representing a plurality of rules using a classifier table having the plurality of rules, the plurality of rules having at least one field;

including a plurality of nodes in the decision tree structure, each node representing a subset of the plurality of rules, each node having a leaf node type or a non-leaf node type;

linking each node having the leaf node type to a bucket, each node having the leaf node type being a leaf node, the bucket representing the subset of the plurality of rules represented by the leaf node;

cutting each node having the non-leaf node type on one or more selected bits of a selected one or more fields of the at least one field creating one or more child nodes having the non-leaf node type or the leaf node type, each node cut being a parent node of the one or more child nodes created, the one or more child nodes created representing one or more rules of the parent node;

identifying duplication in the decision tree structure;

modifying the decision tree structure based on the identified duplication; and

storing the modified decision tree structure.

2. The method of claim 1 wherein identifying duplication includes, for each leaf node:

computing a hash value based on each rule and a total number of rules represented by the leaf node;

comparing the hash value computed to hash values associated with unique buckets and identifying no bucket duplication if none of the hash values associated with the unique buckets match the hash value computed;

validating the comparison if a given hash value associated with a given bucket of the unique buckets matches the hash value computed to provide either a confirmed or a non-confirmed result of the comparison; and

identifying bucket duplication based on the confirmed result being provided and identifying no bucket duplication based on the non-confirmed result being provided.

3. The method of claim 2 wherein modifying the decision tree structure based on the identified duplication includes:

linking the leaf node to the given bucket based on bucket duplication being identified; and

creating a new bucket representing the subset of the plurality of rules represented by the leaf node, linking the leaf node to the new bucket created, and associating the hash value computed with the new bucket created based on no bucket duplication being identified.

4. The method of claim 2 wherein validating the comparison includes:

performing a linear comparison between each rule of the leaf node and rules of the given bucket; and

providing the confirmed result based on an exact match of the performed linear comparison and providing the non-confirmed result based on a non-exact match of the performed linear comparison.

5. The method of claim 2 further including maintaining a list of all unique buckets linked to leaf nodes, wherein unique buckets are allocated buckets associated with unique hash values.

6. The method of claim 5 further including storing the unique buckets in a bucket database.

7. The method of claim 5 further including storing the unique hash values in the decision tree structure.

8. The method of claim 2 wherein normalizing each field of the at least one field of the rule against the leaf node'"'"'s range for the field is based on a field type of the field.

9. The method of claim 8 wherein if the field type is a non-mask field type, normalization includes:

intersecting the field with the leaf node'"'"'s range for the field and subtracting a lower limit of the leaf node'"'"'s range for the field from the lower and upper limits of the intersection to compute a normalized region, wherein the hash value computed is based on the normalized region computed.

10. The method of claim 8 wherein if the field type is a mask field type, normalization includes intersecting the leaf node'"'"'s description for the field with the rule'"'"'s description for the field on a bit-by-bit basis to compute a normalized region, wherein the hash value computed is based on the normalized region computed.

11. The method of claim 10 wherein the leaf node'"'"'s description and the rule'"'"'s description for the field are bitstrings representing the possible values for the field by designating each bit of a respective bitstring as a zero, one, or don'"'"'t care value and further wherein a don'"'"'t care value may be enumerated as a zero and a one for purposes of determining the possible values.

12. The method of claim 11 wherein intersecting the leaf node'"'"'s description for the field with the rule'"'"'s description for the field on a bit-by-bit basis includes applying a set of intersection rules including:

a don'"'"'t-care bit intersected with another don'"'"'t-care bit yields the don'"'"'t-care bit, a value intersected with an equal value yields the value, the don'"'"'t-care bit intersected with the value yields the value, and the value intersected with an unequal value yields an empty intersection.

13. The method of claim 1 wherein identifying duplication includes:

for each level of the decision tree, normalizing each rule of the one or more rules represented by child nodes having a same parent node to a respective rule range for a respective child node, child nodes having the same parent node being siblings;

computing a hash value for each sibling from the normalized one or more rules of the sibling and a total number of the one or more rules represented by the sibling;

comparing the computed hash values for the siblings and identifying no node duplication based on no computed hash values being compared equal;

validating the comparison based on a computed hash value for a sibling being compared equal to a computed hash value for another sibling to provide either a confirmed or a non-confirmed result of the comparison; and

identifying a duplicate node based on the confirmed result being provided and identifying no node duplication based on the non-confirmed result being provided.

14. The method of claim 13 wherein modifying the decision tree structure based on the identified duplication includes:

linking the sibling to a same subtree linked to the identified duplicate node based on the duplicate node being identified; and

creating a new subtree and linking the sibling to the new subtree based on no node duplication being identified.

15. The method of claim 13 wherein validating the comparison includes:

performing a linear comparison between each of the normalized one or more rules represented by the sibling and normalized rules represented by another sibling having the computed hash value; and

providing the confirmed result based on an exact match of the performed linear comparison and providing the non-confirmed result based on a non-exact match of the performed linear comparison.

16. The method of claim 13 wherein normalizing each rule of the one or more rules represented by the sibling includes for each rule, normalizing each field of the at least one field of the rule against the sibling'"'"'s range for the field.

17. The method of claim 16 wherein normalizing each field of the at least one field of the rule against the sibling'"'"'s range for the field is based on a field type of the field.

18. The method of claim 17 wherein if the field type is a non-mask field type, normalization includes:

intersecting the field with the sibling'"'"'s range for the field and subtracting a lower limit of the sibling'"'"'s range for the field from the lower and upper limits of the intersection to compute a normalized region, wherein the hash value computed is based on the normalized region computed.

19. The method of claim 17 wherein if the field type is a mask field type, normalization includes intersecting the sibling'"'"'s description for the field with the rule'"'"'s description for the field on a bit-by-bit basis to compute a normalized region, wherein the hash value computed is based on the normalized region computed.

20. The method of claim 19 wherein the sibling'"'"'s description and the rule'"'"'s description for the field are bitstrings representing the possible values for the field by designating each bit of a respective bitstring as a zero, one, or don'"'"'t care value and further wherein a don'"'"'t care value may be enumerated as a zero and a one for purposes of determining the possible values.

21. The method of claim 20 wherein intersecting the sibling'"'"'s description for the field with the rule'"'"'s description for the field on a bit-by-bit basis includes applying a set of intersection rules including:

a don'"'"'t-care bit intersected with another don'"'"'t-care bit yields the don'"'"'t-care bit, a value intersected with an equal value yields the value, the don'"'"'t-care bit intersected with the value yields the value, and the value intersected with an unequal value yields an empty intersection.

22. An apparatus comprising:

a memory;

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

build a decision tree structure representing a plurality of rules using a classifier table having the plurality of rules, the plurality of rules having at least one field;

include a plurality of nodes in the decision tree structure, each node representing a subset of the plurality of rules, each node having a leaf node type or a non-leaf node type;

link each node having the leaf node type to a bucket, each node having the leaf node type being a leaf node, the bucket representing the subset of the plurality of rules represented by the leaf node;

cut each node having the non-leaf node type on one or more selected bits of a selected one or more fields of the at least one field creating one or more child nodes having the non-leaf node type or the leaf node type, each node cut being a parent node of the one or more child nodes created, the one or more child nodes created representing one or more rules of the parent node;

identify duplication in the decision tree structure;

modify the decision tree structure based on the identified duplication; and

store the modified decision tree structure.

23. The apparatus of claim 22 wherein to identifying duplication the processor is further configured to, for each leaf node:

compute a hash value based on each rule and a total number of rules represented by the leaf node;

compare the hash value computed to hash values associated with unique buckets and identifying no bucket duplication if none of the hash values associated with the unique buckets match the hash value computed;

validate the comparison if a given hash value associated with a given bucket of the unique buckets matches the hash value computed to provide either a confirmed or a non-confirmed result of the comparison; and

identify bucket duplication based on the confirmed result being provided and identifying no bucket duplication based on the non-confirmed result being provided.

24. The apparatus of claim 23 wherein to modify the decision tree structure based on the identified duplication the processor is further configured to:

link the leaf node to the given bucket based on bucket duplication being identified; and

create a new bucket representing the subset of the plurality of rules represented by the leaf node, linking the leaf node to the new bucket created, and associate the hash value computed with the new bucket created based on no bucket duplication being identified.

25. The apparatus of claim 23 wherein to validate the comparison the processor is further configured to:

perform a linear comparison between each rule of the leaf node and rules of the given bucket; and

provide the confirmed result based on an exact match of the performed linear comparison and providing the non-confirmed result based on a non-exact match of the performed linear comparison.

26. The apparatus of claim 23 wherein the processor is further configured to maintain a list of all unique buckets linked to leaf nodes, wherein unique buckets are allocated buckets associated with unique hash values.

27. The apparatus of claim 26 wherein the processor is further configured to store the unique buckets in a bucket database.

28. The apparatus of claim 26 wherein the processor is further configured to store the unique hash values in the decision tree structure.

29. The apparatus of claim 23 wherein the processor is further configured to normalize each field of the at least one field of the rule against the leaf node'"'"'s range for the field is based on a field type of the field.

30. The apparatus of claim 29 wherein if the field type is a non-mask field type, the processor is further configured to:

intersect the field with the leaf node'"'"'s range for the field and subtract a lower limit of the leaf node'"'"'s range for the field from the lower and upper limits of the intersection to compute a normalized region, wherein the hash value computed is based on the normalized region computed.

31. The apparatus of claim 29 wherein if the field type is a mask field type, the processor is further configured to intersect the leaf node'"'"'s description for the field with the rule'"'"'s description for the field on a bit-by-bit basis to compute a normalized region, wherein the hash value computed is based on the normalized region computed.

32. The apparatus of claim 31 wherein the leaf node'"'"'s description and the rule'"'"'s description for the field are bitstrings representing the possible values for the field by designating each bit of a respective bitstring as a zero, one, or don'"'"'t care value and further wherein a don'"'"'t care value may be enumerated as a zero and a one for purposes of determining the possible values.

33. The apparatus of claim 31 wherein to intersect the leaf node'"'"'s description for the field with the rule'"'"'s description for the field on a bit-by-bit basis the processor is further configured to apply a set of intersection rules including:

a don'"'"'t-care bit intersected with another don'"'"'t-care bit yields the don'"'"'t-care bit, a value intersected with an equal value yields the value, the don'"'"'t-care bit intersected with the value yields the value, and the value intersected with an unequal value yields an empty intersection.

34. The apparatus of claim 22 wherein to identify duplication the processor is further configured:

for each level of the decision tree, normalize each rule of the one or more rules represented by child nodes having a same parent node to a respective rule range for a respective child node, child nodes having the same parent node being siblings;

compute a hash value for each sibling from the normalized one or more rules of the sibling and a total number of the one or more rules represented by the sibling;

compare the computed hash values for the siblings and identifying no node duplication based on no computed hash values being compared equal;

validate the comparison based on a computed hash value for a sibling being compared equal to a computed hash value for another sibling to provide either a confirmed or a non-confirmed result of the comparison; and

identify a duplicate node based on the confirmed result being provided and identifying no node duplication based on the non-confirmed result being provided.

35. The apparatus of claim 34 wherein to modifying the decision tree structure based on the identified duplication the processor is further configured:

link the sibling to a same subtree linked to the identified duplicate node based on the duplicate node being identified; and

create a new subtree and linking the sibling to the new subtree based on no node duplication being identified.

36. The apparatus of claim 34 wherein to validate the comparison the processor is further configured to:

perform a linear comparison between each of the normalized one or more rules represented by the sibling and normalized rules represented by another sibling having the computed hash value; and

provide the confirmed result based on an exact match of the performed linear comparison and providing the non-confirmed result based on a non-exact match of the performed linear comparison.

37. The apparatus of claim 34 wherein to normalize each rule of the one or more rules represented by the sibling the processor is further configured to, for each rule, normalize each field of the at least one field of the rule against the sibling'"'"'s range for the field.

38. The apparatus of claim 37 wherein the processor is further configured to normalize each field of the at least one field of the rule against the sibling'"'"'s range for the field based on a field type of the field.

39. The apparatus of claim 38 wherein if the field type is a non-mask field type, the processor is further configured to:

intersect the field with the sibling'"'"'s range for the field and subtract a lower limit of the sibling'"'"'s range for the field from the lower and upper limits of the intersection to compute a normalized region, wherein the hash value computed is based on the normalized region computed.

40. The apparatus of claim 38 wherein if the field type is a mask field type, to normalize the processor is further configured to intersect the sibling'"'"'s description for the field with the rule'"'"'s description for the field on a bit-by-bit basis to compute a normalized region, wherein the hash value computed is based on the normalized region computed.

41. The apparatus of claim 40 wherein the sibling'"'"'s description and the rule'"'"'s description for the field are bitstrings representing the possible values for the field by designating each bit of a respective bitstring as a zero, one, or don'"'"'t care value and further wherein a don'"'"'t care value may be enumerated as a zero and a one for purposes of determining the possible values.

42. The apparatus of claim 40 wherein intersecting the sibling'"'"'s description for the field with the rule'"'"'s description for the field on a bit-by-bit basis includes applying a set of intersection rules including:

a don'"'"'t-care bit intersected with another don'"'"'t-care bit yields the don'"'"'t-care bit, a value intersected with an equal value yields the value, the don'"'"'t-care bit intersected with the value yields the value, and the value intersected with an unequal value yields an empty intersection.

43. 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:

build a decision tree structure representing a plurality of rules using a classifier table having the plurality of rules, the plurality of rules having at least one field;

include a plurality of nodes in the decision tree structure, each node representing a subset of the plurality of rules, each node having a leaf node type or a non-leaf node type;

link each node having the leaf node type to a bucket, each node having the leaf node type being a leaf node, the bucket representing the subset of the plurality of rules represented by the leaf node;

cut each node having the non-leaf node type on one or more selected bits of a selected one or more fields of the at least one field creating one or more child nodes having the non-leaf node type or the leaf node type, each node cut being a parent node of the one or more child nodes created, the one or more child nodes created representing one or more rules of the parent node;

identify duplication in the decision tree structure;

modify the decision tree structure based on the identified duplication; and

store the modified decision tree structure.

44. The non-transitory computer-readable medium of claim 43 wherein to identifying duplication the sequence of instructions further causes the processor to, for each leaf node:

compute a hash value based on each rule and a total number of rules represented by the leaf node;

compare the hash value computed to hash values associated with unique buckets and identifying no bucket duplication if none of the hash values associated with the unique buckets match the hash value computed;

validate the comparison if a given hash value associated with a given bucket of the unique buckets matches the hash value computed to provide either a confirmed or a non-confirmed result of the comparison; and

identify bucket duplication based on the confirmed result being provided and identifying no bucket duplication based on the non-confirmed result being provided.

45. The non-transitory computer-readable medium of claim 44 wherein to modify the decision tree structure based on the identified duplication the sequence of instructions further causes the processor to:

link the leaf node to the given bucket based on bucket duplication being identified; and

create a new bucket representing the subset of the plurality of rules represented by the leaf node, linking the leaf node to the new bucket created, and associate the hash value computed with the new bucket created based on no bucket duplication being identified.

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

perform a linear comparison between each rule of the leaf node and rules of the given bucket; and

provide the confirmed result based on an exact match of the performed linear comparison and providing the non-confirmed result based on a non-exact match of the performed linear comparison.

47. The non-transitory computer-readable medium of claim 44 wherein the sequence of instructions further causes the processor to maintain a list of all unique buckets linked to leaf nodes, wherein unique buckets are allocated buckets associated with unique hash values.

48. The non-transitory computer-readable medium of claim 47 wherein the sequence of instructions further causes the processor to store the unique buckets in a bucket database.

49. The non-transitory computer-readable medium of claim 47 wherein the sequence of instructions further causes the processor to store the unique hash values in the decision tree structure.

50. The non-transitory computer-readable medium of claim 44 wherein the sequence of instructions further causes the processor to normalize each field of the at least one field of the rule against the leaf node'"'"'s range for the field is based on a field type of the field.

51. The non-transitory computer-readable medium of claim 50 wherein if the field type is a non-mask field type, the sequence of instructions further causes the processor to:

intersect the field with the leaf node'"'"'s range for the field and subtract a lower limit of the leaf node'"'"'s range for the field from the lower and upper limits of the intersection to compute a normalized region, wherein the hash value computed is based on the normalized region computed.

52. The non-transitory computer-readable medium of claim 50 wherein if the field type is a mask field type, the sequence of instructions further causes the processor to intersect the leaf node'"'"'s description for the field with the rule'"'"'s description for the field on a bit-by-bit basis to compute a normalized region, wherein the hash value computed is based on the normalized region computed.

53. The non-transitory computer-readable medium of claim 52 wherein the leaf node'"'"'s description and the rule'"'"'s description for the field are bitstrings representing the possible values for the field by designating each bit of a respective bitstring as a zero, one, or don'"'"'t care value and further wherein a don'"'"'t care value may be enumerated as a zero and a one for purposes of determining the possible values.

54. The non-transitory computer-readable medium of claim 52 wherein to intersect the leaf node'"'"'s description for the field with the rule'"'"'s description for the field on a bit-by-bit basis the sequence of instructions further causes the processor to apply a set of intersection rules including:

a don'"'"'t-care bit intersected with another don'"'"'t-care bit yields the don'"'"'t-care bit, a value intersected with an equal value yields the value, the don'"'"'t-care bit intersected with the value yields the value, and the value intersected with an unequal value yields an empty intersection.

55. The non-transitory computer-readable medium of claim 43 wherein to identify duplication the processor is further configured:

for each level of the decision tree, normalize each rule of the one or more rules represented by child nodes having a same parent node to a respective rule range for a respective child node, child nodes having the same parent node being siblings;

compute a hash value for each sibling from the normalized one or more rules of the sibling and a total number of the one or more rules represented by the sibling;

compare the computed hash values for the siblings and identifying no node duplication based on no computed hash values being compared equal;

validate the comparison based on a computed hash value for a sibling being compared equal to a computed hash value for another sibling to provide either a confirmed or a non-confirmed result of the comparison; and

identify a duplicate node based on the confirmed result being provided and identifying no node duplication based on the non-confirmed result being provided.

56. The non-transitory computer-readable medium of claim 55 wherein to modifying the decision tree structure based on the identified duplication the processor is further configured:

link the sibling to a same subtree linked to the identified duplicate node based on the duplicate node being identified; and

create a new subtree and linking the sibling to the new subtree based on no node duplication being identified.

57. The non-transitory computer-readable medium of claim 55 wherein to validate the comparison the sequence of instructions further causes the processor to:

perform a linear comparison between each of the normalized one or more rules represented by the sibling and normalized rules represented by another sibling having the computed hash value; and

provide the confirmed result based on an exact match of the performed linear comparison and providing the non-confirmed result based on a non-exact match of the performed linear comparison.

58. The non-transitory computer-readable medium of claim 55 wherein to normalize each rule of the one or more rules represented by the sibling the sequence of instructions further causes the processor to, for each rule, normalize each field of the at least one field of the rule against the sibling'"'"'s range for the field.

59. The non-transitory computer-readable medium of claim 58 wherein the sequence of instructions further causes the processor to normalize each field of the at least one field of the rule against the sibling'"'"'s range for the field based on a field type of the field.

60. The non-transitory computer-readable medium of claim 59 wherein if the field type is a non-mask field type, the sequence of instructions further causes the processor to:

intersect the field with the sibling'"'"'s range for the field and subtract a lower limit of the sibling'"'"'s range for the field from the lower and upper limits of the intersection to compute a normalized region, wherein the hash value computed is based on the normalized region computed.

61. The non-transitory computer-readable medium of claim 59 wherein if the field type is a mask field type, to normalize the sequence of instructions further causes the processor to intersect the sibling'"'"'s description for the field with the rule'"'"'s description for the field on a bit-by-bit basis to compute a normalized region, wherein the hash value computed is based on the normalized region computed.

62. The non-transitory computer-readable medium of claim 61 wherein the sibling'"'"'s description and the rule'"'"'s description for the field are bitstrings representing the possible values for the field by designating each bit of a respective bitstring as a zero, one, or don'"'"'t care value and further wherein a don'"'"'t care value may be enumerated as a zero and a one for purposes of determining the possible values.

63. The non-transitory computer-readable medium of claim 61 wherein intersecting the sibling'"'"'s description for the field with the rule'"'"'s description for the field on a bit-by-bit basis includes applying a set of intersection rules including:

a don'"'"'t-care bit intersected with another don'"'"'t-care bit yields the don'"'"'t-care bit, a value intersected with an equal value yields the value, the don'"'"'t-care bit intersected with the value yields the value, and the value intersected with an unequal value yields an empty intersection.