论文摘要
为了满足下一代高速信息网提出的Qos、VPN、MPLS、接入控制等新特性，Internet必须提供对带宽，时延，丢包率等各方面网络状况的保证，即必须对各种有不同需求的报文进行分类。 本文首先对现有的各种报文分类算法进行了系统、详细的研究，并对各种算法的查找性能和存储空间需求进行了分析比较，分析总结出当前报文分类领域面临的三个问题。接着本文介绍了应用于大规模规则库的快速分类算法的解决方案——递归流分类，该算法是一种利用线性存储区分块递归映射的算法。本文主要深入研究了该算法利用块等价部分类实现递归映射的过程，并针对该算法三阶段的优化流程结构进行了编程实现。接着本文在深入阐述Tuple Space概念的基础上介绍了元空间算法的原理和算法流程，该算法是目前适应于大规模规则库且支持快速更新的多域报文分类算法。在对加标记的改进方法的详细论述的基础上，本文介绍了一种二维分类算法——矩形算法，该算法是目前一种查找性能和空间需求经过优化的二维算法。然后本文针对TSS原始算法设计的缺陷，提出了基于规则长度的比特向量算法，仿真结果显示该算法的性能优于TSS的原始算法。最后考虑IPv6下的报文分类算法，本文引入了规则子集的概念，并利用该概念使多维报文分类可以利用现有的一维快速IP路由查找算法，提出了可适用于IPv6的分域查找算法，该算法在最坏情况下只需要7次访存。 分析上述各种算法的基本思想、算法结构及流程，本文总结出设计多域报文分类算法的原则：针对当前链路速度不断提高和规则库规模不断扩大的现状，设计快速的多域报文分类算法已经成为一个技术难点，一般的原则是在分析实际规则库规则的分布规律地基础上对现有的经典算法进行组合或者优化改进。