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

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

作　　者：李卓 王童彤 刘开华 LI Zhuo;WANG Tongtong;LIU Kaihua(School of Microelectronics,Tianjin University,Tianjin 300072,China;Peng Cheng Laboratory,Shenzhen 518000,China;Tianjin Microelectronics Technology Key Laboratory of Imaging and Perception,Tianjin 300072,China;Tianjin Digital Information Technology Research Center,Tianjin 300072,China;Tianjin Ren’ai College,Tianjin 300072,China)

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

出　　处：《西安电子科技大学学报》2024年第6期149-158,共10页Journal of Xidian University

基　　金：国家重点研发计划(2022YFB2901100,2022ZD0115303);鹏城实验室算力网重大攻关项目(PCL2023A06)。

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

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

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术]