Method, system and computer program product for classifying packet flows with a bit mask
First Claim
1. A method for creating and/or modifying a dynamically update- able, searchable packet classification databank, comprising the steps of:
- receiving a collection of packet classification rules, each packet classification rule being represented as a plurality of binary locations;
selecting an index key based on a common location among said packet classification rules at a first level, such as to enable partitioning of said collection into two or more siblings at a second level, wherein the binary value of said common location represents a feature whereby the composition of each sibling contains packet classification rules possessing a common feature; and
selecting an index key based on a second common location among said packet classification rules at said second level, such as to enable partitioning of at least one of said two or more siblings at said second level into two or more siblings at a third level.
6 Assignments
0 Petitions
Accused Products
Abstract
Classification of packets into flows is an inherent operation performed by networks that support enhanced services. To support multiple-dimensional packet classification, a packet classification system is provided to select representative bits from a packet to look up a set of rules. The per-flow classification works with a large set of rules, where each rule comprises of multiple fields and also allows fast dynamic variation in the rule set. A lookup process includes a simple and finite set of instructions that can be efficiently implemented as pipelined hardware and support very high packet arrival rates.
171 Citations
30 Claims
-
1. A method for creating and/or modifying a dynamically update- able, searchable packet classification databank, comprising the steps of:
-
receiving a collection of packet classification rules, each packet classification rule being represented as a plurality of binary locations;
selecting an index key based on a common location among said packet classification rules at a first level, such as to enable partitioning of said collection into two or more siblings at a second level, wherein the binary value of said common location represents a feature whereby the composition of each sibling contains packet classification rules possessing a common feature; and
selecting an index key based on a second common location among said packet classification rules at said second level, such as to enable partitioning of at least one of said two or more siblings at said second level into two or more siblings at a third level. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A packet classification system, comprising:
-
a first memory for receiving a collection of packet classification rules, wherein each packet classification rule is represented as a plurality of binary locations; and
a mask constructor for selecting one or more index keys, wherein each index key is based on a common location among said packet classification rules residing at a level, and enables partitioning of said packet classification rules into two or more siblings at another level, and wherein said mask constructor continues to select index keys to repetitively partition each sibling at a respective level into two or more siblings at a lower level until reaching a partition threshold. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29)
-
-
30. A computer program product comprising a computer useable medium having computer readable program code means embedded in said medium for causing an application program to execute on a computer used to classify packet flows, said computer readable program code means comprising:
-
a first computer readable program code means for causing the computer to select one or more index keys, wherein said first computer readable program code means selects each index key such that each index key is based on a common location among a set of packet classification rules residing at a level, and enables partitioning of said set into two or more siblings at another level, and wherein said first computer readable program code means continues to select index keys to repetitively partition each sibling at a respective level into two or more siblings at a lower level until reaching a partition threshold; and
a second computer readable program code means for causing the computer to assemble said one or more index keys into a query key.
-
Specification