Patent Document ID: 8654763
Application ID: 12578824
Patent Flag: 1

Claim One:
1. A method for constructing a packet classifier for a computer network system, comprising: representing a set of input rules for packet classification as a directed graph, where an input rule sets forth values for fields in a data packet and a decision for data packets having matching field values; traversing the directed graph in a bottom up manner from terminal nodes towards a root node of the directed graph; partitioning the directed graph into a plurality of subgraphs, where each subgraphs extends from non-terminal nodes in the directed graph and represent a minimization problem, thereby forming a set of minimization problems; assigning a cost to each edge extending from a given non-terminal node, where each edge terminates at a child node of the given non-terminal node and the cost assigned to an edge correlates to the number of rules associated with its child node; solving the set of minimization problems using dynamic programming to yield a minimal set of rules that are distinct from the set of input rules; removing redundant rules from the minimal set of rules; instantiating the minimal set of rule in a content-addressable memory device; and routing data packets in the computer network system using the packet classifier in the content-addressable memory device.