论文部分内容阅读
数据包分类技术是许多网络关键技术的基础，涉及到网络的控制、性能、安全、管理等多方面内容，已经广泛应用于许多不同的场合，是未来网络发展主要研究的基础内容之一。研究与设计高性能实用的数据包分类算法，对满足网络服务的快速性与多样性意义重大，具有极为重要的学术价值和应用场景。本文分析了近年来一种实用性极高的数据包分类算法——HyperSplit的性能瓶颈，提出了基于多点切分思想的改进算法MultiSplit，并设计了一系列优化方法。经过实验验证，改进算法在分类速率、内存使用量等关键性能评价指标上均取得了较为明显的优化效果。本文主要工作和贡献包括: 1.从一些之前缺乏深入研究的着眼点入手，通过一系列实验对HyperSplit算法的性能瓶颈进行分析，同时指出传统性能分析方法的不足之处。本文进行了不同规则集性能对比、决策树/叶节点子集性能对比、底层节点空间分解效率分析、不同深度节点访存性能对比等四组实验，找到了不同类型中具有代表性的规则集，发现了决策树是影响分类速率的主要因素，而空间二分的分解方法，造成分解到较小规模的子空间后，空间分解效率降低，产生了多层节点，在查找过程中这些节点的访存代价大，处理时间长，是HyperSplit算法的主要性能瓶颈所在。 2.提出了一种基于多点切分思想的数据包分类算法——MultiSplit。在空间分解方法方面，MultiSplit借鉴了HyperSplit启发式的切分维度与切分点选择方法，能够很好地适应规则集特性，同时采用了多点切分的空间分解思想，极大地提升了空间分解效率，尤其对于底层节点能够快速缩小节点规模，大幅减小决策树高度，从而在实际应用中减少节点访存次数，提高分类速率。在数据结构方面，设计了高效的决策树节点数据结构，存储效率很高，扩展性强，对分类速率提升也产生了重要的影响。 3.提出了冗余规则去重、冗余规则范围缩减、过度切分修正三种优化方法，解决了原始算法在复杂规则集可用性、决策树平衡性、内存使用量等方面的潜在问题，进一步提升了算法时空性能。在Intel x86平台下的实验验证结果表明MultiSplit算法在分类速率、决策树内存使用量、适应性与可扩展性等关键性能指标上均明显优于HyperSplit算法，尤其是大规模规则集的分类速率上取得高达66％的平均提升效果。