一种采用混合切分法的报文分类算法∗

摘要

Traditional packet classification algorithms based on space-decomposition usually use only one heuristic to split the rule space, and they don’t adopt different heuristics according to the characteristics of each dimension. This paper proposes a hybrid intelligent cutting (HIC) scheme for packet classification. HIC firstly partitions the ruleset according to the IP prefix length. Then, taking into account the characteristics of current cutting dimension in each subruleset, HIC uses bit cuttings and precise projection point cuttings to cut the IP dimension and port dimension, respectively. At last, HIC builds the decision tree of hybrid cutting structures. Simulation results show that HIC has better scalability with different rulesets. Compared with EffiCuts, its time and space performance have increased by 46% and 74% respectively.%传统的基于几何区域分割的报文分类算法在空间切分时,通常只采用一种切分方法,并不会根据每个域的特点选取不同的对策。提出了一种采用混合切分法的报文分类算法HIC(hybrid intelligent cuttings)。首先,按照IP前缀长度将规则集分组；然后,在每个分组中根据当前切分域的特点,分别对 IP 域和端口域采用比特位切分法和精确投影点切分法实现空间分解；最后,构建混合切分结构的决策树。仿真结果表明,HIC 算法具有较好的规则集适应性,其时间性能与空间性能分别比代表算法EffiCuts提高了46%和74%。