Accelerating Decision Tree Based Traffic Classification on FPGA and Multicore Platforms

作者：Tong Da^*; Qu Yun Rock; Prasanna Viktor K

来源：IEEE Transactions on Parallel and Distributed Systems, 2017, 28(11): 3046-3059.

DOI：10.1109/TPDS.2017.2714661

• Traffic classification
• machine learning
• decision tree
• multicore
• FPGA
• high throughput

Machine learning (ML) algorithms have been shown to be effective in classifying a broad range of applications in the Internet traffic. In this paper, we propose algorithms and architectures to realize online traffic classification using flow level features. First, we develop a traffic classifier based on C4.5 decision tree algorithm and Entropy-MDL (Minimum Description Length) discretization algorithm. It achieves an overall accuracy of 97.92 percent for classifying eight major applications. Next we propose approaches to accelerate the classifier on FPGA (Field Programmable Gate Array) and multicore platforms. We optimize the original classifier by merging it with discretization. Our implementation of this optimized decision tree achieves 7500+Million Classifications Per Second (MCPS) on a state-of-the-art FPGA platform and 75-150 MCPS on two state-of-the-art multicore platforms. We also propose a divide and conquer approach to handle imbalanced decision trees. Our implementation of the divide-and-conquer approach achieves 10,000+MCPS on a state-of-the-art FPGA platform and 130-340 MCPS on two state-of-the-art multicore platforms. We conduct extensive experiments on both platforms for various application scenarios to compare the two approaches.

• 出版日期2017-11-1