Title: TCAM Based Regular Expression Matching
Presenter: Assistant Prof. Xiangyang Liu

Time: 14:00PM Jun 15, 2012
Location: Room 228, CS Building, Xianlin Campus

Abstract:

    Regular expression (RegEx) matching is a core component of deep packet inspection in modern networking and security devices．Prior RegEx matching algorithms are either software-based or FPGA-based. Software-based solutions have to be implemented in customized ASIC chips to achieve high-speed, the limitations of which include high deployment cost and being hard-wired to a specific solution and thus limited ability to adapt to new RegEx matching solutions. Although FPGA-based solutions can be modified, resynthesizing and updating FPGA circuitry in a deployed system to handle RegEx updates is slow and difficult. In this talk, we present the first hardware-based RegEx matching solution that uses Ternary Content Addressable Memories (TCAMs), which are off-the-shelf chips and have been widely deployed in modern networking devices for packet classification. There are three main reasons why TCAM-based RegEx matching works well. First, a small TCAM is capable of encoding a large Deterministic. Finite Automata (DFA) with carefully designed algorithms leveraging the ternary nature and first-match semantics of TCAMs.  Second, TCAMS facilitate high-speed RegEx matching because TCAMs are essentially high-performance parallel lookup systems: any lookup takes constant time (i.e. a few CPU cycles) regardless of the number of occupied entries. Third, because TCAMs are off-the-shelf chips that are widely deployed in modern networking devices, it is easy to design networking devices that include our TCAM based RegEx matching solution.