多决策树包分类算法

Multiple Decision Tree Algorithm for Packet Classification

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

Multiple dimension packet classification is an enabling function for many Internet applications, such as network security, network monitoring, quality of service, flow routing, etc. It is difficult to develop a packet classification algorithm that is efficient in both space and time. Based on the observation that there are only a few possible values for the protocol field in the classifier, a Multiple Decision Tree （MDT） algorithm is proposed. This algorithm is suitable for both software and hardware implementation, and is applicable for IPv6 in theory. When MDT is implemented with hardware, the multiple tree can be searched in parallel and pipeline can be used to search within a specific tree, thus the search complexity of MDT is O（1）. With advantages in preprocessing time, memory consumption, and search time, MDT can be used to improve the widely used HiCuts and HyperCuts algorithms.