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

A Connection-oriented Fast Multi-dimensional Packet Classification Algorithm

作　　者：张斌 吴浩明 ZHANG Bin;WU Haoming(PLA Strategic Support Force Information Engineering University,Zhengzhou 450001,China;Henan Key Laboratory of Information Security,Zhengzhou 450001,China)

机构地区：[1]中国人民解放军战略支援部队信息工程大学,郑州450001 [2]河南省信息安全重点实验室,郑州450001

出　　处：《电子与信息学报》2020年第6期1526-1533,共8页Journal of Electronics & Information Technology

基　　金：河南省基础与前沿技术研究计划基金(142300413201);信息工程大学新兴科研方向培育基金(2016604703);信息工程大学科研项目(2019f3303)。

摘　　要：为进一步提高聚合位向量(ABV)算法分类数据包的速度,该文提出一种面向连接的改进ABV(IABV)算法。该算法利用同一连接包分类查找规则相对一致的特点,建立哈希表-规则库两级优化查找结构,首先通过哈希表查找包分类规则,若未命中继续从规则库中查找。利用连接时效性特点设计哈希表冲突处理机制,根据表项最近命中时间判断是否进行覆写更新,避免规则累积导致查找时间增加;其次对ABV算法各维度进行等分处理,为各等分区间建立数组索引,从而快速缩小向量查找范围,加快查找规则库速度;最后,将规则中前缀转化为范围降低辅助查找结构复杂度,以减少内存空间占用量并加快规则查找速度。实验结果表明,将规则中前缀转化为范围后能够有效提升算法性能,相同条件下IABV算法相比ABV算法时间性能有显著提高。In order to increase the classification speed of Aggregated Bit Vector(ABV)algorithm,an Improved Aggregated Bit Vector(IABV)algorithm is proposed,which is connection-oriented.Based on the characteristic that the packets which belong to the same connection have similar classification results,IABV establishes a Hash table-rule set two-level searching structure.It first searches in the Hash table to check the packet classification rule and then finds the matching rule in the rule set when the Hash table lookup fails.To avoid the accumulation of rules in the table,a collision handling mechanism is proposed.It judges whether to overwrite the Hash table entry which is collision according to the last hit time of the entry;Secondly,for the purpose of accelerate rule set searching,IABV divides each dimension into multiple intervals equally and employs array to index these intervals;Finally,the prefix in the rule is converted into range to reduce the complexity of the search structure,so that the time and memory consumption of the algorithm can be decreased.The experiment result shows that the performance of the algorithm can be improved by converting prefix into range and the time performance of IABV algorithm is significantly improved compared with the ABV algorithm under the same conditions.

关 键 词：包分类 聚合位向量算法 哈希表 维度切分 

分 类 号：TN919[电子电信—通信与信息系统] TP391[电子电信—信息与通信工程]