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.
|