Multiple Decision Tree Algorithm for Packet Classification

网络安全、网络测量、服务质量、流路由等都离不开多维包分类算法。设计一种在时间上和空间上都很好的包分类算法非常困难。该文在分析大规模规则集的特征的基础上，根据协议类型域只有有限的几种取值的特点，提出一种多决策树包分类算法。该算法既可用软件实现，也适宜硬件实现，并且在理论上适用于IPv6的包分类。当采用硬件实现时，多棵树可以并行查找，树内查找可以采用流水结构，算法的查找复杂度为O(1)。该算法可用于改进广泛应用的HiCuts和HyperCuts算法，与之相比，多决策树算法在预处理时间、内存占用和查找时间上都有很大提高。