Packet Classification
First Claim
Patent Images
1. A method comprising:
- in a processor, building a decision tree structure including a plurality of nodes, each node representing a subset of a plurality of rules having at least one field; and
for at least one node of the decision tree, determining a number of cuts that may be made on each at least one field creating child nodes equal to the number of cuts and selecting a field on which to cut the at least one node based on a comparison of an average of a difference between an average number of rules per child node created and an actual number of rules per child node created per each at least one field.
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. The methods may produce wider, shallower trees that result in shorter search times and reduced memory requirements for storing the trees.
-
Citations
21 Claims
-
1. A method comprising:
-
in a processor, building a decision tree structure including a plurality of nodes, each node representing a subset of a plurality of rules having at least one field; and for at least one node of the decision tree, determining a number of cuts that may be made on each at least one field creating child nodes equal to the number of cuts and selecting a field on which to cut the at least one node based on a comparison of an average of a difference between an average number of rules per child node created and an actual number of rules per child node created per each at least one field. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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, each node representing a subset of a plurality of rules having at least one field; and the processor further configured to determine, for at least one node of the decision tree, a number of cuts that may be made on each at least one field creating child nodes equal to the number of cuts and to select a field on which to cut the at least one node based on a comparison of an average of a difference between an average number of rules per child node created and an actual number of rules per child node created per each at least one field. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
19. A non-transitory computer-readable medium having encoded thereon a sequence of instructions which, when executed by a processor, causes the processor to:
-
build a decision tree structure including a plurality of nodes, each node representing a subset of a plurality of rules having at least one field; determine, for at least one node of the decision tree, a number of cuts that may be made on each at least one field creating child nodes equal to the number of cuts; select a field on which to cut the at least one node based on a comparison of an average of a difference between an average number of rules per child node created and an actual number of rules per child node created per each at least one field; cut the at least one node into a number of child nodes on the selected at least field; and store the decision tree structure.
-
-
20. A method comprising:
-
in a processor, building a decision tree structure including a plurality of nodes, each node representing a subset of a plurality of rules having at least one field; and for at least one node of the decision tree, determining a number of cuts that may be made on each at least one field creating child nodes equal to the number of cuts and selecting a field on which to cut the at least one node.
-
-
21. 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, each node representing a subset of a plurality of rules having at least one field; and the processor further configured to determine, for at least one node of the decision tree, a number of cuts that may be made on each at least one field creating child nodes equal to the number of cuts and to select a field on which to cut the at least one node.
-
Specification