Existing network data plane verification approaches check network correctness with various models and algorithms. With respect to a specific scenario, it is hard to judge which network model provides sufficient functionality and suitable performance, because existing verification approaches are implemented with different languages and evaluated against different datasets on different hardware platforms in their papers. A network operator usually has to try out a number of complex verification approaches to find the best one for her/his network and intents. Mahjong has a modular system architecture, a unified input format, and three classic verification tools built-in. Leveraging its well-defined partition interfaces and straight-forward configuration file, not only existing approaches can be refactored and merged into Mahjong, new approaches can also be introduced and evaluated with ease.

Rate limiting with bandwidth-sharing is important and widely used in various scenarios such as multi-tenant cloud. We propose a new rate limiting architecture which fully utilizes the parallel computing capabilities on the multi-core platforms. With Bandwidth Allocator allocating the bandwidth to Rate Limiters, we expand HTB into mHTB, which could provide scalable and flexible rate limiting on multi-core platforms.

Network verification, which is mainly about checking network states against network invariants or operator beliefs, has been a popular research thesis recently. Fast calculation of all-pair reachability of the network beforehand for further query or overall analysis can be a huge assistance to network verification. In this paper, we propose a new fast all-pair reachability calculation algorithm Atomic Predicates Flooding(APF). Experiments on real-life datasets show that the new algorithm based on network atomization is about three to four orders of magnitude faster than existing algorithms without network atomization. On most kinds of datasets, APF is even 2 to 5 times faster than the Warshall based all pair reachability algorithm with atomization. We believe that our method is essential for developing more practical and more efficient network and verification tools.

Nowadays network solutions employ pattern matching methods to apply protocol identification, traffic billing, load balancing, or detecting network malicious activities. Although regular expression (regex) patterns provide a powerful option to express signatures more effectively, they make the matching procedure more challenging. Dozens of finite automata based methods have been proposed to deal with regex patterns and boost the matching procedure. However, they suffer from high spatial or temporal complexity. Recently, we proposed HES as a practical novel method to match thousands of regex patterns in a reasonable time. Although HES was extremely faster than DFA, it was unable to support regex patterns without simple pattern (SP-Free regex patterns). In this paper we developed Enhanced HES (E-HES) to handle these kinds of patterns. Experimental results revealed that E-HES not only supported SP-Free regex patterns, but also it significantly optimized the regex handler check procedure. It leads us to match any kind of regex patterns in high bandwidth networks without spatial or temporal limitation.

Reposting is the basic and key behavior for information diffusion in online social networks. It would be beneficial to understand the influence factors of reposting behavior and predict future reposting status, which could be practically applied in breaking news detection, marketing, social media researches and so on. Existing reposting analytics and prediction approaches mainly focus on factors related to the original information content and the social influence of the information publishers. However, online information diffuses by viral cascades instead of single-source broadcast in social network, which means some reposting behavior actually occurs in information propagators rather than the original publishers. In some social networks, users are allowed to comment when they repost, which represents their views and attitudes to the information they propagate. In this paper, we evaluate how emotional tendencies of information propagators influence future reposting. We first propose a modified sentiment analysis method and present emotional analysis on the user-generated content in online diffusion. Experiments are conducted with a real-world dataset and the results indicate the effectiveness of our fine-grained emotional features in reposting prediction.

With the fast industrial deployment of software-defined networking (SDN) and network function virtualization (NFV) technologies, network function policy enforcement in large scale virtualized networks becomes a key challenge for network management. Distributed policy enforcement heavily involves network policy space analysis, where set operations consume most of the computation. Based on spatial projection and bitmap indexing, a novel algorithm AHI (Atomic Hyper-Rectangle Indexing) is proposed for fast policy space set operations. Experiments with real datasets demonstrated that AHI improves set operation speed by two to three orders of magnitude and achieves the same least space cost, comparing to existing state-of-the-art algorithms r-BDD, wildcard expression, and PSA.

Regular expression matching has been widely used in today's network security systems, where the payloads of network packets are matched against a set of rules specified by regular expressions. Due to the increasing number of rules and the complex semantics of regular expressions, state-of-the-art regular expression matching techniques hardly meet the demands of network development. The rapid growth of parallel technology calls for an efficient parallel regular expression matching method. In this paper, we propose ParaRegex, a novel approach for fast parallel regular expression matching with high efficiency and low overhead. ParaRegex is a framework that implements data- parallel regular expression matching for finite automaton based methods. Experimental evaluation shows that ParaRegex produces a high-performance regular expression matching engine with low memory overhead and linear speed-up ratio, and obtains up to 6 times faster processing speed on a commodity multi-core workstation.

In this paper, we propose ParaRegex, a novel approach for fast parallel regular expression matching. ParaRegex is a framework that implements data-parallel regular expression matching for deterministic finite automaton based methods. Experimental evaluation shows that ParaRegex produces a fast matching engine with speeds of up to 6 times compared to sequential implementations on a commodity 8-thread workstation.

Network operators rely on security services to protect their IT infrastructures. Different kinds of network security policies are defined globally and distributed among multiple security middleboxes deployed in networks. However, due to the complexity of security policy, it is inefficient to directly employ existing path-wise enforcement approaches. This paper models the enforcement of network security policy as the set-covering problem, and designs a computational-geometry-based policy space analysis (PSA) tool for set operations of security policy. Leveraging the PSA, this paper first investigates the topological characteristics of different types of policies. This heuristic information reveals intrinsic complexities of security policy and guides the design of our enforcement approach. Then the paper proposes a scope-wise policy enforcement algorithm that selects a modest number of enforcement network nodes to deploy multiple policy subsets in a greedy manner. This approach can be employed on network topologies of both datacenter and service provider. The efficiencies of the PSA tool and the enforcement algorithm are also evaluated. Compared with the header space analysis, the PSA achieves much better memory and time efficiencies on set operations of security policy. Additionally, the proposed enforcement algorithm is able to guarantee network security within a reasonable number of enforcement network nodes, without introducing many extra rules.

As one of the most popular recommender technologies, Collaborative Filtering (CF) has been widely deployed in industry due to its simplicity and interpretability. However, it is facing great challenge to generate accurate similarities between users or items because of data sparsity. This will cause second order error in the process of using weighted sum as prediction. To alleviate this problem, we propose several methods to learn more accurate item similarities by minimizing the squared prediction error. This optimization problem is solved using Stochastic Gradient Descent. A comprehensive set of experiments on two real-world datasets at error and classification metrics indicate that the proposed methods can achieve comparable or even better performance than other state-of-the-art recommendation methods of Matrix Factorization, and greatly outperform traditional item based CF method. Besides, the proposed methods inherit the interpretability of item based CF, which makes the recommended results more accessible compared to competing methods of Matrix Factorization.

No abstract available.

Regular expression matching has been playing an import role in today's network security systems with deep inspection function. However, compiling a set of regular expressions into one Deterministic Finite Automata (DFA) often leads to state explosion, which means huge or even impractical memory cost. Distributing regular expressions into several groups and building DFAs independently has been proved an efficient solution, but the previous grouping algorithms are either locally optimal or time-consuming. In this work, we proposed a new grouping method based on Spectral Clustering, which defines the similarity between regular expressions and then transforms grouping problem to clustering problem. Preliminary experiments illustrate that our grouping algorithm achieves efficient result with much less processing time.

Deep inspection is widely used to identify network traffic. Due to the complexity of payload in traffic, regular expressions are becoming the preferred choice to specify the rules of deep inspection. Compiling a set of regular expressions into one Deterministic Finite Automata (DFA) often leads to state explosion, which means huge or even impractical memory cost. Distributing a set of regular expressions into multiple groups and building DFAs independently for each group mitigates the problem, but the previous grouping algorithms are either brute-force or locally optimal and thus not efficient in practice. Inspired by the Intelligent Optimization Algorithms, we propose new grouping algorithms based on Genetic Algorithm and Ant Colony Optimization algorithm, to effectively solve the problem of state explosion by acquiring the global optimum tradeoff between memory consumption and the number of groups. Besides, to accelerate the execution speed of the intelligent grouping algorithms, we employ and improve an approximation algorithm that estimates the DFA states according to the conflicting relationship between each pair of regular expressions. Experimental results verify that our solutions save around 25% memory consumption or reduce around 20% of group number compared with existing popular grouping algorithms.

Multi-tenant infrastructures deployed in cloud datacenters need network security protection. However, the rigid control mechanism of current security middleboxes induces inflexible orchestration, limiting the agile and on-demand security provision in virtualized datacenters. This paper presents Tualatin, a consolidated framework of delivering security services in multi-tenant datacenters. It meets security requirements of different scenarios by hardware and software co-design. Leveraging Software-Defined Networking (SDN) and OpenFlow techniques, Tualatin provides fine-grained security protection in dynamically changing network topologies, where both switches and security middleboxes are programmatically controlled by logically centralized controllers. With service-level APIs exposed, Tualatin could be easily integrated with other Cloud Management System (CMS). A proof-of-concept system has been deployed in a Tier-IV datacenter, providing customizable network security services for tenant Virtual Private Cloud (VPC) infrastructure.

Handling link failures is the fundamental task of routing schemes. Routing protocols based on link state (e.g., OSPF) require a global state advertisement and re-computation when link failure happens, and will cause inevitable delivery failures. To improve the routing resilience without introducing significant extra overhead, we propose a new routing approach, Keep Forwarding (KF) to achieve k-link failure resilience using inport-aware forwarding. KF is (i) flexible to handle multiple failures (or k-failure) with only small path stretch, (ii) efficient in recovery speed by instant and local lookup, (iii) bounded on memory requirement. Besides, the proposed approach is compatible with existing Internet protocols and routing infrastructures (e.g., requires no packet labeling or state recording), and the pre-computation has a linear temporal complexity. Experimental results on real ISP and datacenter networks reveal that KF guarantees near-optimal resilience (99.9%~100% for single failure and over 99.7% for multiple failures), with the average path stretch increment less than 5%.

Multituple packet classification is one of the key technologies, and often the performance bottleneck in modern network devices. Devices such as firewalls demand fast packet classification on very complicated rule sets of large size, which is still challenging today. This paper proposes a practical packet classification algorithm named dynamic discrete bit selection (D2BS), which achieves high classification speed while requiring low storage. D2BS employs dynamic heuristic schemes at bit level, to explore the inherent characteristics of the rule sets. D2BS has been implemented on various platforms including Intel-architecture, multicore network processor, and FPGA, and is compared with the state-of-the-art solutions. Experimental results on real-life rule sets show that the memory storage required by D2BS is at least one to two orders of magnitude lower than that of the existing work, while the speed is much higher. With 64-byte Ethernet packet and 10K size ACL rule set, D2BS achieves a throughput over 10 Gbps on Cavium OCTEON CN5860 multicore network processor and over 135 Gbps on Xilinx Virtex-5 FPGA, which outperforms the existing work under the same test environment. All results promise that D2BS is a highly practical solution to satisfy vigorous requirements.

Accurate performance evaluation for network algorithms is vital to meet various requirements of different applications, such as QoS, network security, traffic engineering. Although worst-case and average-case analysis are widely used in algorithm evaluation, they are often insufficient due to the lack of practicality. Smoothed Analysis (SA) introduces a new concept of smoothed complexity, remedying the shortcomings in worst-case and average-case analysis. However, recent research towards SA focuses on theoretical evaluation, and thus those methods tend to be too complicated for the analysis of network algorithms. To address the problem, Sampling-based Smoothed Analysis (SSA) for network algorithm evaluation is proposed. SSA extends feasibility for practical performance evaluation and achieves promising experimental results. As examples, two algorithms for typical network problem are evaluated using the proposed SSA framework, and the results explicitly illustrate their significant performance difference in spite of the same theoretical worst-case complexity. Besides evaluation accuracy, SSA also provide more insight for algorithms to facilitate current algorithms improvement and new algorithms design.

Internet traffic has been exponentially growing with the increasing demand of content dissemination. This explosive growth in traffic poses a significant challenge to the networks, especially backbones. To address the challenge, the emerging content-oriented Named Data Networking (NDN) has been proposed due to its attractive advantages, such as network load reduction, low dissemination latency and energy efficiency. To achieve these benefits from NDN paradigm, the content caching strategy plays the most important role. In this paper, we present a popularity-based coordinated caching scheme with the objective of eliminating both the inter-domain and intra-domain redundant traffic of a backbone network. In this design, the global content popularity is obtained by the weighted aggregation of local content popularity at the routers, then the cache placement can be calculated based on the access cost guided by the global content popularity. We test our caching scheme on the publicly available backbone networks: Abilene and GEANT. Simulation results show that the proposed caching scheme achieves around 30% higher cache hit rate and 20% more traffic reduction, compared with the widely used Leaving Copies Everywhere (LCE) and Random Cache (RanCache) scheme.

The Named Data Networking (NDN) is proposed recently as a promising paradigm for the future Internet due to its built-in caching and name-based routing for efficient content distribution. For the time being, the research on NDN caching is still a preliminary topic, especially for the scenario of an ISP with multiple gateways. For more in-depth excavation, we have studied the effective intra-ISP caching under multiple gateways and multi-path routing in this paper. With the primary objective of reducing the inter-ISP traffic, we develop a popularity-based coordinated caching strategy named the Effective Multi-path Caching scheme (EMC), which substantially saves more than 50% inter-ISP traffic and more than 30% content access latency. Through evaluation, we observe that EMC significantly outperforms the widely used Leaving Copies Everywhere (LCE) scheme and Leaving Copies with Probability (LCProb) scheme in terms of reducing both the inter-ISP traffic as well as the content access latency. Extensive simulation results demonstrate that our proposed caching scheme is effective, scalable and light-weight.

Regular expression matching is popular in today's network devices with deep inspection function, but due to lack of algorithmic scalability, it is still the performance bottleneck in practical network processing. To address this problem, our method first partition regular expression patterns into simple segments to avoid state explosion, and then compile these segments into a compact data structure to achieve fast matching. Preliminary experiments illustrate that our matching engine scales linearly with the size of the real-world pattern set, and outperforms state-of-the-art solutions.

Most recent works demonstrate that grouping methodology could bring significant reduction of memory usage to decision-tree packet classification algorithms, with insignificant impact on throughput. However, these grouping techniques can hardly eliminate rule-replication completely. This work proposes a novel rule grouping algorithm without any replication. At each space decomposition step, all rules projecting on the split dimension form the maximum number of non-overlapped ranges, which guarantees the modest memory usage and grouping speed. Evaluation shows that the proposed algorithm achieves comparable memory size with less pre-processing time.

In this paper, we have designed a Multi-Frequency Scaling scheme for energy conservation of network devices, especially routers and switches. The frequency of components in a network device is scaled dynamically according to the real time workload. A Markov model is developed for performance analysis of this mechanism. We implement a prototype of this scheme in the data path of a general IPv4 router based on a real hardware platform - NetFPGA. Experimental results show excellent energy savings at the cost of a tolerable latency, under various ranges of traffic loads. Our work indicates the feasibility and possibility of deploying this mechanism into real network devices for energy saving.

The built-in caching capability of future Named Data Networking (NDN) promises to enable effective content distribution at a global scale without requiring special infrastructure. The aim of this work is to design efficient caching schemes in NDN to achieve better performance at both the network layer and application layer. With the specific objective of minimizing the inter-ISP (Internet Service Provider) traffic and average access latency, we first formulate the optimization problems for different objectives and then solve them to obtain the optimal replica placement. Then we develop popularity-driven caching schemes which dynamically place the replicas in the caches on the en-route path in a coordination fashion. Simulation results show that the performances of our caching algorithms are much closer to the optimum and outperform the widely used schemes in terms of the inter-ISP traffic and the average number of access hops. Finally, we thoroughly evaluate the impact of several important design issues such as network topology, cache size, access pattern and content popularity on the caching performance and demonstrate that the proposed schemes are effective, stable, scalable and with reasonably light overhead.

Most of state-of-the-art packet classification algorithms employ heuristics to trade off between classification speed and memory usage. However, intelligent heuristics often result in complex data structures in algorithm implementation. This brings difficulties to the deployment and optimization of packet classification algorithms. In this poster, a structural compression approach is presented for decision tree based packet classification algorithms. This approach exploits the similarity in real-life filter sets to achieve high compression ratio without loss of tree semantics.

Cloud datacenters, providing Infrastructure as a Service (IaaS), need to lively orchestrate numerous resource elements with diverse requirements of service provision, which most existing approaches are difficult to meet elastically. This paper presents LiveCloud, a management framework for resources in cloud datacenters. It addresses multiple management issues by employing different views of datacenter resources to satisfy various requirements for both tenants and operators. Leveraging software defined networking (SDN) techniques, LiveCloud further integrates network resources into datacenter orchestration and service provision with improved service-level agreements and faster service delivery. LiveCloud is architected as a data-centric and event-driven system with open management interfaces and service-oriented APIs to simplify system integration and service provision. The LiveCloud system has been deployed in both private and public datacenters to provide elastic cloud infrastructure for production applications.

Archiving Internet traffic is a function essential for retrospective network event analysis. The state-of-art approach for network monitoring and analysis is storing and analyzing the statistics of network flows. However this approach loses much valuable information inside Internet traffic. With the advancement of commodity hardware, especially the volume of storage device and the speed of interconnect technologies used in network adapter card, now it is practical to capture 10Gbps real-time network traffic with a commodity computer. In this context, this paper presents the design and implementation of a novel system for archiving and querying network flows. A flow granularity indexing mechanism and storage are proposed, and the bitmap index database is utilized to store index information. Based on real network traces, we demonstrate that the system has a higher performance in storing and querying with respect to both time and space metrics compared with traditional methods.

Internet has evolved to be content-oriented and its key usage focuses on content dissemination and retrieval, while Internet architecture is designed for host-oriented services. To address the challenge, Named Data Networking (NDN) has been proposed, where in-network caching becomes a new research topic due to its dominant position in NDN architecture. This work develops efficient caching schemes for Internet Service Providers (ISPs) so as to maximize the inter-ISP traffic savings. With the special goal, we design caching system according to the NDN network model and present coordinated caching algorithms which can dynamically determine cache placement along the forwarding path. Comprehensive simulation results show that our schemes outperform the widely used Leaving Copies Everywhere (LCE) both in inter-ISP traffic savings and the average number of access hops by up to 20%. In addition, we demonstrate good feasibility of the proposed caching algorithms in a set of simulations spanning a wide range of parameter values.

TCP and IP fragmentation can be used to evade signature detection at Intrusion Detection/Prevention System (IDS / IPS). Such fragments may arrive out-of-sequence to escape from being detected by the string matching algorithm of IDS / IPS. The common defense is buffering and reassembling packets. However, buffering of out-of-sequence packets can become impractical on high speed links due to limited fast memory capacity, especially when the concurrent flows are in large quantity, or extremely disordered in circumstances such as attacks. So such buffering strategy is vulnerable to memory exhausting denial of service (DoS). In this paper, AC-Suffix-Tree, a buffer free scheme for string matching is proposed, which detects patterns across out-of-sequence packets without buffering and reassembly. This novel algorithm associates the classical Aho-Corasick (AC) algorithm with a pattern suffix tree to search patterns with only the state numbers of AC automaton and suffix tree stored. It demands significantly less memory than buffering the packets themselves. Therefore the IDS can resist memory exhausting DoS attack. AC-Suffix-Tree consumes 1-2 orders of magnitude less memory than buffering the entire packet, and it has the same temporal complexity as AC algorithm when there are no out-of-sequence packets.

Network traffic classification is extremely important in numerous network functions today. However, most of the current approaches based on port number or payload detection are becoming increasingly impractical with the appearance of dynamic or encrypted applications. Even though some supervised learning based work were proposed, it is difficult to collect sufficient flow-labeled traces for training. On the other hand, online classification needs an early identification, which is still challenging for most well-known approaches. In this paper, we propose a semi-supervised learning based traffic classification approach named SMILER, which supports an early classification from the sizes of the first few packets (empirically 5 packets) of a flow. Experiments in real networks demonstrate that SMILER achieves 94% precision and 96% recall on average for all tested applications, even with disordered packets SMILER still works well. With a hybrid scheme, the performance is further improved. Meanwhile, SMILER performs fast in both classification and updating. All experimental results show that SMILER is practical for fast and accurate online traffic classification.

Regular expression matching has become a critical yet challenging technique in content-aware network processing, such as application identification and deep inspection. To meet the requirement for processing heavy network traffic at line rate, Deterministic Finite Automata (DFA) is widely used to accelerate regular expression matching at the expense of large memory usage. In this paper, we propose a DFA-based algorithm named RCDFA (Reorganized and Compact DFA), which dramatically reduces the memory usage while maintaining fast and deterministic lookup speed. Based on the dissection of real-life DFA tables, we observe that almost every state has multiple similar states, i.e. they share identical next-state transitions for most input characters. However, these similar states often distribute at nonadjacent positions in the original DFA table. RCDFA aims at reorganizing all similar states into adjacent entries, so that identical transitions become consecutive along the state dimension, then compresses the reorganized DFA table utilizing bitmap technique. Coupled with mapping along the character dimension, RCDFA is not only efficient in DFA compression, but also effective for hardware implementation. Experiment results show, RCDFA has superior performance in terms of high processing speed, low memory usage and short preprocessing time. RCDFA consistently achieves over 95% compression ratio for existing real-life rule sets. Implemented in a single Xilinx Virtex-6 FPGA platform, RCDFA matching engine achieved 12Gbps throughput.

Modern networks are increasingly becoming content aware to improve data delivery and security via content-based network processing. Content-aware processing at the front end of distributed network systems, such as application identification for datacenter load-balancers and deep packet inspection for security gateways, is more challenging due to the wire-speed and low-latency requirement. Existing work focuses on algorithm-level solutions while lacking system-level design to meet the critical requirement for front-end content processing. In this paper, we propose a system-level solution named FEACAN for front-end acceleration of content-aware network processing. FEACAN employs a software-hardware co-design supporting both signature matching and regular expression matching for content-aware network processing. A two-dimensional DFA compression algorithm is designed to reduce the memory usage and a hardware lookup engine is proposed for high-performance lookup. Experimental results show that FEACAN achieves better performance than existing work in terms of processing speed, resource utilization, and update time.

Multi-dimensional packet classification is a key task in network applications, such as firewalls, intrusion prevention and traffic management systems. With the rapid growth of network bandwidth, wire speed multi-dimensional packet classification has become a major challenge for next-generation network processing devices. In this paper, we present a FPGA-based architecture targeting 100 Gbps packet classification. Our solution is based on HyperSplit, a memory-efficient tree search algorithm. First, we present an efficient pipeline architecture for mapping HyperSplit tree. Special logic is designed to support two packets to be processed every clock cycle. Second, a node-merging algorithm is proposed to reduce the number of pipeline stages without significantly increasing the memory requirement. Third, a leaf-pushing algorithm is designed to control the memory usage and to support on-the-fly rule update. The implementation results show that our architecture can achieve more than 100 Gbps throughput for the 64-byte minimum Ethernet packets. With a single Virtex-6 chip, our approach can handle over 50K rules. Compared with the state-of-the-art multi-core network processor based solutions, our FPGA design offers at least a 10x improvement in throughput performance.

Inline stateful and deep inspection for network intrusion prevention system (NIPS) is progressively challenging to cope with the fast growing volume and ever increasing complexity of network traffic. Traditional cluster-based architectures provide a solution for scalable and high performance NIPS, but with some common limitations. This paper proposed yet another cluster-based architecture (YACA) with a stateful traffic splitter. As an architectural approach for building a high performance NIPS, we present a novel design of stateful traffic splitter. The performance of its network processor implemented prototype demonstrates that such a design is suitable for the proposed architecture.

With the continual growth of network speed and the increasing sophistication of network applications, keeping network operations efficient and secure becomes more challenging. Pattern matching is one of the key technologies for content-ware network processing, such as traffic classification, application identification and intrusion prevention. In this paper, we propose a hybrid pattern matching algorithm optimized for multi-core network processing platforms. As a system-level solution, our scheme focuses on both performance stability and hardware/software co-design. To verify the effectiveness of our design, the proposed algorithm is implemented on a state-of-art 16-MIPS-core network processing platform and evaluated with real-life data sets. Experimental results show that, when compared with the traditional Aho-Corasick algorithm, our hybrid solution saves 60~95% memory space while guarantees stable performance on large pattern sets and against adverse test traffic.

Inline stateful and deep inspection for intrusion prevention is becoming more challenging due to the increase in both the volume of network traffic and the complexity of the analysis requirements. In this work, we pursue a novel architectural approach, named SANS, which takes both the advantage of new generation network processors for packet-header-based processing and the advantage of commodity x86 platforms for packet payload data processing. A session table scheme is designed for the stateful frontend in SANS to achieve wire speed inline processing.

In this paper, we propose an extensible Open-Architecture Services platform (OASis) for high-performance network processing. OASis embraces recent advances of open technologies, including open source software, open system standards and open network architectures. Three programming models are proposed for target-specific processing modules: a multi-granularity packet processing model for network processing; a thread-isolated parallel programming model for service processing; and a message-based management model for centralized system administration. As an application example of OASis, a Unified Threat Management (UTM) prototype is implemented. This prototype provides multiple network security services, including stateful firewall, intrusion detection, and virus scanning. Experimental results show that, the OASis-UTM prototype can achieve 40Gbps stateful firewall performance together with 4--8Gbps intrusion detection and anti-virus performance on a 12U 14-slot ATCA platform.

Network intrusion prevention system (NIPS) becomes more complex due to the rapid growth of network bandwidth and requirement of network security. However existing solutions, either hardware-based or software-based cannot obtain a good tradeoff between performance and flexibility. In this paper, we propose a parallel NIPS architecture using emerging network services processor. To resolve the problems and bottlenecks of high-speed processing, we investigate the main design aspects which have dramatic impacts on most parallel network security system implementations: efficient and flexible pipeline and parallel processing, flow-level packet-order preserving, and latency hiding of deep packet inspection. To these key points, we address several optimizations and modifications with an architecture-aware design principle to guarantee high performance and flexibility of the NIPS on a network services processor implementation. Performance evaluation shows that, our prototype NIPS on Cavium OCTEON3860 processor can reach line-rate stateful inspection and multi-Gbps deep inspection performance.

Packet classification is one of the most critical techniques in many network devices such as firewall, IDS and IPS, etc. In order to meet the performance requirement for high speed Internet (even higher than 10 Gbps), practical algorithms must keep better spatial and temporal performance. Moreover, as the size of rule set is increasing to tens of thousands, novel packet classification algorithms must have good scalability. In this paper, we propose a novel packet classification algorithm named DBS (discrete bit selection) which takes a bit level heuristic design to partition the rule set effectively. To the best of our knowledge, DBS is the first try to design a heuristic classification algorithm at bit-level. To evaluate the performance of our algorithm, DBS is deployed on a popular multi-core network processor platform, compared with two existing well-known algorithms. Experimental results show that DBS achieves 300% higher throughput than HiCuts and HSM, while the memory requirement is reduced to about 10% averagely. DBS works well especially with large rule set (10K), which trends a good scalability.

During the past decade, the packet classification problem has been widely studied to accelerate network applications such as access control, traffic engineering and intrusion detection. In our research, we found that although a great number of packet classification algorithms have been proposed in recent years, unfortunately most of them stagnate in mathematical analysis or software simulation stages and few of them have been implemented in commercial products as a generic solution. To fill the gap between theory and practice, in this paper, we propose a novel packet classification algorithm named HyperSplit. Compared to the well-known HiCuts and HSM algorithms, HyperSplit achieves superior performance in terms of classification speed, memory usage and preprocessing time. The practicability of the proposed algorithm is manifested by two facts in our test: HyperSplit is the only algorithm that can successfully handle all the rule sets; HyperSplit is also the only algorithm that reaches more than 6Gbps throughput on the Octeon3860 multi-core platform when tested with 64-byte Ethernet packets against 10K ACL rules.

To build high-performance network devices with holistic security protection, a large number of algorithms have been proposed. However, multi-core implementation of the existing algorithms suffers from three limitations: performance instability, data-structure heterogeneity, and hardware dependency. In this paper, we propose three principles for effective network processing on multi-core network processors. To verify the effectiveness of these principles, algorithms for two typical network processing tasks are redesigned and implemented on the Cavium Octeon3860 network processor. Test results show that our schemes achieve superior performance in comparison with existing best-known algorithms.

The security gateways today are required not only to block unauthorized accesses by authenticating packet headers, but also by inspecting connection states to defend against malicious intrusions. Hence session creation rate plays a key role in determining the overall performance of stateful intrusion prevention systems. In this paper, we propose a high-speed session creation scheme optimized for network processors. Main contribution includes: a) A high-performance flow classification algorithm on network processors; b) An efficient TCP three-way handshake scheme designed for fast-path processing using a two-stage intelligent hashing. Experimental results show that: a) The presented parallel optimized flow classification algorithm, Parallel Search Cross-Producting, outperforms the original Cross-Producting and Binary Search Cross-Producting algorithms with 300% and 60% increase of classification speed; b) The proposed fast path three-way handshake scheme, IntelliHash, achieves a TCP connection creation rate over 2M connections per second.

There is a growing interest in designing high-performance network devices to perform packet processing at flow level. Applications such as stateful access control, deep inspection and flow-based load balancing all require efficient flow-level packet processing. In this paper, we present a design of high-performance flow-level packet processing system based on multi-core network processors. Main contribution of this paper includes: a) A high performance flow classification algorithm optimized for network processors; b) An efficient flow state management scheme leveraging memory hierarchy to support large number of concurrent flows; c) Two hardware-optimized order-preserving strategies that preserve internal and external per-flow packet order. Experimental results show that: a) The proposed flow classification algorithm, AggreCuts, outperforms the well-known HiCuts algorithm in terms of classification rate and memory usage; b) The presented SigHash scheme can manage over 10M concurrent flow states on the Intel IXP2850 NP with extremely low collision rate; c) The performance of internal packet order-preserving scheme using SRAM queue-array is about 70% of that of external packet order-preserving scheme realized by ordered-thread execution.

The oncoming prosperity of interactive multimedia application triggers significant challenge to current best-effort Internet because of the dynamic and unpredictable available bandwidth, end-to-end delay, and packet loss. Recently, overlay technique has emerged as an approach to help mitigating these problems. In order to understand the potential benefits of using multi-path provided by overlay network to interactive video, this paper examines the performance of two special multi-path deliver schemes dual-path mesh and dual-path round robin, and compares their metrics of round-trip delay, packet loss, one-way delay jitter to the direct Internet path by analyzing 7 days of data collected from 102 geographically diverse PlanetLab nodes. By mapping the collected data with MPEG-4 coded "Foreman" video sequence, the paper also presents multipath benefit on peak signal-to-noise ratio (PSNR).

In this paper, a novel packet classification scheme optimized for multi-core network processors is proposed. The algorithm, Explicit Cuttings (ExpCuts), adopts a hierarchical space aggregation technique to significantly reduce the memory usage. Consequently, without burst of memory usages, the time-consuming linear search in the conventional decision-tree based packet classification algorithms is eliminated, and an explicit worst-case search time is achieved. To evaluate the performance of ExpCuts, we implement the algorithm, as well as HiCuts and HSM, on the Intel IXP2850 network processor. Experimental results show that ExpCuts outperforms the existing best-known algorithms in terms of memory usage and classification speed.

Next-generation high-end network processors (NP) must address demands from both diversified applications and ever-increasing traffic pressure. One major challenge is to design an extraordinary scalable architecture. In this paper, it is argued that such an objective can only be sufficed by introducing highly paralleled structure, namely the paralleled processing-engine cluster (PPC). We demonstrate this point from the trade-off among aspects such as performance, programmability and flexibility. However, PPC natively suffers from several critical issues on load-balancing, intra-flow packet ordering and memory contention. After investigating several existing approaches, we present novel solutions for each issue according to the balance between performance and coast. Through intensive analysis and comprehensive simulations, it is shown that the shortest queue first scheduling with class-based prediction (SQF-C) performs nearly optimally, while the hardware based per-flow ordering mechanism resolves packet out-of-order independently with the load-balancing issue, inducting little throughput degradation. Implementing the unified solution, it is capable to design a PPC supporting up to OC-768c line rate. Real implementation is also carried out in our THNPU-1 prototype to verify the conclusions.

The prosperity of various real-time applications triggers significant challenges for the Internet to meet the critical end-to-end delay requirements. This paper investigates the feasibility and practical issues of using overlay routing to improve end-to-end delay performance, with the analysis of round trip time data collected over three months by the all pairs pings project between each pair of hundreds of nodes on the Planet- Lab. The results show: 1) overlay routing has the potential to reduce the round trip time by 40 milliseconds and increase network connectivity by 7% on average; 2) even simple static overlay paths can reduce end-to-end delay, while the dynamic algorithm does better; 3) Over 80% of the shortest overlay paths have no more than 4 hops, and a simple algorithm leveraging only one relay node can efficiently take the advantages of overlay routing.

While delay-critical applications typified by online multimedia communication are growing rapidly, the end-to-end (E2E) delay behavior in the Internet remains poorly understood. This paper proposes a stochastic process model, in which E2E delay alternations are classified into two categories, jump and perturbation, according to whether the statistical characterizations alter or not. As the chief type of majority delay alternations, perturbations generally occur continuously in a period, and can be analogous to an ergodic stationary process. The authenticity of the model is verified with real life delay measurements in the Internet collected by all pairs pings (APP) project through months from PlanetLab nodes. Based on the model, several delay estimation algorithms are comparatively analyzed, and the experimental results demonstrate that in terms of minimizing the mean squared error, the most accurate delay prediction is the minimum of the two most recent measurements.

Packet classification on multiple header fields is one of the basic techniques used in network devices such as routers and firewalls, and usually the most computation intensive task among others. To determine what action needs to be taken to a packet, a network device responsible for packet classification must identify the packet's property, such as associated packet flow, based on multiple fields of its header. Fast packet classification on multiple fields is known to be difficult mathematically and expensive practically. In this paper, we describe and discuss a fast packet classification algorithm using a multiple stage reduction scheme similar to the previously well-known recursive flow classification (RFC) algorithm. The proposed hierarchical space mapping (HSM) algorithm requires much less memory usage than RFC while keeps average search time on the same order. HSM has been proved to be very effective with commercial products in real networks.