Today, many network devices include a packet classification function to provide various services based on packet headers such as packet filtering, load balancing, and so on. Packet classification includes a rule set consisting of predicates and decisions. To find a matching rule for a packet header, the whole rule set needs to be searched, which causes delay. Ternary content addressable memory (TCAM) is the de facto industry standard for high-speed classification. This paper focuses on TCAM packet classifier optimization to reduce the rule set size while keeping the semantics.

This paper proposes a framework and three packet classifier compression algorithms within the framework. The framework consists of three steps: generate a binary decision diagram (BDD), convert the BDD nodes into ternary data structures, and convert the ternary data structures into TCAM rules via recursive merging. The ternary data structure is a tree in which the path from root to leaf represents a search key and the leaf node represents the decision. The goal of merging is to combine two TCAM classifiers into one representing both, which is a key process that enables classifier optimization.

The three proposed compression algorithms are prefix minimization using trees, ternary minimization using terns, and ternary minimization using access control lists (ACLs). For efficient merging, the paper divides a classifier into a foreground classifier and a background classifier. The prefix minimization using trees algorithm defines merging rules among various combinations of foreground and background classifiers to generate an optimal final solution set. The ternary minimization using terns algorithm develops a new data structure representing 0, 1, or *, which is called tern. Since the nature of TCAM is ternary, the tern is useful for additional compression. The ternary minimization using ACLs algorithm considers the order of rules in ACLs so that merging with a common rule of two classifiers does not ruin the order of each classifier. The experimental results show that the proposed algorithms outperform existing compression techniques by averages of 1.9, 5.4, and 6.2 percent.

As addressed in the paper, the proposed framework is useful for developing a new compression algorithm, since it gives a novel and intuitive view of TCAM classifiers. The paper is technically sound; however, it is not easy to follow, since the algorithms are explained with insufficient examples.