Paper Info
Title
Fast String Matching with Overlapped Substring Classifier in Deep Packet Inspection Systems
Abstract
Traditional DFA based DPI (Deep Packet Inspection) string matching architectures either suffer from throughput bottleneck or unfeasible memory requirement, or both. Bloom Filter based schemes, on the other hand, only provide indefinite and unprecise match results. In this paper, we propose a novel string matching data structure called Overlapped Substring Classifier(OSC), which tries to compromise between these two ends. Instead of using incoming byte flow directly, we use OSC to extract the characteristic digest of the incoming string, which we demonstrate would be sufficient for locating a very small set of possible match, using DFA techniques. This type of match ambiguity and false-positive inaccuracy can be tuned to be negligible. The scheme is perfectly suitable for efficient and parallel hardware implementation, which makes ultra high performance and low memory usage simultaneously possible. A hardware architecture is also designed supporting single-threaded scanning rate of 10Gbp, with only moderate memory requirement and clock rate assumption.
Year
DOI
Venue
2010
10.1109/GLOCOM.2010.5683877
GLOBECOM
Keywords
DocType
ISSN
fast string matching,string matching,dpi,string matching data structure,inspection,osc,dfa techniques,pattern classification,data structures,match ambiguity,computer network security,bloom filter based schemes,supporting single-threaded scanning,deep packet inspection systems,internet security,overlapped substring classifier,matched filters,hardware,pattern matching,memory management,bandwidth,data structure,bloom filter,deep packet inspection,false positive,hardware architecture
Conference
1930-529X E-ISBN : 978-1-4244-5637-6
ISBN
Citations 
PageRank 
978-1-4244-5637-6
0
0.34
References 
Authors
9
4
Name
Order
Citations
PageRank
Zhikai Zhang1794.30
Youjian Zhao227332.53
Guang-hui Yang301.35
Xiaoping Zhang4276.83