US7415023B2
Active / In Force
US
⏱️ 0.1 years remaining
Method for classifying packets using multi-class structures
Assignee: Cisco Technology Inc
•
Filing: 2006-11-30
•
Granted: 2008-08-19
•
Expires: 2026-11-30
Abstract
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.
Inventors
- 👤 Liang Li
- 👤 Thanh Trung Dao
- 👤 Andrew A. McRae
- 👤 Hugh Nhan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 13:16
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/74; H04L45/742; H04L47/00; H04L47/10; H04L47/17; H04L47/24; H04L47/2441; H04L47/43; H04L63/00; H04L63/10; H04L63/101; H04L63/02; H04L63/0227
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
157 words
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.
Claim 2
Independent Claim
157 words
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.
Claim 3
Dependent Claim
29 words
The method of claim 1 , wherein the super class comprises for each matching rule: a class name that identifies that class; a class criterion associated with that class.
Claim 4
Dependent Claim
41 words
The method of claim 1 , wherein the step of applying a network packet further comprises: dividing the network packet into a plurality of sections; and applying each section to a different lookup table of the first level of lookup tables.
Claim 5
Dependent Claim
36 words
The method of claim 1 , wherein the step of converting further comprises: merging two or more first level lookup tables and associated equivalence sets to produce a next level lookup table and associated equivalence set.
Claim 6
Dependent Claim
36 words
The method of claim 4 , wherein the step of converting further comprises: merging two or more next level lookup tables and associated equivalence sets to produce the final level lookup table and associated equivalence set.
Claim 7
Dependent Claim
43 words
The method of claim 1 , further comprising: transferring the hierarchical arrangement of lookup tables and the final equivalence set to a separate network device; and wherein the separate network device implements the steps of applying a network packet and applying the index.
Claim 8
Independent Claim
192 words
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.
Claim 9
Independent Claim
192 words
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.
Claim 10
Dependent Claim
30 words
The apparatus of claim 7 , wherein the super class comprises for each matching rule: a class name that identifies that class; and a class criterion associated with that class.
Claim 11
Dependent Claim
39 words
The apparatus of claim 7 , wherein the processor is further configured to divide the network packet into a plurality of sections, and to apply each section to a different lookup table of the first level of lookup tables.
Claim 12
Dependent Claim
36 words
The apparatus of claim 7 , wherein the processor is further configured to merge two or more first level lookup tables and associated equivalence sets to produce a next level lookup table and associated equivalence set.
Claim 13
Dependent Claim
36 words
The apparatus of claim 10 , wherein the processor is further configured to merge two or more next level lookup tables and associated equivalence sets to produce the final level lookup table and associated equivalence set.
Claim 14
Independent Claim
168 words
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.
Claim 15
Independent Claim
168 words
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.
Claim 16
Independent Claim
135 words
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.
Claim 17
Independent Claim
135 words
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.
Claim 18
Dependent Claim
52 words
The apparatus of claim 13 , wherein the processor is further configured to apply a network packet to the 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.
Claim 19
Dependent Claim
37 words
The apparatus of claim 14 , wherein the processor is further 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.
Claim 20
Dependent Claim
39 words
The apparatus of claim 14 , wherein the processor is further configured to divide the network packet into a plurality of sections, and to apply each section to a different lookup table of the first level of lookup tables.
Claim 21
Dependent Claim
36 words
The apparatus of claim 13 , wherein the processor is further configured to merge two or more first level lookup tables and associated equivalence sets to produce a next level lookup table and associated equivalence set.
Claim 22
Dependent Claim
49 words
The apparatus of claim 13 , further comprising: an interface configured to transfer the hierarchical arrangement of lookup tables and the final equivalence set from the apparatus to a separate network device that applies a network packet to the hierarchical arrangement of lookup tables and the final equivalence set.
Claim 23
Independent Claim
109 words
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.
Claim 24
Independent Claim
109 words
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.
Claim 25
Dependent Claim
36 words
The apparatus of claim 19 , further comprising: an interface configured to transfer the hierarchical arrangement of lookup tables and the final equivalence set from the apparatus to a separate network device that applies a network.
References Cited (Backward Citations)
US5027350A
Cited
US5473607A
Cited
US5509006A
Cited
US6091725A
Cited
US6243667B1
Cited
US5917820A
Cited
US5872783A
Cited
US5881242A
Cited
US5852607A
Cited
US6282546B1
Cited
US6324656B1
Cited
US6308219B1
Cited
US6219706B1
Cited
US6167445A
Cited
US6643260B1
Cited
US6529508B1
Cited
US6970462B1
Cited
US7154888B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2011-08-19 | 2012-02-18 | 2012-08-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2015-08-19 | 2016-02-18 | 2016-08-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2019-08-19 | 2020-02-18 | 2020-08-19 | $7700.00 | Window Closed / Lapsed |