| Citation: | Bin ZHANG, Haoming WU. A Connection-oriented Fast Multi-dimensional Packet Classification Algorithm[J]. Journal of Electronics & Information Technology, 2020, 42(6): 1526-1533. doi: 10.11999/JEIT190434
|
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.
|
SHEN Tong, ZHANG Dafang, XIE Gaogang, et al. Optimizing multi-dimensional packet classification for multi-core systems[J]. Journal of Computer Science and Technology, 2018, 33(5): 1056–1071. doi: 10.1007/s11390-018-1873-9
|
|
BI Xiaan, LUO Xianhao, and SUN Qi. Branch tire packet classification algorithm based on single-linkage clustering[J]. Mathematics and Computers in Simulation, 2019, 155: 78–91. doi: 10.1016/j.matcom.2017.11.003
|
|
亓亚烜, 李军. 高性能网包分类理论与算法综述[J]. 计算机学报, 2013, 36(2): 408–421. doi: 10.3724/SP.J.1016.2013.00408
QI Yaxuan and LI Jun. Theoretical analysis and algorithm design of high-performance packet classification algorithms[J]. Chinese Journal of Computers, 2013, 36(2): 408–421. doi: 10.3724/SP.J.1016.2013.00408
|
|
陈小雨, 陆月明. 基于多维空间动态划分与RFC的包分类改进算法[J]. 网络与信息安全学报, 2018, 4(3): 35–41. doi: 10.11959/j.issn.2096-109x.2018024
CHEN Xiaoyu and LU Yueming. Improved packet classification algorithm based on multidimensional space dynamic division and RFC[J]. Chinese Journal of Network and Information Security, 2018, 4(3): 35–41. doi: 10.11959/j.issn.2096-109x.2018024
|
|
LAKSHMAN T V and STILIADIS D. High-speed policy-based packet forwarding using efficient multi-dimensional range matching[J]. ACM SIGCOMM Computer Communication Review, 1998, 28(14): 203–214. doi: 10.1145/285243.285283
|
|
万云凯, 嵩天, 刘苗苗, 等. 流量自适应的多维度包分类方法研究[J]. 计算机学报, 2017, 40(7): 1543–1555. doi: 10.11897/SP.J.1016.2017.01543
WAN Yunkai, SONG Tian, LIU Miaomiao, et al. A flow adaptive multi-dimensional packet classification algorithm[J]. Chinese Journal of Computers, 2017, 40(7): 1543–1555. doi: 10.11897/SP.J.1016.2017.01543
|
|
ZHOU Shijie, QU Y R, and PRASANNA V K. Multi-core implementation of decomposition-based packet classification algorithms[J]. The Journal of Supercomputing, 2014, 69(1): 34–42. doi: 10.1007/s11227-014-1205-y
|
|
ABBASI M, TAHOURI R, and RAFIEE M. Enhancing the performance of the aggregated bit vector algorithm in network packet classification using GPU[J]. PeerJ Computer Science, 2019, 5: e185. doi: 10.7717/peerj-cs.185
|
|
BABOESCU F and VARGHESE G. Scalable packet classification[J]. IEEE/ACM Transactions on Networking, 2005, 13(1): 2–14. doi: 10.1109/TNET.2004.842232
|
|
贺亚威, 侯整风, 吴亮亮. 一种基于位向量流分类算法的改进[J]. 合肥工业大学学报: 自然科学版, 2015, 38(3): 331–335. doi: 10.3969/j.issn.1003-5060.2015.03.009
HE Yawei, HOU Zhengfeng, and WU Liangliang. An improved flow classification algorithm based on bit vector[J]. Journal of Hefei University of Technology:Natural Science, 2015, 38(3): 331–335. doi: 10.3969/j.issn.1003-5060.2015.03.009
|
|
李林. 防火墙规则集关键技术研究[D]. [博士论文], 电子科技大学, 2009.
LI Lin. Research on key techniques of firewall rule set[D]. [Ph.D. dissertation], University of Electronic Science and Technology of China, 2009.
|
|
CAIDA. The CAIDA UCSD anonymized internet traces 2016[EB/OL]. http://www.caida.org/data/passive/passive_2016_dataset.xml, 2016.
|
|
颜天信, 王永纲, 石江涛, 等. 区域分割包分类算法的优化实现[J]. 通信学报, 2004, 25(6): 80–88. doi: 10.3321/j.issn:1000-436X.2004.06.011
YAN Tianxin, WANG Yonggang, SHI Jiangtao, et al. Optimized implementation of regional partition algorithm for packet classification[J]. Journal of China Institute of Communications, 2004, 25(6): 80–88. doi: 10.3321/j.issn:1000-436X.2004.06.011
|
|
TAYLOR D E and TURNER J S. ClassBench: A packet classification benchmark[C]. Proceedings of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, USA, 2005: 2068–2079. doi: 10.1109/INFCOM.2005.1498483.
|
|
孙鹏浩, 兰巨龙, 陆肖元, 等. 一种基于匹配域裁剪的包分类规则集压缩方法[J]. 电子与信息学报, 2017, 39(5): 1185–1192. doi: 10.11999/JEIT160740
SUN Penghao, LAN Julong, LU Xiaoyuan, et al. Field-trimming compression model for rule set of packet classification[J]. Journal of Electronics &Information Technology, 2017, 39(5): 1185–1192. doi: 10.11999/JEIT160740
|
Figures(3) / Tables(3)
DownLoad:
