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

• US 8,462,786 B2
• Filed: 08/13/2010
• Issued: 06/11/2013
• 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: Meiners, Chad R., Torng, Eric, Liu, Alex X.
• Primary Examiner(s): Ton, Dang T
• Assistant Examiner(s): AMBAYE, MEWALE A
• Application Number:
  US12/855,992
• Publication Number:
  US 20110038375A1
• Time in Patent Office: 1,033 Days
• Field of Search: 726 11- 14, 703/1, 370/389, 370/392
• 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 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.

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.

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.