Fast Algorithms for Multi-stream Content Detection

High-speed packet content inspection and filtering devices rely on a fast multi-pattern matching algorithm which is used to detect predefined keywords or signatures in the packets. In TCP, a communication data stream is split into packets. Therefore, a target pattern may span multiple packets. Such fragmented pattern cannot be discovered by a per-packet scan. This is a serious problem in applications such as NIDS that require a complete scan. To avoid the problem, it is necessary to scan TCP streams. Stream-level parallelism is not a substantial solution because bandwidth depends on the number of active TCP streams. To scan each stream separately using one matching unit, the match states must be swapped appropriately. Another problem is, as parts of network infrastructure, the inspection units should support the function of QoS. In this paper, we proposed a multi-pattern matching automaton DSC-AC for high speed multi-stream packet scanning. We given out the construction of DSC-AC and optimized it with optimal and two binary searching tree and bit-map AC. Analysis and test showed that the optimized DSC-AC is capable of lightweight switching , enables a little state saving between streams and support the Diff-Serv Qos model. Furthermore, our method also enables easy implementation of multi-stream scanners with high throughput.