Fast and Scalable TCAM Based Regular Expression

Friday, 3 October 2014 - 11:00am - 1:00pm
Dr. Alex X. Liu/Associate Professor/Department of Computer Science and Engineering

 Dr. Alex X. Liu, Associate Professor

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 devices. It is easy to design networking devices that include our TCAM based RegEx matching solution. 


About the speaker

Dr. Alex X. Liu received the Ph.D. degree in computer science from The University of Texas at Austin, Austin, TX, in 2006. He is currently an Associate Professor of the Department of Computer Science and Engineering at Michigan State University. His research interests focus on networking and security. Dr. Liu is an Associate Editor of the IEEE/ACM TRANSACTIONS ON NETWORKING and an Area Editor of Elsevier Computer Communications. He is the TPC Co-Chair of ICNP 2014. He received the IEEE & IFIP William C. Carter Award in 2004, an NSF CAREER Award in 2009, and the Michigan State University Withrow Distinguished Scholar Award in 2011. He received Best Paper Awards from ICNP 2012, SRDS 2012, LISA 2010, and TSP 2009.


See event PDF.