摘要： 针对现有高速、大容量、多域报文分类算法普遍存在内存使用量大的问题，提出一种改进的HyperSplit多域报文分类算法。通过分析现有算法内存使用量大的原因，修正和设计选择分割维度与分割点、去除冗余结构的启发式算法，最大限度减少决策树中的复制规则数量，消除决策树中存在的冗余规则和冗余节点，优化决策树结构。仿真结果表明，该算法与现有多域报文分类算法相比，不依赖于规则集类型和特征，在保证内存访问次数不增加、报文得到线速处理的情况下，可降低算法的内存使用量，当规则集容量为105时，内存使用量降低到HyperSplit算法的80%。

关键词: 报文分类, 规则复制, 决策树, 内存使用量, 内存访问, 冗余规则, 冗余节点

Abstract: In order to solve the problem of too much memory usage in existing work for high speed large volume multi-field packet classification, an improved HyperSplit algorithm is proposed. By analyzing the cause of too much memory usage, the heuristic algorithms are modified and designed to choose the cutting points and dimensions and eliminate redundancy. Rule replication is greatly reduced, redundant rules and nodes are removed, and the decision tree’s structure is optimized. Simulation results demonstrate that compared with the existing work, independent of rule base’s type and characteristic, the algorithm can greatly reduce memory usage without increasing the number of memory accesses and ensure that packets can be processed at wire speed, and when the volume of classifier is 105, the algorithm consumes about 80% memory usage as that of HyperSplit.

Key words: packet classification, rule replication, decision tree, memory usage amount, memory access, redundant rule, redundant node

中图分类号: 

• TP301.6