1Fast Regular Expression Matching Using Small TCAM

Abstract—Regular expression (RE) matching is a core compo-nent of deep packet inspection in modern networking and security devices. In this paper, we propose the first hardware-based RE matching approach that uses Ternary Content Addressable Memory (TCAM), which is available as off-the-shelf chips and has been widely deployed in modern networking devices for tasks such as packet classification. We propose three novel techniques to reduce TCAM space and improve RE matching speed: transition sharing, table consolidation, and variable striding. We tested our techniques on 8 real-world RE sets, and our results show that small TCAMs can be used to store large Deterministic Finite Automata (DFAs) and achieve potentially high RE matching throughput. For space, we can store each of the corresponding 8 DFAs with 25,000 states in a 0.59Mb TCAM chip. Using a different TCAM encoding scheme that facilitates processing multiple characters per transition, we can achieve potential RE matching throughput of 10 to 19 Gbps for each of the 8 DFAs using only a single 2.36 Mb TCAM chip