Incremental compilation for classification and filtering rules

• US 7,236,493 B1
• Filed: 06/13/2002
• Issued: 06/26/2007
• Est. Priority Date: 06/13/2002
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: McRae, Andrew
• Primary Examiner(s): Nguyen; Chau
• Assistant Examiner(s): PARK, JUNG H
• Application Number:
  US10/170,896
• Time in Patent Office: 1,839 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/101 Access control lists [ACL]

Abstract

A technique classifies packets in a manner that is both deterministic and efficient. A hierarchical arrangement of lookup tables is organized into levels to classify the packets. Entries contained in the lookup tables are incrementally built and added to the lookup tables as packets are classified. A packet is divided into a series of fields and a first-level lookup table is built for each of these fields. Successive-level-lookup tables are then allocated and initialized to contain “missing” entries. When a packet is classified, it is applied to the first-level lookup tables to produce a series of indices. These indices are then applied to the second-level lookup tables to select indices that are the applied to a next-level table and so on until an outcome index is selected from a final-level lookup table. If the entry selected in the second-level lookup table is empty the successive-level entries are built and the classification is retried.

Claims

1. A method for generating a hierarchy of lookup tables for use in classifying a network packet in accordance with an access control list (ACL) containing one or more rules, the hierarchy comprising a first level and one or more successive levels, the method comprising the steps of:

dividing a packet header contained in the network packet into a plurality of sections wherein each section is associated with a plurality of section values;

generating a first-level lookup table and equivalence set associated with the first level in the hierarchy for each of the sections wherein the equivalence set contains one or more equivalence-set entries and wherein each equivalence-set entry is associated with one or more rules, and the first-level lookup table containing one or more first-level lookup table entries wherein each first-level lookup table entry associates each section value with an equivalence-set entry;

allocating one or more successive-level lookup tables for each successive level in the lookup table hierarchy wherein each successive-level lookup table contains one or more successive-level entries;

initializing the successive-level entries to indicate they are missing;

creating a matching rule bitmap for each section value;

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

associating the equivalence-set index value with the first-level lookup table entry associated with the section value.

2. The method of claim 1 wherein each section is the same length.

3. The method of claim 1 wherein the step of creating further comprises the steps of:

for each rule and each section value, determining if the section value matches the rule; and

if so, setting a bit in the matching rule bitmap that corresponds to the rule, otherwise, clearing the bit.

4. A method for classifying a network packet in accordance with an access control list (ACL) containing one or more rules using a hierarchy of lookup tables, the hierarchy comprising a first level and one or more successive levels, the method comprising the steps of:

dividing a packet header contained in the network packet into a plurality of sections wherein each section is associated with a section value;

applying each section value to a respective first-level lookup table associated with the first level to generate one or more first-level index values;

applying each first-level index value to a successive-level lookup table associated with the successive level to generate one or more successive-level index values;

determining if the successive-level index values indicate that successive-level entries contained in the successive-level lookup tables and associated with the successive-level index values are empty;

if so, building the successive-level entries; and

using at least one successive-level entry to classify the network packet in accordance with the ACL.

5. The method of claim 4 further comprising the step of:

applying the first-level index values to the successive-level lookup tables to generate a final-level table index value.

6. The method of claim 5 wherein the step of using further comprises the step of:

applying the final-level table index to a results table to determine a first matching rule, from the one or more rules, that is associated with the packet.

7. The method of claim 4 wherein the step of determining further comprises the steps of:

concluding the successive-level entry is empty if the successive-level index values are zero.

8. The method of claim 4 wherein the step of building further comprises the steps of:

A) calculating the cross-product of a first equivalence-set entry associated with a first lookup table associated with a prior level and a second equivalence-set entry associated with a second lookup table associated with the prior level to generate a next-level-equivalence-set index; and

B) associating the next-level-equivalence-set index with a successive-level entry.

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

repeating steps A and B for all levels in the lookup table hierarchy.

10. An apparatus for classifying a network packet in accordance with an access control list (ACL) containing one or more rules, using a hierarchy of lookup tables, the hierarchy comprising a first level and one or more successive levels, the apparatus comprising:

a processor configured to divide a packet header contained in the network packet into a plurality of sections wherein each section is associated with a section value, apply each section value to a respective first-level lookup table associated with the first level to generate one or more first-level index values, apply each first-level index value to a successive-level lookup table associated with the successive level to generate one or more successive-level index values, determine if the successive-level index values indicate that successive-level entries contained in the successive-level lookup tables and associated with the successive-level index values are empty and if so, build the successive-level entries, and use at least one successive-level entry to classify the network packet in accordance with the ACL; and

a memory connected to the processor and configured to hold the hierarchy of lookup tables.

11. The apparatus of claim 10 wherein the processor is further configured to apply the first-level index values to the successive-level lookup tables to generate a final-level table index value.

12. The apparatus of claim 11 wherein the processor is further configured to apply the final-level table index to a results table to determine a first matching rule, from the one or more rules, that is associated with the packet.

13. The apparatus of claim 10 wherein the processor is further configured to conclude the successive-level entry is empty if the successive-level index values are zero.

14. The apparatus of claim 10 wherein the processor is further configured to calculate the cross-product of a first equivalence-set entry associated with a first lookup table associated with a prior level and a second equivalence-set entry associated with a second lookup table associated with the prior level to generate a next-level-equivalence-set index;

and associate the next-level-equivalence-set index with a successive-level entry.

15. An apparatus for classifying a network packet in accordance with an access control list (ACL) containing one or more rules, using a hierarchy of lookup tables, the hierarchy comprising a first level and one or more successive levels, comprising:

means for dividing a packet header contained in the network packet into a plurality of sections wherein each section is associated with a section value;

means for applying each section value to a respective first-level lookup table associated with the first level to generate one or more first-level index values;

means for applying each first-level index value to a successive-level lookup table associated with the successive level to generate one or more successive-level index values;

means for determining if the successive-level index values indicate that successive-level entries contained in the successive-level lookup tables and associated with the successive-level index values are empty;

means for building the successive-level entries; and

means for using at least one successive-level entry to classify the network packet in accordance with the ACL.

16. The apparatus of claim 15 further comprising:

means for applying the first-level index values to the successive-level lookup tables to generate a final-level table index value.

17. The apparatus of claim 16 wherein the means for using further comprise:

means for applying the final-level table index to a results table to determine a first matching rule from the one or more rules that is associated with the packet.

18. The apparatus of claim 15 further comprising:

means for calculating the cross-product of a first equivalence-set entry associated with a first lookup table associated with a prior level and a second equivalence-set entry associated with a second lookup table associated with the prior level to generate a next-level-equivalence-set index; and

means for associating the next-level-equivalence-set index with a successive-level entry.

19. A computer readable media comprising computer executable instructions for execution in a processor for:

dividing a packet header contained in the network packet into a plurality of sections wherein each section is associated with a plurality of section values;

generating a first-level lookup table and equivalence set associated with the first level in the hierarchy for each of the sections wherein the equivalence set contains one or more equivalence-set entries and wherein each equivalence-set entry is associated with one or more rules, and the first-level lookup table containing one or more first-level lookup table entries wherein each first-level lookup table entry associates each section value with an equivalence-set entry;

allocating one or more successive-level lookup tables for each successive level in the lookup table hierarchy wherein each successive-level lookup table contains one or more successive-level entries;

initializing the successive-level entries to indicate they are missing;

creating a matching rule bitmap for each section value;

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

associating the equivalence-set index value with the first-level lookup table entry associated with the section value.

20. A computer readable media comprising computer executable instructions for execution in a processor for:

dividing a packet header contained in a network packet into a plurality of sections wherein each section is associated with a section value;

applying each section value to a respective first-level lookup table associated with the first level to generate one or more first-level index values;

applying each first-level index value to a successive-level lookup table associated with the successive level to generate one or more successive-level index values;

determining if the successive-level index values indicate that successive-level entries contained in the successive-level lookup tables and associated with the successive-level index values are empty;

if so, building the successive-level entries; and

using at least one successive-level entry to classify the network packet.