40Gbps业务识别系统中模式匹配算法研究

作     者：陈正虎 

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

学位级别：硕士

导师姓名：兰巨龙

授予年度：2011年

学科分类：08[工学] 080402[工学-测试计量技术及仪器] 0804[工学-仪器科学与技术] 

主      题：业务识别 深度报文检测 模式识别 三态内容寻址存储器 40Gbps 

摘      要：骨干网链路吞吐速率提高对实时业务识别管控系统带来了极大的挑战,如何对互联网上承载的业务进行精确的线速逐包识别和管理成为构建新一代高可信网络亟待解决的问题。本文结合国家高技术研究发展计划(863计划)“高可信业务管控系统总体技术相关课题的研究需求,分析了模式匹配算法的研究现状,重点研究了基于TCAM芯片的高速匹配算法,并从匹配方式和识别机制上进行改进,设计了一种可行的高速业务识别方案,主要工作成果如下: 1、详细分析了经典模式匹配算法。从算法的时间和空间复杂度、工程实现难度等方面进行了比较,总结了各种经典模式匹配算法的优缺点,为高速业务识别方案设计打下了基础。 2、提出了一种基于HASH压缩关键词的高速TCAM匹配算法——HASH-TCAM算法,解决了传统TCAM查找方式在处理长模式串时存在的匹配速率低和存储空间不足的问题。HASH-TCAM算法通过哈希算法对待匹配的关键词预处理以压缩其匹配字长,相对于输入宽度固定的TCAM芯片,该算法降低了芯片查表的输入时间,在模式集数量为5000时,以8.9 ? 10?8冲突率代价提高了算法的匹配速率和存储空间利用率,实验表明该算法可以满足40Gbps骨干网上高速业务识别的需求。 3、提出了一种基于Bloom-Filter引擎过滤的TCAM模式匹配算法——BF-TCAM算法,解决了非敏感数据包的大量存在导致业务识别的误判率过高问题。BF-TCAM算法将多重哈希的思想引入到TCAM表项压缩中,通过FPGA实现的BF过滤引擎以6.56 ? 10?12的漏检概率将非模式集中的关键词滤出,测试表明该算法可明显提高业务识别的精确度。 4、设计了一种可实现的40Gbps环境下的高速业务识别方案。详细描述了40GbpsPOS线路接口板和FPGA内部模块的设计方案,并重点介绍了文中所提算法在业务识别子模块中的硬件实现。测试结果表明:系统具备40Gbps线速逐包的业务识别能力,适合作为骨干网络业务识控设备部署在下一代高可信网络中。