基于搜索空间分解的IP报文分类技术研究

摘要

报文分类是指网络设备根据预先定义的某些规则将流经的IP报文分成不同的类并对每类进行相应处理的过程，广泛地应用于防火墙、区分服务、虚拟专用网、入侵检测、流量计费等领域。近年来随着网络链路速率的增长和网络中一些新增加应用的出现，网络设备的处理能力逐渐落后于网络流量的增长速度，现有的基于软件或网络处理器的报文分类算法很难满足性能需要。研究人员开始从硬件上寻求问题的解决方案，如专用集成电路（ASIC）和现场可编程门阵列（FPGA）等。
　　本文针对搜索空间分解的分类算法进行了研究，主要工作如下：
　　1.对现有经典分类算法特别是对基于Trie结构的分类算法进行分析总结，从理论上分析了各类算法在最坏情况下的时间复杂度、空间复杂度、及其应用环境。为了能够有效评测报文分类算法的各种性能指标，采用了两种分类算法性能评价工具，一种是华盛顿大学开发的ClassBench，另一种是斯坦福大学开发的PALAC（Packet Lookup And Classification Simulator）。ClassBench能够根据真实的规则集特征来产生不同数量的实验规则集用来对算法进行测试，因此它能有效地解决规则集来源的问题；PALAC在它的COLAR模块中有一个算法类，用户只需要把自己的算法添加为该类的子类，因此PALAC使用起来更方便。
　　2.提出了一种基于搜索空间分解优化的i-HyperCuts算法。研究分析了搜索空间分解的分类算法HiCuts及其改进算法HyperCuts的机制机理，由于HiCuts算法和HyperCuts算法对搜索空间进行了均匀切割,造成了规则的复制，增加了算法的存储空间需求，因此本文根据HyperCuts算法中规则复制的两个来源做了相应的改进，提出了i-HyperCuts算法。该算法主要思想为：一、减少规则重叠，把需要复制到各个子空间中的规则挑选出来另行处理，不再复制到各个子空间去；二、对端口域的搜索区间进行切割时寻找导致规则复制最小点，而不是平均切割。实验结果表明，基于核心路由器规则集（CR2，该规则集包含125条过滤规则）测试样例，改进后的i-HyperCuts算法所需存储空间从2,440字节降低至2,135字节；建立的决策树深度（也即访存次数）从11次降低到8次。
　　3.在Xilinx FPGAVirtex-6平台上对i-HyperCuts算法进行了验证。布局布线的结果表明，在单个FPGA芯片中存储10K个规则的情况下，与HyperCuts算法相比，i-HyperCuts算法的吞吐量从90Gbps提高到100Gbps，FPGA芯片中可用逻辑资源（Slices）的利用率从41％降到33%，效率（吞吐量除以每个规则消耗的存储空间）从1600.4Gbps/KB提高到1705.6Gbps/KB，该项指标主要说明了算法中时间与空间的平衡度问题。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 引言

1.2 问题的提出

1.3 本文主要工作及结构安排

第二章 相关研究

2.1引言

2.2 算法的评价标准

2.3 典型的分类算法

2.4 分类算法的评价工具

2.5 本章小结

第三章 搜索空间分解算法（i-HyperCuts算法）

3.1 引言

3.2Hicuts算法

3.3 HyperCuts算法

3.4 HyperCuts算法的改进(i-HyperCuts算法)

3.5 本章小结

第四章 i-HyperCuts算法在FPGA平台上的验证

4.1 FPGA介绍

4.2 i-HyperCuts算法在FPGA上的实现过程

4.3 本章小结

第五章 全文总结

致谢

参考文献

作者简历