深度包检测技术中多模式匹配算法研究

An Optimized Multi-pattern Matching Algorithm in Deep Packet Inspection

网络数据流量的急速增长给深度包检测技术带来了新的挑战,作为深度包检测技术的重要基础,字符串匹配算法针对大模式集合的优化结果直接决定了深度包检测技术的性能优劣。对广泛应用的多模式串匹配AC算法进行了改进,通过引入平衡二叉树结构消除AC自动机中的无用状态节点,在保证算法速度的前提下解决其在大规模模式集合匹配过程中内存占用过大的问题,经过实验验证,在模式集规模达100 000时,改进的AVLAC算法内存占用为传统AC算法的5%左右。

The rapid growth of network traffic has brought new challenges to the deep packet inspection （DPI） technology ; as a basic module, string matching algorithm greatly affects the performance of DPI. This paper optimizes the widely used multi -pattern matching AC algorithm by importing a balanced binary tree structure; it helps the algorithm to eliminate the useless state node of AC automaton, so it can accommodate the environment of large - scale pattern matching. The test resuits show that memory consumption of the optimized AVLAC algorithm is about 5% compared with the traditional AC algorithm when the pattern set comes to the 100 000 level.