Efficient multi-category packet classification using TCAM

Packet classification is the base of various network functions such as firewall filtering, network intrusion detection and quality of services, etc. Ternary content addressable memory (TCAM) is widely employed in performing efficient packet classification. However, TCAM has some drawbacks, including limited capacity, high energy consumption, and incapability to store arbitrary ranges. Moreover, TCAM is only suitable for single-match packet classification natively, which is associated with one rule-set and reports one rule, for it only reports the first matching entry. However, except for single-match packet classification, another type of packet classification, multi-category packet classification, which is associated with multiple rule-sets and reports one matching rule for each rule-set, is also required in some scenarios, such as in the consolidation of multiple single-match network functions. The naive scheme performing multi-category packet classification with TCAM is to search a packet in multiple rule-sets one by one. Its performance decreases linearly as the number of rule-sets increases. To efficiently perform multi-category packet classification using TCAM, a novel scheme named REM is proposed in this paper. REM is based on the idea of reducing TCAM accesses per classification by merging rule-entry sets converted from rule-sets. The experiments show that compared with the naive scheme, REM can achieve 3x to 5x improvement on packet classification throughput, and reduce the energy consumption by 50% to 75%.