Method for high speed packet classification

• US 6,970,462 B1
• Filed: 04/24/2000
• Issued: 11/29/2005
• Est. Priority Date: 04/24/2000
• 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): Ton, Dang
• Assistant Examiner(s): Harper, Kevin C.
• Application Number:
  US09/557,480
• Time in Patent Office: 2,045 Days
• Field of Search: 370/389, 370/392, 370/395.31, 370/395.32, 707/2
• US Class Current: 370/392
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 43/028 by filtering
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 63/0236 Filtering by address, protocol, port number or service, e.g. IP-address or URL
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

The present invention allows for processing classification and/or security filtering rules by using bitmaps as representations. In one instance, the packet header involved in the packet classification is divided into sections (fields) such as 16 bit portions. Once, this is performed, a data lookup table is built for each of the packet header fields. In particular, a bitmap is created representing which filter rules match a certain packet header field value. The created data lookup tables, typically one for each packet header field, are merged to form intermediate level data lookup tables. The intermediate level data lookup tables are continuously merged until one final data lookup table is formed. The result of the final data lookup table represents all the possible packets to be classified. Thus, each final data entry has a bitmap representing the filtering rules that matches this entry. The bitmap can be used to selectively provide a desired result of the classification. For instance, a first matching rule is represented by the first bit set in the bitmap; the best matching rule is determined by processing the bitmap and selecting the most appropriate rule; and a complete set of rules that match is represented by the full bits set in the bitmap.

Claims

1. A method for use with classifying packets, comprising:

creating a plurality of logical segments, each of the logical segments corresponding to a portion of a packet header;

iterating values in each of the plurality of logical segments from zero to a maximum value;

creating a bitmap for each of the iterated values, each bitmap having one or more bits, each bit corresponding to a rule, each bit indicating whether a rule applies to the iterated value; and

grouping, to create an equivalency set for each of the plurality of logical segments, ranges of iterated values having equivalent bitmaps into one or more index sets, each index set having an index number.

2. The method as in claim 1, further comprising:

cross-producting the equivalency sets of each of the plurality of logical segments to create intermediate equivalency sets.

3. The method as in claim 2, wherein the step of cross-producting further comprises:

performing an AND operation on the bitmap of each of the one or more index sets of two or more equivalency sets to create one or more new bitmaps; and

grouping, to create a new equivalency set for each AND operation, equivalent new bitmaps into one or more new index sets, each index set having an index number.

4. The method as in claim 2, further comprising:

continuing the step of crossproducting until a final equivalency set is created, the final equivalency set having one or more final bitmaps.

5. The method as in claim 4, further comprising:

receiving a packet having a packet header;

dividing the packet header into the plurality of logical segments, each logical segment having a value; and

determining which rules apply to the packet by,

i) looking up the index set to which the value of each of the logical segments belongs,

ii) looking up the cross-producted relationships until the final equivalency set is reached, and

iii) looking up a corresponding final bitmap.

6. The method as in claim 1, further comprising:

storing, as lookup tables, all of the index numbers of the equivalency sets and their cross-producted relationships.

7. The method as in claim 6, further comprising:

deleting, from the equivalency sets, all bitmaps but the one or more final bitmaps.

8. The method as in claim 1, further comprising:

using 16-bit segments as the plurality of logical segments.

9. The method as in claim 1, further comprising:

dividing the packet header into a plurality of logical segments including fields selected from the group consisting of;

source address, destination address, protocol, type of service (TOS), precedence, source port number, destination port number, and flags.

10. A method for classifying a packet using rules, comprising:

receiving a packet having a packet header;

dividing the packet header into a plurality of logical segments, each logical segment having a value; and

determining which rules apply to the packet by,

i) looking up a predetermined range to which the value of each of the logical segments belongs, the range corresponding to a predetermined index set,

ii) looking up predetermined cross-producted relationships based on the predetermined index sets to reach a final cross-producted relationship, and

iii) looking up a final bitmap corresponding to the final cross-producted relationship, the final bitmap having one or more bits, each bit corresponding to a rule, each bit indicating whether a rule applies to the packet.

11. The method as in claim 10, further comprising:

using lookup tables, the lookup tables storing all of the index numbers of the equivalency sets and their crossproducted relationships.

12. The method as in claim 10, further comprising:

using 16-bit segments as the plurality of logical segments.

13. The method as in claim 10, further comprising:

dividing the packet header into a plurality of logical segments including fields selected from the group consisting of;

source address, destination address, protocol, type of service (TOS), precedence, source port number, destination port number, and flags.

14. A computer, comprising:

means for creating a plurality of logical segments, each of the logical segments corresponding to a portion of a packet header;

means for iterating values in each of the plurality of logical segments from zero to a maximum value;

means for creating a bitmap for each of the iterated values, each bitmap having one or more bits, each bit corresponding to a rule, each bit indicating whether a rule applies to the iterated value; and

means for grouping, to create an equivalency set for each of the plurality of logical segments, ranges of iterated values having equivalent bitmaps into one or more index sets, each index set having an index number.

15. A computer readable media, comprising:

the computer readable media containing instructions for execution on a processor for the practice of the method of,

creating a plurality of logical segments, each of the logical segments corresponding to a portion of a packet header;

iterating values in each of the plurality of logical segments from zero to a maximum value;

creating a bitmap for each of the iterated values, each bitmap having one or more bits, each bit corresponding to a rule, each bit indicating whether a rule applies to the iterated value; and

grouping, to create an equivalency set for each of the plurality of logical segments, ranges of iterated values having equivalent bitmaps into one or more index sets, each index set having an index number.

16. Electromagnetic signals propagating on a computer network, comprising:

the electromagnetic signals carrying instructions for execution on a processor for the practice of the method of,

creating a plurality of logical segments, each of the logical segments corresponding to a portion of a packet header;

iterating values in each of the plurality of logical segments from zero to a maximum value;

creating a bitmap for each of the iterated values, each bitmap having one or more bits, each bit corresponding to a rule, each bit indicating whether a rule applies to the iterated value; and

grouping, to create an equivalency set for each of the plurality of logical segments, ranges of iterated values having equivalent bitmaps into one or more index sets, each index set having an index number.

17. A computer, comprising:

means for receiving a packet having a packet header;

means for dividing the packet header into a plurality of logical segments, each logical segment having a value; and

means for determining which rules apply to the packet by,

i) looking up a predetermined range to which the value of each of the logical segments belongs, the range corresponding to a predetermined index set,

ii) looking up predetermined cross-producted relationships based on the predetermined index sets to reach a final cross-producted relationship, and

iii) looking up a final bitmap corresponding to the final cross-producted relationship, the final bitmap having one or more bits, each bit corresponding to a rule, each bit indicating whether a rule applies to the packet.

18. A computer readable media, comprising:

the computer readable media containing instructions for execution on a processor for the practice of the method of,

receiving a packet having a packet header;

dividing the packet header into a plurality of logical segments, each logical segment having a value; and

determining which rules apply to the packet by,

i) looking up a predetermined range to which the value of each of the logical segments belongs, the range corresponding to a predetermined index set,

ii) looking up predetermined cross-producted relationships based on the predetermined index sets to reach a final cross-producted relationship, and

iii) looking up a final bitmap corresponding to the final cross-producted relationship, the final bitmap having one or more bits, each bit corresponding to a rule, each bit indicating whether a rule applies to the packet.

19. Electromagnetic signals propagating on a computer network, comprising:

the electromagnetic signals carrying instructions for execution on a processor for the practice of the method of,

receiving a packet having a packet header;

dividing the packet header into a plurality of logical segments, each logical segment having a value; and

determining which rules apply to the packet by,

i) looking up a predetermined range to which the value of each of the logical segments belongs, the range corresponding to a predetermined index set,

ii) looking up predetermined cross-producted relationships based on the predetermined index sets to reach a final cross-producted relationship, and

iii) looking up a final bitmap corresponding to the final cross-producted relationship, the final bitmap having one or more bits, each bit corresponding to a rule, each bit indicating whether a rule applies to the packet.

20. A method for setting up lookup tables for classification of packets, comprising:

A. establishing a plurality of fields for a header of a packet of the type to be classified;

B. inserting a first value into the first field;

C. comparing the first value with each of a plurality of rules, there being an established number of rules in the plurality of rules;

D. setting a bit in a bitmap, the bitmap having a plurality of bits, each bit corresponding to each rule of the plurality of rules, the bit being set in the event that the corresponding rule applies to the first value;

E. repeating steps B, C, and D for each possible value which can be in the first field to create a bitmap for each possible value;

F. grouping the bitmaps into sets, a set having equal values of the bits in the bitmap;

G. assigning a label to each set; and

H. repeating steps B, C, D, E, F, and G for each field.

21. The method as in claim 20, further comprising:

I. logically combining the sets of one or more fields with the sets of one or more other fields to create intermediate sets.

22. The method as in claim 21, further comprising:

logically combining the sets by performing an AND operation on the bitmaps of the sets to create new bitmaps; and

grouping the new bitmaps into intermediate sets.

23. The method as in claim 21, further comprising:

logically combining intermediate sets until a final set is created, the final set having one or more final bitmaps.

24. The method as in claim 23, further comprising:

storing the sets in a plurality of lookup tables.

25. The method as in claim 23, further comprising:

deleting, from the sets, all bitmaps but the one or more final bitmaps.

26. The method as in claim 25, further comprising:

receiving a packet having a packet header;

dividing the packet header into the plurality of fields, each field having a value; and

determining which rules apply to the packet by,

i) looking up the set to which the value of each field belongs,

ii) looking up the logical combinations of set labels until the final set is reached, and

iii) looking up a corresponding final bitmap.

27. A computer, comprising:

A. means for establishing a plurality of fields for a header of a packet of the type to be classified;

B. means for inserting a first value into the first field;

C. means for comparing the first value with each of a plurality of rules, there being an established number of rules in the plurality of rules;

D. means for setting a bit in a bitmap, the bitmap having a plurality of bits, each bit corresponding to each rule of the plurality of rules, the bit being set in the event that the corresponding rule applies to the first value;

E. means for repeating steps B, C, and D for each possible value which can be in the first field to create a bitmap for each possible value;

F. means for grouping the bitmaps into sets, a set having equal values of the bits in the bitmap;

G. means for assigning a label to each set; and

H. means for repeating steps B, C, D, E, F, and G for each field.

28. A computer readable media, comprising:

the computer readable media containing instructions for execution on a processor for the practice of the method of,

A. establishing a plurality of fields for a header of a packet of the type to be classified;

B. inserting a first value into the first field;

C. comparing the first value with each of a plurality of rules, there being an established number of rules in the plurality of rules;

D. setting a bit in a bitmap, the bitmap having a plurality of bits, each bit corresponding to each rule of the plurality of rules, the bit being set in the event that the corresponding rule applies to the first value;

E. repeating steps B, C, and D for each possible value which can be in the first field to create a bitmap for each possible value;

F. grouping the bitmaps into sets, a set having equal values of the bits in the bitmap;

G. assigning a label to each set; and

H. repeating steps B, C, D, E, F, and G for each field.

29. Electromagnetic signals propagating on a computer network, comprising:

the electromagnetic signals carrying instructions for execution on a processor for the practice of the method of,

A. establishing a plurality of fields for a header of a packet of the type to be classified;

B. inserting a first value into the first field;

C. comparing the first value with each of a plurality of rules, there being an established number of rules in the plurality of rules;

D. setting a bit in a bitmap, the bitmap having a plurality of bits, each bit corresponding to each rule of the plurality of rules, the bit being set in the event that the corresponding rule applies to the first value;

E. repeating steps B, C, and D for each possible value which can be in the first field to create a bitmap for each possible value;

F. grouping the bitmaps into sets, a set having equal values of the bits in the bitmap;

G. assigning a label to each set; and

H. repeating steps B, C, D, E, F, and G for each field.

30. A computer for use with classifying a packet, comprising:

a memory to store,

i) a plurality of first lookup tables, each of the plurality of first lookup tables having a plurality of predetermined first index sets, the plurality of predetermined index sets corresponding to predetermined ranges of possible values for logical segments of a packet header,

ii) a plurality of intermediate lookup tables, each of the plurality of intermediate lookup tables having a plurality of predetermined intermediate index sets, the plurality of predetermined intermediate index sets corresponding to predetermined cross-producted relationships between the predetermined first index sets, and

iii) a final lookup table, the final lookup table having a plurality of predetermined final index sets, the plurality of final index sets corresponding to predetermined cross-producted relationships between the predetermined intermediate index sets, each of the predetermined final index sets having a final bitmap, the final bitmap having one or more bits, each bit corresponding to a rule, each bit indicating whether a rule applies to the packet.

31. The computer as in claim 30, further comprising:

a port to receive a packet having a packet header; and

a processor to divide the packet header into a plurality of logical segments, each logical segment having a value, and to determining which rules apply to the packet by,

i) looking up the first lookup tables to determine a predetermined first index set to which the value of each of the logical segments belongs,

ii) looking up the intermediate lookup tables to determine the corresponding intermediate index sets based on the first index sets to which the value of each of the logical segments belongs to reach a corresponding final index set, and

iii) looking up a final bitmap corresponding to the final index set.