Identifying duplication in decision trees
First Claim
Patent Images
1. A method comprising:
- in a processor, using a classifier table having a plurality of rules, the plurality of rules having at least one field, building a decision tree structure including a plurality of nodes, each node representing a subset of the plurality of rules;
grouping rules, by the processor, based on whether or not rules overlap;
assigning, by the processor, priority values to the plurality of rules including assigning unique priority values within each group of overlapping rules and enabling non-overlapping rules to have a same priority value; and
storing, by the processor, the decision tree structure, including storing the plurality of rules and the priority value assigned, in a memory.
6 Assignments
0 Petitions
Accused Products
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. By identifying duplication in decision trees, the methods may produce wider, shallower trees that result in shorter search times and reduced memory requirements for storing the trees.
47 Citations
21 Claims
-
1. A method comprising:
-
in a processor, using a classifier table having a plurality of rules, the plurality of rules having at least one field, building a decision tree structure including a plurality of nodes, each node representing a subset of the plurality of rules; grouping rules, by the processor, based on whether or not rules overlap; assigning, by the processor, priority values to the plurality of rules including assigning unique priority values within each group of overlapping rules and enabling non-overlapping rules to have a same priority value; and storing, by the processor, the decision tree structure, including storing the plurality of rules and the priority value assigned, in a memory.
-
-
2. An apparatus comprising:
-
a memory; a processor coupled to the memory, the processor configured to; use a classifier table having a plurality of rules, the plurality of rules having at least one field; build a decision tree structure including a plurality of nodes, each node representing a subset of the plurality of rules; group rules based on whether or not rules overlap; assign priority values to the plurality of rules including assigning unique priority values within each group of overlapping rules and enabling non-overlapping rules to have a same priority value; and store the decision tree structure in the memory including storing the plurality of rules and the priority value assigned.
-
-
3. A non-transitory computer-readable medium having encoded thereon a sequence of instructions which, when executed by a processor, causes the processor to:
-
use a classifier table having a plurality of rules, the plurality of rules having at least one field; build a decision tree structure including a plurality of nodes, each node representing a subset of the plurality of rules; group rules based on whether or not rules overlap; assign priority values to the plurality of rules including assigning unique priority values within each group of overlapping rules and enabling non-overlapping rules to have a same priority value; and store the decision tree structure including storing the plurality of rules and the priority value assigned.
-
-
4. A method comprising:
-
in a processor, using a classifier table having a plurality of rules, the plurality of rules having at least one field, building a decision tree structure including a plurality of nodes, each node representing a subset of the plurality of rules; identifying, by the processor, duplication in the decision tree structure; modifying, by the processor, the decision tree structure based on the identified duplication; and storing, by the processor, the modified decision tree structure in a memory. - View Dependent Claims (5, 6, 7, 8, 9)
-
-
10. An apparatus comprising:
-
a memory; a processor coupled to the memory, the processor configured to; use a classifier table having a plurality of rules, the plurality of rules having at least one field, building a decision tree structure including a plurality of nodes, each node representing a subset of the plurality of rules; identify duplication in the decision tree structure; modify the decision tree structure based on the identified duplication; and store the modified decision tree structure in the memory. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
16. A non-transitory computer-readable medium having encoded thereon a sequence of instructions which, when executed by a processor, causes the processor to:
-
use a classifier table having a plurality of rules, the plurality of rules having at least one field, building a decision tree structure including a plurality of nodes, each node representing a subset of the plurality of rules; identify duplication in the decision tree structure; modify the decision tree structure based on the identified duplication; and store the modified decision tree structure in a memory. - View Dependent Claims (17, 18, 19, 20, 21)
-
Specification