Efficient TCAM-based packet classification using multiple lookups and classifier semantics

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 a top partition and a bottom partition, the top partition having a single sub-graph with a 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.

2. 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 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.

3. The method of claim 2 wherein selecting one label further comprises selecting the label whose range implicates the fewest number of rules in the set of rules.

4. The method of claim 2 wherein constructing the second stage classifier further comprises comparing each field for a given rule in the set of rules to corresponding representative labels for the field; and creating a mapping from the results from the first stage classifier to the decision associated with the given rule when a field in the given rule overlaps with corresponding representative labels for the field.

5. The method of claim 2 wherein constructing the second stage classifier further comprises eliminating the given rule from the second stage classifier when a field of the given rule does not overlap with at least one representative label for the field.

6. The method of claim 2 further comprises instantiating the first and second stage classifier on content-addressable memory, a random access memory or a combination thereof.

7. The method of claim 2 further comprise instantiating the first stage classifier on a first content-addressable memory device and the second stage classifier on a second content-addressable memory device.

8. The method of claim 1 further comprises representing the set of rules as a firewall decision diagram.

9. The method of claim 8 further comprises 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.

10. The method of claim 1 further comprises reducing the size of the directed graph by merging isomorphic subgraphs before partitioning the graph.

11. The method of claim 1 further comprises defining the content-addressable memory device as ternary content addressable memory.