基于动态点切分的多决策树包分类算法

摘要

Traditional packet classification algorithms often have many redundant rules. To solve this issue, a packet classification algorithm called Clustered Dynamic Point Split (CDPS) is proposed based on the analysis of the characteristics of rule sets. CDPS divides the rule set by clustering the rules with similar cross-space relationship, then, it dynamically selects the rule projection points to complete the space decomposition and to build the decision tree. Simulation results show that, without reducing the time performance, the memory cost of CDPS is 95%and 50%less than HyperSplit and EffiCuts, respectively.%针对传统的包分类算法存在较多规则冗余问题，该文在分析规则集特征的基础上，提出一种基于动态点切分的多决策树包分类算法(Clustered Dynamic Point Split, CDPS)。该算法首先通过聚类具有相似空间交叉关系的规则，划分规则集为若干子集，然后在每个子集中动态地选取规则投影点完成空间分解并建立决策树。仿真结果表明，在保证算法的时间性能前提下，CDPS算法的内存占用较HyperSplit和EffiCuts分别减少了95%和50%。