高速IP网络中深度包检测算法研究

作     者：陈围 

作者单位：解放军信息工程大学 

学位级别：硕士

导师姓名：陈庶樵

授予年度：2011年

学科分类：0810[工学-信息与通信工程] 08[工学] 081001[工学-通信与信息系统] 

主      题：深度包检测 字符串匹配 正则表达式匹配 确定性有限状态机 三态内容可寻址寄存器 

摘      要：随着网络传输速率的不断提高和应用业务的迅速拓展,业务识控系统对深度包检测算法的搜索速率和规则容量提出了更高的要求。传统深度包检测算法以高存储空间消耗换取高搜索速率,导致其支持的规则数有限,难以满足高速网络环境下大规模特征识别与业务管控的应用需求。论文依托国家863计划重点项目“高可信网络业务管控系统课题,在对现有深度包检测算法进行分析和总结的基础上,针对大规则库匹配存在的存储空间膨胀问题,研究了高速网络环境下大规模字符串特征和正则表达式特征的匹配算法及其工程实现。本文主要工作如下: 1.提出了采用集合切分编码的大容量字符串匹配算法LSMA-SC(Large-capacity String Matching Algorithm Using Set-segment Coding)。算法结合有限状态机灵活的搜索方式与TCAM快速的并行比较能力,构造多字节确定性有限状态机(Muti-character DFA),加速特征搜索过程,同时采用编号编码机制合并冗余转移路径,提升了算法的规则容量。实验仿真表明,LSMA-SC不仅具有较高的搜索速率,还能够大幅压缩存储空间,支持大规模特征库匹配。 2.提出了基于元字符分割的正则表达式匹配算法MRMA(Metacharacter-based Regular Expression Matching Algorithm)。MRMA在深入分析确定性有限状态机匹配特点的基础上,从消除正则表达式语法多义性的角度出发,利用元字符分割表达式,构建分离式确定性有限状态机(Divisional DFA),将复杂的正则表达式匹配转换为多个连续的子表达式匹配,解决了存储空间膨胀的问题。仿真结果表明,MRMA能够有效地压缩存储空间,实现了大规模正则表达式特征的高速检测。 3.设计了一种支持字符串规则与正则表达式规则的深度包检测引擎实现方案。该方案采用软硬件协同、控制平面与数据平面分离的系统架构,增强了系统的灵活性和可扩展性;结合算法扩展与流水线设计,提高了引擎对高速数据的实时检测能力;通过构造TCAM映射表和状态编号存储表,实现了用户规则的高效管理。性能分析和测试结果验证了该方案的可行性与有效性。