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.

Sketch, a highly accurate data stream summarization technique, has gained much interest in the research community in recent years. Because of its sub-linear memory complexity, Sketch-based techniques consume significantly less memory than the traditional per-item-state techniques for processing high throughput data streams. One of the major applications of Sketch is in network anomaly detection, which is critical for network management and security in both Internet and data centers. Due to the low memory complexity, Sketch-based techniques can be supported by the fast on-chip storage of state-of-the-art computing platforms to achieve high throughput. In this work, we first propose a generic architecture on FPGA to accelerate Sketch and adopt it to 2 widely used Sketches: Count-min Sketch and K-ary Sketch. We propose online Sketch-based algorithms for 2 key network anomaly detection tasks: heavy hitter detection and heavy change detection. We adopt the proposed generic architecture for Sketch to accelerate these online algorithms. The post place-and-route results on a state-of-the-art FPGA show that our generic architecture can accelerate both Count-min Sketch and K-ary Sketch to over 150 Gbps, demonstrating significant performance improvements compared with other Sketch acceleration techniques. Our architectures for online anomaly detection tasks sustain 100-150 Gbps throughput for various configurations.