基于智能规则存储匹配模型的包分类算法研究

doi:10.19665/j.issn1001-2400.20240913

西安电子科技大学学报 ›› 2024, Vol. 51 ›› Issue (6): 149-158.doi: 10.19665/j.issn1001-2400.20240913

• 计算机科学与技术 & 网络空间安全 • 上一篇下一篇

基于智能规则存储匹配模型的包分类算法研究

李卓¹^,²^,³^,⁴(), 王童彤¹^,⁴(), 刘开华⁴^,⁵()

1.天津大学微电子学院,天津 300072
2.鹏城国家实验室,广东深圳 518000
3.天津市成像与感知微电子技术重点实验室,天津 300072
4.天津市数字信息技术研究中心,天津 300072
5.天津仁爱学院,天津 300072

收稿日期:2024-03-22 出版日期:2024-12-20 发布日期:2024-10-09
作者简介:李卓(1984—),男,副教授,E-mail:zli@tju.edu.cn;
王童彤(1998—),女,天津大学硕士研究生,E-mail:tt_wang@tju.edu.cn;
刘开华(1956—),男,教授,E-mail:liukaihua@tju.edu.cn
基金资助:
国家重点研发计划(2022YFB2901100);国家重点研发计划(2022ZD0115303);鹏城实验室算力网重大攻关项目(PCL2023A06)

Research on the packet classification algorithm based on the intelligent rule storage matching model

LI Zhuo¹^,²^,³^,⁴(), WANG Tongtong¹^,⁴(), LIU Kaihua⁴^,⁵()

1. School of Microelectronics,Tianjin University,Tianjin 300072,China
2. Peng Cheng Laboratory,Shenzhen 518000,China
3. Tianjin Microelectronics Technology Key Laboratory of Imaging and Perception,Tianjin 300072,China
4. Tianjin Digital Information Technology Research Center,Tianjin 300072,China
5. Tianjin Ren’ai College,Tianjin 300072,China

Received:2024-03-22 Online:2024-12-20 Published:2024-10-09

摘要/Abstract

摘要：

在包分类技术研究中,设计高效的索引结构以实现数据包的快速匹配是有效包分类的关键。因此,为了提升基于哈希方法的包分类算法的存储效率,解决规则存储映射不均匀、易产生大量哈希冲突的问题,设计了一种规则存储匹配模型。该模型可实现更均匀的规则存储映射,进而提升分类子集内规则的存储效率。基于该模型,提出了一种包分类算法。该算法首先利用前缀长度压缩算法将规则集划分为多个子集,再为每个子集设置相同的存储结构。该存储结构包括标识信息处理单元、数据索引模型单元和规则查询匹配单元,其中数据索引模型单元包含了规则存储匹配模型,可实现子集内部规则的高效映射与存储,进而提升包分类的整体性能。实验表明,相比于现有算法,该算法的分类吞吐量平均提升1倍、存储消耗平均减少约20%、更新速度平均提升3倍,规则映射的均匀程度也有所提升。

关键词: 包分类, 规则存储匹配模型, 索引结构设计

Abstract:

In the research on packet classification technology,designing an efficient index structure to achieve fast packet matching is the key to effective packet classification.Therefore,in order to improve the memory utilization of packet classification technology based on hash-based methods,a rule storage matching model is proposed to achieve more uniform mapping and reduce hash collisions.This model can support more uniform rule storage mapping within a classification subset.Based on this model,a packet classification algorithm is proposed,which uses the Prefix Length Reduction algorithm to divide the ruleset into multiple subsets,and then the same storage structure is allocated for each subset.This storage structure includes an identification information processing unit,a mapping model unit and a rule query matching unit.In the packet classification stage,the identification information processing unit converts the packet headers into multi-dimensional vectors and then these vectors are input to the mapping model unit.Based on the output of the model,the matching rules can be retrieved from the rule query matching unit.Experimental results show that,compared with the existing algorithms,the proposed algorithm doubles the classification throughput,reduces the storage consumption by about 20% on average and increases the update speed by 3 times on average with the uniformity of the rule mapping also improved.

Key words: packet classification, rule storage matching model, index structure design

中图分类号:

TP393.0

李卓, 王童彤, 刘开华. 基于智能规则存储匹配模型的包分类算法研究[J]. 西安电子科技大学学报, 2024, 51(6): 149-158.

LI Zhuo, WANG Tongtong, LIU Kaihua. Research on the packet classification algorithm based on the intelligent rule storage matching model[J]. Journal of Xidian University, 2024, 51(6): 149-158.

图/表 8

图1

图2

表1

图3

图4

表2

图5

图6

参考文献 24

[1]	AL RESHAN M S, SYED D, ISLAM N, et al. A Fast Converging and Globally Optimized Approach for Load Balancing in Cloud Computing[J]. IEEE Access, 2023, 11:11390-11404.
[2]	ARAFAT M Y, PAN S, BAK E S. QQAR:A Q-Learning-Based QoS-Aware Routing for IoMT-Enabled Wireless Body Area Networks for Smart Healthcare[J]. Internet of Things, 2024:101151.
[3]	熊婉寅, 毛剑, 刘子雯, 刘文懋, 刘建伟. 软件定义网络中流规则安全性研究进展[J]. 西安电子科技大学学报, 2023, 50(6):172-194.
	XIONG Wanyin, MAO Jian, LIU Ziwen, et al. Advances in Security Analysis of Software-Defined Networking Flow Rules[J]. Journal of Xidian University, 2023, 50(6):172-194.
[4]	沈潼. 面向未来网络的高性能数据包查找与分类技术研究[D]. 长沙: 湖南大学, 2019.
[5]	GUPTA P, MCKEOWN N. Packet Classification Using Hierarchical Intelligent Cuttings[J]. Hot Interconnects VII, 1999, 40:1-9.
[6]	QI Y, XU L, YANG B, et al. PacketClassification Algorithms:From Theory to Practice[C]// IEEE INFOCOM 2009. Piscataway:IEEE, 2009:648-656.
[7]	LI W, LI X, LI H, et al. Cutsplit:A Decision-Tree Combining Cutting and Splitting for Scalable Packet Classification[C]// IEEE INFOCOM 2018-IEEE Conference on Computer Communications. Piscataway:IEEE, 2018:2645-2653.
[8]	LI Y, WANG J, CHEN X, et al. SplitTrie:A Fast Update Packet Classification Algorithm with Trie Splitting[J]. Electronics, 2022, 11(2):199.
[9]	ZHANG C, XIE G, HE P. Pextcuts:A High-Performance Packet Classification Algorithm with Pext Cpu Instruction[C]// 2022 IEEE/ACM 30th International Symposium on Quality of Service(IWQoS). Piscataway:IEEE, 2022:1-10.
[10]	LIAO Z, QIAN S, ZHENG Z, et al. PT-Tree:A Cascading Prefix Tuple Tree for Packet Classification in Dynamic Scenarios[J]. IEEE/ACM Transactions on Networking, 2024, 32(1):506-519.
[11]	SRINIVASAN V, SURI S, VARGHESE G. PacketClassification Using Tuple Space Search[C]// Proceedings of the Conference on Applications,Technologies,Architectures,and Protocols for Computer Communication. New York: ACM, 1999:135-146.
[12]	DALY J, BRUSCHI V, LINGUAGLOSSA L, et al. Tuplemerge:Fast Software Packet Processing for Online Packet Classification[J]. IEEE/ACM Transactions on Networking, 2019, 27(4):1417-1431.
[13]	ALIMOHAMMADI H, AHMADI M. Common Non-Wildcard Portion-Based Partitioning Approach to SDN Many-Field Packet Classification[J]. Computer Networks, 2020, 181:107534.
[14]	ZHANG C, XIE G. MultilayerTuple:A General,Scalable and High-performance Packet Classification Algorithm for Software Defined Network System[C]// 2021 IFIP Networking Conference(IFIP Networking). Piscataway:IEEE, 2021:1-9.
[15]	ZHANG C, XIE G, WANG X. DynamicTuple:The Dynamic Adaptive Tuple for High-Performance Packet Classification[J]. Computer Networks, 2022, 202:108630.
[16]	PFAFF B, PETTIT J, KOPONEN T, et al. The Design and Implementation of Open vSwitch[C]// 12th USENIX Symposium on Networked Systems Design and Implementation(NSDI 15). Berkely:USENIX, 2015:117-130.
[17]	ALIMOHAMMADI H, AHMADI M. Clustering-Based Many-Field Packet Classification in Software-Defined Networking[J]. Journal of Network and Computer Applications, 2019, 147:102428.
[18]	ZHANG X, XIE G, WANG X, et al. FastOnline Packet Classification with Convolutional Neural Network[J]. IEEE/ACM Transactions on Networking, 2021, 29(6):2765-2778.
[19]	LIU Y, YAO X, LI W, et al. HybridTSS:A Recursive Scheme Combining Coarse- and Fine- Grained Tuples for Packet Classification[C]// Proceedings of the 6th Asia-Pacific Workshop on Networking. New York: ACM, 2022:43-49.
[20]	YAN L, LI Z, LIU K. LearningTree:Neural Network-Based Index for NDN Forwarding Plane[C]// Proceedings of the ACM SIGCOMM 2019 Conference Posters and Demos. New York: ACM, 2019:63-65.
[21]	LI Z, XU Y, ZHANG B, et al. Packet Forwarding in Named Data Networking Requirements and Survey of Solutions[J]. IEEE Communications Surveys & Tutorials, 2018, 21(2):1950-1987.
[22]	KRASKA T, BEUTEL A, CHI E H, et al. TheCase for Learned Index Structures[C]// Proceedings of the 2018 International Conference on Management of Data. New York: ACM, 2018:489-504.
[23]	TAYLOR D E, TURNER J S. Classbench:A Packet Classification Benchmark[J]. IEEE/ACM Transactions on Networking, 2007, 15(3):499-511.
[24]	YINGCHAREONTHAWORNCHAI S, DALY J, LIU A X, et al. ASorted-Partitioning Approach to Fast and Scalable Dynamic Packet Classification[J]. IEEE/ACM Transactions on Networking, 2018, 26(4):1907-1920.

参数名称	参数值
学习率	0.01
损失函数	Mean Square Error
激活函数	Tanh
目标误差	10^-12
最小梯度	10^-12

基于智能规则存储匹配模型的包分类算法研究

Research on the packet classification algorithm based on the intelligent rule storage matching model

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 24

相关文章 15

Metrics

本文评价

推荐阅读 0

规则集类型	TSS	TM	PS	Multi	MRT
acl1	31	10	10	6/9	4
acl2	50	17	14	9/105	6
acl3	89	15	15	9/14	4
acl4	98	18	15	9/15	5
acl5	31	4	9	6	3
fw1	22	15	10	9/14	5
fw2	8	8	8	7	3
fw3	13	12	10	6/11	5
fw4	12	18	19	7/13	5
fw5	17	16	10	9/14	5
ipc1	93	12	10	9/13	3
ipc2	5	4	2	4	2

[1]	宋文超, 杨帆, 邢泽华, 张钰杰. 时间二维变化建模的网络流量多步预测方法[J]. 西安电子科技大学学报, 2025, 52(1): 22-36.
[2]	姜来为, 顾海洋, 谢丽霞, 杨宏宇. 机器学习在WSN入侵检测中的应用研究[J]. 西安电子科技大学学报, 2024, 51(4): 206-225.
[3]	付安民,毛安,黄涛,胡超,刘莹,张晓明,王占丰. 基于主动交互式学习的工控协议逆向分析[J]. 西安电子科技大学学报, 2023, 50(4): 22-33.
[4]	张越,陈庆旺,刘宝旭,于存威,谭儒,张方娇. 面向云原生的API攻击诱捕技术研究[J]. 西安电子科技大学学报, 2023, 50(4): 237-248.
[5]	潘森杉,徐腊梅. DorChain:利用休眠币提高交易验证效率[J]. 西安电子科技大学学报, 2022, 49(2): 182-189.
[6]	沈利香,慕德俊,曹国,谢光前,束方勇. 针对硬件木马的形式化验证模型构造方法[J]. 西安电子科技大学学报, 2021, 48(3): 146-153.
[7]	柴艳娜,李坤伦,宋焕生. 智能汽车的入侵检测系统安全研究[J]. 西安电子科技大学学报, 2021, 48(3): 31-39.
[8]	吕翊,朱博,吴大鹏. 一种负载均衡的FiWi网络视频多路径传输机制[J]. 西安电子科技大学学报, 2021, 48(3): 63-70.
[9]	刘华渊,苏云飞,李瑞林,唐朝京. 结构状态覆盖导向的灰盒模糊测试技术[J]. 西安电子科技大学学报, 2021, 48(1): 117-123.
[10]	张璐,慕德俊,胡伟,邰瑜. 能量隐通道安全高层综合设计方法[J]. 西安电子科技大学学报, 2020, 47(4): 64-69.
[11]	张书博,任淑霞,吴涛. 结合概率矩阵的改进谱聚类社区发现算法[J]. 西安电子科技大学学报, 2019, 46(3): 167-172.
[12]	董守玲;苏孟辉;林香鑫;李佳 . IPv6校园网拓扑自动节点获取与发现算法 [J]. J4, 2015, 42(2): 116-121.
[13]	王叶群;叶向阳;戚云军;黄国策;张衡阳. 一种跳频MAC协议的自适应机制[J]. J4, 2013, 40(5): 78-85.
[14]	张昌利;侯蓉晖. 社会化标签系统语义相关度的拓扑图法计算[J]. J4, 2012, 39(3): 196-201.
[15]	任方;马建峰;郝选文. 物联网感知层一种基于属性的访问控制机制[J]. J4, 2012, 39(2): 66-72.