Accommodating Two Genies Into One Jar --- TCAM-based DFA Deflation For Fast and Scalable Regular Expression Matching
浏览数：0
Time: 9/16/2011,Friday, 10:00 am
Where: Room 214, SEIEE Building No.5.
Speaker: Dr. Qunfeng Dong, Professor, University of Science and Technology of China
Title: Accommodating Two Genies Into One Jar --- TCAM-based DFA Deflation For Fast and Scalable Regular Expression Matching
Abstract
------------
Regular expression matching is the core engine of many network functions such as 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 as a promising approach to achieving 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 quite close to the linearly growing NFA size. This not only means superior scalability, but also allows us to implement regular expression matching at extremely fa
st matching speed.
Speaker's bio
-------------------
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, both in computer science, and currently leads the Networked Systems Lab. He received his Ph.D. degree, also in computer science, 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. Recently, his research has aimed 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.
Where: Room 214, SEIEE Building No.5.
Speaker: Dr. Qunfeng Dong, Professor, University of Science and Technology of China
Title: Accommodating Two Genies Into One Jar --- TCAM-based DFA Deflation For Fast and Scalable Regular Expression Matching
Abstract
------------
Regular expression matching is the core engine of many network functions such as 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 as a promising approach to achieving 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 quite close to the linearly growing NFA size. This not only means superior scalability, but also allows us to implement regular expression matching at extremely fa
st matching speed.
Speaker's bio
-------------------
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, both in computer science, and currently leads the Networked Systems Lab. He received his Ph.D. degree, also in computer science, 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. Recently, his research has aimed 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.