吴浩明,
1.中国人民解放军战略支援部队信息工程大学 郑州 450001
2.河南省信息安全重点实验室 郑州 450001
基金项目:河南省基础与前沿技术研究计划基金(142300413201)，信息工程大学新兴科研方向培育基金(2016604703)，信息工程大学科研项目(2019f3303)
详细信息
作者简介:张斌：男，1969年生，教授、博士生导师，研究方向为网络空间安全
吴浩明：男，1995年生，硕士生，主要研究方向为网络流量检测
通讯作者:吴浩明 wuhaoming0512@126.com
中图分类号:TN919; TP391计量
文章访问数:1611
HTML全文浏览量:454
PDF下载量:36
被引次数:0
出版历程
收稿日期:2019-06-13
修回日期:2020-03-03
网络出版日期:2020-03-27
刊出日期:2020-06-22
A Connection-oriented Fast Multi-dimensional Packet Classification Algorithm
Bin ZHANG,Haoming WU,
1. PLA Strategic Support Force Information Engineering University, Zhengzhou 450001, China
2. Henan Key Laboratory of Information Security, Zhengzhou 450001, China
Funds:The Foundation and Frontier Technology Research Project of Henan Province (142300413201), The New Research Direction Cultivation Fund of Information Engineering University (2016604703), The Research Project of Information Engineering University (2019f3303)
摘要
摘要:为进一步提高聚合位向量(ABV)算法分类数据包的速度，该文提出一种面向连接的改进ABV(IABV)算法。该算法利用同一连接包分类查找规则相对一致的特点，建立哈希表-规则库两级优化查找结构，首先通过哈希表查找包分类规则，若未命中继续从规则库中查找。利用连接时效性特点设计哈希表冲突处理机制，根据表项最近命中时间判断是否进行覆写更新，避免规则累积导致查找时间增加；其次对ABV算法各维度进行等分处理，为各等分区间建立数组索引，从而快速缩小向量查找范围，加快查找规则库速度；最后，将规则中前缀转化为范围降低辅助查找结构复杂度，以减少内存空间占用量并加快规则查找速度。实验结果表明，将规则中前缀转化为范围后能够有效提升算法性能，相同条件下IABV算法相比ABV算法时间性能有显著提高。
关键词:包分类/
聚合位向量算法/
哈希表/
维度切分
Abstract: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.
Key words:Packet classification/
Aggregated Bit Vector (ABV) algorithm/
Hash table/
Dimension cutting
PDF全文下载地址:
https://jeit.ac.cn/article/exportPdf?id=c4086177-04f9-4fb7-b555-d3d8eed1a5d9
