Partition filter set for power-efficient packet classification

Abstract — Ternary Content-Addressable Memory (TCAM) has been widely used for high-performance multi-dimensional packet classification. High power consumption limits the use of TCAM for large filter sets. TCAM power consumption is proportional to the number of TCAM entries enabled for search. Dividing TCAM into many blocks and enabling only a few blocks for search has been proposed to reduce the power consumption dramatically. However, it is quite challenging to design efficient algorithms to partition a set of multi-dimensional filters into many subsets (a subset is placed in one TCAM block). The efficiency of the algorithm is evaluated in three aspects: the maximum number of TCAM blocks that need to be enabled for a single search, the storage utilization of TCAM blocks, and the time and space complexity of the partition algorithm. In this paper, we developed a simple but efficient partition algorithm based on the Hilbert curve. The algorithm reduces TCAM power consumption by a factor of ten on average. The TCAM storage utilization is over 99%. The algorithm takes O(n log n) time and O(n) space