Duplication in decision trees
AssigneeCavium, Inc.
InventorsRajan Goyal, Kenneth A. Bullis, Satyanarayana Lakshmipathi Billa
Life of this patent
Estimating the term…
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.
Claims63
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.
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.
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.
Dependencies are inferred from the claim text.