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.

High-performance and dynamically updatable hardware architectures for multi-field packet classification have regained much interest in the research community. For example, software defined networking requires 15 fields of the packets to be checked against a predefined rule set. Many algorithmic solutions for packet classification have been studied over the past decade. FPGA-based packet classification engines can achieve very high throughput; however, supporting dynamic updates is yet challenging. In this paper, we present a two-dimensional pipelined architecture for packet classification on FPGA; this architecture achieves high throughput while supporting dynamic updates. In this architecture, modular Processing Elements (PEs) are arranged in a two-dimensional array. Each PE accesses its designated memory locally, and supports prefix match and exact match efficiently. The entire array is both horizontally and vertically pipelined. We exploit striding, clustering, dual-port memory, and power gating techniques to further improve the performance of our architecture. The total memory is proportional to the rule set size. Our architecture sustains high clock rate even if we scale up (1) the length of each packet header, or/and (2) the number of rules in the rule set. The performance of the entire architecture does not depend on rule set features such as the number of unique values in each field. The PEs are also self-reconfigurable; they support dynamic updates of the rule set during run-time with very little throughput degradation. Experimental results show that, for a 1 K 15-tuple rule set, a state-of-the-art FPGA can sustain a throughput of 650 Million Packets Per Second (MPPS) with 1 million updates/second. Compared to TCAM, our architecture demonstrates at least four-fold energy efficiency while achieving two-fold throughput.

Online set intersection operations have been widely used in network processing tasks, such as Quality of Service differentiation, firewall processing, and packet/traffic classification. The major challenge for online set intersection is to sustain line-rate processing speed; accelerating set intersection using state-of-the-art hardware devices is of great interest to the research community. In this paper, we present a novel high-performance set intersection approach on FPGA. In our approach, each element in any set is represented by a combination of Group ID (GID) and Bit Stride (BS); all the sets are intersected using linear merge techniques and bitwise AND operations. We map our online set intersection algorithm onto hardware; this is done by constructing modular Processing Element (PE) and concatenating multiple PEs into a tree-based parallel architecture. In order to improve the throughput on a state-of-the-art FPGA, we feed all the inputs to FPGA in a streaming fashion with the help of the synchronization GIDs. Post place-and-route results show that, for a typical set intersection problem in network processing, our design can intersect$\text{eight}$sets, each of up to$32$K elements, at a throughput of$47.4$Thousand Intersections Per Second (KIPS) and a latency of$94.8\,\mu$s per batch of inputs. Compared to the classic linear merge or bitwise AND techniques on state-of-the-art multi-core processors, our designs on FPGA achieves up to$66\times$throughput improvement and$80\times$latency reduction.

Due to the rapid growth of Internet, there is an increasing need for efficiently classifying packets with many header fields in large rule sets. For example, in Software Defined Networking (SDN), the OpenFlow table lookup can require 15 packet header fields to be examined. In this paper, we present several decomposition-based packet classification implementations with efficient optimization techniques. In the searching phase, packet headers are split or combined. In the merging phase, the partial searching results from all the fields are merged to generate the final result. We prototype our implementations on state-of-the-art Field Programmable Gate Array (FPGA), multi-core General Purpose Processor (GPP), and Graphics Processing Unit (GPU). On FPGA, we propose two optimization techniques to divide generic ranges; modular processing elements are constructed and concatenated into a systolic array. On multi-core GPP, we parallelize both the searching and merging phases using parallel program threads. On the GPU-accelerated platform, we minimize branch divergence and reduce the data communication overhead. Experimental results show that 500Million Packets Per Second (MPPS) throughput and 3μs latency can be achieved for 1:5K rule sets on FPGA. We achieve 14:7MPPS throughput and 30:5MPPS throughput for 32K rule sets on multi-core GPP and GPU-accelerated platforms, respectively. As a heterogeneous solution, our GPU-accelerated packet classier shows 2x speedup compared to the implementation using multi-core GPP only. Compared with prior works, our designs can match long packet headers against very complex rule sets.

Packet classification is a key network function enabling a variety of network applications, such as network security, Quality of Service (QoS) routing, and other value-added services. Routers perform packet classification based on a predefined rule set. Packet classification faces two challenges: (1) the data rate of the network traffic keeps increasing, and (2) the size of the rule sets are becoming very large. In this paper, we propose an FPGA-based packet classification engine for large rule sets. We present a decomposition-based approach, where each field of the packet header is searched separately. Then we merge the partial search results from all the fields using a merging network. Experimental results show that our design can achieve a throughput of 147 Million Packets Per Second (MPPS), while supporting upto 256K rules on a state-of-the-art FPGA. Compared to the prior works on FPGA or multi-core processors, our design demonstrates significant performance improvements.

As an important network management task, Internet traffic classification requires high throughput. Virtualization is a technique sharing the same piece of hardware for multiple users. We present a high-throughput and virtualized architecture for online traffic classification. To explore massive parallelism, we provide a conversion from a decision-tree into a compact rule set table, we employ modular processing elements and map the table to a 2-dimensional pipelined architecture. To support hardware virtualization, we develop a novel dynamic update mechanism, it requires small resource overhead and has little impact on the overall throughput. To evaluate the performance of this architecture, we implement an online traffic classification engine on a state-of-the-art FPGA. Post place-and-route results show that, our classification engine achieves 5-fold throughput compared with existing dynamically up datable online traffic classification engines on FPGA.

Packet classification is a kernel application performed at network routers. Many classification engines are optimized for prefix and exact match, while a range-to-prefix translation can lead to rule set expansion. Under limited power budget, it is challenging to achieve high classification throughput. In this paper, we present a high-performance and power-efficient packet classification engine on FPGA. We construct a modular Processing Element (PE); each PE compares a stride of the input packet header against a stride of a range boundary. We concatenate multiple PEs into a systolic array. Efficient power optimization techniques including self-enabled power gating and entropy-based scheduling are explored on our architecture. Experimental results show that, for 4K 15-field rule sets, our prototype on a state-of-the-art FPGA can achieve 250 Million Packets Per Second (MPPS) throughput. Using the proposed power optimization techniques, our classification engine consumes 30% of the power without sacrificing the throughput.

Large-scale packet classification such as Open-Flow table lookup in Software Defined Networking (SDN) is a key task performed at the Internet routers. However, the increasing size of the rule set and the increasing width of each individual rule make large-scale packet classification a challenging problem. In this paper, we present a decomposition-based approach for large-scale packet classification on multicore processors. We develop a model to predict the performance of the classification engine with respect to throughput and latency. This model involves the architectural parameters of the multi-core processors and the design requirements of packet classification. Based on this model, we employ optimization techniques such as grouping short fields in the search phase and early termination of the merge phase. The performance model can be applied to other generic multi-field classification problems as well. To evaluate the accuracy of the performance model, we implement a 15-field classification engine on state-of-the-art multi-core processors. Experimental results show that, the proposed model predicts the performance with less than ±10% error. For a 32 K 15-field rule set, the optimized decomposition-based approach achieves 2000 ns per packet latency and 33 Million Packets Per Second (MPPS) throughput (49% of the peak throughput). The peak performance assumes an ideal execution model that uses an optimized execution sequence and ignores memory access latency, data dependencies, and context switch overhead.

Traffic classification is a critical task in network management. Decision-trees are commonly used in Machine Learning (ML)-based traffic classification algorithms. Most of the existing implementations are hardware-based, while a new trend for network applications is to use software-based solutions. Since the decision-tree used for traffic classification is highly unbalanced, it is challenging to achieve high throughput for decision-tree-based traffic classification on multi-core platforms. In this paper, we present a high-throughput traffic classifier employing a scalable data structure on multi-core platforms. We convert decision-trees used in ML-based algorithms into a compact rule set table. Based on this data structure, we develop a divide-and-conquer algorithm by (1) searching all the columns of this table in parallel, and (2) merging the outcomes from all the columns into the final classification result. High throughput is sustained using our approach even if the size of the rule set table is scaled up with respect to (1) the number of decision-tree leaves and (2) the number of features examined during the classification process. We prototype our design on state-of-the-art multi-core platforms. For a typical decision-tree-based traffic classifier consisting of 128 leaf nodes and 6 flow-level features, our implementation achieves a throughput of 98 Million Lookups Per Second (MLPS). Our traffic classifier sustains high throughput even for highly unbalanced decision-trees. We achieve 1.5× throughput compared with the C4.5 decision-tree-based implementations, and 13× throughput compared with the SVM based traffic classifiers on multi-core platforms.

Traffic classification is one of the kernel applications in network management. Many Machine Learning (ML) traffic classification algorithms are based on decision-trees. While most of the existing implementations of decision-trees are hardware-based, a new trend in network applications is to use software-based solutions. The decision-tree used for traffic classification is highly unbalanced; it is challenging to achieve high performance on multi-core platforms. In this paper, we present a high-throughput and low-latency traffic classification engine on multi-core platforms. We convert the decision-tree used in the C4.5 algorithm into multiple compact tables. All the compact tables are searched in parallel; efficient hashing techniques are employed to reduce the processing latency. The outcomes from all the tables are merged into the final classification result. High throughput can be sustained even if we scale up (1) the number of concurrent traffic classifiers, (2) the number of decision-tree leaves and (3) the number of features examined during the classification process. We prototype our design on state-of-the-art AMD and Intel multi-core platforms. For a typical C4.5 decision-tree consisting of 92 leaf nodes and 7 flow-level features, we achieve 134.15 Million Lookups Per Second (MLPS) throughput and 238.53 ns processing latency per lookup. Even for highly unbalanced decision-trees or large decision-trees consisting of up to 2 K leaf nodes, our traffic classification engine sustains high throughput and low latency without sacrificing classification accuracy (≥ 98.15%). We achieve 2.7× throughput compared with the classic C4.5 decision-tree-based implementations, and at least 12× speed-up compared with the existing traffic classifiers on multi-core platforms.

Algorithms and FPGA based implementations for packet classification have been studied over the past decade. Algorithmic solutions have focused on high throughput; however, supporting dynamic updates has been challenging. In this paper, we present a 2-dimensional pipelined architecture for packet classification on FPGA, which achieves high throughput while supporting dynamic updates. Fine grained processing elements are arranged in a 2-dimensional array; each processing element accesses its designated memory locally, resulting in a scalable architecture. The entire array is both horizontally and vertically pipelined. As a result, it supports high clock rate that does not deteriorate as the length of the packet header or the size of the rule set increases. The performance of the architecture does not depend on rule set features such as the number of unique values in each field. The architecture also efficiently supports range searches in individual fields. The total memory is proportional to the rule set size. Dynamic updates- modify, delete and insert operations for the rule set during run-time are also supported on the self-reconfigurable processing elements with very little impact on the sustained throughput. Experimental results show that, for a 1K 15-tuple rule set, a state-of-the-art FPGA can sustain 190Gbps throughput with 1million updates/second. To the best of our knowledge, we are not aware of any packet classification approach that simultaneously supports both high throughput and dynamic updates of the rule set. Our architecture demonstrates 4× energy efficiency while achieving 2× throughput compared to TCAM.

Packet classification requires multiple fields of the packet header to be matched against entries in a prioritized table; it is still challenging to support dynamic updates for packet classification without sacrificing throughput performance. In this paper, we present a high-throughput pipelined architecture for packet classification on FPGA supporting dynamic updates of the rule set. This architecture is based on Dynamic Bit Vector (Dynamic-BV) approach and supports modify, delete and insert operations during run-time with very little impact on sustained throughput. Experimental results show that, for a 1K rule set on a state-of-the-art FPGA, a throughput of 120 Gbps with 1 million updates/second can be sustained using a single pipeline.