Efficient mapping of range classifier into ternary-CAM

Packet classification is inherently a multidimensional search problem which is either very computation intensive or memory intensive for software implementation. Thus, hardware based solution is necessary to keep up with gigabit line rate processing. We consider using standard ternary content addressable memory (TCAM) as a hardware classification engine. Traditionally, this approach has been deemed inefficient because ranges have to be broken into prefixes before stored in TCAM, resulting in large expansion. We propose a novel scheme where we can efficiently map ranges into TCAM. Our proposal has no expansion at all, or very little expansion for width constrained application. Our proposal enables high speed deterministic classification using low cost commodity hardware.