多维并行报文分类算法的研究与实现

摘要

随着Internet的迅猛发展，网络速度越来越快，各种类型的应用也随之大规模运用，如QoS、入侵检测系统、流量记账，负载均衡，防火墙等。这些应用的基础都是报文分类技术，其中很多应用不仅仅涉及到了IP地址，还包括了对端口和协议类型的关注，要求路由器等网络设备不仅要有快速分类的能力，而且必须要能够支持多维报文分类。 位并行算法和BV算法是多维报文分类中两个具有代表性的算法，这两个算法对空间和时间复杂度进行了较好的折衷，且都支持并行处理，与硬件结合后能提高分类速度，适应多数报文分类环境。但是在规则集较大的情况下，这两个算法很容易导致内存占用量的爆炸，本文针对这个问题对两个算法进行了改进，大大节省了核心数据结构的内存占用。 首先，研究发现，位并行算法中对于规则集的单独一维来说，规则间的重复率很高。对此，论文提出了CBP（Compressed Bit Parallel）算法，将每一维上相同的规则先进行合并，形成若干个完全不同的规则块，然后根据这些规则块来确定区间位串，消除了位串长度对规则集大小的依赖性，大大减少了空间的占用；通过研究还发现，位并行算法划分的所有区间中存在着一些无用区间，删除这些区间并不会影响到整个分类过程，而且通过这种方式可以减少区间的个数，进而可以减少内存空间的占用。仿真结果表明，CBP算法能将核心数据结构的内存空间压缩40%至50%，而且随着规则集的增大，分类速度也能超过位并行算法。另外CBP算法的一个缺点是不能支持规则集的动态更新，对此，论文为CBP算法添加了一部分附加数据结构，使之能支持规则集的动态更新。 其次，论文对BV算法进行了研究，针对BV算法不支持范围类型的规则集的缺点，论文提出了一种将范围类型的规则转化为前缀类型规则的算法，使BV算法能适用于含有范围类型规则的多维报文分类环境；并且针对BV算法内存空间占用较大的缺点，论文通过删除Trie树中无用的位串来减少算法的空间占用。改进后的算法对于Trie树的优化并不影响原算法的分类速度，仍能达到较高的执行效率。仿真结果表明，改进算法在一定范围内，规则集越大，对内存空间的节省越明显。

目录

文摘

英文文摘

论文说明:图表目录、注释表

声明

第一章 绪论

第二章 报文分类技术研究现状

第三章 位并行算法的研究和改进

第四章 BV算法的改进方案

第五章 算法的实验与分析

第六章 总结与展望

参考文献

致谢

在学期间的研究成果及发表的论文