Compiler with mask nodes

• US 9,595,003 B1
• Filed: 05/17/2013
• Issued: 03/14/2017
• 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: Bullis, Kenneth A., Goyal, Rajan
• Primary Examiner(s): Rifkin, Ben
• Application Number:
  US13/896,798
• Time in Patent Office: 1,397 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

A packet classification system, methods, 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 including a plurality of nodes, the plurality of nodes including a subset of the plurality of rules. The plurality of nodes may be stride nodes, mask nodes, or a combination thereof. A mask node may remove restrictions of stride nodes, such as markers and consumption of contiguous bits. As long as a bit of a field is a non-consumed bit, the bit may be used for cutting a field in a mask node. An advantage of a mask node is that the mask node may consume fewer resources (e.g., memory) than a stride node.

Claims

1. A method comprising:

building a decision tree structure including a plurality of nodes using a classifier table having a plurality of rules representing a search space, the plurality of rules having at least one field, each node representing a subset of the search space;

building the decision tree structure including, at each node, (a) dividing the subset of the search space represented by the node into smaller subsets by (i) determining a node type for the node, the node type determination enabling a combination of node types in the decision tree structure, (ii) selecting one or more fields of the at least one field and selecting one or more bits of the selected one or more fields based on the node type determined for the node, a node type of a parent node of the node, and a consumed bit indicator for the node, the consumed bit indicator specifying all bits consumed for search space division by each ancestor of the node, and (iii) cutting the node into child nodes on the selected one or more bits to create the smaller subsets and allocating the created smaller subsets to the child nodes;

(b) updating the consumed bit indicator to specify the selected one or more bits as utilized and associating the updated consumed bit indicator with each of the child nodes; and

storing the built decision tree structure.

2. The method of claim 1 wherein determining the node type for the node includes selecting the node type from a set of node types including at least a mask node type and a stride node type.

3. The method of claim 2 wherein selecting the one or more bits of the selected one or more fields includes:

given the selected mask node type, enabling an arbitrary contiguous or non-contiguous selection of the one or more bits from a set of bits including all non-consumed bits for search space subdivision by each ancestor of the node; and

given the selected stride node type, constraining selection of the one or more bits to one or more contiguous non-consumed bits adjacent to and of lesser significance than a least significant consumed bit specified by the consumed bit indicator.

4. The method of claim 2 wherein the consumed bit indicator for the selected mask node type is a bit mask representing a consumed state for each bit in the selected one or more fields and further wherein the consumed bit indicator for the selected stride node type includes a bit location marker indicating a bit location of a most significant non-consumed bit.

5. The method of claim 2 wherein the built decision tree structure includes at least one node with the selected mask node type or at least one node with the selected stride node type or a combination thereof.

6. The method of claim 2 wherein in an event the stride node type is selected and the node type of the parent node is the mask node type, cutting the node into child nodes on the selected one or more bits includes selecting a first bit of the selected one or more bits, the first bit used to cut being adjacent to and of lesser significance than a least significant bit used to cut the parent node of the node.

7. The method of claim 1 wherein cutting the node into child nodes on the selected one or more bits includes:

for each child node, creating a node description for the child node based on the selected one or more bits, wherein the node description is a mask represented as a bitstring including ones, zeroes, or don'"'"'t care bits, or a combination thereof, in arbitrary bit locations of the mask and the mask is a one-dimensional or multi-dimensional mask; and

computing on a bit-by-bit basis an intersection between the node description for the child node and rules represented by the node to determine a set of intersecting rules and assigning the set of intersecting rules determined to the child.

8. The method of claim 7 wherein computing on the bit-by-bit basis the intersection of all rules belonging to the node with the node description of the child node includes applying on the bit-by-bit basis 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, and further wherein a given rule of the node intersects the child node if the computed intersection for the given rule with a rule of the child node is non-empty.

9. The method of claim 7 further including for each child node, determining a redundancy status for each intersecting rule in the determined set of intersecting rules for the child node.

10. The method of claim 9 wherein determining the redundancy status for each intersecting rule for each child node includes comparing each intersecting rule with each rule of higher priority in the determined set using a bit-by-bit basis comparison for each pair of rules compared, wherein (iv) if the intersecting rule and the rule of higher priority have differing values for a corresponding bit, the redundancy status for the intersecting rule is non-redundant, (v) if the rule of higher priority has a non-don'"'"'t-care value for a particular bit and the intersecting rule has a don'"'"'t-care value for the particular bit, the redundancy status for the intersecting rule is non-redundant, and (vi) if neither (iv) nor (v) apply at any bit, the redundancy status for the intersecting rule is redundant and the rule of higher priority is identified as a covering rule for the intersecting rule, the method further including:

for each child node, omitting each intersecting rule having the redundant redundancy status and populating a cover list associated with the child node and the covering rule identified for the omitted intersecting rule.

11. An apparatus comprising:

a memory;

a processor coupled to the memory, the processor configured to build a decision tree structure including a plurality of nodes using a classifier table having a plurality of rules representing a search space, the plurality of rules having at least one field, each node representing a subset of the search space;

to build the decision tree structure, the processor further configured to, at each node, (a) divide the subset of the search space represented by the node into smaller subsets by (i) determining a node type for the node, the node type determination enabling a combination of node types in the decision tree structure, (ii) selecting one or more fields of the at least one field and selecting one or more bits of the selected one or more fields based on the node type determined for the node, a node type of a parent node of the node, and a consumed bit indicator for the node, the consumed bit indicator specifying all bits consumed for search space division by each ancestor of the node, and (iii) cutting the node into child nodes on the selected one or more bits to create the smaller subsets and allocating the created smaller subsets to the child nodes;

(b) update the consumed bit indicator to specify the selected one or more bits as utilized and associating the updated consumed bit indicator with each of the child nodes; and

store the built decision tree structure in the memory.

12. The apparatus of claim 11 wherein to determine the node type for the node, the processor is further configured to select the node type from a set of node types including at least a mask node type and a stride node type.

13. The apparatus of claim 12 wherein to select the one or more bits of the selected one or more fields, the processor is further configured to:

given the selected mask node type, enable an arbitrary contiguous or non-contiguous selection of the one or more bits from a set of bits including all non-consumed bits for search space subdivision by each ancestor of the node; and

given the selected stride node type, constrain selection of the one or more bits to one or more contiguous non-consumed bits adjacent to and of lesser significance than a least significant consumed bit specified by the consumed bit indicator.

14. The apparatus of claim 12 wherein the consumed bit indicator for the selected mask node type is a bit mask representing a consumed state for each bit in the selected one or more fields and further wherein the consumed bit indicator for the selected stride node type includes a bit location marker indicating a bit location of a most significant non-consumed bit.

15. The apparatus of claim 12 wherein the built decision tree structure includes at least one node with the selected mask node type or at least one node with the selected stride node type or a combination thereof.

16. The apparatus of claim 12 wherein in an event the stride node type is selected and the node type of the parent node is the mask node type, the processor is further configured to cut the node into child nodes on the selected one or more bits and select a first bit of the selected one or more bits, the first bit used to cut being adjacent to and of lesser significance than a least significant bit used to cut the parent node of the node.

17. The apparatus of claim 11 wherein to cut the node into child nodes on the selected one or more bits the processor is further configured to:

for each child node, create a node description for the child node based on the selected one or more bits, wherein the node description is a mask represented as a bitstring including ones, zeroes, or don'"'"'t care bits, or a combination thereof, in arbitrary bit locations of the mask and the mask is a one-dimensional or multi-dimensional mask; and

compute on a bit-by-bit basis an intersection between the node description for the child node and rules represented by the node to determine a set of intersecting rules and assign the set of intersecting rules determined to the child.

18. The apparatus of claim 17 wherein to compute the intersection of all rules belonging to the node with the node description of the child node on the 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, and further wherein a given rule of the node intersects the child node if the computed intersection for the given rule with a rule of the child node is non-empty.

19. The apparatus of claim 17 wherein the processor is further configured to for each child node, determine a redundancy status for each intersecting rule in the determined set of intersecting rules for the child node.

20. The apparatus of claim 19 wherein to determine the redundancy status for each intersecting rule for each child node, the processor is further configured to compare each intersecting rule with each rule of higher priority in the determined set using a bit-by-bit basis comparison for each pair of rules compared, wherein (iv) if the intersecting rule and the rule of higher priority have differing values for a corresponding bit, the redundancy status for a lower priority rule of the compared pair of rules is non-redundant, (v) if the rule of higher priority has a non-don'"'"'t-care value for a particular bit and the intersecting rule has a don'"'"'t-care value for the particular bit, the redundancy status for the intersecting rule is non-redundant, and (vi) if neither (iv) nor (v) apply at any bit, the redundancy status for the intersecting rule is redundant and the rule of higher priority is identified as a covering rule for the intersecting rule, the processor further configured to:

for each child node, omit each intersecting rule having the redundant redundancy status and populate a cover list associated with the child node and the covering rule identified for the omitted intersecting rule.

21. 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 including a plurality of nodes using a classifier table having a plurality of rules representing a search space, the plurality of rules having at least one field, each node representing a subset of the search space;

build the decision tree structure, the sequence of instructions further causing the processor to, at each node, (a) divide the subset of the search space represented by the node into smaller subsets by (i) determining a node type for the node, the node type determination enabling a combination of node types in the decision tree structure, (ii) selecting one or more fields of the at least one field and selecting one or more bits of the selected one or more fields based on the node type determined for the node, a node type of a parent node of the node, and a consumed bit indicator for the node, the consumed bit indicator specifying all bits consumed for search space division by each ancestor of the node, and (iii) cutting the node into child nodes on the selected one or more bits to create the smaller subsets and allocating the created smaller subsets to the child nodes;

(b) update the consumed bit indicator to specify the selected one or more bits as utilized and associating the updated consumed bit indicator with each of the child nodes; and

store the built decision tree structure in a memory.

22. The non-transitory computer-readable medium of claim 21 wherein to determine the node type for the node, the sequence of instructions further causes the processor to select the node type from a set of node types including at least a mask node type and a stride node type.

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

given the selected mask node type, enable an arbitrary contiguous or non-contiguous selection of the one or more bits from a set of bits including all non-consumed bits for search space subdivision by each ancestor of the node; and

given the selected stride node type, constrain selection of the one or more bits to one or more contiguous non-consumed bits adjacent to and of lesser significance than a least significant consumed bit specified by the consumed bit indicator.

24. The non-transitory computer-readable medium of claim 22 wherein the consumed bit indicator for the selected mask node type is a bit mask representing a consumed state for each bit in the selected one or more fields and further wherein the consumed bit indicator for the selected stride node type includes a bit location marker indicating a bit location of a most significant non-consumed bit.

25. The non-transitory computer-readable medium of claim 22 wherein the built decision tree structure includes at least one node with the selected mask node type or at least one node with the selected stride node type or a combination thereof.

26. The non-transitory computer-readable medium of claim 22 wherein in an event the stride node type is selected and the node type of the parent node is the mask node type, the sequence of instructions further causes the processor to cut the node into child nodes on the selected one or more bits and select a first bit of the selected one or more bits, the first bit used to cut being adjacent to and of lesser significance than a least significant bit used to cut the parent node of the node.

27. The non-transitory computer-readable medium of claim 21 wherein to cut the node into child nodes on the selected one or more bits, the sequence of instructions further causes the processor to:

for each child node, create a node description for the child node based on the selected one or more bits, wherein the node description is a mask represented as a bitstring including ones, zeroes, or don'"'"'t care bits, or a combination thereof, in arbitrary bit locations of the mask and the mask is a one-dimensional or multi-dimensional mask; and

compute on a bit-by-bit basis an intersection between the node description for the child node and rules represented by the node to determine a set of intersecting rules and assign the set of intersecting rules determined to the child.

28. The non-transitory computer-readable medium of claim 27 wherein to compute the intersection of all rules belonging to the node with the node description of the child node on the 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, and further wherein a given rule of the node intersects the child node if the computed intersection for the given rule with a rule of the child node is non-empty.

29. The non-transitory computer-readable medium of claim 27 wherein the sequence of instructions further causes the processor to for each child node, determine a redundancy status for each intersecting rule in the determined set of intersecting rules for the child node.

30. The non-transitory computer-readable medium of claim 29 wherein to determine the redundancy status for each intersecting rule, the sequence of instructions further causes the processor to compare each intersecting rule with each rule of higher priority in the determined set using a bit-by-bit basis comparison for each pair of rules compared, wherein (iv) if the intersecting rule and the rule of higher priority have differing values for a corresponding bit, the redundancy status for the intersecting rule is non-redundant, (v) if the rule of higher priority has a non-don'"'"'t-care value for a particular bit and the intersecting rule has a don'"'"'t-care value for the particular bit, the redundancy status for the intersecting rule is non-redundant, and (vi) if neither (iv) nor (ii) (v) apply at any bit, the redundancy status for the intersecting rule is redundant and the rule of higher priority is identified as a covering rule for the intersecting rule, wherein the sequence of instructions still further causes the processor to:

for each child node, omit each intersecting rule having the redundant redundancy status and populate a cover list associated with the child node and the covering rule identified for the omitted intersecting rule.