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线速逐包的业务识别能力,适合作为骨干网络业务识控设备部署在下一代高可信网络中。

论文目录

• 表目录
• 图目录
• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究的背景和目的
• 1.1.1 课题研究背景
• 1.1.2 课题研究的目的
• 1.2 DPI 的研究现状和面临的问题
• 1.2.1 DPI 概念的提出
• 1.2.2 DPI 的研究现状
• 1.2.3 DPI 面临的问题
• 1.3 本文的主要工作
• 1.4 本文的结构安排
• 第二章 模式匹配算法综述
• 2.1 经典的基于软件实现的模式匹配算法
• 2.1.1 KMP 匹配算法
• 2.1.2 BM 匹配算法
• 2.1.3 AC 匹配算法
• 2.1.4 Wu-Manber 算法
• 2.2 基于HASH 匹配算法
• 2.2.1 哈希算法介绍
• 2.2.2 结合存储器的FPGA 实现
• 2.3 基于BLOOM-FILTER 匹配算法
• 2.3.1 Bloom-Filter 算法介绍
• 2.3.2 Bloom-Filter 算法的误检率分析
• 2.3.3 Bloom-Filter 算法的硬件实现
• 2.4 基于TCAM 匹配算法
• 2.4.1 TCAM 介绍
• 2.4.2 TCAM 的工作方式
• 2.4.3 TCAM 算法介绍
• 2.5 本章小结
• 第三章 基于HASH 压缩关键词的高速TCAM 匹配算法
• 3.1 引言
• 3.2 HASH-TCAM 算法分析
• 3.2.1 算法介绍
• 3.2.2 算法的性能分析
• 3.3 HASH-TCAM 算法验证及结果分析
• 3.3.1 性能比较
• 3.3.2 HASH-TCAM 算法功能验证
• 3.4 本章小结
• 第四章 基于BLOOM-FILTER 引擎过滤的TCAM 模式匹配算法
• 4.1 引言
• 4.2 BF-TCAM 算法分析
• 4.2.1 BF-TCAM 算法的流程
• 4.2.2 算法的性能分析
• 4.2.3 硬件化的BF-TCAM 算法分裂性能分析
• 4.2.4 算法的误判概率分析
• 4.3 实验环境建立和结果分析
• 4.4 性能比较
• 4.5 本章小结
• 第五章 40GBPS 高速业务识别系统的设计与实现
• 5.1 业务识别管控系统
• 5.1.1 系统模块的构成
• 5.1.2 系统应用环境
• 5.2 系统硬件平台
• 5.2.1 40Gbps POS 线路接口板
• 5.2.2 板级处理机的功能
• 5.2.3 FPGA 主程序模块功能划分
• 5.3 业务识别子模块详述
• 5.3.1 关键词压缩子模块
• 5.3.2 BF 过滤引擎子模块
• 5.3.3 查表子模块
• 5.4 测试结果
• 5.4.1 基于载荷特征的业务识别原理
• 5.4.2 测试方案设计
• 5.4.3 系统功能测试过程分析
• 5.5 小结
• 结束语
• 参考文献
• 作者简历 攻读硕士学位期间完成的主要工作
• 致谢