Chad R. Meiners and Alex X. Liu and Eric Torng
January, 2009
Ternary Content Addressable Memories (TCAMs) have become the de facto standard in industry for fast packet classification. Unfortunately, TCAMs have limitations of small capacity, high power consumption, high heat generation, and high cost. The well-known range expansion problem exacerbates the problem of smaller TCAMs by significantly decreasing the already limited capacity of these TCAMs as each classifier rule typically has to be converted to multiple TCAM rules. One method for coping with smaller TCAMs is to use compression schemes to reduce the number of TCAM rules required to represent a classifier. Although several TCAM-based classifier compression schemes have been proposed, they are all limited to producing prefix classifiers, which means that they all miss the compression opportunities created by non-prefix ternary classifiers. In this paper, we propose bit weaving, the first non-prefix classifier compression scheme. Bit weaving is based on the observation that adjacent TCAM entries that have a hamming distance of one (\ie, differ by only one bit) can be merged into one entry by replacing the bit in question with *. Bit weaving consists of two new techniques, \emph{bit swapping} and \emph{bit merging}, to first identify and then merge such rules together. The key advantages of bit weaving are that it runs fast and it is composable with other TCAM optimization methods as a pre/post-processing routine. We implemented bit weaving and conducted experiments on both real-world and synthetic packet classifiers. Our experimental results show the following: (i) bit weaving is an effective stand-alone compression technique (it achieves an average compression ratio of $23.6\%$) and (ii) bit weaving finds compression opportunities that other methods miss. Specifically, bit weaving improves the prior TCAM optimization techniques of TCAM Razor and Topological Transformation by an average of $12.8\%$ and $36.5\%$, respectively.
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format.