Knowledge graph embedding (KGE) is typically used for link prediction to automatically predict missing links in knowledge graphs. Current KGE models are mainly based on complicated mathematical associations, which are highly expressive but ignore the uniformity behind the classical bilinear translational model TransE, a model that embeds all entities of knowledge graphs in a uniform space, enabling accurate embeddings. This study analyses the uniformity of TransE and proposes a novel KGE model called ConvUs that follows uniformity with expressiveness. Based on the convolution neural network (CNN), ConvUs proposes constraints on convolution filter values and employs a multi-layer, multi-scale CNN architecture with a non-parametric L2 norm-based scoring function for the calculation of triple scores. This addresses potential uniformity-related issues in existing CNN-based KGE models, allowing ConvUs to maintain a uniform embedding space while benefiting from the powerful expressiveness of CNNs. Furthermore, circular convolution is applied to alleviate the potential orderliness contradictions, making ConvUs more suitable for conducting uniform space KGE. Our model outperformed the base model ConvKB and several baselines on the link prediction benchmark WN18RR and FB15k-237, demonstrating strong applicability and generalization and indicating that the uniformity of embedding space with high expressiveness enables more efficient knowledge graph embeddings.

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. In these applications, throughput is a key performance metric. Due to the low memory complexity, Sketch-based techniques can be supported by the fast onchip storage of the 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 Sketchbased 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 150Gbps, demonstrating significant throughput performance improvements compared with other Sketch acceleration techniques. Our architectures for online anomaly detection tasks sustain 100-150 Gbps throughput for various system configurations.

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.

Detecting heavy activity aggregation in data streams is a critical task for many networking, data base and data-mining applications. The aggregation points often belong to hierarchical domains (e.g. IP domain, XML data tree, etc.). These aggregation points are referred to as hierarchical heavy hitters. The hierarchical domains is usually very large with respect to both the number of aggregation points and the number of levels in the hierarchy. Due to the huge amount of intermediate data to be maintained and the dependency between hierarchy levels, it is challenging to detect hierarchical heavy hitters in very large hierarchical domains at high throughput. In this work, we propose a novel Sketch-counter-hybrid algorithm that decomposes the online hierarchical heavy hitter detection to independent and parallel online heavy hitter detection at each hierarchy level. We then propose a fully pipelined architecture suitable for FPGA implementation to accelerate the algorithm. We use IP network monitoring as an example of application. The post place-and-route results on a state-of-the-art FPGA show high throughput and scalability. Our architecture achieves 123 Gbps throughput assuming minimum-sized IPv4 packets while supporting the entire 32-bit IPv4 hierarchy on a single FPGA device. It sustains 100+ Gbps throughput while supporting various hierarchy sizes, stream sizes and accuracy requirements. Our architecture achieves much higher throughput than other techniques when accelerating Sketches of similar number of rows and columns, and counter sizes.

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.

Machine learning (ML) algorithms have been shown to be effective in classifying the dynamic internet traffic today. Using additional features and sophisticated ML techniques can improve accuracy and can classify a broad range of application classes. Realizing such classifiers to meet high data rates is challenging. In this paper, we propose two architectures to realize complete online traffic classifier using flow-level features. First, we develop a traffic classifier based on C4.5 decision tree algorithm and Entropy-MDL discretization algorithm. It achieves an accuracy of 97.92% when classifying a traffic trace consisting of eight application classes. Next, we accelerate our classifier using two architectures on FPGA. One architecture stores the classifier in on-chip distributed RAM. It is designed to sustain a high throughput. The other architecture stores the classifier in block RAM. It is designed to operate with small hardware footprint and thus built at low hardware cost. Experimental results show that our high throughput architecture can sustain a throughput of $550$ Gbps assuming 40 Byte packet size. Our low cost architecture demonstrates a 22% better resource efficiency than the high throughput design. It can be easily replicated to achieve $449$ Gbps while supporting 160 input traffic streams concurrently. Both architectures are parameterizable and programmable to support any binary-tree-based traffic classifier. We develop a tool which allows users to easily map a binary-tree-based classifier to hardware. The tool takes a classifier as input and automatically generates the Verilog code for the corresponding hardware architecture.