Method for classifying packets using multi-class structures
First Claim
Patent Images
1. A method comprising:
- reading a classification policy that specifies a plurality of classes, each class associated with one or more matching rules;
generating a super class that includes the matching rules associated with the plurality of classes;
converting the matching rules in the super class into a hierarchical arrangement of lookup tables and associated equivalence sets, the hierarchical arrangement having a first level and a final level, the final level associated with a final equivalence set;
associating each entry in the final equivalence set with one of the classes of the plurality of classes;
applying a network packet to each level of the hierarchical arrangement of lookup tables to generate indexes into subsequent levels of the hierarchical arrangement of lookup tables, and ultimately to generate an index into the final equivalence set; and
applying the index to the final equivalence set to yield a particular entry that indicates the network packet is associated with a particular class.
1 Assignment
0 Petitions
Accused Products
Abstract
In one embodiment, a super class that contains a plurality of matching rules is generated. The matching rules of the super class are converted into a hierarchical arrangement of lookup tables and equivalence sets, the hierarchical arrangement having a plurality of levels including a first level and a final level. A final equivalence set is associated with the final level. The lookup tables and final equivalence set are then used to generate a results table that indicates a network packet is associated with a particular class.
-
Citations
20 Claims
-
1. A method comprising:
-
reading a classification policy that specifies a plurality of classes, each class associated with one or more matching rules; generating a super class that includes the matching rules associated with the plurality of classes; converting the matching rules in the super class into a hierarchical arrangement of lookup tables and associated equivalence sets, the hierarchical arrangement having a first level and a final level, the final level associated with a final equivalence set; associating each entry in the final equivalence set with one of the classes of the plurality of classes; applying a network packet to each level of the hierarchical arrangement of lookup tables to generate indexes into subsequent levels of the hierarchical arrangement of lookup tables, and ultimately to generate an index into the final equivalence set; and applying the index to the final equivalence set to yield a particular entry that indicates the network packet is associated with a particular class. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. An apparatus comprising:
-
a memory configured to store a classification policy that specifies a plurality of classes, each class associated with one or more matching rules; a processor configured to generate a super class that includes the matching rules associated with the plurality of classes, convert the matching rules in the super class into a hierarchical arrangement of lookup tables and associated equivalence sets, the hierarchical arrangement having a first level and a final level, the final level associated with a final equivalence set, the processor further configured to associate each entry in the final equivalence set with one of the classes of the plurality of classes; and a packet memory configured to store a network packet; wherein the processor is further configured to apply the network packet to each level of the hierarchical arrangement of lookup tables to generate indexes into subsequent levels of the hierarchical arrangement of lookup tables, and ultimately to generate an index into the final equivalence set, and the processor father configured to apply the index to the final equivalence set to yield a particular entry that indicates the network packet is associated with a particular class. - View Dependent Claims (8, 9, 10, 11)
-
-
12. An apparatus comprising:
-
means for reading a policy that specifies a plurality of classes, each class associated with one or more matching rules; means for generating a super class that includes the matching rules associated with the plurality of classes; means for converting the matching rules in the super class into a hierarchical arrangement of lookup tables and associated equivalence sets, the hierarchical arrangement having a first level and a final level, the final level associated with a final equivalence set; means for associating each entry in the final equivalence set with one of the classes of the plurality of classes; means for applying a network packet to each level of the hierarchical arrangement of lookup tables, to generate indexes into subsequent levels of the hierarchical arrangement of lookup tables, and ultimately to generate an index into the final equivalence set; and means for applying the index to the final equivalence set to yield a particular entry that indicates the network packet is associated with a particular class.
-
-
13. An apparatus comprising:
-
a processor configured to read a classification policy that specifies a plurality of classes, each class associated with one or more matching rules, the processor further configured to generate a super class that contains the matching rules associated with the classes, the super class including for each class a class name that identifies the class, a class criterion associated with the class, and a representation of the one or more matching rules associated with the class; and a memory configured to store the super class as well as a hierarchical arrangement of lookup tables and associated equivalence sets generated by the processor from the super class, the hierarchical arrangement having a plurality of levels including a first level and a final level, a final equivalence set being associated with the final level. - View Dependent Claims (14, 15, 16, 17, 18)
-
-
19. An apparatus comprising:
-
a memory; a processor coupled to the memory, the processor configured to generate a super class that contains a plurality of matching rules and to convert the matching rules of the super class into a hierarchical arrangement of lookup tables and equivalence sets, the hierarchical arrangement having a plurality of levels including a first level and a final level, a final equivalence set associated with the final level, the processor further configured to place the lookup tables and final equivalence set in the memory and to generate a results table from the entries in the final equivalence set and place the results table in the memory. - View Dependent Claims (20)
-
Specification