acceleration of decision tree searching for ip traffic classification
Traffic classification remains a hot research problem, especially when facing new traffic trends and new hardware architectures. We propose a classification tree search method called explicit range search , motivated by the characteristics of machine learning based classification approaches. Our method differs from previously known algorithms such as HiCut and HyperCut in how to cut the ranges within a dimension and how to search within the ranges. By storing explicit marks and performing hardware supported parallel comparison, the explicit range search can reduce the worst-case number of memory accesses from 26 to 5 on a number of realistic rule sets generated from a well-known machine learning algorithm (C4.5). We also describe in this paper the proposed design based on FPGA devices.
decision tree traffic classification machine learning fpga