Simple CART Based Real-Time Traffic Classification Engine on FPGAs

Abstract

Traffic classification is a process which assorts computer network traffic into predefined traffic classes by utilizing packet header information or network packet statistics. Real-time traffic classification is mainly used in network management tasks comprising traffic shaping and flow prioritization as well as in network security applications for intrusion detection. Machine Learning (ML) based traffic classification that exploits statistical characteristics of traffic, has come into prominence recently, due to its ability to cope with encrypted traffic and newly emerging network applications utilizing non-standard ports to circumvent firewalls. To meet high data rates and achieve online classification with ML-based techniques, Field Programmable Gate Arrays (FPGAs) providing abundant parallelism and high operating frequency is the most appropriate platform. In this paper, we propose to use Simple Classification and Regression Trees (Simple CART) machine learning algorithm for traffic classification. However, the variations in node sizes of Simple CART decision tree caused by discretization pre-process incur memory and resource inefficiency problems when the tree is directly mapped onto the hardware. To resolve these problems, we propose to represent Simple CART decision tree by two stage hybrid data structure (Extended-Simple CART) that comprises multiple range trees in Stage 1 and a Simple CART decision tree enriched with bitmaps at its nodes in Stage 2. Our design is implemented on parallel and pipelined architectures using Field Programmable Gate Arrays (FPGAs) to acquire high throughput. Extended-Simple CART architecture can sustain 557 Gbps or 1741 million classification per second (MCPS) (for the minimum packet size of 40 Bytes) on a state-of-the-art FPGA and achieve an accuracy of 96.8% while classifying an internet traffic trace including eight application classes.