US6529508B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for packet classification with multiple answer sets
Assignee: Ericsson AB
•
Filing: 1999-05-21
•
Granted: 2003-03-04
•
Expires: 2019-05-21
Abstract
Abstract Providing different levels of quality of service for different data flows being transported over a data link requires a very fast way to classify individual packets. Providing meaningful classification generally requires classifying data packets in several dimensions. A classification method processes multiple parameter values for a packet in parallel to obtain answer sets indicating which rules are matched by each parameter value. Answer indexes identify logical blocks in each answer set which contain TRUE values. The method performs an AND operation on the answer indexes to identify those blocks in the answer sets which could contain bits corresponding to matched rules. An AND operation is performed on the identified blocks to identify the particular rule matched by the packet. The classification method allows extremely fast wire speed packet classification.
Inventors
- 👤 Renwei Li
- 👤 Thomas W. Ng
- 👤 Paul Terry
- 👤 Henry Lee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 12:09
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/24; H04L47/2475; H04L45/00; H04L45/302; H04L45/308; H04L47/13; H04L47/2408; H04L47/2416; H04L47/2441; H04L69/00; H04L69/16; H04L69/161; H04L69/22
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
199 words
A method for classifying data packets, the method comprising: (a) providing a plurality of classification rules, each rule providing matching criteria for one or more parameters; (b) obtaining a signature comprising a plurality of parameter values for a data packet; (c) for each of a plurality of the parameter values obtaining an answer set comprising a first group of flags, one of the first group of flags in each answer set corresponding to each of the rules, each answer set divided into a plurality of blocks; (d) for each of one or more answer sets, obtaining an answer index comprising a second group of flags, one of the second group of flags corresponding to each block in the corresponding answer set, each flag of the second group of flags set to TRUE if any flag in the corresponding block is TRUE; and, (e) performing a logical AND operation on corresponding answer indexes to identify second flags which are set to TRUE in all of the answer indexes; and, (f) performing a logical AND operation on those blocks from all of the answer sets for which the corresponding second flags are set to TRUE in all of the answer indexes.
Claim 2
Independent Claim
199 words
A method for classifying data packets, the method comprising: (a) providing a plurality of classification rules, each rule providing matching criteria for one or more parameters; (b) obtaining a signature comprising a plurality of parameter values for a data packet; (c) for each of a plurality of the parameter values obtaining an answer set comprising a first group of flags, one of the first group of flags in each answer set corresponding to each of the rules, each answer set divided into a plurality of blocks; (d) for each of one or more answer sets, obtaining an answer index comprising a second group of flags, one of the second group of flags corresponding to each block in the corresponding answer set, each flag of the second group of flags set to TRUE if any flag in the corresponding block is TRUE; and, (e) performing a logical AND operation on corresponding answer indexes to identify second flags which are set to TRUE in all of the answer indexes; and, (f) performing a logical AND operation on those blocks from all of the answer sets for which the corresponding second flags are set to TRUE in all of the answer indexes.
Claim 3
Dependent Claim
23 words
The method of claim 1 wherein obtaining an answer set for a parameter value comprises looking up the parameter value in a table.
Claim 4
Dependent Claim
79 words
The method of claim 1 wherein, for at least one parameter value, obtaining an answer set comprises, selecting a first part of the parameter value, using the first part of the parameter value as an index to an entry in a first table; determining whether the entry in the first table is a pointer to a second table and, if so, using a second part of the parameter value as an index to an entry in the second table.
Claim 5
Dependent Claim
16 words
The method of claim 3 wherein the at least one parameter value is an IP address.
Claim 6
Dependent Claim
38 words
The method of claim 4 wherein the first part of the parameter value comprises 16 highest order bits of the IP address and the second part of the parameter value comprises lower order bits of the IP address.
Claim 7
Dependent Claim
42 words
The method of claim 3 comprising determining whether the entry in the second table is a pointer to a third table and, if so, using a third part of the parameter value as an index to an entry in the third table.
Claim 8
Dependent Claim
65 words
The method of claim 6 wherein the at least one parameter value is an IP address, the first part of the parameter value comprises 16 highest order bits of the IP address, the second part of the parameter value comprises four lower order bits of the IP address and the third part of the parameter value comprises four lowest order bits of the IP address.
Claim 9
Dependent Claim
25 words
The method of claim 2 wherein looking up the parameter value in a table yields a pointer to a memory location containing the answer set.
Claim 10
Dependent Claim
80 words
The method of claim 1 wherein the second group of flags in the answer index comprises a plurality of subsets of the second group of flags and the answer index comprises a third group of flags, the third group of flags comprising one flag corresponding to each subset in the second group of flags, each flag of the third group of flags set to TRUE if any flag in the corresponding subset of the second group of flags is TRUE.
Claim 11
Dependent Claim
76 words
The method of claim 9 comprising a) selecting one or more subsets of the second group of flags for which corresponding flags in the third group of flags in each answer index are TRUE; b) selecting blocks in the answer sets for which corresponding flags in the selected subset of the second group of flags in each answer index are TRUE; c) and performing a logical AND operation on the selected blocks of the answer sets.
Claim 12
Dependent Claim
168 words
The method of claim 1 wherein each answer index comprises a top level group of flags and one or more intermediate level groups of flags each comprising a plurality of subsets, each subset corresponding to a flag in a higher level group of flags and, each flag in the top level group corresponding to a subset in a highest level one of the intermediate level groups, the method comprising identifying one or more subsets of a lowest level one of the intermediate groups of flags, the subset including at least one TRUE flag in each answer index by: a) performing a logical AND operation on the top level groups of flags of the answer indexes to identify those corresponding subsets of a lower level group of flags which include at least one TRUE flag in each answer index; b) iteratively repeating step (a) on the identified corresponding identified subsets until receiving a result which identifies second flags which are set to TRUE in all of the answer indexes.
Claim 13
Dependent Claim
59 words
The method of claim 1 wherein the signature comprises two or more parameter values selected from the group consisting of: input port on which the packet arrived; source address; destination address; source UDP or TCP port number; destination UDP or TCP port number; Type of Service (“TOS”) value; layer 4 packet type; ack flag; and, time of packet arrival.
Claim 14
Dependent Claim
12 words
The method of claim 1 wherein the blocks are equal in size.
Claim 15
Dependent Claim
34 words
The method of claim 13 wherein the AND operations are performed in a processor having a register size and each of the blocks has a size equal to the register size of the processor.
Claim 16
Dependent Claim
34 words
The method of claim 1 wherein, for one of the parameters, the rules are grouped so that flags corresponding to subsets of the rules which are neighbors are grouped together in groups of rules.
Claim 17
Dependent Claim
45 words
The method of claim 15 comprising ordering the rules within the groups such that if a first rule sets a condition on the parameter which is a prefix of the condition set by a second rule the first rule is ordered behind the second rule.
Claim 18
Dependent Claim
20 words
The method of claim 15 wherein rules in each group are assigned to flags which are in the same block.
Claim 19
Dependent Claim
71 words
The method of claim 17 comprising ordering the rules by selecting subsets of the rules so that each subset contains only neighboring rules, if any rules are present in both of any two of the subsets of neighboring rules removing those rules which are common to the two subsets from a larger one of the two subsets, and assigning each subset of rules to adjacent flags in one of the blocks.
Claim 20
Dependent Claim
13 words
The method of claim 1 wherein the matching criteria include range matching conditions.
Claim 21
Dependent Claim
13 words
The method of claim 1 wherein the matching criteria include set matching conditions.
Claim 22
Independent Claim
221 words
A method for classifying data packets, the method comprising: (a) providing a plurality of classification rules, each rule providing matching criteria for one or more parameters; (b) a step for obtaining a signature comprising a plurality of parameter values for a data packet; (c) for each of a plurality of the parameter values, a step for setting a first group of flags, one of the first group of flags corresponding to each of the rules, each flag set to TRUE if the parameter value matches the matching criteria for the rule corresponding to the flag, each flag set to FALSE otherwise, each first group of flags divided into a plurality of blocks; (d) for each of the first groups of flags, a step for setting a second group of flags, one of the second group of flags corresponding to each block in the corresponding first group of flags, each flag of the second group of flags set to TRUE if any flag in the corresponding block of the first group of flags is set to TRUE, each flag of the second group of flags set to FALSE otherwise; and, (e) performing a logical AND operation on those blocks in the first groups of flags for which the corresponding flags are set to TRUE in all of the second groups of flags.
Claim 23
Independent Claim
221 words
A method for classifying data packets, the method comprising: (a) providing a plurality of classification rules, each rule providing matching criteria for one or more parameters; (b) a step for obtaining a signature comprising a plurality of parameter values for a data packet; (c) for each of a plurality of the parameter values, a step for setting a first group of flags, one of the first group of flags corresponding to each of the rules, each flag set to TRUE if the parameter value matches the matching criteria for the rule corresponding to the flag, each flag set to FALSE otherwise, each first group of flags divided into a plurality of blocks; (d) for each of the first groups of flags, a step for setting a second group of flags, one of the second group of flags corresponding to each block in the corresponding first group of flags, each flag of the second group of flags set to TRUE if any flag in the corresponding block of the first group of flags is set to TRUE, each flag of the second group of flags set to FALSE otherwise; and, (e) performing a logical AND operation on those blocks in the first groups of flags for which the corresponding flags are set to TRUE in all of the second groups of flags.
Claim 24
Dependent Claim
12 words
The method of claim 21 wherein the blocks are equal in size.
Claim 25
Dependent Claim
34 words
The method of claim 22 wherein the AND operations are performed in a processor having a register size and each of the blocks has a size equal to the register size of the processor.
Claim 26
Dependent Claim
30 words
The method of claim 21 wherein, for one of the parameters, the rules are grouped so that flags corresponding to subsets of the rules which are neighbors are grouped together.
Claim 27
Dependent Claim
20 words
The method of claim 24 wherein rules in each subset are assigned to flags which are in the same block.
Claim 28
Dependent Claim
71 words
The method of claim 25 comprising ordering the rules by selecting subsets of the rules so that each subset contains only neighboring rules, if any rules are present in both of any two of the subsets of neighboring rules removing those rules which are common to the two subsets from a larger one of the two subsets, and assigning each subset of rules to adjacent flags in one of the blocks.
Claim 29
Dependent Claim
23 words
The method of claim 21 wherein each of the first groups of flags comprises a bit vector and each flag comprises a bit.
Claim 30
Dependent Claim
173 words
Packet classification apparatus, the apparatus comprising: (a) a computer accessible memory having a plurality of answer sets stored therein, each answer set comprising a plurality of first flags grouped into a plurality of blocks; (b) an answer index in the memory, the answer index comprising a plurality of second flags with one second flag corresponding to each block, the second flag set TRUE if any first flag in the corresponding block is set TRUE; and, (c) a processor connected to receive a signature characterizing a data packet, the signature comprising a plurality of parameter values, the processor adapted to: (i) identify an answer set corresponding to each parameter value in the signature; (ii) retrieve from the memory and perform a first logical AND operation on answer indexes corresponding to the identified answer sets to yield a result; and, (iii) retrieve from the memory and perform a second logical AND operation on those blocks in the answer sets corresponding to TRUE bits in the result to identify a class to which the packet belongs.
Claim 31
Dependent Claim
173 words
Packet classification apparatus, the apparatus comprising: (a) a computer accessible memory having a plurality of answer sets stored therein, each answer set comprising a plurality of first flags grouped into a plurality of blocks; (b) an answer index in the memory, the answer index comprising a plurality of second flags with one second flag corresponding to each block, the second flag set TRUE if any first flag in the corresponding block is set TRUE; and, (c) a processor connected to receive a signature characterizing a data packet, the signature comprising a plurality of parameter values, the processor adapted to: (i) identify an answer set corresponding to each parameter value in the signature; (ii) retrieve from the memory and perform a first logical AND operation on answer indexes corresponding to the identified answer sets to yield a result; and, (iii) retrieve from the memory and perform a second logical AND operation on those blocks in the answer sets corresponding to TRUE bits in the result to identify a class to which the packet belongs.
Claim 32
Dependent Claim
33 words
The packet classification apparatus of claim 28 wherein the processor comprises a plurality of parallel processors, each parallel processor identifying the answer set corresponding to one of the parameter values in the signature.
References Cited (Backward Citations)
US4736363A
Cited
US6104728A
Cited
WO1998023080A2
Cited
EP0859492A2
Cited
WO1998045976A2
Cited
US6034958A
Cited
US5951651A
Cited
US6212183B1
Cited
US6075791A
Cited
US6289013B1
Cited
US6308219B1
Cited
WO2000008817A2
Cited
US6389506B1
Cited
WO2000011885A2
Cited
US6289414B1
Cited
WO2002015521A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-03-03 | 2006-09-02 | 2007-03-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-03-03 | 2010-09-02 | 2011-03-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-03-03 | 2014-09-02 | 2015-03-04 | $7700.00 | Window Closed / Lapsed |