Bit weaving: a non-prefix approach to compressing packet classifiers in TCAMs

摘要: Ternary content addressable memories (TCAMs) have become the de facto standard in industry for fast packet classification. Unfortunately, TCAMs limitations of small capacity, high power consumption, heat generation, and cost. The well-known range expansion problem exacerbates these as each classifier rule typically has to be converted multiple TCAM rules. One method coping with is use compression schemes reduce number rules required represent a classifier. all existing only produce prefix classifiers. Thus, they miss opportunities created by non-prefix ternary In this paper, we propose bit weaving, first scheme. Bit weaving based on observation that entries same decision whose predicates differ one can merged into entry replacing question . consists two new techniques, swapping merging, identify then merge such together. key advantages are it runs fast, effective, composable other optimization methods pre/post-processing routine. We implemented conducted experiments both real-world synthetic Our experimental results show following: 1) an effective standalone technique (it achieves average ratio 23.6%); 2) finds miss. Specifically, improves prior techniques Razor Topological Transformation 12.8% 36.5%, respectively.