Packet classification is the core mechanism that enables many networking services such as packet filtering and traffic accounting. Using Ternary Content Addressable Memories (TCAMs) to perform high-speed packet classification has become the de facto standard in industry because TCAMs can facilitate constant time classification by comparing a packet with all rules of ternary encoding in parallel. Despite their high speed, TCAMs have limitations of small capacity, large power consumption, and relatively slow access times. The well-known range expansion problem in converting range rules to ternary rules significantly exacerbates these TCAM limitations. While we can expect some gain in TCAM performance from improved hardware, the demands on TCAM performance as measured by the number of rules in packet classifiers increase far more rapidly due to the explosive growth of Internet services and threats.

Space reduction is key to addressing these three issues facing TCAMs because power consumption and access time are determined by the capacity of the TCAM. This dissertation describes four methods in which to reduce the space that classifiers occupy within TCAMs: TCAM Razor, All-Match Redundancy Removal, Sequential Decomposition, and Topological Transformations. These methods demonstrate that in must cases a substantial reduction of space is achieved.