西安电子科技大学学报（自然科学版）2025，Vol.52Issue(5)：48-58,11.DOI:10.19665/j.issn1001-2400.20250505
基于区间树的混合包分类算法
CITree:a hybrid packet classification algorithm based interval tree
摘要
Abstract
High-performance classification throughput and dynamic update of rule sets are two core requirements for packet classification algorithms.Hybrid packet classification algorithms combining hash tables and decision trees typically replace tree nodes with hash tables to compensate for the inherent shortcomings of decision trees in terms of update performance.However,the hash table instead of tree nodes introduces additional hash mappings in the packet classification and disrupts the original single query path of the tree structure,ultimately degrading the classification performance.Consequently,a hybrid packet classification algorithm based on the interval tree,named CutIntervalTree(CITree),is proposed to achieve a high classification performance while supporting fast rule updates.The algorithm avoids introducing hash tables into the tree structure and instead introduces a preprocessing unit to partition the rule set into independent and non-independent rules,and stores them in the two-level tree structure and the hash table,respectively.The categorized storage of rules fully utilizes the advantages of high-speed classification of tree structure and fast update of the hash table.In addition,the CITree stores independent rules in the root node,intermediate nodes and leaf nodes of the interval tree,so that the matching operation can be completed in any node without traversing to the leaf nodes,thus realizing effective pruning.Experimental results show that the proposed algorithm improves the classification throughput by 72.2％and the rule updating efficiency by 63％compared with the current state-of-the-art algorithm.关键词
包分类/区间树/元组/哈希Key words
packet classificaiton/interval tree/tuple/hash分类
信息技术与安全科学引用本文复制引用
李卓,裴宇恒,荀淏,刘金典..基于区间树的混合包分类算法[J].西安电子科技大学学报（自然科学版）,2025,52(5):48-58,11.基金项目
国家重点研发计划(2022YFB2901100,2022ZD0115303) （2022YFB2901100,2022ZD0115303）
鹏城实验室算力网重大攻关项目(PCL2023A06) （PCL2023A06）
天津市自然科学基金重点项目(24JCZDJC01180) （24JCZDJC01180）
