基于规则集划分的多决策树报文分类算法

为克服决策树算法处理高速网络、大容量规则集下的报文分类问题时内存使用量大的弊端,提出一种基于规则集划分的多决策树报文分类算法。在保证规则子集数量可控的前提下,采用启发式算法将规则集划分为有限个规则子集,最大限度分离交叠规则;提出两级级联决策树结构,降低决策树深度以减少规则查找时间。理论分析表明,该算法空间复杂度较传统单决策树算法大幅降低。仿真结果表明,该算法的内存使用量比目前空间性能最好的EffiCuts算法减少了30%,且维度可扩展性更好。

Multiple decision-tree packet classification algorithm based on rule set partitioning

For solving the problem of decision-tree algorithms' too much memory usage when coping with packet classification under the circumstance of high rate network and large volume rule set, a multiple decision-tree algorithm based on rule set partitioning was proposed in this paper. On the condition of controlling the number of subsets, heuristics were used to partition the rule set into limited number of subsets, in which the overlapping rules had been separated. Cascading decision-tree structure was proposed to lower the depth and reduce search time. The theoretical analysis shows that space complexity has been reduced greatly compared to traditional single decision-tree algorithm. The simulation results demonstrate that the algorithm reduces memory usage about 30% and has better dimension scalability when being compared with EffiCuts, which has the best performance for memory usage so far.