EFFICIENT TCAM-BASED PACKET CLASSIFICATION USING MULTIPLE LOOKUPS AND CLASSIFIER SEMANTICS
First Claim
1. A method for constructing a packet classifier for a computer network system, comprising:
- receiving a set of rules for packet classification, where a rule sets forth values for fields in a data packet and a decision for data packets having matching field values;
representing the set of rules as a directed graph;
partitioning the graph into at least two partitions;
generating at least one lookup table for each partition of the graph; and
instantiating the lookup tables from one partition on a first content-addressable memory and the lookup tables from the other partition on a second content-addressable memory device.
1 Assignment
0 Petitions
Accused Products
Abstract
A method is provided for constructing a packet classifier for a computer network system. The method includes: receiving a set of rules for packet classification, where a rule sets forth values for fields in a data packet and a decision for data packets having matching field values; representing the set of rules as a directed graph; partitioning the graph into at least two partitions; generating at least one lookup table for each partition of the graph; and instantiating the lookup tables from one partition on a first content-addressable memory and the lookup tables from the other partition on a second content-addressable memory device.
-
Citations
17 Claims
-
1. A method for constructing a packet classifier for a computer network system, comprising:
-
receiving a set of rules for packet classification, where a rule sets forth values for fields in a data packet and a decision for data packets having matching field values; representing the set of rules as a directed graph; partitioning the graph into at least two partitions; generating at least one lookup table for each partition of the graph; and instantiating the lookup tables from one partition on a first content-addressable memory and the lookup tables from the other partition on a second content-addressable memory device. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method for constructing a packet classifier for a computer network system, comprising:
-
receiving a set of rules for packet classification, where a rule sets forth values for fields in a data packet and a decision for data packets having matching field values; representing the set of rules as a directed graph; partitioning the graph into at least a top partition and a bottom partition, the top partition having a single sub-graph with the vertex of the graph and the bottom partition having a plurality of sub-graphs; generating a lookup table from the sub-graph in the top partition; generating a lookup table for each sub-graph in the bottom partition; assigning each table associated with the bottom partition a unique identifier; linking the lookup table from the top partition with the lookup tables in the bottom partition using the assigned table identifiers; and instantiating the lookup table from the top partition on a first content-addressable memory device and the lookup tables from the bottom partition on a second content-addressable memory device.
-
-
8. A method for constructing a packet classifier for a computer network system, comprising:
-
receiving a set of rules for packet classification, where each rule sets forth values for fields in a data packet and a decision for data packets having matching field values; constructing a firewall decision diagram from the set of rules for each field defined in the set of rules, where a root node in each of the firewall decision diagrams corresponds to a different field; reducing the size of each firewall decision diagram by merging isomorphic subgraphs therein; selecting one label for each outgoing edge from the root node in each of the firewall decision diagrams to be a representative label; constructing a first stage classifier from each of the reduced firewall decision diagrams, where values for a given field of a data packet maps to a result which corresponds to an input of a second stage classifier; and constructing the second stage classifier from the set of rules based on overlap of a given rule in the set of rules with a representative label from the reduced firewall decision diagrams. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. A method for encoding multiple ranges of values for a given field in a data packet as defined in a rule of a packet classifier, comprising:
-
finding candidate cut points over an entire domain of values for the given field, where candidate cut points correspond to starting or ending points in the ranges of values for the given field; selecting a number of bits to be used to encode the domain in a binary format; and recursively dividing the domain of values along the candidate cut points using dynamic programming and mapping each range of values to a result that is represented in a binary format using the selected number of bits. - View Dependent Claims (15, 16, 17)
-
Specification