EFFICIENT TCAM-BASED PACKET CLASSIFICATION USING MULTIPLE LOOKUPS AND CLASSIFIER SEMANTICS

• US 20110038375A1
• Filed: 08/13/2010
• Published: 02/17/2011
• Est. Priority Date: 08/17/2009
• Status: Active Grant

• Current Assignee: The Board of Trustees of Michigan State University (Michigan State University)
• Original Assignee: The Board of Trustees of Michigan State University (Michigan State University)
• Inventors: LIU, Alex X., Meiners, Chad R., Torng, Eric
• Granted Patent: US 8,462,786 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]

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.

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.

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

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

4. The method of claim 1 further comprises partitioning the graph into k partitions, where k is less than the number of fields defined by a rule in the set of rules.

5. The method of claim 1 further comprises partitioning the graph into at least three partitions such that the lookup tables for each partition are instantiated on a different content-addressable memory device.

6. The method of claim 1 further comprises optimizing each of the lookup tables prior to instantiating the lookup tables on a content-addressable memory device.

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.

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

10. The method of claim 8 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.

11. The method of claim 8 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.

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

13. The method of claim 8 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.

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.

15. The method of claim 14 wherein selecting a number of bits further comprises initializing the number of bits as the logarithm to the base two of an atomic range set of the ranges of values.

16. The method of claim 14 wherein recursively dividing the domain further comprises representing the domain as a binary cut graph and mapping values associated with a terminal node in the graph in accordance with the path from a root node to the terminal node.

17. The method of claim 14 further comprises

incrementing the number of bits by one;

recursively dividing the domain of values along the candidate cut points using dynamic programming;

mapping each range of values to a result that is represented in a binary format using the incremented number of bits; and

repeating each of these steps until the mapping of range values has been optimized.