高性能报文分类算法的研究与实现

摘要

报文分类作为实现网络安全和QoS路由的核心技术，在近几年有着很高的关注度。虽然目前已有很多基于软件的报文分类算法，但他们或是需要很长的预处理时间，或是有着令人无法接受的内存占用，因此这些算法并没有太大的实用性。基于硬件的解决方案如TCAM,较于这些软件算法来说有着更高的效率，但TCAM经常达到自身的容量限制。因此，在大带宽环境下为海量规则集设计一个实用的报文分类算法仍然是一个十分具有挑战性的工作。在这篇文章中，为了应对这个挑战，我们提出了一个新的报文分类算法来处理海量规则集，这个算法叫做公共掩码树(CMT)。和目前存在的算法不同，我们提出的CMT同时具有理想的预处理时间，查找时间和内存占用。此外，CMT还支持不连续掩码的规则和任意维度(如100维)的规则集。我们在一个具有60Gbps最大吞吐率的平台上全面测试了CMT的性能，结果显示CMT可以在2分钟内预处理一千万条由ClassBench生成的规则，同时具有2.7GB的内存占用和40Gbps的查询速率。

目录

声明

符号使用说明

第一章 绪论

1.2 研究现状

1.3 研究内容与主要工作

1.4 论文组织结构

第二章 高性能报文分类算法

2.1 基于决策树的报文分类算法

2.2 基于元组搜索的报文分类算法

2.3 小结

第三章 基于公共掩码树（CMT）的高性能报文分类算法

3.1 引言

3.2 一维前缀规则集

3.3 一维词缀规则集

3.4 一维区间规则集

3.5 其他规则集

3.6 实验评估

3.7 小结

第四章 CMT在大带宽环境下的实现

4.1 多核/16环境下的规则集更新

4.2 实验评估

4.3 小结

第五章 总结与展望

5.2 下一步工作展望

致谢

参考文献

作者在学期间取得的学术成果