Method for high speed packet classification
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
31 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12, 13)
-
-
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.
- the computer readable media containing instructions for execution on a processor for the practice of the method of,
-
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.
- the electromagnetic signals carrying instructions for execution on a processor for the practice of the method of,
-
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.
- the computer readable media containing instructions for execution on a processor for the practice of the method of,
-
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.
- the electromagnetic signals carrying instructions for execution on a processor for the practice of the method of,
-
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. - View Dependent Claims (21, 22, 23, 24, 25, 26)
-
-
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.
- the computer readable media containing instructions for execution on a processor for the practice of the method of,
-
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.
- the electromagnetic signals carrying instructions for execution on a processor for the practice of the method of,
-
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. - View Dependent Claims (31)
Specification