一种基于位向量流分类算法的改进

在流分类算法中,聚合位向量(ABV)算法分类速度快、并行性好,但内存开销过大;位向量折叠(AFBV)算法对ABV算法进行了改进,降低了运行时内存的消耗,但其冗余计算增加了时间开销。针对上述不足,文章提出一种改进的位向量流分类算法,该算法无需进行位向量聚合,减少了内存开销,并按规则的源/目的IP地址前缀建立分组表,根据表中分组所包含IP地址数目降序排列,使得算法具有良好的时间性能。实验结果表明,本算法在大规模规则库下具有良好的时间和空间效率。

一种面向连接的快速多维包分类算法

为进一步提高聚合位向量(ABV)算法分类数据包的速度,该文提出一种面向连接的改进ABV(IABV)算法。该算法利用同一连接包分类查找规则相对一致的特点,建立哈希表-规则库两级优化查找结构,首先通过哈希表查找包分类规则,若未命中继续从规则库中查找。利用连接时效性特点设计哈希表冲突处理机制,根据表项最近命中时间判断是否进行覆写更新,避免规则累积导致查找时间增加;其次对ABV算法各维度进行等分处理,为各等分区间建立数组索引,从而快速缩小向量查找范围,加快查找规则库速度;最后,将规则中前缀转化为范围降低辅助查找结构复杂度,以减少内存空间占用量并加快规则查找速度。实验结果表明,将规则中前缀转化为范围后能够有效提升算法性能,相同条件下IABV算法相比ABV算法时间性能有显著提高。