Packet classification using binary Content Addressable Memory

Packet classification is the core mechanism that enables many networking devices. Although using Ternary Content Addressable Memories (TCAMs) to perform high speed packet classification has become the widely adopted solution, TCAMs are very expensive, have limited capacity, consume large amounts of power, and generate tremendous amounts of heat because of their extremely dense and parallel circuitry. In this paper, we propose the first packet classification scheme that uses Binary Content Addressable Memories (BCAMs). BCAMs are similar to TCAMs except that in BCAMs, every bit has only two possible states: 0 or 1; in contrast, in TCAMs, every bit has three possible states: 0, 1, or * (don´t care). Because of the high complexity in implementing the extra “don´t care” state, TCAMs have much higher circuit density than BCAMs. As the power consumption, heat generation, and price grow non-linearly with circuit density, BCAMs consume much less power, generate much less heat, and cost much less money than TCAMs. Our BCAM based packet classification scheme is built on two key ideas. First, we break a multi-dimensional lookup into a series of one-dimensional lookups. Second, for each one-dimensional lookup, we convert the ternary matching problem into a binary string exact matching problem. To speed up the lookup process, we propose a number of optimization techniques including skip lists, free expansion, minimizing maximum lookup time, minimizing average lookup time, and lookup short circuiting. We evaluated our BCAM scheme on 17 real-life packet classifiers. On these classifiers, our BCAM scheme requires roughly 5 times fewer CAM bits than the traditional TCAM based scheme. The penalty is a throughput that is roughly 4 times less.