Speaker: Dr. Alex X. Liu
Time: 7:00pm, 7 SEP. 2011
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.
Short Bio:
received his Ph.D. degree in computer science from the University of Texas at Austin in 2006. He is currently an assistant professor in the Department of Computer Science and Engineering at Michigan State University. He received the IEEE & IFIP William C. Carter Award in 2004 and an NSF CAREER award in 2009. He received the MSU College of Engineering Withrow Distinguished Scholar Award in 2011. His research interests focus on networking, security, and dependable systems.
