Method for classifying packets using multi-class structures

• US 7,154,888 B1
• Filed: 02/08/2002
• Issued: 12/26/2006
• Est. Priority Date: 02/08/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Li, Liang, Dao, Thanh Trung, McRae, Andrew A., Nhan, Hugh
• Primary Examiner(s): Harper, Kevin C.
• Application Number:
  US10/072,824
• Time in Patent Office: 1,782 Days
• Field of Search: 370/389, 370/392, 370/395.3, 370/395.31, 707/2
• US Class Current: 370/389
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/101 Access control lists [ACL]

Abstract

A technique for classifying a packet in a deterministic number of lookup operations. The technique builds a single “super class” that contains the match criteria for all the rules associated with packet classification. The “super class” is then compiled to produce a series of lookup tables and equivalence sets, including a final lookup table and equivalence set. The final equivalence set is then “post-processed” to associate the entries in the final lookup table with a particular result.

Claims

1. A method for generating lookup tables and a final equivalence set for use in classifying a network packet in accordance with a policy that specifies one or more classes, each class containing one or more match statements, the match statements being one of a stand-alone matching rule and a matching rule in an access control list (ACL) defining one or more matching rules, the method comprising the steps of:

generating a super class that contains all of the matching rules associated with the classes specified by the policy and that contains for each class a class name that identifies the class, a class criterion associated with the class, and a bitmap representing the matching rules associated with the class;

converting the matching rules of the super class into a single, hierarchical arrangement of lookup tables and associated equivalence sets, the hierarchical arrangement having a plurality of levels including a first level and a final level, the final equivalence set being associated with the final level.

2. A method for generating lookup tables and a final equivalence set for use in classifying a network packet in accordance with a policy that specifies one or more classes, each class containing one or more match statements, the match statements being one of a stand-alone matching rule and a matching rule in an access control list (ACL) defining one or more matching rules, the method comprising the steps of:

generating a super class that contains all of the matching rules associated with the classes specified by the policy; and

converting the matching rules of the super class into a single, hierarchical arrangement of lookup tables and associated equivalence sets, the hierarchical arrangement having a plurality of levels including a first level and a final level;

generating a first-level lookup table and a first-level equivalence set for a network packet section using the matching rules of the super class;

merging the first-level equivalence sets to produce one or more next-level lookup tables and next-level equivalence sets; and

merging the equivalence sets for each level to produce one or more next-level lookup tables and next-level equivalence sets until a lookup table and equivalence set associated with final level is produced.

3. The method of claim 2 wherein the step of generating a super class comprises the step of:

saving class information associated with each class.

4. The method of claim 2 wherein each network packet section is associated with a value and the step of generating the first-level lookup tables and first-level equivalence sets comprises the steps of:

creating a bitmap that represents the matching rules associated with a respective network packet section'"'"'s value;

determining if the bitmap matches an entry in the first-level equivalence set and, if so, assigning an equivalence set index value associated with the matching entry to the bitmap, otherwise, assigning a new equivalence set index value to the bitmap and placing the bitmap in the equivalence set; and

associating the equivalence set index value with the first-level lookup table entry associated with the respective network packet section'"'"'s value.

5. The method of claim 2 wherein the step of merging the equivalence sets for each level to produce one or more next-level lookup tables and next-level equivalence sets, comprises the steps of:

a) calculating the cross-product of a first bitmap associated with a first equivalence set and a second bitmap associated with a second equivalence set to produce a third bitmap;

b) determining if the third bitmap matches an entry in the next-level equivalence set and, if so, assigning an equivalence set index value associated with the matching entry to the third bitmap, otherwise, assigning a new equivalence set index value to the third bitmap and placing the third bitmap in the equivalence set;

c) associating a next-level lookup table entry with the equivalence set index value; and

d) repeating steps a through c for all entries in the first equivalence set and all the entries in the second equivalence set.

6. The method of claim 2 further comprising the step of:

associating each entry in the final equivalence set with one or more classes.

7. The method of claim 2 further comprising the step of:

transferring the lookup tables and final equivalence set to a network device that performs packet classification.

8. A method for generating lookup tables, a final equivalence set and a results table for use in classifying a network packet in accordance with one or more match statements, the match statements being one of a stand-alone matching rule and a matching rule in an access control list (ACL) defining one or more matching rules, the method comprising the steps of:

generating a super class that contains all of the matching rules;

converting the matching rules of the super class into a single, hierarchical arrangement of lookup tables and equivalence sets, the hierarchical arrangement having a plurality of levels including a first level and a final level, the final equivalence set being associated with the equivalence set of the final level; and

generating the results table from the entries in the final equivalence set.

9. The method of claim 8 wherein each entry in the final equivalence set is associated with an equivalence set index value and the step of generating the results table from the entries in the final equivalence set, comprises the step of:

associating the equivalence set index value with a result associated with the packet.

10. The method of claim 8 further comprising the step of:

transferring the lookup tables and final equivalence set to a network device that performs packet classification.

11. A method for classifying a network packet in accordance with one or more match statements, the match statements being one of a stand-alone matching rule and a matching rule in an access control list (ACL) defining a plurality of matching rules, the method comprising the steps of:

generating a super class that contains all of the matching rules;

converting the matching rules of the super class into a single, hierarchical arrangement of lookup tables, 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;

generating a results table from entries in the final equivalence set;

applying the network packet to the lookup tables to generate an outcome index; and

applying the outcome index to the results table to determine a result that applies to the network packet.

12. The method of claim 11 wherein the result is a pointer to a class associated with the network packet.

13. The method of claim 11 wherein the result is a pointer to a matching rule associated with the network packet.

14. The method of claim 11 further comprising the step of:

dividing the network packet into a plurality of sections.

15. A network device for classifying a network packet in accordance with one or more match statements, the match statements being one of a stand-alone matching rule and a matching rule in an access control list (ACL) defining a plurality of matching rules, the network device comprising:

means for generating a super class that contains all of the matching rules;

means for converting the matching rules of the super class into a single, 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 being associated with the final level;

means for generating a results table from entries in the final equivalence set;

means for applying the network packet to the lookup tables associated with the first level to generate an outcome index; and

means for applying the outcome index to the results table to determine a result that applies to the network packet.

16. A method for generating lookup tables, the method comprising the steps of:

generating a super class that contains a plurality of matching rules for sorting incoming packets into classes;

converting the plurality of matching rules of the super class into a single, hierarchical arrangement of lookup tables and equivalence sets; and

generating a final lookup table in response to the hierarchical arrangement of lookup tables and equivalence sets.

17. The method of claim 16 further comprising the step of:

transferring the lookup tables and the equivalence sets to a network device that performs packet classification.

18. An apparatus for generating lookup tables, comprising:

means for generating a super class that contains a plurality of matching rules for sorting incoming packets into classes;

means for converting the plurality of matching rules of the super class into a single, hierarchical arrangement of lookup tables and equivalence sets; and

means for generating a final lookup table in response to the hierarchical arrangement of lookup tables and equivalence sets.

19. The apparatus claim 18 further comprising:

means for transferring the lookup tables and the equivalence sets to a network device that performs packet classification.

20. A system for generating lookup tables, comprising:

a processor configured to generate a super class that contains a plurality of matching rules for sorting incoming packets into classes;

the processor further configured to convert the plurality of matching rules of the super class into a single, hierarchical arrangement of lookup tables and equivalence sets;

the processor further configured to generate a final lookup table in response to the hierarchical arrangement of lookup tables and equivalence sets; and

a memory coupled to the processor, the memory configured to store the final lookup table.

21. A computer readable media comprising:

the computer readable media containing computer executable instructions for execution in a processor for the practice of generating lookup tables, comprising,

generating a super class that contains a plurality of matching rules for sorting incoming packets into classes;

converting the plurality of matching rules of the super class into a single, hierarchical arrangement of lookup tables and equivalence sets; and

generating a final lookup table in response to the hierarchical arrangement of lookup tables and equivalence sets.

22. An apparatus for generating lookup tables, a final equivalence set and a results table for use in classifying a network packet in accordance with one or more match statements, the match statements being one of a stand-alone matching rule and a matching rule in an access control list (ACL) defining a plurality of matching rules, comprising:

a processor;

a memory coupled to the processor; and

means for generating a super class that contains all of the matching rules;

whereby the processor is configured to a) convert the matching rules of the super class into a single, hierarchical arrangement of lookup tables and equivalence sets, the hierarchical arrangement having a plurality of levels including a first level and a final level, the final equivalence set being associated with the final level, b) place the lookup tables and final equivalence set in the memory, and c) generate the results table from entries in the final equivalence set.

23. The apparatus of claim 22 further comprising:

a content-addressable memory (CAM);

whereby the processor is configured to place the lookup tables in the CAM.

24. A computer readable media containing computer executable instructions for execution in a processor for generating lookup tables, a final equivalence set and a results table for use in classifying a network packet in accordance with one or more match statements, the match statements being one of a stand-alone matching rule and a matching rule in an access control list (ACL) defining one or more matching rules, the instructions adapted for:

generating a super class that contains all of the matching rules;

converting the matching rules of the super class into a single, hierarchical arrangement of lookup tables and equivalence sets, the hierarchical arrangement having a plurality of levels including a first level and a final level, the final equivalence set being associated with the equivalence set of the final level; and

generating the results table from the entries in the final equivalence set.

25. A computer readable media containing computer executable instructions for execution in a processor for classifying a network packet in accordance with one or more match statements, the match statements being one of a stand-alone matching rule and a matching rule in an access control list (ACL) defining a plurality of matching rules, the instructions adapted for:

generating a super class that contains all of the matching rules;

converting the matching rules of the super class into a single, hierarchical arrangement of lookup tables, 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;

generating a results table from entries in the final equivalence set;

applying the network packet to the lookup tables to generate an outcome index; and

applying the outcome index to the results table to determine a result that applies to the network packet.