Regular expression matching is the core engine of many network functions including intrusion detection, worm detection, protocol analysis, traffic analysis and so on. Despite the long line of research, existing methods either sacrifice matching speed or require exponentially exploding storage space. Accommodating the two genies --- matching speed and storage space --- into one jar is the central challenge that has plagued us over a decade; we are still in need of a method for fast and scalable regular expression matching, where it takes one simple memory lookup to match each input character (like DFA) and storage space growing linearly with regular expression pattern set size (like NFA). In this talk, I will present TCAM-based DFA deflation, the first memory-based approach that has the potential to achieve this ultimate goal of fast and scalable regular expression matching. Our proposed DFA deflation method takes only one simple TCAM lookup to match each input character, while the number of TCAM entries needed comes close to the linearly growing NFA size. This not only means superior scalability, but also allows us to implement regular expression matching at extremely fast matching speed.

Dr. Qunfeng Dong is a professor with the School of Computer Science and Technology, University of Science and Technology of China (USTC), where he received his B.E. and M.E. degrees and currently leads the Networked Systems Lab. He received his Ph.D. degree from the University of Wisconsin - Madison, and has worked/collaborated with industry partners including AT&T, Bell Labs, Cisco, IBM Research, Microsoft Research and NEC Labs. Since 2005, he as the first/correspondence author has actively published at premium conferences including ACM SIGMETRICS, ACM MobiCom, IEEE ICNP, ACM/IEEE ANCS, ACM MobiHoc, IEEE INFOCOM, etc. His recent research aims to provide technological support for the ongoing transition from 'network system' to 'networked systems' --- a vision that has motivated the founding of his Networked Systems Lab at USTC. The current focus of his research is high performance packet processing and computing architectures, with applications in high speed networked systems and network security. His research was awarded by the Ministry of Education (MOE) Program for New Century Excellent Talents (NCET) in University, and by the Science and Technological Fund of Anhui Province for Outstanding Youth.