Monitoring the Mean Opinion Score (MOS) of video conferencing is critical for Internet Service Providers (ISPs) to ensure user satisfaction. However, a significant technical challenge arises: MOS is a subjective measure, while ISPs primarily rely on deep packet inspection (DPI) data for performance monitoring, making direct mapping between MOS and DPI data nearly impossible. To address this gap, we develop DePI-MOSE, a novel solution that leverages sub-application-level video context clues to build machine-learning models. By inferring the type of end devices and identifying the motion level within video content during a conference session, DePI-MOSE can estimate MOS values from DPI data accurately. We implemented and tested DePI-MOSE in a real-world ISP network, and experimental results show that DePI-MOSE is more accurate than state-of-the-art methods. We also built a network resource management platform for ISPs to dynamically adjust users' network resources by precisely monitoring users' video conferencing QoE.

Stateful data plane network applications are indispensable but their efficiency is hindered by prevalent network device architectures which utilize a Blocking Scheme to maintain state consistency. The Blocking Scheme results in poor throughput and latency performance due to its frequent halts during packet processing. In response to this issue, we propose an innovative Non-Blocking Scheme and construct a theoretical model based on the G/GI/m queueing model. The new scheme leverages the speculative execution method, avoiding unnecessary blocking by taking advantage of the fact that the state update ratio is usually much smaller than the incoming packet rate. In case of speculation failures, the affected packets are reprocessed to guarantee state consistency. We provide an approximate model for the Blocking Scheme, and show that, even with relaxed approximations, the Blocking Scheme still performs worse than the Non-Blocking Scheme. The superior performance of the Non-Blocking Scheme is further corroborated through rigorous simulations, conducted under both realistic and synthetic traces. Based on our model, we propose an enhanced architecture: SN_RAPID (Sequence Number and unidirectional Reverse path-Augmented PIpeline Dataplane), to support speculative execution. The architecture is simpler than the other architectures supporting stateful network functions. Serving as a design foundation for future iterations, we implement a prototype of SN_RAPID in FPGA which can run at line speed, and also develop a software ASIC emulator. The experiments show the superiority of the improved architecture.

Despite considerable advancements in specialized hardware, the majority of IoT edge devices still rely on CPUs. The burgeoning number of IoT users amplifies the challenges associated with performing multiple Deep Neural Network inferences on these resource-limited, CPU-only edge devices. Existing strategies, including model compression, hardware acceleration, and model partitioning, often involve a trade-off in inference accuracy, are unsuitable due to hardware specificity, or lead to inefficient resource utilization. In response to these challenges, this paper introduces L-PIC (Latency Minimized Parallel Inference on CPU)—a framework expressly devised to optimize resource allocation, decrease inference latency, and maintain result accuracy on CPU-only edge devices. A series of comprehensive experiments have verified the superior efficiency and effectiveness of the L-PIC framework in comparison to the state-of-the-art method. Remarkably, compared to the state-of-the-art method, L-PIC can reduce the inference latency of multi-DNN by an average of approximately 30% across all tested scenarios.

Interconnection network in HPC is becoming a bottleneck due to increasing traffic load. We model adaptive routing mechanisms and prove that even with advanced adaptive routing, static networks like Dragonfly cannot handle non-uniform traffic efficiently, let alone the frequently changing non-uniform traffic. Therefore, it requires architectural changes for network-wide improvements, e.g., reconfigurable networks.Existing reconfigurable networks hardly support agile reaction to traffic changes with little impact on network. Therefore, we propose MUSE1, a Dragonfly-based runtime incrementally reconfigurable network to enable a small number of link adjustments for agility and little impact on transmitting flows during every reconfiguration with optical circuit switch (OCS).Simulations with both synthetic traffic and real-world workloads prove that MUSE can prevent saturation under typical traffic patterns that cause congestion in static Dragonfly. MUSE is 30-55% better than static Dragonfly and Flexfly w.r.t commonly used performance metrics like flow completion time (FCT). We also build a MUSE prototype and demonstrate that MUSE enables 20-30% less application finish time (AFT).

Network dataplane calls for better programmability. Current programmable network processing chips are based on either pipeline or multi-core Run-To-Completion (RTC) architecture with various trade-offs in flexibility, performance, and cost. The existing attempts to amalgamate the strengths of the two are stilted and inflexible. In this paper, we challenge the status quo by introducing a more fluid and organic programmable chip architecture, OptimusPrime, built from identical hardware blocks. Unlike the conventional static hybrid architecture, OptimusPrime allows each block to be transformed into either a pipeline stage processor or a multi-core RTC processor through software-defined configuration, enabling versatile data plane programming tailored to a wide range of applications (e.g., stateful packet processing and in-network computing). We integrate the C and P4 languages for application programming and develop algorithms to map a user program to the optimal distribution of pipeline stages and RTC cores. We demonstrate the viability of OptimusPrime through practical use cases such as in-network aggregation, in-network caching, and network function integration. We developed an FPGA-based prototype and a software-based ASIC simulator to validate the feasibility of OptimusPrime, which can be used by switches and smartNICs to enhance their programmability to a new level with high performance and low cost.

This work aims to design a real-time inference scheduler that delivers accurate and timely edge inference ser-vices for dynamic inference arrivals by leveraging dynamic batching and early-exiting techniques. Specifically, we consider an edge inference server that is preinstalled with multiple early-exit Deep Neural Networks (DNNs) that support batch processing. The in-ference tasks with strict deadline requirements arrive at the edge server randomly, and the utility of each timely processed task depends on the achieved accuracy. Therefore, we aim to design an edge inference scheduler that maximizes the system's total utility subject to resource and deadline constraints. We present this problem's mixed integer linear programming formulation. This problem is challenging due to high computational complexity, coupled-decision making, and task randomness. We propose to decompose the original problem into two sub-problems: the task assignment problem and the DNN configuration problem. For the task assignment problem, we develop a greedy task assignment algorithm. For the DNN configuration problem, we propose a Deep Reinforcement Learning-based solution. Simulation results show that the proposed algorithms outperform the state-of-the-art baselines.

As a programmable accelerator, SmartNIC provides more opportunities for algorithmic packet classification. Our aim in this work is to achieve both line-speed rule search and efficient rule update, two highly desired metrics for SDN data plane. We leverage the parallelism offered by the FPGA in SmartNIC following an algorithm/hardware co-design paradigm. Particularly, we first design an algorithm that constructs multiple trees for the rule set with a recursive rule sifting process. Unlike traditional space-cutting-based multi-tree construction, our rule sifting mechanism breaks the space constraints of rule-to-tree mapping and enables bounded height on each tree, thus providing the potential of bounded worst-case and line-speed performance. We then design a flexible hardware architecture with multiple systolic arrays that can be implemented in parallel on FPGA. Each systolic array works as a coarse-grained pipeline, and the multiple trees constructed earlier will be mapped onto these pipeline stages. This hardware-software mapping enables bounded worst-case rule searching. Additionally, incremental rule update is achieved simply by traversing the pipeline in one pass, with little and bounded impact on rule searching. Experimental results show that our design achieves an average classification throughput of 600.8/147.5 MPPS and an update throughput of 8.2/5.9 MUPS for 10k/100k-scale 5-tuple and OpenFlow rule sets.

Software-based IP route lookup is a key component for packet forwarding in Software Defined Networks. Running lookup algorithms on commodity CPUs is flexible and scalable, which shows advantages on cost and power consumption over the hardware-based forwarding engines. However, dynamic network functions and services make route updates more frequent than ever. Existing algorithms often fall short of the incremental update requirements. In this paper, we propose the Overlay BitMap Algorithm (OBMA), which contains several variations, to support extraordinary update performance while maintaining the highest-in-class lookup speed and storage efficiency. Starting from the basic OBMA_B, we develop two variations with different tradeoffs for different application scenarios. OBMA_L supports faster lookups than OBMA_B at a small cost of update speed. OBMA_S achieves better storage efficiency than OBMA_B at a small cost of lookup throughput. We run our algorithms on a commodity CPU and evaluate them with real-world route tables and traces. The experiments show that OBMA achieves the lowest memory footprint, the highest update speed, and over 200 Mpps lookup throughput. Specifically, OBMA_S reduces the memory footprint to 3.98 bytes/prefix which is 25.33% smaller that of the state-of-the-art Poptrie; OBMA_L supports 252.02 Mpps lookup throughput with a single thread, and more than 600 Mpps with multiple parallel threads in a single CPU, significantly outperforming the state-of-the-art Poptrie and SAIL; OBMA_B supports updates at a rate of 14.58M updates/s which is 15 times faster than Poptrie. The tests show that the update process has little interference with the lookup process for OBMA, and achieves zero-interrupt to lookups with multiple threads.

Low Earth orbit (LEO) satellite networks have attracted extensive research due to their potential to provide high-quality Internet access services. However, the existing TCP variants, which are designed for terrestrial networks, can hardly work in LEO satellite networks with characteristics such as error-prone, bandwidth variations, and link switching. To address these challenges, in this paper we present a new information-centric transport layer protocol LEOTP to guarantee reliable, high-throughput, and low-latency data transmission in LEO satellite networks. It leverages the idea of Information-Centric Networking (ICN) with a Request-Response transmission model and in-network caching. The connectionless transmission paradigm in LEOTP makes it resilient to dynamic topology changes. The caches equipped in intermediate nodes help to recover packet loss while the hop-by-hop congestion control mechanism provides a fast reaction to time-varying network conditions. We evaluate the performance of LEOTP in emulated Starlink constellation, which shows that it increases the throughput by 8%-12% with 40%-60% delay reduction compared with the state-of-the-art TCP variants in the transcontinental data transmission.

Accurate per-flow counting is beyond the capability of network switches due to the sheer flow number. The conventional divide-and-conquer method by distributing the traffic to multiple servers for software processing is costly. The solution therefore quests for a combination of hardware and software where the hardware with limited resources aims to undertake a part of the job and reduce the workload of software, achieving a desirable balance of cost and performance. To this end we design FASTeller to be deployed on SmartNICs. It is tuned to maximize the counting aggregation level in hardware, leaving the server a much lower workload for accurate per-flow counting and sparing the server capacity for post-counting functions such as network intrusion detection. The novelty lies in the multi-tier hardware caching data structure which is tailored for the flow distribution properties of real traffic. We build an FPGA-based prototype and evaluate the performance of FASTeller. The low-cost implementation achieves the highest performance among the methods in comparison and can easily sustain the accurate perflow counting for 100Gbps traffic with the least software load.

Flow table is a fundamental and critical component in network data plane. Numerous algorithms and architectures have been devised for efficient flow table construction, lookup, and update. The diversity of flow tables and the difficulty to acquire real data sets make it challenging to give a fair and confident evaluation to a design. In the past, researchers rely on ClassBench and its improvements to synthesize flow tables, which become inadequate for today’s networks. In this paper, we present a new flow table benchmark tool, FlowBench. Based on a novel design methodology, FlowBench can generate large-scale flow tables with arbitrary combination of matching types and fields in a short time, and yet keep accurate characteristics to reveal the real performance of the algorithms under evaluation. The open-source tool facilitates researchers to evaluate both existing and future algorithms with unprecedented flexibility.

Flow table capacity in programmable switches is constrained due to the limited on-chip hardware resource. The current mainstream approach is to cache only the popular rules in hardware. By taking advantage of traffic locality, the majority of packets can be forwarded directly after matching the rules cached in hardware and the remaining missed packets are handled by software that accommodates the full flow table. Existing works focus on selecting the cache entries for a single-stage flow table to achieve a high cache hit-rate, which cannot adapt to multi-stage flow tables. Due to hardware constraints as well as service requirements, it is often necessary to decompose a single-stage flow table to a multi-stage flow table or directly create multiple stages of tables in hardware. For the first time, we abstract and model the multi-stage flow table caching problem and prove the NP-hardness of the Optimal Multi-stage Flow table Caching (OMFC). Further, we propose a Greedy Caching Algorithm (GCA) for OMFC, which considers both the rule popularity across multiple stages of flow tables and entry popularity within the same stage of flow table when determining the content and size of the multi-stage flow tables. The simulation results show that GCA achieves a l0~30% higher cache hit-rate than the existing algorithms.

To meet increasing demands for machine-learning-based applications, pushing inference services to the network edge has been a trend. This work aims to design an on-demand edge inference scheduler with accuracy and deadline guarantee for repetitive tasks. Specifically, we consider an edge server that is preinstalled with multiple early-exit Deep Neural Networks (DNNs), and each DNN-exit pair can provide inference service of different quality. We also consider tasks' diversity in quality of service requirements and related utility. We aim to maximize the system's total utility by optimizing service assignment and time scheduling subject to resource, accuracy, and deadline constraints. We present this problem's integer linear problem formulation and show this problem is NP-hard even for the offline case. This problem is challenging due to the coupled effect of service assignment and time scheduling. To derive low-complexity scheduling solutions, we introduce a task-service graph and convert this problem into a service assignment selection problem with schedulability constraints. Then, we design a polynomial complexity algorithm with$\frac{\rho}{\delta}$-approximation ratio for the offline problem, with$\rho$referring to the task-wise utility ratio,$\delta$referring to the maximum number of concurrent tasks. To handle the online problem, we propose an online heuristic algorithm. Simulation results show that the proposed algorithms outperform the state-of-the-art baseline algorithms.

In-Network Computing (INC) has found many applications for performance boosts or cost reduction. However, given heterogeneous devices, diverse applications, and multi-path network typologies, it is cumbersome and error-prone for application developers to effectively utilize the available network resources and gain predictable benefits without impeding normal network functions. Previous work is oriented to network operators more than application developers. We develop ClickINC to streamline the INC programming and deployment using a unified and automated workflow. Click-INC provides INC developers a modular programming abstractions, without concerning to the states of the devices and the network topology. We describe the ClickINC framework, model, language, workflow, and corresponding algorithms. Experiments on both an emulator and a prototype system demonstrate its feasibility and benefits.

Time-Sensitive Networking (TSN) is proposed in recent years to satisfy the strict performance requirements of time-sensitive traffic in a growing number of emerging applications. Even though several traffic scheduling algorithms have been standardized for TSN to pursue this goal, time-sensitive flows may not be forwarded as planned and thus fail to achieve the expected performance in real networks. The fundamental cause lies in the fact that static offline planning cannot adapt to the intrinsic dynamic factors in TSN (e.g., time-synchronization error) at runtime. Hence, next-generation TSN will benefit from a closed-loop design where a performance monitoring system provides feedback of real-time packet-forwarding information. In our research, TSN-Peeper, a light-weight, fast-response and full-coverage TSN performance monitoring system, is designed and evaluated. This paper describes its architecture design and data collection mechanisms that enable timely identification and collection of packet-forwarding misbehavior at low-cost in TSN. TSN-Peeper offloads the misbehavior identification in the switch to relieve the burden on the controller and network bandwidth. To reduce the interruption frequency to the controller, it uses probe packets to collect misbehavior information in aggregation with optimized path planning. To realize controllable reporting delays, it optimizes the sending moments of probe packets according to the flow settings. Experimental results verify that TSN-Peeper offers fast response with low cost while providing full coverage and being scalable.

The unique hardware structure of Ternary Content-Addressable Memory (TCAM) enables its unparalleled lookup throughput but also causes slow update due to the Priority Order Constraint (POC). With the increase of application demands, TCAM update has become a bottleneck in the network. This paper proposes a new TCAM management mechanism named BubbleTCAM to enable fast TCAM update, in which available empty entries are defined as bubbles. The core idea of Bub-bleTCAM is to uniformly distribute bubbles and dependency chains in TCAM, which is beneficial to updates. BubbleTCAM consists of two components: bubble management and rule insertion. Bubble management enables TCAM to have uniformly distributed bubbles at all times through three key procedures: bubble lock reservation, bubble lock release and bubble generation. Rule insertion ensures that dependency chains of rules are uniformly stretched and distributed in TCAM. In addition, BubbleTCAM avoids the reorder problem by pre-sorting. Our evaluation based on the rulesets generated by ClassBench shows that BubbleTCAM effectively reduces the average cost and worst cost (in units of rule movements) during rule updates by at least 48% and 50%, respectively. Especially for the worst cost, the performance can be improved by up to 196x.

With the ever-increasing deployment of 5G and IoT, the number of end-hosts/terminals is increasing rapidly, so that routers have to cache more and more forwarding entries to guarantee communication reachability of these terminals, which makes Ternary Content Addressable Memory (TCAM)-based routers keep expanding resource requirements. However, the design and implementation of large-capacity TCAM-based routers are faced with such challenges: difficult circuit design, high production cost and energy consumption, thereby posing an urgent requirement on a lightweight TCAM that can still maintain those massive communication connections. In this paper, we aim to design a lightweight router with small storage requirement while still retaining the original communication connection performance, which is not straightforward due to the following two challenges: First, under the condition of massive sequential flow data, it’s difficult to accurately and timely select the entries to cache for a small capacity TCAM. Second, given the strict prefix matching principle, how to efficiently insert the selected entries into TCAM is also challenging. To address these problems, we propose A&B: an AI-based Routing entry prediction strategy (AIR) and a Block-based entry Insertion Tactic (BIT). AIR can precisely select entries by conducting accurate entry predictions, which converts dynamic flow-based prediction into stable and parallelizable entry-based prediction by decoupling spatio-temporal characteristics. BIT optimizes entry insertion by isolating TCAM into several blocks, thus eliminating the time-consuming entry movements. The experiment results based on real backbone traffic show that our lightweight A&B achieves comparable performance compared to the traditional schemes by using only 1/8 TCAM storage.

The existing chip architecture and programming language are incapable of supporting in-service updates by loading or offloading on-demand protocols and functions at runtime. We examine the fundamental reasons for the inflexibility and design a new In-situ Programmable Switch Architecture (IPSA) as a fix. We further design rP4, a P4 extension, for programming IPSA-based devices. To manifest the in-situ programming feasibility, we develop an rP4 compiler and demonstrate several use cases on both a software switch, ipbm, and an FPGA-based prototype. Our preliminary experiments and analysis show that, compared to PISA, IPSA provides higher flexibility in enabling runtime functional update with limited performance and gate-count penalty. The in-situ programming capability enabled by IPSA and rP4 opens a promising design space for programmable networks.

Visibility is essential for operating and troubleshooting intricate networks. In-band Network Telemetry (INT) has been embedded in the latest merchant silicons to offer high-precision device and traffic state visibility. INT is actually an underlying technique and each INT instance covers only one monitoring path. The network-wide measurement coverage therefore requires a high-level orchestration to provision multiple INT paths. An optimal path planning is expected to produce a minimum number of paths with a minimum number of overlapping links. Eulerian trail has been used to solve the general problem. However, in production networks, the vantage points where one can deploy probes to start and terminate INT paths are constrained. In this work, we propose an optimal path planning algorithm, INT-probe, which achieves the network-wide telemetry coverage under the constraint of stationary probes. INT-probe formulates the constrained path planning into an extended multi-depot k-Chinese postman problem (MDCPP-set) and then reduces it to a solvable minimum weight perfect matching problem. We analyze algorithm's theoretical bound and the complexity. Extensive evaluation on both wide area networks and data center networks with different scales and topologies are conducted. We show INT-probe is efficient, high-performance, and practical for real-world deployment. For a large-scale data center networks with 1125 switches, INT-probe can generate 112 monitoring paths (reduced by 50.4 %) by allowing only 1.79% increase of the total path length, promptly resolving link failures within 744.71ms.

TCAM is widely used for flow table lookup in Software-Defined Networking (SDN) switches for datacenter and enterprise networks. While its lookup throughput is unparalleled, TCAM updating, particularly for new rule insertions, can impair the overall system performance. A rule insertion entails two steps: 1) Computing the rule moving operations; and 2) Interrupting the TCAM lookups to apply the operations. In previous work, the performance gain on one step is always at the expense of the performance loss on the other. However, update throughput and latency depend on both. In this paper, we present a faster and more balanced TCAM update scheme, which not only achieves the shortest interrupt time so far but also significantly reduces the computation time. By using a novel sequential stack, FastUp reduces the time and space complexity of the state-of-the-art schemes from$O(m^{2})$and$O(m)$to$O(m\log h)$and$O(h)$, respectively, where$h << m$. Evaluations show that FastUp shortens the computation time and the interrupt time by$100\times$and$1.6\times$, respectively, which is equivalent to update delay${15\times}$reduction and$\mathbf{10\times}$update throughput gain against the state-of-the-art schemes. Moreover, we debunk a common mistake and show the dynamic programming based algorithm cannot be used to solve the reorder problem, and instead we use a bidirectional rule moving method to address the problem. In addition, we propose a practical method to find the theoretical lower bound of interrupt time in relatively large TCAM, which can be used to evaluate the optimality degree of TCAM update schemes. Evaluations show that FastUp achieves 90 % optimality.

Ternary Content-Addressable Memory (TCAM) is a popular solution for high-speed flow table lookup in Software-Defined Networking (SDN). Rule insertion in TCAM is a time-consuming operation. To ensure semantic correctness, rules overlapped must be stored in TCAM with decreasing priority order and many rule movements may be needed to make space for a single inserted rule. When a rule insertion is in progress, the regular flow table lookup will be suspended, which could lead to a degraded user experience for SDN applications. In this paper, we propose a multiple-TCAM framework named MagicTCAM to reduce the rule movements during a rule insertion. The core of MagicTCAM lies in three operations: layering, partitioning and rotating. By layering, rules with the least overlapping will be grouped (i.e., layered) into a sub-ruleset. The number of rule movements is therefore greatly reduced as most of rules in a sub-ruleset are non-overlapped. To achieve balanced load in TCAMs, rules in each sub-ruleset are further partitioned and dispatched into different TCAMs in a rotating manner. In addition, an inter-TCAM movement algorithm is proposed to allow rules to be moved between TCAMs for reduced rule movement. Experiment results show that with two half-sized TCAMs, MagicTCAM reduces the rule movements by 39% on average compared with the state-of-the-art work while the computation time is shortened by half as well.

Time Sensitive Networking (TSN) is an emerging Ethernet technology for real-time systems. To address different Quality-of-Service (QoS) requirements of applications, IEEE 802.1 TSN Task Group has standardized several packet scheduling and shaping algorithms. The software implementation of these algorithms is hard to meet the performance requirements, while the hardware implementation in Application-Specific Integrated Circuit (ASIC) is inflexible. A hardware-programmable scheduler is necessary to deal with this dilemma. Among the existing primitives, the most expressive one is Push-In-Extract-Out (PIEO), but its complexity makes the implementation very expensive. A relatively lower-cost implementation of PIEO cannot guarantee the scheduling correctness for the most critical Time-Triggered (TT) traffic in TSN. As a remedy, in this paper we propose a new Push-In-Pick-Out (PIPO) primitive under a TSN programmable scheduling framework. Composed of simple priority queues, PIPO can express all existing TSN scheduling and shaping algorithms, and is flexible enough to support future ones. Our PIPO implementation guarantees the TT traffic scheduling correctness. The simulation results corroborate the theoretical analysis that the low-cost PIPO can closely approximate PIEO and sustain a high bandwidth utilization. The prototype on Xilinx FPGA shows that, with 2,048 inputs, the PIPO-based scheduler achieves a throughput of 70 Mpps, which is 1.64x higher than the PIEO-based one, but using only 14.7% Look-Up Tables (LUTs) and 40.5% Block RAMs of the latter.

Rule update in TCAM has long been identified as a key technical challenge due to the rule order constraint. Existing algorithms take each rule update as an independent task. However, emerging applications produce batch rule update requests. Processing the updates individually causes high aggregated cost which can strain the processor and/or incur excessive TCAM lookup interrupts. This paper presents the first true batch update algorithm, ABUT. Unlike the other alleged batch update algorithms, ABUT collectively evaluates and optimizes the TCAM placement for whole batches throughout. By applying the topology grouping and maintaining the group order invariance in TCAM, ABUT achieves substantial computing time reduction yet still yields the best-in-class placement cost. Our evaluations show that ABUT is ideal for low-latency and high-throughput batch TCAM updates in modern high-performance switches.

Offloading the 3D object detection from autonomous vehicles to MEC is appealing because of the gains on quality, latency, and energy. However, detection requests lead to repetitive computations since the multitudinous requests share approximate detection results. It is crucial to reduce such fuzzy redundancy by reusing the previous results. A key challenge is that the requests mapping to the reusable result are only similar but not identical. An efficient method for similarity matching is needed to justify the use case. To this end, by taking advantage of TCAM's ap-proximate matching capability and NMC's computing efficiency, we design SODA, a first-of-its-kind hardware accelerator which sits in the mobile base stations between autonomous vehicles and MEC servers. We design efficient feature encoding and partition algorithms for SODA to ensure the quality of the similarity matching and result reuse. Our evaluation shows that SODA significantly improves the system performance and the detection results exceed the accuracy requirements on the subject matter, qualifying SODA as a practical domain-specific solution.

Current Internet is evolving with the gradual shift from the traditional host-to-host communication model to the new host-to-content paradigm, which will eventually lead to a network of caches. The novel Named Data Networking (NDN) has been proposed as a future Internet architecture to embrace this paradigmatic shift, where caching becomes an ubiquitous functionality available at each router.A router with the functionality of content caching, running on NDN mechanisms, is termed as an NDN-based content router. Previous researchers focused on software content routers (SCR), which leverage a commercial off-the-shelf computer to execute content caching/accessing and named-based packet forwarding. SCR can only achieve limited throughput, which is far below the speed requirements of modern routers. Facing this situation, in this paper, we propose a hardware-based content router (HCR), aiming at purchasing wire-speed processing. We design a physically concise architecture for decoupling the packet buffers in line cards from the content caches attached to storage cards, enabling separate management and optimization while facilitating a modular structure for smooth capacity upgrade in response to increasing storage utilization. For lowering the operating complexity and reducing the storage management cost, we choose to employ distributed caches working in a cooperated manner by using consistent hashing. We model several candidate storage organizing schemes and carry out theoretical analyses for comparison. Analytical and synthetic workload-driven results show that the consistent hashing scheme achieves high cache performance and low cost simultaneously.

Vehicle to Vehicle (V2V) communication opens a new way to make vehicles directly communicate with each other, providing faster responses for time-sensitive tasks than cellular networks. Effective V2V routing protocols are essential yet challenging, as the high dynamic road environment makes communication easy to break. Many prediction methods proposed in the existing protocols to address this issue are either flawed or have a poor effect. In this paper, to cope with the two aspects of the problems that cause communication interrupt, i.e., link breaks and route quality degradation, we design an acceleration-based trajectory prediction algorithm to estimate the link lifetime, and a machine learning model to predict route quality. Based on the prediction algorithms, we propose PQR, a Prediction-supported Quality-aware Routing protocol, which can proactively switch to a better route before the current link breaks or the route quality degrades. Especially, considering the limitations of the current routing protocols, we elaborate a new hybrid routing protocol that integrates the topology-based method and location-based method to achieve instant communication. Simulation results show that PQR outperforms the existing protocols in Packet Delivery Ratio (PDR), Roundtrip Time (RTT), and Normalized Routing Overhead (NRO). Specifically, we have also implemented a vehicular testbed to demonstrate PQR’s real-world performance, and results show that PQR achieves almost no packet loss with latency less than 10ms during route handoff for topology change.

Ternary Content Addressable Memory (TCAM) is an important hardware used to store route entries in routers, which is used to assist routers to make fast decision on forwarding packets. In order to cope with the explosion of route entries due to massive IP terminals brought by 5G and the Internet of Things (IoT), today’s commercial TCAM has to keep the corresponding growth in capacity. But large TCAM capacity is causing many problems such as circuit design difficulties, production costs, and high energy consumption, so it is urgent to design a lightweight TCAM with small capacity while still maintains the original query performance.Designing such a TCAM faces two fundamental challenges. Firstly, it is essential to accurately predict the incoming flows in order to cache correct entries in limited TCAM capacity, but prediction on aggregated time-sequential data is challenging in the massive IoT scenarios. Secondly, the prediction algorithm needs to be real-time as the lookup process is in line-rate. In order to address the above two challenges, in this paper, we proposed a lightweight AI-based solution, called AIR, where we successfully decoupled the route entries and designed a parallel-LSTM prediction method. The experiment results under real backbone traffic showed that we successfully achieved comparable query performance by using just 1/8 TCAM size.

For autonomous driving, an essential task is to detect surrounding objects accurately. To this end, most existing systems use optical devices, including cameras and light detection and ranging (LiDAR) sensors, to collect environment data in real time. In recent years, many researchers have developed advanced machine learning models to detect surrounding objects. Nevertheless, the aforementioned optical devices are vulnerable to optical signal attacks, which could compromise the accuracy of object detection. To address this critical issue, we propose a framework to detect and identify sensors that are under attack. Specifically, we first develop a new technique to detect attacks on a system that consists of three sensors. Our main idea is to: 1) use data from three sensors to obtain two versions of depth maps (i.e., disparity) and 2) detect attacks by analyzing the distribution of disparity errors. In our study, we use real data sets and the state-of-the-art machine learning model to evaluate our attack detection scheme and the results confirm the effectiveness of our detection method. Based on the detection scheme, we further develop an identification model that is capable of identifying up to n-2 attacked sensors in a system with one LiDAR and n cameras. We prove the correctness of our identification scheme and conduct experiments to show the accuracy of our identification method. Finally, we investigate the overall sensitivity of our framework.

Information-Centric Networking (ICN) provides scalable and efficient content distribution at the Internet scale due to in-network caching and native multicast. To support these features, a content router needs high performance at its data plane, which consists of three forwarding steps: checking the Content Store (CS), then the Pending Interest Table (PIT), and finally the Forwarding Information Base (FIB). In this work, we build an analytical model of the router and identify that CS is the actual bottleneck. Then, we propose a novel mechanism called “NB-Cache” to address CS’s performance issue from a network-wide point of view. In NB-Cache, when packets arrive at a router whose CS is fully loaded, instead of being blocked and waiting for the CS, these packets are forwarded to the next-hop router, whose CS may not be fully loaded. This approach essentially utilizes Content Stores of all the routers along the forwarding path in parallel rather than checking each CS sequentially. NB-Cache follows a design pattern of on-demand load balancing and can be formulated into a non-trivial N-queue bypass model. We use the Markov chain to establish its theoretical base and find an algorithm for automated transition rate matrix generation. Experiments show significant improvement of data plane performance: 70% reduction in round-trip time (RTT) and 130% increase in throughput. NB-Cache decouples the fast packet forwarding from the slower content retrieval thus substantially reducing CS’s heavy dependency on fast but expensive memory.

Ternary Content Addressable Memory (TCAM) is widely used by modern routers and switches to support policy-based forwarding due to its incomparable lookup speed and flexible matching patterns. However, the limited TCAM capacity does not scale with the ever-increasing rule table size due to the high hardware cost and high power consumption. At present, using TCAM just as a rule cache is an appealing solution, but one must resolve several tricky issues including the rule dependency and the associated TCAM updates. In this paper, we propose a new approach which can generate dependency-free rules to cache. By removing the rule dependency, the complex TCAM update problem also disappears. We provide the complete T-cache system design including slow path processing and cache replacement, and implement a T-cache prototype on Barefoot Tofino switches. We conduct comprehensive software simulations and hardware experiments based on real-world and synthesized rule tables and packet traces to show that T-cache is efficient and robust for network traffic in various scenarios.

Intelligent Transport System (ITS) raises the increasing demand on accurate vehicle trajectory prediction for navigation efficiency. The rapidly developing 5G networks provides communications with high transmission bandwidth and super-low latency, paving the way for Mobile Edge Computing (MEC) to calculate more accurate trajectory prediction for vehicles, as the MEC server holds more comprehensive vehicular information. However, the current methods for trajectory prediction are not efficient due to the dynamical environment. To address this issue, we propose GlobalInsight, a Long Short-Term Memory (LSTM) based model, which runs on the MEC to perform accurate trajectory prediction for multiple vehicles no matter how scenario changes. In particular, we use three auxiliary layers to respectively capture the principal component of vehicle features, social interaction of adjacent vehicles, and the cross-vehicle correlation of similar vehicles. We further integrate the above information into LSTM in the main layer to enhance the trajectory learning and prediction. We evaluate our model under the NGSIM dataset, and experimental results exhibit that our model outperforms the state-of-the-art approaches.

While widely used for flow tables in SDN switches, TCAM faces challenges for rule updates. Both the computation time and interrupt time need to be short. We propose FastUp, a new TCAM update algorithm, which improves the previous dynamic programming-based algorithms. Evaluations show that FastUp shortens the computation time by 40~100× and the interrupt time by 1.2~2.5×. In addition, we are the first to prove the NP-hardness of the optimal TCAM update problem, and provide a practical method to evaluate an algorithm's degree of optimality. Experiments show that FastUp's optimality reaches 90%.

In this paper, we put forward a HOListic traffic control framework for datacenter NETworks (HOLNET). HOLNET reformulates the network utility maximization (NUM) framework into a HOLNET NUM framework that fully harnesses the potential of the existing NUM-based solutions to allow large families of traffic control protocols of various degrees of sophistication to be developed, i.e., host-based, single or multiple Class-of-Service (CoS) enabled, single or multi-path congestion control, with or without in-network load balancing. Unlike the existing solutions that are largely empirical and point by design, HOLNET is a principled, systematic framework. All the protocols in a family developed under HOLNET share a common, user-defined global optimization objective and fairness criterion. As a result, the protocols in a family can be fairly compared and carefully selected to fully explore the performance, scalability and design complexity tradeoffs. Case studies, based on both a single and a multi-path host-based solutions, demonstrate the viability and flexibility in HOLNET design space exploration. To further test the backward compatibility and performance with respect to some existing lightweight solutions, we develop HOLNET-UTA, an integrated congestion control and load balancing protocol, achieving TCP-fair resource allocation. HOLNET-UTA is found by simulation to improve the average flow completion time (FCT) by more than 20%, compared to DRILL with DCTCP.

Ternary Content Addressable Memory (TCAM) is widely used by modern routers and switches to support policy-based forwarding. However, the limited TCAM capacity does not scale with the ever-increasing rule table size. Using TCAM just as a rule cache is a plausible solution, but one must resolve several tricky issues including the rule dependency and the associated TCAM updates. In this paper, we propose a new approach which can generate dependency-free rules to cache. By removing the rule dependency, the TCAM update problem also disappears. We provide the complete T-cache system design including slow path processing and cache replacement. Evaluations based on real-world and synthesized rule tables and traces show that T-cache is efficient and robust for network traffic in various scenarios.

Existing routing algorithms that based on traditional Vehicular Ad-Hoc NETwork (VANET) architectures cannot provide fast and diverse routing services due to dynamic and unstable environment. To address this issue, we propose a three-level routing hierarchy in improved Software-Defined VANET architecture based on Mobile Edge Computing (SDN-MEC-VANET) to improve routing performance and enrich the data transmission mode for the VANET. Moreover, it can be applied to almost all VANET protocols, enabling protocol-independent forwarding. Besides, this improved architecture can coordinate different edge devices to timely adjust the service delivery strategy under the predictive correction from controllers, providing high-bandwidth and low-delay transmission for Internet of Vehicles (IoV). Meanwhile, MEC technology is introduced to perform local control, leveraging the storage and computing capabilities of edge devices to reduce the processing pressure of the controller. Simulation results show that our routing algorithm in improved network architecture can achieve a higher packet delivery ratio within a reasonable delay than other approaches under different scenarios of network scale, communication frequency and vehicular velocity.

Vehicular Ad hoc network (VANET) has received great attention in recent research, but many challenges still lie in innovating efficient routing protocols to support the highly dynamic environment. Existing ID-based routing protocols cannot fundamentally tackle the dynamic topology problem in VANET. The recent emerging Information-Centric Networking (ICN) makes routing decisions based on data itself instead of a particular host, seeming to have the potential to handle the dynamic topology, but problems (e.g., severe flooding overhead) still remain. Therefore, inspired by the idea of ICN, we propose a name/ID hybrid routing (NIHR) protocol that combines the data-namebased routing and host-ID-based routing to address the above two issues simultaneously. In particular, we develop an announce strategy to improve the efficiency of the in-network cache, and we design a bloom filter based structure to achieve fast content lookup. Simulation results show NIHR's high performance in terms of Packet Delivery Ratio (PDR), Roundtrip time (RTT) and roundtrip hop count. Especially, to verify NIHR's performance in real-world scenarios, we have implemented a vehicular real-time video conference system based on MK5 OBU [1] (On-Board Unit).

As the signal-to-noise ratio (SNR) of surface microseismic monitoring data is generally low and large, traditional detection and picking algorithms cannot satisfy the real-time and high accuracy to processing. Therefore, a Fast Akaike information criterion (Fast-AIC) algorithm is proposed for microseismic event automatic detection and first arrival time picking. First, an automatic detection method of microseismic events based on multitrace energy stacking is proposed, to avoid the missed detection and false detection in conventional automatic detection methods. Second, the Fast-AIC algorithm is developed by mathematical derivation from the Vector Auto-regressive (VAR-AIC algorithm), to improve the efficiency of first arrival time picking of microseismic signals. Finally, the new method and three other conventional first arrival time picking methods are tested on microseismic monitoring data from a hydraulic fracture site in Shanxi, China. We have found that the new method has the highest picking accuracy and computational efficiency.

High topology dynamics and intermittent connectivity in Vehicular Ad hoc Network (VANET) bring huge challenges to end-to-end communication. Existing routing protocols for MANET such as AODV and OLSR work fine under modest mobility, but have a difficult time to handle frequent topology changes in VANET. This paper proposes Peeking at the Past and Present Routing (P3R), a routing protocol that will calculate next-hops when the past forwarding is considered invalid. The next-hop calculation is based on the predicted locations of forwarder's neighbors and the packet's destination node, overcoming the inaccuracy caused by stale location information. Furthermore, we differentiate vehicles on crossroads as they have high connectivity in actual urban streets. In this way, P3R is able to deal with link breakages quickly and exploit new links. Simulation results show that P3R outperforms state-of-the-art alternatives in terms of packet delivery ratio, delay and cost, while maintaining strong scalability and robustness. We also implement P3R in a real vehicular testbed and the results reveal it has high connectivity on real streets.

With the ever-increasing complexity of networks, fine-grained network monitoring enables better network reliability and timely feedback control. The In-band Network Telemetry (INT) allows cost-effective network monitoring by encapsulating device-internal states into probe packets. However, INT only specifies an underlying device-level primitive while how to achieve network-wide traffic monitoring remains undefined. In this work, we propose INT-path, a network-wide telemetry framework, by decoupling the system into a routing mechanism and a routing path generation policy. Specifically, we embed source routing into INT probes to allow specifying the route the probe packet takes through the network. Above the mechanism, we develop an Euler trail-based path planning policy to generate non-overlapped INT paths that cover the entire network with a minimum path number. Besides, an exhaustive analysis of algorithm's run-time complexity is also provided. INT-path can “encode” the network-wide traffic status into a series of “bitmap images”, transforming network troubleshooting into pattern recognition problems. INT-path is very suitable for deployment in data center networks thanks to their symmetric network topologies.

Information-Centric Networking (ICN) provides scalable and efficient content distribution at the Internet scale due to its in-network caching and native multicast capabilities. To support these features, a content router needs high performance at its data plane, which consists of three forwarding steps: checking the Content Store (CS), then the Pending Interest Table (PIT), and finally the Forwarding Information Base (FIB). While prior works focus on performance optimization of a single step, we build an analytical model of content router's entire data plane and identify that CS is the actual bottleneck in the pipeline. Compared with PIT and FIB, CS is more challenging because it has more data to read/write, may have more entries in its table to store and lookup, and needs to organize content objects to sustain frequent cache replacement. Then, we propose a novel mechanism called "NB-Cache" to address CS's performance issue from a network-wide point of view rather than a single router's. In NB-Cache, when packets arrive at a router whose CS is fully loaded, instead of being blocked and waiting for the CS, these packets are forwarded to the next-hop router, whose CS may not be fully loaded. This approach essentially utilizes Content Stores of all the routers along the forwarding path in parallel rather than checking each CS sequentially. Our experiments show significant improvement of data plane performance: 70% reduction in round-trip time (RTT) and 130% increase in throughput.

The network link speed is growing at an ever-increasing rate, which requires all network functions on routers/switches to keep pace. Bloom filter is a widely-used membership check data structure in networking applications. Correspondingly, it also faces the urgent demand of improving the performance in membership check speed. To this end, this paper proposes a new Bloom filter variant called Ultra-Fast Bloom Filters (UFBF), by leveraging the Single Instruction Multiple Data (SIMD) techniques. We make three improvements for UFBF to accelerate the membership check speed. First, we develop a novel hash computation algorithm which can compute multiple hash functions in parallel with the use of SIMD instructions. Second, we elaborate a Bloom filter's bit-test process from sequential to parallel, enabling more bit-tests per unit time. Third, we improve the cache efficiency of membership check by encoding an element's information to a small block so that it can fit into a cache-line. We further generalize UFBF, called c-UFBF, to make UFBF supporting large number of hash functions. Both theoretical analysis and extensive evaluations show that the UFBF greatly outperforms the state-of-the-art Bloom filter variants on membership check speed.

Software Defined Network (SDN) enables flexible update of network functions with a well-defined abstraction between the control and the data plane. However, multiple active network functions with the same priority will potentially trigger conflicts among policies with overlapped flow space, causing the flow table explosion. In contrast to the local switch conflict resolution schemes proposed by previous works, this paper tackles the same problem from a different angle and resolves the policy conflict problem by coordinating all switches under a global centralized view. Specifically, we propose COnflict RAzor (CORA), which tremendously reduces the storage cost of conflicting policies leveraging the global network information obtained in the controller. The basic idea of CORA is migrating policies causing large explosions across the network if necessary, while keeping the semantics equivalence. We prove CORA's NP hardness and propose a heuristic to efficiently search a near-optimal policy migration strategy. Our experiments demonstrate that, CORA can effectively reduce the flow table storage occupation by at least 49% within less than 40 seconds.

Software-based IP route lookup is one of the key components in Software Defined Networks. To address challenges on density, power and cost, Commodity CPU is preferred over other platforms to run lookup algorithms. As network functions become richer and more dynamic, route updates are more frequent. Unfortunately, previous works put less effort on fast incremental updates. On the other hand, The cache in CPU could be a performance limiter due to its small size, which requires algorithm designers to give high priority on storage efficiency in addition to time complexity. In this paper, we propose a new route lookup algorithm, OBMA, which improves update performance and storage efficiency while maintaining high lookup speed. The extensive experiments over real-word traces show that OBMA reduces the memory footprint to just 4.52 bytes/prefix, supports update speed up to 7.2 M/s which is 12.5 times faster than the state-of-the-art algorithm Poptrie. Besides, OBMA achieves up to 195.87 Mpps lookup speed with a single thread. Tests on comprehensive performance of lookup and update show that OBMA can sustain high lookup speed with update speed increasing.

Longest Prefix Match (LPM) is a basic and important function for current network devices. Hash-based approaches appear to be excellent candidate solutions for LPM with the capability of fast lookup speed and low latency. The number of hash table probes, i.e. the search path of a hash-based LPM algorithm, directly determines the lookup performance. In this paper, we propose Ω-LPM to improve the lookup performance by optimizing the search path of the hash-based LPM. Ω-LPM first reconstructs the forwarding table to support random search [19], then it applies a dynamic programming algorithm to find the shortest search path based on the statistics of the matching probabilities. Ω-LPM concretely reduces the number of hash table probes via searching most of the packets in optimal search paths. Even in the worst case, the upper bound of the average search path of Ω-LPM is 1 + log2(N), here N is the length of the longest prefix in the routing table. The case studies of the name lookup in Named Data Networking and the IP lookup in current Internet demonstrate that Ω-LPM can shorten 61.04% and 86.88% search paths compared with the basic hash-based methods of name lookup [22] and IP lookup [12], respectively, furthermore Ω-LPM reduces 32.3% probes of the name lookup and 73.55% probes of the IP lookup compared with the optimal linear search. The experimental results conducted on extensional name tables and IP tables also show that Ω-LPM has both low memory overhead and excellent scalability.

A data-centric network architecture, Named Data Networking (NDN) has been developed to meet applications' growing demands of network effciency and resilience. Currently, the deployment of NDN in real network environments requires careful system design to not only enable NDN but also support IP traffc, considering IP network has been prevalent for decades and almost all the equipments and applications are IP-based. In this paper, we take the most popular local area network (LAN) technology, Ethernet, as an example to investigate incremental deployment of NDN. Assuming a local network with both NDN and IP traffc, we mainly layout three deployment scenarios: NDN-enabled hosts and all Ethernet switches, NDN-enabled hosts and all Dual-Stack switches (i.e., it can process both NDN and IP traffc), and a hybrid network with both Dual-Stack switches and Ethernet switches. We examine the technical issues involved in each scenario and present solutions. In particular, in the hybrid scenario, we propose heuristics to optimize the placement of Dual-Stack switches. Compared with traditional Ethernet, introducing Dual-Stack switches can improve network effciency and resiliency by utilizing more links, reducing each link's traffc load, and taking shorter paths, at the same time also maintaining the functionality of IP-based applications.

Collapsed forwarding has long been used in cache systems to reduce the load on servers by aggregating requests for the same content. Named Data Networking (NDN) as a future Internet architecture incorporates this technique through a data structure called Pending Interest Table (PIT). The request aggregation feature suggests that PIT can be viewed as a nonreset time-to-live (TTL) based cache. The Content Store (CS) is a content cache placed in front of the PIT on the NDN forwarding path, so they make up a tandem cache network. To investigate the metrics of interest in this network, like the hit probability for the PIT and the CS, the expected PIT size, non-zero download delay (non-ZDD) should be taken into consideration. Caching policies usually assume zero download delay (ZDD), i.e., request and object arrive simultaneously, and numerous analytical methods have been proposed to study the ZDD caching policies. In this paper, after dissecting the LRU policy, we for the first time propose two LRU variants considering non-ZDD by defining separate operations for the request and object arrivals. When CS adopts the proposed LRU variants, the analysis of the CS-PIT network can still take advantage of the existing models, so the metrics of interest can be computed. Especially, the distribution for the “inter-miss” time of this network can be derived, which has not been achieved by prior works. Finally, the analytical results are verified through simulations.

The network link speed is increasing at an alarming rate, which requires all network functions on routers/switches to keep pace. Bloom filter is a widely-used membership check data structure in network applications. It also faces the urgent demand of improving the performance in membership check speed. To this end, this paper proposes a new Bloom filter variant called Ultra-Fast Bloom Filters, by leveraging the SIMD techniques. We make three improvements for the UFBF to accelerate the membership check speed. First, we develop a novel hash computation algorithm which can compute multiple hash functions in parallel with the use of SIMD instructions. Second, we change a Bloom filter's bit-test process from sequential to parallel. Third, we increase the cache efficiency of membership check by encoding an element's information to a small block which can easily fit into a cache-line. Both theoretical analysis and extensive simulations show that the UFBF greatly exceeds the state-of-the-art Bloom filter variants on membership check speed.

Named data networking (NDN) is a future Internet architecture that directly emphasizes accessible content by assigning each piece of content a unique name. Data transmission in NDN is realized via name-based routing and forwarding. Name-based forwarding information base (FIB) usually has much more and longer prefixes than IP-based ones, and therefore, name-based forwarding brings more challenges on the NDN router in terms of high forwarding throughput, low memory consumption, and fast FIB update. In this paper, we present an index data structure called BFAST for the name-based FIB. BFAST is designed based on a basic hash table, it employs a counting Bloom filter to balance the load among hash table slots, so that the number of items in each non-empty slot is close to 1, leading to low searching time in each slot. Meanwhile, the first-rank-indexed scheme is proposed to effectively reduce the massive memory consumption required by the pointers in all the hash table slots. Evaluation results show that, for the longest prefix match FIB lookup, BFAST achieves a speed of 2.14 MS/S using one thread, and meanwhile, the memory consumption is reasonably low. By leveraging the parallelism of today's multi-core CPU, BFAST arrives at an FIB lookup speed of 33.64 MS/S using 24 threads, and the latency is around 0.71 μs.

No abstract available.

The OpenFlow paradigm embraces third-party development efforts, and therefore suffers from potential attacks that usurp the excessive privileges of control plane applications (apps). Such privilege abuse could lead to various attacks impacting the entire administrative domain. In this paper, we present SDNShield, a permission control system that helps network administrators to express and enforce only the minimum required privileges to individual controller apps. SDNShield achieves this goal through (i) fine-grained SDN permission abstractions that allow accurate representation of app behavior boundary, (ii) automatic security policy reconciliation that incorporates security policies specified by administrators into the requested app permissions, and (iii) a lightweight thread-based controller architecture for controller/app isolation and reliable permission enforcement. Through prototype implementation, we verify its effectiveness against proof-of-concept attacks. Performance evaluation shows that SDNShield introduces negligible runtime overhead.

The explosion of network bandwidth poses greatchallenges to data-plane flow processing. Due to the variable andpoor worst-case performance, naive hash table is incapable ofwire-speed processing. State-of-the-art schemes rely on multiplehash functions for enhanced load balancing to improve the worst-case performance. These schemes exploit the memory hierarchyand allocate compact on-chip data structures as the off-chiphash table summaries. However, when the flow number inflates, they fail to scale the on-chip memory consumption gracefully. This work is inspired by modern DRAM's burst-transfer feature. Specifically, we propose bandwidth-greedy hashing which resolveshash collisions with just one DRAM burst. Besides, load balancingefforts are made in an "on-demand" fashion. This radicaldesign surmounts the major obstacle of mapping multiple choicehashing schemes to real-world hierarchical memory systems formassive-scale items. Essentially, this solution follows a designpattern of on-demand load balancing and can be regarded asa generalization of closed hashing. To establish its theoreticalbase, we analyze it via Poisson distribution approximation. Theevaluation on DRAMSim2 reports that our scheme requires onlyone DRAM burst access (in 99.999% cases) and minuscule on-chip memory (less than 16MB, or 1% of the previous) to supportlookups for 100M flows at a throughput of 122.82Mpps.

Per-flow measurement can provide fine-grained statistics for advanced network management and thus has been studied extensively. As network line rate continues its rapid growth, wire-speed per-flow measurement meets great challenges, for large numbers of statistics counters are required to record flow information at extremely high speed. Most of the previous efforts are committed to elaborate excellent sampling algorithms to make counters' memory occupation as small as possible, so as to fit into off-chip SRAM(s), but the throughput is rigidly bounded by the speed of SRAM. To break the wall, we explore a new path by proposing CASE: a cache-assisted stretchable estimator, which uses the on-chip memory as the fast cache of the off-chip SRAM. In this way, most of the accesses to the counters will happen on cache, thanks to the heavy-tailed distribution of Internet traffic. In this paper, we present CASE's design and derive strict mathematical proof to its relative error bound. Extensive experiments on real-world traces are conducted and the evaluation results indicate CASE can achieve up to 300Gbps throughput when using on-chip memory with 128K entries (equivalent to 1.125MB). Meanwhile CASE is more accurate and stretchable than uncached approaches.

The fast path, as the cache of exact-match rules in the slow path, is applied in software-based OpenFlow switches to improve the forwarding performance. A microflow in the fast path is the specification of its corresponding rules in the slow path, i.e., every field is explicit in a microflow. A rule can generate multiple microflows in the fast path, and a microflow can be generated from multiple rules since there are multiple flow tables in an OpenFlow switch. Due to the many-to-many mapping relationship between the microflows and the rules, the update consistency between the slow path and the fast path becomes a big challenge in software switches, e.g., Open vSwitch (OVS). In this paper, we propose a cache-based scheme (named FlowShadow) to achieve high update performance while keeping update consistency in OVS. In order to examine the reliability, validity, utility and scalability of FlowShadow, we implement FlowShadow on the OVS and conduct numerous experiments with different settings to measure the performance of FlowShadow. The experimental results demonstrate that FlowShadow achieves a lookup speed of 75 million packets per second on a commodity PC under the real backbone traces; the system with FlowShadow speeds up 3.4× times of the original OVS; and FlowShadow also shows high update performance and good scalability at different update speeds and with different numbers of flow tables.

We investigated the cache allocation and replacement problems in CCN within a single ISP and propose the scheme called Tube Caching that can dynamically distribute contents across the forwarding paths based on the energy-related benefit. Through the preliminary evaluations, Tube Caching has been proven to be effective.

As the network infrastructure has been consuming more and more power, various schemes have been proposed to improve the power efficiency of network devices. Many schemes put links to sleep when idle and wake them up when needed. A presumption in these schemes, though, is that router's line cards can be waken up very quickly. However, through systematic measurement of a major vendor's high-end routers, we find that it takes minutes to get a line card ready under the current design. To address this issue, we propose a new line card design that 1) keeps the host processor in a line card standby, which only consumes a small fraction of power but will save considerable wakeup time, and 2) downloads a slim slot of popular prefixes with higher priority, so that the line card will be ready for forwarding most of the traffic much earlier. We design algorithms as well as architecture that ensure fast and correct longest prefix match during prioritized routing prefix download. Experiments on an FPGA-based prototype show that the customized hardware can be ready to forward packets in 127.27 ms, which is 0.3% of the time the original design takes. This can better support numerous power-saving schemes based on the sleep/wakeup mechanism.

Updating rules in the flow tables of SDN switches are complex and time-consuming. Therefore, we propose a cache-based scheme (named FlowShadow) to improve the packet processing performance and keep continuous operating while updating rules in the flow tables. FlowShadow caches the microflows in the hash table to build a fast path for packet processing. By leveraging the Action Table, FlowShadow achieves update consistency and good update performance. In order to examine the reliability, validity, utility and scalability of FlowShadow, we implement FlowShadow on the Open VSwitch and conduct numerous experiments with different settings to measure the performance of FlowShadow. The experimental results demonstrate that FlowShadow achieves a lookup speed of 75 million packets per second on a commodity PC under the real backbone traces; the system with FlowShadow speeds up 3.4× times of the original Open VSwitch.

Named Data Networking (NDN) as an instantiation of the Content-Centric Networking (CCN) approach, embraces the major shift of the network function - from host-to-host conversation to content dissemination. The NDN forwarding architecture consists of three tables - Content Store (CS), Pending Interest Table (PIT) and Forwarding Information Base (FIB), as well as two lookup rules - Longest Prefix Match (LPM) and Exact Match (EM). A software-based implementation for this forwarding architecture would be low-cost, flexible and have rich memory resource, but may also make the pipelining technique not readily applicable to table lookups. Therefore, forwarding a packet would go through multiple tables sequentially without pipelining, leading to high latency and low throughput. In order to take advantage of the software-based implementation and overcome its shortcoming, we find that, a single unified index that supports all the three tables and both LPM and EM lookup rules would benefit the forwarding performance. In this paper, we present such an index data structure called BFAST (Bloom Filter-Aided haSh Table). BFAST employs a Counting Bloom Filter to balance the load among hash table buckets, making the number of prefixes in each non-empty bucket close to 1, and thus enabling high lookup throughput and low latency. Evaluation results show that, for solely LMP lookup, BFAST can arrive at 36.41 million lookups per second (M/s) using 24 threads, and the latency is around 0.46 μs. When utilized to build the NDN forwarding architecture, BFAST obtains remarkable performance promotion under various request composition, e.g., BFAST achieves a lookup speed of 81.32 M/s with a synthetic request trace where 30% of the requests hit CS, another 30% hit PIT and the rest 40% hit FIB, while the lookup latency is only 0.29 μs

Bloom filters are widely used in many network applications but the high computation cost limits the system performance. In this paper, we introduce a new variation of Bloom filter named One-Hashing Bloom Filter (OHBF) to solve the problem. OHBF requires only one base hash function plus a few simple operations to implement a Bloom filter. While keeping nearly the same theoretical false positive ratio as an ideal Bloom filter, OHBF significantly reduces the hash computation overhead. We show that the false positive performance of a standard Bloom filter implementation strongly relies on the selection of hash functions, even if these hash functions are considered good. In contrast, OHBF presents consistently better performance with a proven mathematical foundation. OHBF is ideal for high throughput and low latency applications. As OHBF is a fundamental technique in Bloom filter theory, it can be applied to many other Bloom filter variations, such as Counting Bloom Filter and Space-Code Bloom Filter.

As the network infrastructure has been consuming more and more power, various schemes have been proposed to improve power efficiency of network devices. Many schemes put links to sleep when idle and wake them up when needed. A presumption in these schemes, though, is that router's line cards can be waken up quickly. However, through systematic measurement of a major vender's high-end router, we find that it takes minutes to get a line card ready under the current implementation. To address this issue, we propose a new line card design that (1) keeps the host processor in a line card always up, which only consumes a small fraction of power, and (2) downloads a slim slot of popular prefixes with higher priority, so that the line card will be ready for forwarding most of the traffic much earlier. We design algorithms that ensure fast and correct longest prefix match lookup during prioritized routing prefix download. Experiments on real hardware show that the wakeup time can be reduced to 127.27ms, which is 0.3% of the original line card wakeup time, well supporting many power-saving schemes.

NDN enables routers to cache received contents for future requests to reduce upstream traffic. To this end, various caching policies are proposed, typically based on some notion of content popularity, e.g., LFU. But these policies simply assume the availability of content popularity information without elaborating how that information is obtained and maintained in routers. Towards line-speed and accurate on-line popularity monitoring on NDN routers, we propose a Bloom filter-based method to continuously capture content popularity with efficient usage of memory. In this method, multiple Bloom filters are employed and each one is responsible for a particular range of popularity. Content objects whose popularities fall into a Bloom filter's range will be inserted into that Bloom filter. Meanwhile, a sliding window monitoring scheme is proposed to implement more frequent and real-time update of the popularities. Moreover, we put forward three optimization schemes to further speed up the monitoring operations. Using a real trace stored in off-chip memory as input and setting the monitoring time window to 30 min, this method achieves a monitoring speed of 20.92 million objects per second (M/s) with multiple threads. This speed is equivalent to 16.74 Gbps throughput assuming the content length is 100 Bytes in average, but only consumes around 32 MB memory. By simulating the environment on the line card using a real-time generated synthetic trace, this method even reaches a speed of 251.07 M/s (equivalent to 200.86 Gbps) because the trace is fetched from high speed on-chip memory, rather than the off-chip DRAMs. Furthermore, both theoretical and experimental analyses elucidate very low relative error of this method. At last, a real trace-driven comparison shows that LFU policy achieves higher hit rate than LRU with much less unnecessary cache replacements.

High speed routers in Internet are becoming increasingly more powerful, as well as more energy hungry. However, they always show power-inefficient property due to we unilaterally in pursuit of high speed before. In response to this problem, we present a power-efficient router architecture named GreenRouter in this paper. GreenRouter separates a line card into two parts physically: the network interface card (named as DB) and the packet processing card (named as MB), which are interconnected by a two-stage unidirectional switch fabric. Traffic from all the DBs shares all the MBs in GreenRouter, thus the traffic can be aggregated to a few active MBs when traffic is light and the inactive MBs can be shut down to save power. We give the detailed architectural design of GreenRouter. Real-trace driven experiments show that GreenRouter can save about 50% power compared to the conventional router when the average traffic load is 30%, while providing quality of service guarantee at the same time.

Complex name constitution plus huge-sized name routing table makes wire speed name lookup a challenging task in Named Data Networking. To overcome this challenge, we propose two techniques to significantly speed up the lookup process. First, we look up name prefixes in an order based on the distribution of prefix length in the forwarding table, which can find the longest match much faster than the linear search of current prototype CCNx. The search order can be dynamically adjusted as the forwarding table changes. Second, we propose a new near-perfect hash table data structure that combines many small sparse perfect hash tables into a larger dense one while keeping the worst-case access time of O(1) and supporting fast update. Also the hash table stores the signature of a key instead of the key itself, which further improves lookup speed and reduces memory use.

String matching is a key technique for network security applications such as network intrusion detection systems and antivirus scanners, where the payload of every packet is inspected against thousands of patterns in real time. As the transmission rate of Internet links is getting higher and higher, the speed of matching engines is required to be faster and faster. Existing deterministic finite automaton (DFA)-based approaches achieve high throughput at the expense of extremely expensive memory cost; therefore, they are not suitable for the scenarios where only limited on-chip memory resources are available. To achieve fast matching speed while controlling memory expense, in this paper, we propose Kangaroo, a compact string matching scheme that scans multiple characters each time by running multiple small-sized finite state machines in parallel. Specifically, Kangaroo processes k consecutive characters mostly in one cycle by accessing k different memories in parallel, where k is a predefined factor that can be tuned based on the requirement of applications. Kangaroo is memory efficient. Experimental evaluations on Snort and ClamAV rule sets show that a tenfold increase in speed can be practically achieved by a single Kangaroo matching engine with a reduced memory cost comparing with the state-of-the-art DFA-based approaches.

A complete flow statistics report should include both flow size (the number of packets in a flow) counting and flow volume (the number of bytes in a flow) counting. Although previous studies have contributed a lot to the flow size counting problem, it is still a great challenge to well support the flow volume statistics due to the demanding requirements on both memory size and memory bandwidth in monitoring device. In this paper, we propose a DIScount COunting (DISCO) method, which is designed for both flow size and flow bytes counting. For each incoming packet of length l, DISCO increases the corresponding counter assigned to the flow with an increment that is less than l. With an elaborate design on the counter update rule and the inverse estimation, DISCO saves memory consumption while providing an accurate unbiased estimator. The method is evaluated thoroughly under theoretical analysis and simulations with synthetic and real traces. The results demonstrate that DISCO is more accurate than related work given the same counter sizes. DISCO is also implemented on the network processor Intel IXP2850 for a performance test. Using only one microengine (ME) in IXP2850, the throughput can reach up to 11.1 Gb/s under a traditional traffic pattern. The throughput increases to 39 Gb/s when employing four MEs.

Content-centric Networking (CCN) and the later proposed Named Data Networking (NDN) have attracted wide attention in both academia and industry, as the clean slate future Internet architecture. Wire speed name lookup for packet forwarding is one of the most challenging tasks in CCN/NDN. As a promising technology, its feasibilities including reachable speed, scalability, and update performance are imperative to be deeply evaluated. However, CCN/NDN is currently on its initial stage and no actual network is deployed, which means no real name routing tables and NDN traffic are available. In order to fulfill performance comparisons among various innovative name lookup solutions and facilitate future name lookup researches, we present NDNBench, a publicly available platform for evaluation, comparison and experiments with different name lookup approaches. NDNBench can generate various Forwarding Information Bases (FIBs), traces with structure and size diversity to conduct the tests thoroughly by adjusting the parameters. NDNBench provides a simulation package tool with flexibility to evaluate various name lookup approaches. Furthermore, in order to verify the effectiveness of NDNBench, we benchmark some existing name lookup schemes and the results are very supportive. NDNBench has been applied to recent work and is publicly available at the following site: http://s-router.cs.tsinghua.edu.cn/∼zhangting/.

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.

Network virtualization allows multiple virtual routers to coexist in the same physical router but offer independent routing services. Each virtual router needs to perform millions of lookups and thousands of updates per second to meet the requirements of high-speed Internet. The coexistence of these virtual routers intensifies scalability challenges to the routing lookup scheme: Can it scale well in storage, lookup speed and update performance as the number of virtual routers increases? In this paper, we propose Layer-based Overlay and Optimized Polymerization (LOOP) which has favorable scalability regardless of the number of virtual routers. Experiments on the general-purpose CPU show that LOOP achieves efficient storage, fast lookup, and fast incremental update. It compacts 18 FIBs with about 7M prefixes in total to only 4.6MB. One single thread can perform about 50M lookups per second on real-world traces. LOOP allows an update thread to run in parallel with lookup threads and barely interrupt them, and pure update testing indicates it can perform about 1M updates per second. One of the key advantages of LOOP is that it supports inserting and deleting virtual routers incrementally so it is ideal for fast and dynamic configuration of virtual networks.

In this paper we design, implement and evaluate NameFilter, a two-stage Bloom filter-based scheme for Named Data Networking name lookup, in which the first stage determines the length of a name prefix, and the second stage looks up the prefix in a narrowed group of Bloom filters based on the results from the first stage. Moreover, we optimize the hash value calculation of name strings, as well as the data structure to store multiple Bloom filters, which significantly reduces the memory access times compared with that of non-optimized Bloom filters. We conduct extensive experiments on a commodity server to test NameFilter's throughput, memory occupation, name update as well as scalability. Evaluation results on a name prefix table with 10M entries show that our proposed scheme achieves lookup throughput of 37 million searches per second at low memory cost of only 234.27 MB, which means 12 times speedup and 77% memory savings compared to the traditional character trie structure. The results also demonstrate that NameFilter can achieve 3M per second incremental updates and exhibit good scalability to large-scale prefix tables.

Different from the IP-based routers, Named Data Networking routers forward packets by content names, which consist of characters and have variable and unbounded length. This kind of complex name constitution plus the huge-sized name routing table makes wire speed name lookup an extremely challenging task. Greedy name lookup mechanism is proposed to speed up name lookup by dynamically adjusting the search path against the changes of the prefix table. Meanwhile, we elaborate a string-oriented perfect hash table to reduce memory consumption which stores the signature of the key in the entry instead of the key itself. Extensive experimental results on a commodity PC server with 3 million name prefix entries demonstrate that greedy name lookup mechanism achieves 57.14 million searches per second using only 72.95 MB memory.

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.

Internet has witnessed its paramount function transition from host-to-host communication to content dissemination. Named Data Networking (NDN) and Content-Centric Networking (CCN) emerge as a clean slate network architecture to embrace this shift. Pending Interest Table (PIT) in NDN/CCN keeps track of the Interest packets that are received but yet un-responded, which brings NDN/CCN significant features, such as communicating without the knowledge of source or destination, loop and packet loss detection, multipath routing, better security, etc. This paper presents a thorough study of PIT for the first time. Using an approximate, application-driven translation of current IP-generated trace to NDN trace, we firstly quantify the size and access frequencies of PIT. Evaluation results on a 20 Gbps gateway trace show that the corresponding PIT contains 1.5 M entries, and the lookup, insert and delete frequencies are 1.4 M/s, 0.9 M/s and 0.9 M/s, respectively. Faced with this challenging issue and to make PIT more scalable, we further propose a Name Component Encoding (NCE) solution to shrink PIT size and accelerate PIT access operations. By NCE, the memory consumption can be reduced by up to 87.44%, and the access performance significantly advanced, satisfying the access speed required by PIT. Moreover, PIT exhibits good scalability with NCE. At last, we propose to place PIT on (egress channel of) the outgoing line-cards of routers, which meets the NDN design and eliminates the cumbersome synchronization problem among multiple PITs on the line-cards.

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.

Routing is undoubtedly the foundation of NDN's data transmission service. We propose a two-layer routing protocol for NDN [1], [2], which is composed of a Topology Maintaining (TM) layer and a Prefix Announcing (PA) layer. The underlying layer (TM) maintains the full topology of an NDN network domain and calculates the shortest-path trees. The upper layer (PA) provides content in two ways: active publishing and passive serving. However, solely adopting either of them will lead to the problem of scalability. We compare the efficiency and cost of the two methods, and evaluation results show that active publishing is much more efficient than the passive serving method in terms of triggered traffic, but actively publishing all the content will lead to Forwarding Information Base (FIB) explosion. Therefore, we further propose a popularity-based active publishing policy and arrive at a compromise between the active and passive methods. Moreover, we put forward several methods to aggregate FIB entries, and the FIB size shrinks effectively after aggregation. This routing protocol is compliant with the NDN characteristics and supports NDN multipath routing.

Flow-based packet processing exists widely in a variety of network applications, where a large sized flow table is built to keep the alive flow records. To accelerate the search speed of the flow table, numerous systems employ cache mechanism to track the most recently referenced flows. However, network traffic exhibits some different characteristics from the workload of the general computational tasks, and classic replacement policies like LRU, Random, fail to perform well in the network scenarios. To develop a network-oriented flow cache replacement policy, we propose ALFE (Adaptive Least Frequently Evicted) based on the observations of traffic's heavy tailed feature and the statistically positive correlation between the flow size and the flow cache evict times. Specifically, the correlation helps us identify elephant flows at a tiny extra cost of a few more bits allocated to each flow entry. For those who are identified as possible elephant flows, ALFE favors their priorities in the cache, thus preventing them from being flooded by the massive mice flows. A prototype system employing ALFE policy is elaborately designed and implemented besides extensive simulations. Experimental results indicate that with 1K cache entries, ALFE can achieve up to 15% higher cache hit rate than LRU on real traces.

The size of routing tables has been growing rapidly, while the link transmission speed of Internet backbone has increased up to 100Gbps commercially and towards 400Gbps Ethernet for laboratory experiments. In order to alleviate the pressure from both the huge large routing table and very high interface speed, ISPs are trying to find ways to compress the table while striving to design a more powerful lookup engine. To address this issue, we propose an algorithm, named Optimal Non-overlap Routing Table Constructor (ONRTC), to compute an equivalent routing table with a minimal number of prefixes under the constraint that all the prefixes are not overlapped. Experimental evaluations show that, for large backbone routing tables, the ONRTC algorithm requires only about 71% of the original number of prefixes. We release ONRTC's source code in [10].

Name-based route lookup is a key function for Named Data Networking (NDN). The NDN names are hierarchical and have variable and unbounded lengths, which are much longer than IPv4/6 address, making fast name lookup a challenging issue. In this paper, we propose an effective Name Component Encoding (NCE) solution with the following two techniques: (1) A code allocation mechanism is developed to achieve memory-efficient encoding for name components, (2) We apply an improved State Transition Arrays to accelerate the longest name prefix matching and design a fast and incremental update mechanism which satisfies the special requirements of NDN forwarding process, namely to insert, modify, and delete name prefixes frequently. Furthermore, we analyze the memory consumption and time complexity of NCE. Experimental results on a name set containing 3,000,000 names demonstrate that compared with the character trie NCE reduces overall 30% memory. Besides, NCE performs a few millions lookups per second (on an Intel 2.8 GHz CPU), a speedup of over 7 times compared with the character trie. Our evaluation results also show that NCE can scale up to accommodate the potential future growth of the name sets.

The sizes of routing table in backbone routers continue to keep a rapid growth and some of them currently increase up to 400K entries [1]. An effective solution to deflate the large table is the routing table compression. Meanwhile, there is an increasingly urgent demand for fast routing update mainly due to the change of network topology and new emerging Internet functionalities. Furthermore, the Internet link transmission speed has scaled up to 100Gbps commercially and towards 400Gbps Ethernet for laboratory experiments, resulting in a raring need of ultra-fast routing lookup. To achieve high performance, backbone routers must gracefully handle the three issues simultaneously: routing table Compression, fast routing Lookup, and fast incremental Update (CLUE), while previous works often only concentrate on one of the three dimensions. To address these issues, we propose a complete set of solutions-CLUE, by improving previous works and adding a novel incremental update mechanism. CLUE consists of three parts: a routing table compression algorithm, an improved parallel lookup mechanism, and a new fast incremental update mechanism. The routing table compression algorithm is based on ONRTC algorithm [2], a base for fast TCAM parallel lookup and fast update of TCAM. The second part is the improvement of the logical caching scheme for dynamic load balancing parallel lookup mechanism [3]. The third one is the conjunction of the trie, TCAM and redundant prefixes update algorithm. We analyze the performance of CLUE by mathematical proof, and draw the conclusion that speedup factor is proportional to the hit rate of redundant prefixes in the worst case, which is also confirmed by experimental results. Large-scale experimental results show that, compared with the mechanism in [3], CLUE only needs about 71% TCAM entries, 4.29% update time, and 3/4 dynamic redundant prefixes for the same throughput when using four TCAMs. In addition, CLUE has another advantage over the mechanism in [3] - the frequent interactions between control plane and data plane caused by redundant prefixes update can be avoided.

With the rapid growth of the Internet, the update messages in backbone routers become more and more frequent due to the ever-increasing dynamic changes on network topologies and new emerging functionalities of the Internet. In addition, update messages often come as a burst. Update action interrupts the packet lookup operation in the router's data plane, thus inefficient incremental update algorithm slows down IP lookup speed, and potentially badly degrades the system performance during bursty updates. Among trie-based routing lookup algorithms, binary trie has the best update complexity O(W) (W is the maximum depth of the trie), but exhibits slow lookup speed, failing to be competent for forwarding tens of gigabit-per-second traffic in backbone routers. Therefore, various improved routing lookup algorithms are proposed to pursue high speed based on binary trie, but sacrificing the performance of incremental update. To minimize the interruption time that update operation incurs, we propose Blind Spot (BS) algorithm by picking out those updating nodes which would have produced domino effect, achieving an update complexity of O(lookup+h), meanwhile keeping the lookup speed almost unchanged. Blind Spot algorithm is a universal methodology, which is applicable to all the trie-based lookup algorithms. To evaluate the performance of BS algorithm, we applied it to Lulea [1] and LC-trie [2] algorithms as two representatives. Extensive experimental results show that both Lulea+BS and LC+BS algorithms achieve a much faster update speed than binary trie, while keeping the same lookup speed as the original Lulea and LC-trie algorithms.

Virtual router research has drawn increasing attention in recent years, and the most challenging issues of virtual routers are compression, lookup, and incremental update of 10∼200 routing tables. In this paper, we propose a set of solutions to achieve that storage, lookup time, and update time don't expand to 10∼200 times, but reduce to 1∼2 times.

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.

Green networking in the Internet becomes increasingly important. In a high-performance router, the dominant power consumer on the Internet, half of its total power usage goes into the line-cards, where the traffic managers inside consume most of it. In this paper, we propose an energy-efficient design on the traffic manager architecture for packet buffering and storage. Unlike traditional routers where packets are always kept in off-chip memory, we propose a dynamic on-chip and off-chip scheduling mechanism, called Dynamic Packet Manager (DPM), to reduce both peak and average power consumption caused by the traffic manager. DPM buffers packets in a small on-chip memory in the light-traffic period, and activates the off-chip memory on when the on-chip memory is to overflow. In this design, when the traffic is light, the off-chip memory is put into power saving state by clock gating so that the average power consumption is reduced. With an on-chip flow based and off-chip class-based design, DPM can save one off-chip memory otherwise used for the per-flow index information storage, therefore further reduce the peak power usage. We present the theoretic analysis guiding the implementation of the DPM mechanism. Experiments on three prototypes implemented on different hardware show that the peak and average power consumptions can be reduced by 27.9% and 37.5% respectively, along with less on-chip memory cost. Besides, the traffic manger with DPM shows better performance on average packet scheduling delay than the one without DPM.

Today's Internet applications exhibit increased diversity, while the Internet routers are still oblivious to this trend. To improve the end-to-end application QoS, one solution is to embed the application information explicitly in packet headers, but it will bring global changes. Another local solution is router-assisted traffic differentiation. To achieve this, the functionalities including packet identification and flow tracking inside the router are required. While most existing studies focus on the former, fewer efforts are put on the later. Given a large flow table is involved, how to track millions of concurrent flows in a cost-effective manner on a router's line card raises a great space-time challenge. To address this, we design an on-chip/off-chip flow tracking system to accommodate millions of flows and achieve the throughput at tens of Gigabits. By exploiting temporal locality and heavy-tailedness of Layer-4 traffic, we design the Adaptive Least Frequently Evicted (ALFE) replacement policy to catch elephant flows, therefore maintain a high cache hit rate. To alleviate performance penalty due to the cache misses, we organize the flow table in a fixed-allocated manner to fully utilize modern DRAM's burst feature. We have implemented a research prototype using FPGA for performance evaluation. The experiment results show that our system can reach 80% hit rate with a small-sized cache of 16K entries, while achieving 70Mpps throughput. This enables backbone line rate processing. Further, more than 40% power saving can be achieved by our system, which is fast and accurate with only 3% FPGA resource usage.

Traditional network processors (NPs) adopt pull model, where NP cores pull packet data from external memory to local memory, triggered by cache miss or fetch instructions. Due to the long latency of data fetching, hardware multithreading is typically used to reduce the waiting time. Multithreading incurs context switch overhead, leading to inefficiency in payload processing applications. We propose a push model for future NP's architectural design to increase throughput and decrease processing delay. A hardware push unit helps to move the segments of a packet to a core's local memory to reduce hardware thread switching. Theoretical analyses are given to compare the pull and push model's performance. Further, we selected our FPGA based THNPU NP platform for verification. Experimental results indicate that the push model not only improves the system throughput, but also reduces the delay, with only a fraction of logic gate increase.

With the fast development of Internet, the size of routing tables in the backbone routers keeps a rapid growth in recent years. An effective solution to control the memory occupation of the ever-increased huge routing table is the Forwarding Information Base (FIB) compression. Existing optimal FIB compression algorithm ORTC suffers from high computational complexity and poor update performance, due to the loss of essential structure information during its compression process. To address this problem, we present two suboptimal FIB compression algorithms — EAR-fast and EAR-slow, respectively, based on our proposed Election and Representative (EAR) algorithm which is an optimal FIB compression algorithm. The two suboptimal algorithms preserve the structure information, and support fast incremental updates while reducing computational complexity. Experiments on an 18-month real data set show that compared with ORTC, the proposed EAR-fast algorithm requires only 9.8% compression time and 37.7% memory space, but supports faster update while prolonging the recompression interval remarkably. All these performance advantages come at a cost of merely a 1.5% loss in compression ratio compared with the theoretical optimal ratio.

Peer-to-Peer (P2P) mode dominates the way that files are shared over the Internet today. A measurement study on the user behaviour during the P2P file sharing is important and helpful to better understand and design P2P networks. In this study, the authors developed a method to collect information about peers and connections in movie sharing at the BitTorrent client side. Movie is selected as the investigation object since its immense popularity and large size among all the file types over P2P networks. The method proposed in this study can be easily applied to study the distribution behaviour of other types of files. Based on the collected data, the authors have derived 10 observations in three categories: (i) distributions of peers and connections over globe time and local time (after adjustment of time differences); (ii) distributions of peers and connections over geographic areas (at different levels of continents, countries, cities); and (iii) the influence to the above distributions by differences of population, gross domestic product (GDP) and life style.

SYN flood attacks still dominate distributed denial of service attacks. It is a great challenge to accurately detect the SYN flood attacks which utilise skillful spoofs to evade traditional detection methods. An intelligent attacker would evade the public detection methods by suitably spoofing the attack to appear benign. Keeping per-flow or per-connection state could eliminate such a spoofing, but meanwhile, it is very difficult to be implemented in practice. A more accurate and fast SYN flood detection method, named SACK2, is proposed to deal with all kinds of SYN flood attacks with limited implementation costs. SACK2 exploits the behaviour of the SYN/ACK-CliACK pair to identify the victim server and the TCP port being attacked, where a SYN/ACK packet is sent by a server when receiving a connection request and a CliACK packet is the ACK packet sent by the client to complete the three-way handshake. It also utilises the space efficient data structure, counting Bloom filter, to recognise the CliACK packet. The memory cost of SACK2 for a 10 Gbps link is 364 KB and can be easily accommodated in modern routers. SACK2 can report the start of the attack in less than one detection period, and the end of the attack less than two detection periods. It is also demonstrated that SACK2 is the most accurate detection method through comprehensive experiments.

Multipath Switching systems (MPS) are intensely used in state-of-the-art core routers to provide terabit or even petabit switching capacity. One of the most intractable issues in designing MPS is how to load balance traffic across its multiple paths while not disturbing the intraflow packet orders. Previous packet-based solutions either suffer from delay penalties or lead to O(N^2 ) hardware complexity, hence do not scale. Flow-based hashing algorithms also perform badly due to the heavy-tailed flow-size distribution. In this paper, we develop a novel scheme, namely, Flow Slice (FS) that cuts off each flow into flow slices at every intraflow interval larger than a slicing threshold and balances the load on a finer granularity. Based on the studies of tens of real Internet traces, we show that setting a slicing threshold of 1-4 {\rm ms}, the FS scheme achieves comparative load-balancing performance to the optimal one. It also limits the probability of out-of-order packets to a negligible level (10^{ - 6}) on three popular MPSes at the cost of little hardware complexity and an internal speedup up to two. These results are proven by theoretical analyses and also validated through trace-driven prototype simulations.

Sampling technology has been widely deployed in network measurement systems to control memory consumption and processing overhead. However, most of the existing methods suffer from large errors for the estimation of small-size flows. To address this problem, we propose an adaptive non-linear sampling (ANLS) method for flow size estimation. Instead of statically pre-configuring the sampling rate, ANLS dynamically adjusts the sampling rate for each flow according to the value of a corresponding counter. A smaller sampling rate is utilized when the counter value is large, while a larger sampling rate is employed for a smaller counter. In this paper, the unbiased flow size estimation, the relative error, and the required counter size are studied through theoretical analysis and experimental evaluations. The analysis and experiments demonstrate that ANLS can significantly improve the estimation accuracy (particularly for small-size flows), and save memory consumption, while maintaining processing overhead comparable to existing methods. Moreover, we validate the design of ANLS by implementing an FPGA-based prototype, which is capable of measuring traffic throughput up to 26.5 Gbps.

In response to Internet emergencies, Internet resiliency is investigated directly through an autonomous system (AS) level graph inferred from policy-compliant BGP paths or/and traceroute paths. Due to policy-driven inter-domain routing, the physical connectivity does not necessarily imply network reachability in the AS-level graph, i.e., many physical paths are not visible by the inter-domain routing protocol for connectivity recovery during Internet outages. We call the invisible connectivity at the routing layer, which can be quickly restored for recovering routing failures by simple configurations, as the potential routing diversities. In this paper, we evaluate two kinds of potential routing diversities, which are recognized as Internet eXchange Points (IXPs) participant reconnection and peering policy relaxation. Using the most complete dataset containing AS-level map and IXP participants that we can achieve, we successfully evaluate the ability of potential routing diversity for routing recovery during different kinds of Internet emergencies. Encouragingly, our experimental results show that 40% to 80% of the interrupted network pairs can be recovered on average beyond policy-compliant paths, with rich path diversities and a little traffic shifts. Thus, this paper implies that the potential routing diversities are promising venues to address Internet failures.

L7-filter is a significant deep packet inspection (DPI) extension to Netfilter in Linux's QoS framework. It classifies network traffic based on information hidden in the packet payload. Although the computationally intensive payload classification can be accelerated with multiple processors, the default OS scheduler is oblivious to both the software characteristics and the underlying multicore architecture. In this paper, we present a parallelized L7-filter algorithm and an efficient scheduler technique for multicore servers. Our multithreaded L7-filter algorithm can process the incoming packets on multiple servers boosting the throughput tremendously. Our scheduling algorithm is based on Highest Random Weight (HRW), which maintains the connection locality for the incoming traffic, but only guarantees load balance at the connection level. We present an Adapted Highest Random Weight (AHRW) algorithm that enhances HRW by applying packet-level load balancing with an additional feedback vector corresponding to the queue length at each processor. We further introduce a Hierarchical AHRW (AHRW-tree) algorithm that considers characteristics of the multicore architecture such as cache and hardware topology by developing a hash tree architecture. The algorithm reduces the scheduling overhead toO(logN) instead ofO(N) and produces a better balance between locality and load balancing. Results show that the AHRW-tree scheduler can improve the L7-filter throughput by about 50% on a Sun-Niagara-2-based server compared to a connection locality-based scheduler. Although extensively tested for L7-filter traces, our technique is applicable to many other packet processing applications, where connection locality and load balancing are important while executing on multiple processors. With these speedups and inherent software flexibility, our design and implementation provide a cost-effective alternative to the traffic monitoring and filtering ASICs.

Name-based route lookup is a key function for Named Data Networking (NDN). The NDN names are hierarchical and have variable and unbounded lengths, which are much longer than IPv4/6 address, making fast name lookup a challenging issue. In this paper, we propose a parallel architecture for NDN name lookup called Parallel Name Lookup (PNL) which leverages hardware parallelism to achieve high lookup speedup while keeping a low and controllable memory redundancy. The core of PNL is an allocation algorithm that maps the logically tree-based structure to physically parallel modules, with low computational complexity. We evaluate the PNL's performance and show that PNL dramatically accelerates the name lookup process. Furthermore, with certain knowledge of prior probability, the speedup can be significantly improved.

How to design the next-generation Internet is an open technique issue. One of the mainstream ideas is to enhance network routers with application-oriented intelligence. For example, firewalls,Web proxies/caches, mobile gateways, and multicast capable nodes are equipments with application-oriented intelligence for security/performance enhancement. However, there is no systematic study on what intelligence should be incorporated into the router and what the fundamental benefit of the application-oriented networking is. This paper presents a generic application-oriented networking (GAON) simulation framework compatible with the Network Simulator ns-2 to facilitate the research in the area. With GAON, developers can conveniently enhance the ns-2 nodes with customized functionalities, and seamlessly incorporate them into the regular ns-2 system. GAON provides a generic scenario control interface, through which ns- 2 users can flexibly load/unload customized GAON processing agents on network nodes. The regular ns-2 node structure is extended, where a GAON agent classifier is set up to dispatch GAON traffic to correct GAON agents. Moreover, a unified interface to the ns-2 built-in routing table is developed to facilitate GAON agents forwarding packets. Two multicast protocols are implemented to demonstrate the validation of GAON, with the simulation results presented.

Deep packet inspection (DPI) has become one of the key components of a Network Intrusion Detection System (NIDS) and it compares packet content to a set of rules written in regular expression. The need to keep up with ever-increasing line speed has forced NIDS designers to move to hardware or high-speed memory where memory resources are limited. In this paper, we present LBM, a novel accelerating scheme for regular expression matching which converts the original byte stream into much shorter integer stream and then matches it with a variant of DFA, called StriD2FA. In the instance of LBM that we realize, 10 to 15 speedup is reasonable while the memory is much smaller than traditional DFA.

Peer-to-Peer (P2P) mode dominates the way that files are shared over the Internet today. A measurement study on the user behavior during the P2P file sharing is important and helpful to better understand and design P2P networks. In this paper, we developed a method to collect information about peers and connections in movie sharing at the BitTorrent client side. Based on the collected data, we have derived 5 observations in the influence upon peers and connections distributions over geographic areas (at different levels of continents, countries, cities) by differences of population, GDP (Gross Domestic Product), time zone and life style.

Deep Packet Inspection (DPI) involves searching a packet's header and payload against thousands of rules to detect possible attacks. The increase in Internet usage and growing number of attacks which must be searched for has meant hardware acceleration has become essential in the prevention of DPI becoming a bottleneck to a network if used on an edge or core router. In this paper we present a new multi-pattern matching algorithm which can search for the fixed strings contained within these rules at a guaranteed rate of one character per cycle independent of the number of strings or their length. Our algorithm is based on the Aho-Corasick string matching algorithm with our modifications resulting in a memory reduction of over 98% on the strings tested from the Snort ruleset. This allows the search structures needed for matching thousands of strings to be small enough to fit in the on-chip memory of an FPGA. Combined with a simple architecture for hardware, this leads to high throughput and low power consumption. Our hardware implementation uses multiple string matching engines working in parallel to search through packets. It can achieve a throughput of over 40 Gbps (OC-768) when implemented on a Stratix 3 FPGA and over 10 Gbps (OC-192) when implemented on the lower power Cyclone 3 FPGA.

Flow-level sampling methods have been widely studied and extensively employed in network traffic measurement systems. However, traffic anomalies are becoming more prevalent and severe in the Internet, which pose great challenges to the traffic measurement. Existing solutions targeted at such scenario have either low accuracy or high memory usage. In this paper, we propose a two-stage sampling approach-Anti Attack Counters (A2C) and an efficient parameter adapting method to solve the problem. The proposed sampling mechanism can adapt to the network condition automatically and collect more information even under severe traffic attacks. Theoretical analysis on accuracy and resource requirement is presented in our work. Furthermore, we validate our approach using both synthetic and real traces. The experimental results demonstrate that A2C is of high resilience while providing significantly improved measurement accuracy with reduced memory occupation comparing with other existing anti-attack countermeasures.

Today's file sharing networks are creating potential security problems to enterprise networks, i.e., the leakage of confidential documents. In order to prevent such leakage, we propose the Data Leakage Prevention System (DLPS) which is applied at the entrance of the enterprise network to filter out the outgoing sensitive information. The DLPS is based on a content scanning engine which defines a new type of matching problem, called longest overlap matching which also exits in many other applications as a basic problem where contents are delivered by small blocks. We study the problem by comparing it with the traditional pattern matching problem in Deep Packet Inspection (DPI) of Network Intrusion Detection Systems (NIDS) whose solutions are based on finite automata. We develop a new finite automata representation called Skip-Finite Automata (Skip-FA) which detects the packets carrying sensitive information by using default transitions to implicitly track the overlapping parts between packets' payloads and sensitive files. The simulation results shows that our system achieves a matching speed of about 10B+ per memory access for small file set (>;20KB) and 100B+ per memory access for large file set (>;2500KB). We also find that the memory consumption of Skip-FA is almost the same to that of the original files.

Multi-string matching is a key technique for implementing network security applications like Network Intrusion Detection Systems (NIDS). Existing DFA-based approaches always tradeoff between memory and throughput, and fail to has the best of both worlds. This paper extends the classic longest prefix principle from single-character to multi-character string matching and proposes a multi-string matching acceleration scheme named Independent Parallel Compact Finite Automata (PC-FA). In the scheme, DFA is divided into k PC-FAs, each of which can process one character from the input stream, achieving a speedup up to k with reduced memory occupation. Theoretical proof is given for the equivalency between traditional DFA and PC-FA approach. Experimental evaluations show that seven times of speedup can be practically achieved with a reduced memory size than up-to-date DFA-based compression approaches.

Regular expression (Regex) becomes the standard signature language for security and application detection. Deterministic finite automata (DFAs) are widely used to perform regex matching in linear time. Previously researches mostly focus on how to compress DFA to reduce memory requirements in recent years. However, memory requirement is not the only problem caused by DFA explosion when implementation DFA matching system. In this paper, we propose a new issue in DFA matching procedure. We notice that the DFA produced from regex never considers the physical locality of logical neighbor, which results in a low cache hit rate when using cache as matching accelerator. This problem becomes severe for current increasingly complex security regex which producing huge DFA with nearly no locality in physical location. We propose to solve this problem through reordering the state number of existing DFA and further put forward two methods on reordering DFA from different viewpoints. In our algorithms, we achieve more than twice cache hit rate compared with traditional method. Moreover, our methods will not affect the existing matching system. Hence, all the cache hit rate improvement is achieved without any cost in wire speed matching.

Most multicast routing protocols construct reverse shortest path trees (SPTs) to deliver shared data. However, the use of the reverse SPT presents a challenge in the inter-domain routing environment, as the path from the source to a receiver could be asymmetric to the one used to go from the receiver to the source. A possible approach is to utilize the round-trip joining message but it incurs the demerit of long joining delay. In this paper, we propose a BGP-view based fast-join (BFJ) mechanism, where the receiver domain border router leverages the BGP routing information in the border router of the source domain to identify an efficient joining path. The initial joining message can then be delivered using source routing along the identified path to quickly construct the reverse SPT even in asymmetric routing environment. Subsequent joining messages temporarily label corresponding interfaces at intermediate routers so that requested data packets are steered to the subscriber as soon as possible. The NS2 simulation results show that the proposed BFJ scheme is more efficient than the approach of round-trip joining message even under the favored condition of the latter.

More complicated computational tasks are posed to the network equipments, such as Deep packet inspection (DPI) for network security check and network coding to achieve efficient multicast, etc. These complicated applications need processors to process the whole packet payload, potentially causing low throughput and long latency due to the large access delay to external memories. The behind hint lies that we can get the packet-processor/thread pair binding information in advance from the front-end dispatching component before the packet will be actually processed by cores. This interesting observation enables us design a new architecture of memory access for packet processors instead of the traditional model. In this paper we explore to apply push model to packet processors. The push model makes the data being pushed into the local memory/on-chip L1 cache in an on-demand and fine granularity manner ahead of being asked by running instructions, making a core always feels getting its data from the local memory/L1 cache instead of fetching them from the external memory in pull model. In order to verify the effectiveness, we design and implement the push model with the Intel IXP2850, and then conduct experiments to show the performance of push model in the IXP2850 simulator compared with the pull model. Simulation results indicate that applying push model to packet processors could improve the system throughput and reduce the packet processing latency and reducing required number of hardware threads.

Per-flow queuing is believed to be an effective approach to guarantee Quality of Service (QoS) in high performance routers. However, its brute-force implementation consumes a huge amount of memory and is not scalable as the number of flows increases. Dynamic Queue Sharing (DQS) mechanism, in which a physical queue is dynamically created on-demand when a new flow comes and released when the flow temporarily paused, is able to achieve per-flow queuing performance with much less memory. In this paper, based on DQS, an active per-flow queuing system is designed, implemented and tested. To evaluate the effectiveness of DQS, we implement two FPGA-based Traffic Manager (TM) prototypes, one with DQS and the other a traditional one. The real chip implementation shows that DQS can not only scale down the required memory for per-flow queuing but also reduce the total number of control logic elements. As a result of reduced control logic, original 3-stage scheduling in naive scheme can be improved to be a single stage while maintaining the same delay performance, thus resulting in a faster speed potential. Besides, the power consumption can also considerably be reduced. Our experiments on a 4Gbps TM prototype using Stratix EP1S80F1508C5 FPGA show a 58.6% decrease in control memory. Meanwhile, the logic cells and LC registers are reduced by 6.8% and 15.0% respectively, and the power consumption is saved by 23% compared with the brute-force per-flow queuing implementation with 8K queues.

Multi-pattern matching is a key technique for implementing network security applications such as Network Intrusion Detection/Protection Systems (NIDS/NIPSes) where every packet is inspected against predefined attack signatures written in regular expressions (regexes). To this end, Deterministic Finite Automaton (DFA) is widely used for multi-regex matching, but existing DFAbased researches have claimed high throughput at an expenses of extremely high memory cost. In this paper, we propose a parallel architecture of DFA called Parallel DFA (PDFA), using multiple flow aggregations to increase the throughput with nearly no extra memory cost. The basic idea is to selectively store the DFA in multiple memory modules which can be accessed in parallel and to explore the potential parallelism. The memory cost of our system in both the average cases and the worst cases is analyzed, optimized and evaluated by numerical results. The evaluation shows that we obtain an average speedup of about 0.5k to 0.7k where k is the number of parallel memory modules under our synthetic trace and compressed real trace in a statistical average case, compared with the traditional DFA-based matching approaches.

In Network Intrusion Detection System, De-terministic Finite Automaton (DFA) is widely used to compare packet content at a constant speed against a set of patterns specified in regular expressions (regex patterns). However, combining many regex patterns into a single DFA causes a serious state explosion. Partitioning the pat-tern set into several subsets, each of which produces a small DFA, is a practical way to deflate the state explosion. In this paper, we propose a regex pattern grouping scheme based on a new DFA model called Pattern-Based DFA (P-DFA) which supports efficient pattern-based op-erations, such as insertion, deletion, and etc. By using these basic operations, one can easily measure the state explo-sion when combining a set of regex patterns into a single DFA. Based on the privilege, we develop regex grouping algorithms for mitigating the state explosion in parallel and sequential matching environments, respectively. The evaluation shows that under the same constraints, our ap-proach requires only half the number of groups compared with the most well-known algorithms.

There is an increasing demand for network devices to perform deep packet inspection (DPI) to enhance network security. In DPI the packet payload is compared against a set of predefined patterns which can be specified using regular expressions (regexes). It is well-known that mapping regexes to deterministic finite automata (DFA) will suffer from the state explosion problem. Through observation, we attribute DFA explosion to the necessity of remembering matching history. In this paper, we investigate how to record the matching history efficiently and propose an extended DFA approach for regex matching called fcq-FA, which can make a memory size reduction of about 1000 times with a fully automated approach. In fcq-FA, we use pipeline queues and counters to help recording the matching history. Hence, state explosion caused by Kleene closure and repetitions can be definitely avoided. Further, it achieves a fully automated signature compilation with polynomial running time and space.

A basic task in network passive measurement is collecting flow statistics information for network state characterization. With the continuous increase of Internet link speed and the number of flows, flow statistics has become a great challenge due to the demanding requirements on both memory size and memory bandwidth in measurement devices. In this paper, we propose a DIScount COunting (DISCO) method, which is designed for both flow size and flow volume counting. For each incoming packet of length l, DISCO increases the corresponding counter assigned to the flow with an increment that is less than l. With an elaborate design on the counter update rule and the inverse estimation, DISCO saves memory consumption while providing an accurate unbiased estimator. The method is evaluated thoroughly under theoretical analysis and simulations with synthetic and real traces. The results demonstrate that DISCO is more accurate than related work given the same counter size. DISCO is also implemented on network processor Intel IXP2850 for performance test. Using only one MicroEngine (ME) in IXP2850, the throughput can reach up to 11.1Gbps under a traditional traffic pattern, and it increases almost linearly with the number of MEs employed.

Current network infrastructures exhibit poor power efficiency, running network devices at full capacity all the time regardless of the traffic demand and distribution over the network. Most research on router power management are at component level or link level, treating routers as isolated devices. A complementary approach is to facilitate power management at network level by routing traffic through different paths to adjust the workload on individual routers or links. Given the high path redundancy and low link utilization in today's large networks, this approach can potentially allow more network devices or components to go into power saving mode. This paper proposes an intra-domain traffic engineering mechanism, GreenTE, which maximizes the number of links that can be put into sleep under given performance constraints such as link utilization and packet delay. Using network topologies and traffic data from several wide-area networks, our evaluation shows that GreenTE can reduce line-cards' power consumption by 27% to 42% under constraints that the maximum link utilization is below 50% and the network diameter remains the same as in shortest path routing.

As the Internet becomes a critical infrastructure component of our global information-based society, any interruption to its availability can have significant economical and societal impacts. Although many researches tried to improve the resilience through the BGP policy-compliant paths, it has been demonstrated that the Internet is still highly vulnerable when major failures happen. In this paper, we aim to overcome the inherent constraint of the existing BGP-compliant recovery schemes and propose to seek additional potential routing diversity by relaxing BGP peering links and through Internet eXchange Points (IXPs). The focus of this paper is to evaluate the potentiality of these two schemes, rather than on their implementations. By collecting most complete AS link map up-to-date with 31K nodes and 142K links, we demonstrate that the proposed potential routing diversity can recover 40% to 80% of the disconnected paths on average beyond BGP-compliant paths. This work suggests a promising venue to address the Internet failures.

False routing announcements are a serious security problem, which can lead to widespread service disruptions in the Internet. A number of detection systems have been proposed and implemented recently, however, it takes time to detect attacks, notify operators, and stop false announcements. Thus detection systems should be complemented by a mitigation scheme that can protect data delivery before the attack is resolved. We propose such a mitigation scheme, QBGP, which decouples the propagation of a path and the adoption of a path for data forwarding. QBGP does not use suspicious paths to forward data traffic, but still propagates them in the routing system to facilitate attack detection. It can protect data delivery from routing announcements of false sub-prefixes, false origins, false nodes and false links. QBGP incurs overhead only when there are suspicious paths, which happen infrequently in real BGP traces. Results from large scale simulations and BGP trace analysis show that QBGP is light-weight yet effective, and it converges faster and incurs less overhead than Pretty Good BGP.

The emerging multi-core platforms provide a high-performance, easy-to-develop and flexible way to implement high-speed network applications. For example, multi-core solutions for layer 7 protocol identification achieve 2 Gbps or higher processing speed. However, they occupy most of the processing cores in the system, leaving limited headroom for more complex manipulations, such as intrusion detection/prevention, anti-malware, data loss prevention, etc. Based on the deep understanding of the application bottlenecks and the optimization techniques of X86-64 platforms, we achieve the same or higher speed using only one core, saving more resources for further processing. In this paper, we make a deep system-wide profile and analyze the major hotspots of a typical network system on an Intel X86-64 platform, including a complete TCP/IP stack and a protocol identification engine by deep packet inspection (DPI). Profiling results and analysis show that network applications containing layer 2 to layer 7 processing are inherently memory and computation intensive. Then we propose optimization guidelines and techniques: 1) removing memory bottlenecks: combining independent irregular memory access to hide delay, using software-assistant cache prefetch to improve cache hit ratio, and mapping memory from kernel space to user space to reduce access overhead; 2) removing computation bottlenecks: using 64-bit registers and instructions to speed up the common computations, and using Streaming SIMD Extensions (SSE) instructions to accelerate special time-consuming tasks. Compared to the state-of-the-art multi-core implementations, our implementation on the X86-64 platform using only one core can deliver the same or higher processing speed of 7 Gbps with the average packet size of 501 bytes and 2 Gbps with the average packet size of 110 bytes.

Accuracy and speed are the two most important metrics for Network Intrusion Detection/Prevention Systems (NIDS/NIPSes). Due to emerging polymorphic attacks and the fact that in many cases regular expressions (regexes) cannot capture the vulnerability conditions accurately, the accuracy of existing regex-based NIDS/NIPS systems has become a serious problem. In contrast, the recently-proposed vulnerability signatures (a.k.a data patches) can exactly describe the vulnerability conditions and achieve better accuracy. However, how to efficiently apply vulnerability signatures to high speed NIDS/NIPS with a large ruleset remains an untouched but challenging issue.

With rapid advancement in Internet technology and usages, some emerging applications in data communications and network security require matching of huge volume of data against large signature sets with thousands of strings in real time. In this article, we present a memory-efficient hardware implementation of the well-known Aho-Corasick (AC) string-matching algorithm using a pipelining approach called P-AC. An attractive feature of the AC algorithm is that it can solve the string-matching problem in time linearly proportional to the length of the input stream, and the computation time is independent of the number of strings in the signature set. A major disadvantage of the AC algorithm is the high memory cost required to store the transition rules of the underlying deterministic finite automaton. By incorporating pipelined processing, the state graph is reduced to a character trie that only contains forward edges. Together with an intelligent implementation of look-up tables, the memory cost of P-AC is only about 18 bits per character for a signature set containing 6,166 strings extracted from Snort. The control structure of P-AC is simple and elegant. The cost of the control logic is very low. With the availability of dual-port memories in FPGA devices, we can double the system throughput by duplicating the control logic such that the system can process two data streams concurrently. Since our method is memory-based, incremental changes to the signature set can be accommodated by updating the look-up tables without reconfiguring the FPGA circuitry.

Ubiquitous multi-core-based web servers and edge routers are increasingly popular in deploying computationally intensive Deep Packet Inspection (DPI) programs. Previous work has shown the benefits of connection locality-based scheduling on multi-core servers to improve L7-filter performance. However, we show that highly threaded hierarchical multi-core processors, such as the Sun Niagara 2 processor, accumulate imbalanced workload at each resource layer. This workload imbalance potentially offsets the benefits from connection locality. In addition, connection-locality-based load balance fails to work when network traffic is unevenly distributed.

Deterministic Finite Automaton (DFA) is well-known for its constant matching speed in worst case, and widely used in multi-string matching, which is a critical technique in high performance Network Intrusion Detection System (NIDS) design. Existing DFA-based researches achieve high throughput at the expense of extremely high memory cost, so they fail to be used in situations like embedded systems where very tight memory resource is available. In this paper, we propose a memory-efficient multi-string matching acceleration scheme named Synergic Parallel Compact (SPC) Match Engine, which can provide a high matching speedup with no extra memory cost than the traditional DFA. Our scheme can be understood as consisting of k SPC-FAs, each of which can process one character from the input stream, causing achieving a constant speedup factor k with reduced memory occupation. Experimental evaluations with Snort and ClamAV rulesets show that a speedup of 9X can be practically achieved by a single SPC Match Engine instance with a reduced memory size than the up-to-date DFA-based compression approaches.

Deep packet inspection (DPI) relies highly on regular expression due to its power of description, generalization and flexibility. In DPI, packet payload is compared against a large number of rules written in regular expression. To achieve high throughput, multiple regular expressions are combined and compiled into one DFA, which leads to two problems: a) State explosion; b) Sub-rule distinguishing in the combined rule set. While the first problem has been extensively studied in the recent years, we did not find any literature which formally discusses the second problem in detail. We formulate it and propose sub-rule distinguishable DFA (SRD-DFA), an extended DFA structure, and develop techniques to distinguish sub-rules from multiple regular expressions upon this structure. SRD-DFA can achieve the same throughput as minimized DFA, since it only incurs little extra memory consumption without extra run-time computation. Experimental results under the L7-filter rule set and a subset of Snort rule set demonstrate that our approach achieves 8 to 14 times higher throughput than the DFA without rule combination, while only introducing less than 8.4% overhead of state increase compared to the minimized DFA after rule combination. SRD-DFA can be easily used with advanced DFA compression algorithms to achieve much less memory consumption.

The publicly available BGP vantage points (VPs) have been heavily used by the research community to build the Internet autonomous system (AS) level topology, which is a key input to many applications, such as routing protocol design, performance evaluation and network security issues. However, a detailed study on the eyeshots of these VPs has received little attention before. In this paper, we inspect these VPs carefully. Specifically, we do a measurement work to evaluate the effect of various factors on the eyeshot of each individual VP as well as the relationship between the eyeshots of different VPs. Based on the measurements, we disclose several counterintuitive observations and explain the possible reasons behind, which will help people to better understand the eyeshots of VPs and make better use of them in practice.

The common objective of network traffic engineering is to minimize the maximal link utilization in a network in order to accommodate more traffic and reduce the chance of congestion. Traditionally this is done by either optimizing OSPF link weights or using MPLS tunnels to direct traffic. However, they both have problems: OSPF weight optimization triggers network-wide convergence and significant traffic shift, while pure MPLS approach requires a full mesh of tunnels to be configured throughout the network. This paper formulates the traffic engineering problem as a Multi-Commodity Flow problem with hybrid MPLS/OSPF routing (MCFTE). As a result, the majority of traffic is routed by regular OSPF, while only a small number of MPLS tunnels are needed to fine-tune the traffic distribution. It keeps OSPF link weights unchanged to avoid triggering network convergence, and needs far fewer MPLS tunnels than the full-mesh to adjust traffic. Compared with existing hybrid routing approaches, MCFTE achieves the optimal link utilization, runs about two orders of magnitude faster, and is more robust against measurement inaccuracy in traffic demand.

New applications such as real-time deep packet inspection require high-speed regular expression (regex) matcher, and the number of regexes in pattern store is increasing to several thousands, which requires a memory efficient solution. In this paper, a kind of hardware based compact DFA structure for multiple regexes matching called CPDFA is presented. According to statistics of regexes in Snort and L7-filter rules, transitions from each state to its next states are not evenly distributed. The summation of transitions from each state to its top three most popular next states takes about 90% of all the transitions. Therefore, CPDFA employs an indirect index table to represent transitions to top three most popular next states more efficiently. The remaining transitions which take about 10% of all the transitions are stored in direct transition table or K parallel SRAMs according to the number of remaining transitions from the same state is more than K or not. Simulation shows that CPDFA structure can save about 90% of memory storage comparing with the original DFA structure. By using pipelined architecture in FPGA, CPDFA can advance one character in one memory access cycle.

As line rates increase, the task of designing high performance architectures with reduced power consumption for the processing of router traffic remains important. In this paper, we present a multi-engine packet classification hardware accelerator, which gives increased performance and reduced power consumption. It follows the basic idea of decision-tree based packet classification algorithms, such as HiCuts and HyperCuts, in which the hyperspace represented by the ruleset is recursively divided into smaller subspaces according to some heuristics. Each classification engine consists of a Trie Traverser which is responsible for finding the leaf node corresponding to the incoming packet, and a Leaf Node Searcher that reports the matching rule in the leaf node. The packet classification engine utilizes the possibility of ultra-wide memory word provided by FPGA block RAM to store the decision tree data structure, in an attempt to reduce the number of memory accesses needed for the classification. Since the clock rate of an individual engine cannot catch up to that of the internal memory, multiple classification engines are used to increase the throughput. The implementations in two different FPGAs show that this architecture can reach a searching speed of 169 million packets per second (mpps) with synthesized ACL, FW and IPC rulesets. Further analysis reveals that compared to state of the art TCAM solutions, a power savings of up to 72% and an increase in throughput of up to 27% can be achieved.

SYN flood attacks still dominate distributed denial of service attacks. It is a great challenge to accurately detect the SYN flood attacks in high speed networks. An intelligent attacker would evade the public detection methods by suitably spoofing the attack to pretend to be benign. Keeping per-flow or per-connection state could eliminate such a spoofing, but meanwhile, it also consumes extremely huge resources. We propose a more accurate and fast SYN flood detection method, named SACK2, which could detect all kinds of SYN flood attacks with limited implementation costs. SACK2exploits the behavior of the SYN/ACK-CliACK pair to identify the victim server and the TCP port being attacked, where a SYN/ACK packet is sent by a server when receiving a connection request and a CliACK packet is the ACK packet sent by the client to complete the three-way handshake. We utilize the space efficient data structure, counting Bloom filter, to recognize the CliACK packet. Comprehensive experiments demonstrate that, SACK2is the fastest and most accurate detection method compared with related methods which also leverage the packet pair's behavior. The memory cost of SACK2for a 10 Gbps link is 364 KB and can be easily accommodated in modern routers.

Network processors have exploited many aspects of architecture design, such as employing multi-core, multi-threading and hardware accelerator, to support both the ever-increasing line rates and the higher complexity of network applications. Micro-architectural techniques like superscalar, deep pipeline and speculative execution provide an excellent method of improving performance without limiting either the scalability or flexibility, provided that the branch penalty is well controlled. However, it is difficult for traditional branch predictor to keep increasing the accuracy by using larger tables, due to the fewer variations in branch patterns of packet processing. To improve the prediction efficiency, we propose a flow-based prediction mechanism which caches the branch histories of packets with similar header fields, since they normally undergo the same execution path. For packets that cannot find a matching entry in the history table, a fallback gshare predictor is used to provide branch direction. Simulation results show that the our scheme achieves an average hit rate in excess of 97.5% on a selected set of network applications and real-life packet traces, with a similar chip area to the existing branch prediction architectures used in modern microprocessors.

This paper develops an efficient and scalable multicast scheme for high-quality multimedia distribution. The traditional IP multicast, a pure network-layer solution, is bandwidth efficient in data delivery but not scalable in managing the multicast tree. The more recent overlay multicast establishes the data-dissemination structure at the application layer; however, it induces redundant traffic at the network layer. We propose an application-oriented multicast (AOM) protocol, which exploits the application-network cross-layer design. With AOM, each packet carries explicit destinations information, instead of an implicit group address, to facilitate the multicast data delivery; each router leverages the unicast IP routing table to determine necessary multicast copies and next-hop interfaces. In our design, all the multicast membership and addressing information traversing the network is encoded with bloom filters for low storage and bandwidth overhead. We theoretically prove that the AOM service model is loop-free and incurs no redundant traffic. The false positive performance of the bloom filter implementation is also analyzed. Moreover, we show that the AOM protocol is a generic design, applicable for both intra-domain and inter-domain scenarios with either symmetric or asymmetric routing.

L7-filter is a significant component in Linux's QoS framework that classifies network traffic based on application layer data. It enables subsequent distribution of network resources in respect to the priority of applications. Considerable research has been reported to deploy multi-core architectures for computationally intensive applications. Unfortunately, the proliferation of multi-core architectures has not helped fast packet processing due to: 1) the lack of efficient parallelism in legacy network programs, and 2) the non-trivial configuration for scalable utilization on multi-core servers.In this paper, we propose a highly scalable parallelized L7-filter system architecture with affinity-based scheduling on a multi-core server. We start with an analytical study of the system architecture based on an offline design. Similar to Receive Side Scaling (RSS) in the NIC, we develop a model to explore the connection level parallelism in L7-filter and propose an affinity-based scheduler to optimize system scalability. Performance results show that our optimized L7-filter has superior scalability over the naive multithreaded version. It improves system performance by about 50% when all the cores are deployed.

Today's routers need to perform packet classification at wire speed in order to provide critical services such as traffic billing, priority routing and blocking unwanted Internet traffic. With everincreasing ruleset size and line speed, the task of implementing wire speed packet classification with reduced power consumption remains difficult. Software approaches are unable to classify packets at wire speed as line rates reach OC-768, while state of the art hardware approaches such as TCAM still consume large amounts of power.

Caching mechanism has achieved great success in general purpose processor; however, its deployment in Network Processor (NP) raises questions over its effectiveness under the new context. In this study, we thoroughly evaluate the performance of caches in NP with architectural features like multicore, multithread, and integrated packet interface. Our major findings include: (1) In general, a sufficiently large cache effectively reduces the number of memory requests and improves the utilization of the NP computation power. (2) The lower efficiency of private caches caused by duplicate information deteriorates the NP performance under certain circumstances. (3) The appropriate cache block size is constrained by the low spatial locality of network applications. (4) For workloads involving large amount of data movement, increasing cache size cannot bring more benefits when the bottleneck in interconnection bus is reached. In short, caching mechanism in NP can be helpful under appropriate usage.

DNS amplification attacks utilize IP address spoofing and large numbers of open recursive DNS servers to perform the bandwidth consumption attack. During an attack, it ceaselessly fabricates DNS queries to the exploited open recursive DNS servers, and all the responses, often with larger size than the query messages, are reflected to the single victim due to the source IP address spoofing. While it is difficult to defend against this attack from the root causes by eliminating the open recursive DNS servers and IP spoofing for the whole Internet, in this paper, we take a different methodology to defend against it at the leaf router of victim's ISP or organization. We propose an efficient and low-cost hardware approach to first detect the DNS amplification attack accurately and responsively. Once the attack is confirmed, our approach is then activated to filter out all the illegitimate DNS responses by using a two-Bloom filter solution. We demonstrate that the memory cost of our approach is feasible for the hardware implementation even up to the OC-768 link. Through trace-driven simulations, it is shown that our approach is effective in both the detecting and filtering phases.

This paper proposes an efficient and scalable multicast scheme based on the concept of application-oriented networking (AON). The traditional IP multicast is bandwidth efficient but suffers from the scalability problem. The overlay multicast, proposed in recent decade, manages a data-dissemination tree at the application layer, and only utilizes unicasts among pairs of hosts; the overlay approach, however, usually incurs a considerable amount of redundant traffic. The essence of AON is to integrate application intelligence into the network. For AON-based multicasting, each packet will carry necessary explicit addressing information, instead of an implicit class-D group address, to facilitate the multicast data delivery. Each AON router will leverage the unicast IP routing table to compute necessary multicast copies and next-hop interfaces. The proposed AON multicast eliminates the need for constructing and maintaining the network-layer multicast routing table, while its bandwidth efficiency is very close to that of the IP multicast.

Efficiency and effectiveness are always the emphases of a scheduler, for both link and processor scheduling. Well-known scheduling algorithms such as surplus round robin (SRR) and elastic round robin (ERR) suffer from two fold shortcomings: 1) additional pre-processing queuing delay and post-processing resequencing delay are incurred due to the lack of short-term load-balancing; 2) bursty scheduling is caused due to blind preservation of scheduling history under non-backlogged traffic. In this paper, we propose a quantum-adaptive scheduling (QAS) algorithm, which: 1) synchronizes all the quanta in a fine-grained manner and, 2) adjusts the quanta intelligently based on processor utilization. We theoretically prove that the queuing fairness bound (QFB) for QAS is one third tighter than SRR and ERR. This result approaches the optimal value as obtained in shortest queue first (SQF) algorithm, while still maintaining O(1) complexity. Trace-driven simulations show that QAS reduces average packet delay by 18%~24% while cutting down the resequencing buffer size by more than 40% compared to SRR and ERR.

New applications such as real-time packet processing require high-speed string matcher, and the number of strings in pattern store is increasing to tens of thousands, which requires a memory efficient solution. In this paper, a pipelined parallel approach for hardware implementation of Aho-Corasick (AC) algorithm for multiple strings matching called P2-AC is presented. P2-AC organizes the transition rules in multiple stages and processes in pipeline manner, which significantly simplifies the DFA state transition graph into a character tree that only contains forwarding edges. In each stage, parallel SRAMs are used to store and access transition rules of DFA in memory. Transition rules can be efficiently stored and accessed in one cycle. The memory cost is less than 47% of the best known AC-based methods. P2-AC supports incremental update and scales well with the increasing number of strings. By employing two-port SRAMs, the throughput of P2-AC is doubled with little control overhead.

Sampling technology has been widely deployed in measurement systems to control memory consumption and processing overhead. However, most of the existing sampling methods suffer from large estimation errors in analyzing small-size flows. To address the problem, we propose a novel adaptive non-linear sampling (ANLS) method for passive measurement. Instead of statically configuring the sampling rate, ANLS dynamically adjusts the sampling rate for a flow depending on the number of packets having been counted. We provide the generic principles guiding the selection of sampling function for sampling rate adjustment. Moreover, we derive the unbiased flow size estimation, the bound of the relative error, and the bound of required counter size for ANLS. The performance of ANLS is thoroughly studied through theoretic analysis and experiments under synthetic/real network data traces, with comparison to several related sampling methods. The results demonstrate that the proposed ANLS can significantly improve the estimation accuracy, particularly for small-size flows, while maintain a memory and processing overhead comparable to existing methods.

Packet classification is an important function in a router's line-card. Although many excellent solutions have been proposed in the past, implementing high speed packet classification reaching up to OC-192 and even OC-768 with reduced cost and low power consumption remains a challenge. In this paper, the HiCut and HyperCut algorithms are modified making them more energy efficient and better suited for hardware acceleration. The hardware accelerator has been tested on large rulesets containing up to 25,000 rules, classifying up to 77 Million packets per second (Mpps) on a Virtex5SX95T TPGA and 226 Mpps using 65 nm ASIC technology. Simulation results show that our hardware accelerator consumes up to 7,773 times less energy compared with the unmodified algorithms running on a StrongARM SA-1100 processor when classifying packets. Simulation results also indicate ASIC implementation of our hardware accelerator can reach OC- 768 throughput with less power consumption than TCAM solutions.

One of the most critical resource management issues in the use of ternary content addressable memory (TCAM) for packet classification/filtering is how to effectively support filtering rules with ranges, known as range matching. In this paper, a Dynamic Range Encoding Scheme (DRES) is proposed to significantly improve TCAM storage efficiency for range matching. Unlike the existing range encoding schemes requiring additional hardware support, DRES uses the TCAM coprocessor itself to assist range encoding. Hence, DRES can be readily programmed in a network processor using a TCAM coprocessor for packet classification. A salient feature of DRES is its ability to allow a subset of ranges to be encoded and hence to have full control over the range code size. This feature allows DRES to exploit the TCAM structure to maximize TCAM storage efficiency. DRES is a comprehensive solution, including a dynamic range selection algorithm, a search key encoding scheme, a range encoding scheme, and a dynamic encoded range update algorithm. While the dynamic range selection algorithm running in software allows optimal selection of ranges to be encoded to maximize the TCAM storage efficiency, the dynamic encoded range update algorithm allows the TCAM database to be updated lock-free without interrupting the TCAM database lookup process. DRES is evaluated based on real-world databases and the results show that DRES can reduce the TCAM storage expansion ratio from 6.20 to 1.23. The performance analysis of DRES based on a probabilistic model demonstrates that DRES significantly improves TCAM storage efficiency for a wide spectrum of range distributions.

Multi-Path Switching systems (MPS) are intensively used in the state-of-the-art core routers. One of the most intractable issues is how to load-balance traffic across its multiple paths while not disturbing the intra-flow packet orders. In this paper, based on the studies of tens of real Internet traces, we develop a novel scheme, namely Flow-Slice (FS), which cuts off each flow into flow-slices at every intra-flow interval larger than a slicing threshold set to 1ms 4ms and balances the load on the finer granularity. Through theoretical analyses and comprehensive trace-driven simulations, we show that FS achieves impressive load-balancing performance with little hardware cost while limiting the packet out-of-order chances to a negligible level (below 10 -6).

Sampling is increasingly utilized by passive measurement systems to save the resources consumption. However, the widely adopted static linear sampling selects packets with the same sampling rate (probability) for both large flows and small flows, which leads to intolerably high relative error for small flows. In order to bound the relative error for both small and large flows, we have proposed an adaptive nonlinear sampling method for passive measurement, which dynamically tunes the sampling rate according to the counter value. We have provided the unbiased estimation of the actual number of events n and have demonstrated that the relative error is radic[(1-1/n)a/2] for both large flows and small flows, where a is a constant parameter, and the counter size is bounded by a logarithmic function, log(1+an)/log(1+a). The theoretical and experimental results have shown that the proposed adaptive sampling method obtain a better tradeoff between relative error and memory consumption than existing sampling methods.

Peer-to-Peer (P2P) systems provide decentralization, self-organization, scalability and failure-resilience, but suffer from high worst-case latencies. Researchers have proposed various replication algorithms to place multiple copies of objects across the network in pursuit of better performance for P2P computing; nevertheless, they neither presented clear analysis nor derived worst-case bound for their algorithms. In this paper, we model the replica placement problem arising in real-world P2P networks as a Clustered K-Center problem which we prove to be NP-complete. Then we propose an efficient approximation algorithm to this problem with a provable upper bound. Extensive experiments have been conducted to demonstrate the effectiveness and efficiency of our algorithm. The experimental results show that our approach can run several orders of magnitude faster than the optimal solution while being able to minimizing the query latency.

Per-flow queuing is believed to be able to guarantee advanced Quality of Service (QoS) for each flow. With the dramatic increase of link speed and number of traffic flows, per-flow queuing faces a great challenge since millions of queues need to be maintained for implementation in a traditional sense. In this paper, by setting only a small number of physical queues, we propose a Dynamic Queue Sharing (DQS) mechanism to achieve an equal performance to the pure per-flow queuing with a lower cost. The proposed mechanism is based on an interesting fact that the number of simultaneous active flows in the router buffer is far less than that of in-progress flows. In DQS, a physical queue is dynamically created on-demand when a new flow comes and then dynamically released when the flow temporarily pauses. Hashing and binary sorting tree (or linked list) are combined to manage the mapping between flows and queues, so as to isolate flows in different queues. Theoretical analysis and traces experiments are conducted to evaluate DQS. The results demonstrate that when the parameters are well set, the operation delay is less than two time cycles in average with an extra memory of 16k bits.

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.

Switch-Memory-Switch (SMS) architecture exhibits an excellent performance due to its emulating the Output Queueing structure. However, in order to achieve the maximal matching, the first stage scheduling operates at a huge computational complexity, which blocks the SMS from practical implementation. In order to put SMS into more effective industrial applications, especially in super-large size switches/routers with multi-services environment, two parallel iterative scheduling algorithms, named IS-RRM and AIS-RRM respectively, are proposed in this paper. The algorithms abolish totally the traditional departure-time-compatible (DTC) graph, and by using iteration-sharing technology, greatly reduce the required iteration number in each time slot. Using a discrete-time Markov chain to model the AIS-RRM algorithm, we obtain its upper bound of cell loss rate. Meanwhile, experimental and theoretical results show that so long as the number of shared memories is twice the switch size, AIS-RRM algorithm can achieve a cell loss rate of 10 when the input buffer size is 15 and the iteration number of each time slot is 6, despite the arrival traffic pattern and the switch size. Furthermore, the iteration number required in each time slot can be further decreased by increasing the input buffer size.

Flow-mapping parallel packet switch (FM-PPS) is the class of parallel packet switch adopting flow-level load-balancing algorithms. It dispatches packets of a micro-flow into an unchanged parallel switch, thus natively guarantees intra-flow packet orders. Due to the heavy tail of flow size distribution, it is concerned that FM-PPS may suffer from unpredictable performance which prevents it from real deployments. Motivated to clarify this issue, in this paper, we present an effective analytical model on FM-PPS and carry out intensive performance analysis. We find that under current Internet traffic patterns, both statistical packet delay and backlog bounds can be guaranteed if only several stability conditions are met. We further validate that a FM-PPS with OC-768c line rate is able to provide such guarantees under state-of-the-art RAM technology. A practical flow-mapping algorithm, namely constrained output round robin (CORR), is also proposed, which is designed to conform to these stability conditions, hence holds the delay and backlog bound.

With the continuous advances in optical communications technology, the link transmission speed of Internet backbone has been increasing rapidly. This in turn demands more powerful IP address lookup engine. In this paper, we propose a power-efficient parallel TCAM-based lookup engine with a distributed logical caching scheme for dynamic load-balancing. In order to distribute the lookup requests among multiple TCAM chips, a smart partitioning approach called pre-order splitting divides the route table into multiple sub-tables for parallel processing. Meanwhile, by virtual of the cache-based load balancing scheme with slow-update mechanism, a speedup factor ofN-1 can be guaranteed for a system with N (N>2) TCAM chips, even with unbalanced bursty lookup requests.

In order to reduce network congestion and fully use link bandwidth, when there are equal-cost-multi-paths (ECMPs) between a forwarding node and a destination subnet, traffic load should be balanced among ECMPs and packets of the same TCP flow should reach destination host in the same order. An algorithm called LRU-based caching with counting (LCC) is proposed. Packet length differentiation is considered to achieve load balance by adapting a counter for each ECMP, and counter overflow is solved by relative counting and restrictions. UDP packets only need to be concerned to achieve load balance. Furthermore, flow delay differentiation forwarding to different hosts of the same destination subnet is transformed to entries in cache invalided time period difference. Simulation shows that when delay differentiation among ECMPs is not significant, storage requirement is small, only one cycle is needed for each cache lookup, load balance is near optimal, and only 2% of packets are out of order

Most conventional IPv4-based route lookup algorithms are no more suitable for IPv6 packet forwarding due to the significantly increased 128-bit-long address. However, as a result of lacking of standard IPv6 route databases, it is hard to make benchmarks for the new generation IPv6-based algorithms developing/evaluation. In this paper, based on the studies of initial IPv6 prefix distributions and the associated RFC documents, we originally develop a scalable IPv6 prefix generator, called V6Gene, for IPv6-based route lookup algorithms benchmarking. According to the RFCs and other associated standards, V6Gene generates IPv6 route prefixes from the initially assigned LIR (local Internet registries) prefixes collected from the real world, simulating the process of future IPv6 address block allocation from the LIRs to their subscribers. V6Gene is totally flexible for generation of all kinds of route databases with different characteristics. It is simple for implementation and can be easily integrated within other IPv6 benchmark tools/systems.

Flow-level traffic measurement is important for network management. The widely used centralized per-flow measurement faces a great challenge due to the demanding requirement on both memory bandwidth and memory size within a single traffic monitor. This paper addresses the issue of deploying a Distributed Passive Measurement System (DPMS) in a large scale network; specifically, we study how to optimally place traffic monitors and sample stochastic traffic flows, so that the probability of a packet being sampled (a.k.a. measurement coverage) is maximized. We formulate this problem as a Stochastic Chance Constrained Optimization (SCCO) problem; and we propose a Hybrid Intelligent (HI) algorithm to solve this problem. The HI algorithm consists of two major components, namely, uncertain function approximation and genetic algorithm. Equipped with the HI algorithm, we are able to address the optimal tradeoff between measurement coverage and deployment cost for networks with random traffic, which has not been studied before. Our simulations and experiments demonstrate the effectiveness of our algorithm, i.e., a small deployment cost or a small number of monitors are sufficient to maintain a high level of measurement coverage.

Caching, multithreading and the combination of them are the major latency hiding techniques adopted in network processors (NPs). Although they achieve great success in general purpose processors (GPPs), none of them have been well studied under the new context of packet processing. In this paper, we simulate the processing procedure of a four-PE (processing element) network processor and thoroughly evaluate different configurations of these techniques with real-life packet traces. Our major findings include: (1) In general, all of these latency hiding techniques effectively increase the traffic throughput and robustness of NP; but thread allocation policy has great impact on their performance. (2) If assigning packets of the same flow to different threads is allowed, multithreading keeps the PE in a working state as long as possible and less jitter in packet sending rate is resulted than caching schemes; otherwise, a cache with a reasonable size outperforms multithreading in almost all metrics such as traffic throughput, packet loss rate, queuing and total delay. (3) When access latency is comparable to the working time of execution unit, the performance of multithreading is more sensitive to packet arrival process and memory reference pattern than caching. In short, caching and multithreading have their respective advantages under different environment. In some cases, combined caching and multithreading tend to bring more performance gain than simply adding more threads or cache entries.

Parallel Packet Switch (PPS) is used intensively in today's terabit router to construct the switching fabric. Basic PPS equally deals with all of the traffic in order to achieve uniform load-balancing and high throughput, but it fails to support differentiated QoS. With the recent blooming of delay- sensitive Internet traffic, such as the peer-to-peer live streaming and IPTV, differentiated QoS is becoming an urgent demand. In this paper, we propose a novel and practical framework, the Differentiated Service Parallel Packet Switch (DS-PPS), which supports three fundamental QoS features: guaranteed-delay (GD), guaranteed-bandwidth (GB) and best-effort (BE). By adaptively adjusting the number of switching planes offered to each QoS class, DS-PPS precisely controls the delay bounds of GD traffic and the drop precedence of GB traffic. We evaluate DS-PPS by extensive theoretical analyses and comprehensive simulations. Experimental results on a prototype implementation of the framework show that DS-PPS outperforms the basic PPS in three main aspects. First, the average delay of TCP short packet under full load is reduced by more than 94%. Second, the average delay of real-time traffic under full load is reduced by more than 82%. And third, the GB traffic of low drop precedence is guaranteed of nearly three times the throughput of high drop precedence at the hotspots. Significantly, our proposed DS-PPS framework is universal and scalable to support various kinds of emerging QoS-sensitive applications in multi-service terabit routers without any extra overhead.

Packet Classification serves as a plinth for many newly emerging network applications. Most of the previous packet classification schemes are IPv4-oriented, and some of them have achieved high throughput with chip-level parallelism of Ternary Content Addressable Memories (TCAM). However, due to their inefficient utilization of TCAM resources, further upgrade incurs prohibitive hardware costs. As IPv6 will dominate the Next Generation Internet, IPv6-oriented packet classification is of increasing importance. In this paper, we propose a packet classification scheme geared towards IPv6. This scheme incorporates efficient and flexible algorithms for parallelism and distributed storing, which provides an unprecedentedly high throughput with relatively low storage costs. Our scheme also integrates delicate parallel encoding algorithms to maximize the TCAM utilization and increase its throughput. Using commercially available TCAM, the scheme is able to classify 266 million IPv6 packets per second (Mpps), matching 4×OC-768 (160 Gbps) line rate. Key words—Packet Classification, Encoding, IPv6, TCAM

The ability to inspect both packet headers and payloads to identify attack signatures makes network intrusion detection system (NIDS) a promising approach to protect Internet systems. Since most of the known attacks can be represented with strings or combinations of multiple substrings, string matching is a key component, as well as the bottleneck in NIDS to address the requirement of constantly increasing capacity. We propose a memory-efficient multiple-character-approaching architecture consisting of multiple parallel deterministic finite automata (DFAs), called TDP-DFA. By employing efficient representations for the transition rules in each DFA, TDP-DFA significantly reduces the complexity. We also present a novel scheme to share the storage of transition rules among multiple DFAs, substantially decreasing the total storage cost, and avoiding the cost increase being proportional to the number of DFAs. We evaluate this design through theoretical analysis and comprehensive experiments. Results show that TDP-DFA is able to meet the critical requirement of OC-768 wirespeed processing, as well as constituting a promising way for scaling up to cope with throughput over 100 Gb/s in the future.

Packet classification has been a critical data path function for many emerging networking applications. An interesting approach is the use of ternary content addressable memory (TCAM) to achieve deterministic, high-speed packet classification performance. However, apart from high cost and power consumption, due to slow growing clock rate for memory technology, in general, the traditional single TCAM-based solution has difficulty to keep up with fast growing line rates. Moreover, the TCAM storage efficiency is largely affected by the need to support rules with ranges or range matching. In this paper, a distributed TCAM scheme that exploits chip-level-parallelism is proposed to greatly improve the throughput performance. This scheme seamlessly integrates with a range encoding scheme which not only solves the range matching problem, but also ensures a balanced high throughput performance. A thorough theoretical worst-case analysis of throughput, processing delay, and power consumption, as well as the experimental results show that the proposed solution can achieve scalable throughput performance matching up to OC768 line rate or higher. The added TCAM storage overhead is found to be reasonably small for the five real-world classifiers studied.

For a combined input and output queued (CIOQ) switch, maximal matching (MM) algorithm with a speedup of 2 has been known to deliver 100% throughput under any admissible traffic, where in each time slot, two independent schedulings and two cell transferrings are made respectively. This paper proposes a new kind of extended maximal matching (EMM) algorithm, which just utilizes a little information of VOQ length. We show that the implementation complexity of CIOQ switches is reduced by using the EMM(2) algorithm, where only one scheduling and two cell transferrings (data speedup of 2) are necessary in each time slot to achieve 100% throughput when input traffic is admissible. The EMM(2) algorithm can be easily realized by modifying the existing MM algorithms. In this paper, we provide a practical instance of EMM(2) algorithm, named EiSLIP(1,2), based on the well-known iSLIP algorithm. Simulations show that EiSLIP(1,2) algorithm with a data speedup of 2 achieves almost the same delay performance as output queued policy under uniform and non-uniform traffic with Bernoulli arrival, as well as the bursty traffic.

Although output queued (OQ) switches are prominent for their high performance, they are not easy to implement due to the high speedup requirement. Using a special scheduling algorithm in the first stage switch, a more scalable switch-memory-switch (SMS) architecture can emulate an OQ switch, where cells must be transferred from the inputs to the shared memories per time slot without arrival and departure conflicts. Although scheduling algorithm achieves good performance, the time complexity for constructing the bipartite graph is too high to be used in practice. In this paper, we propose a new iterative random round-Robin matching (iRRM) algorithm together with its constrained version CiRRM, where no bipartite graph is required to be constructed in advance to solve the departure conflict, and thus high computation overhead is avoided. In our algorithms, both the arrival and the departure conflicts are melted in the iterations. Each iterations consist of two steps: request step and grant step, where randomness and more easily implemented round-robin principle are used respectively. Through theoretical analysis, we obtain that with M=2/spl phi/(N-1) shared memories, where N is the port number and /spl phi/ is a constant larger than (2N-1)/(2N-2), iRRM/CiRRM can complete a matching within O(logM) iterations with high probability in M and the time complexity of CiRRM is only O(log/sup 2/M/loglogM), which is much lower than prior algorithms.

Packet classification (PC) has been a critical data path function for many emerging networking applications. An interesting approach is the use of TCAM to achieve deterministic, high speed PC However, apart from high cost and power consumption, due to slow growing clock rate for memory technology in general, PC based on the traditional single TCAM solution has difficulty to keep up with fast growing line rates. Moreover, the TCAM storage efficiency is largely affected by the need to support rules with ranges, or range matching. In this paper, a distributed TCAM scheme that exploits chip-level-parallelism is proposed to greatly improve the PC throughput. This scheme seamlessly integrates with a range encoding scheme, which not only solves the range matching problem but also ensures a balanced high throughput performance. Using commercially available TCAM chips, the proposed scheme achieves PC performance of more than 100 million packets per second (Mpps), matching OC768 (40 Gbps) line rate.

Prior survey of RED algorithm deployment on multiqueue system with shared buffer was unfair and sensitive to congestion level by statically setting the parameters. In this paper, our goal is to deploy the Random Early Detection (RED) algorithm in routers on shared buffer and solve these problems. A novel buffer management scheme that dynamically adjusts the parameters of RED named RED-ODT is proposed. Simulations under uniform traffic load and nonuniform traffic load are given, the results of which ascertain and demonstrate the superiority of the proposed scheme in terms of low packet drop ratio, satisfying buffer utilization and fairness. Simulation also shows that RED-ODT is insensitive to congestion level.

One of the key design issues for network processors (NPs) is hiding long latency of random off-chip memory accesses. We present a novel memory subsystem especially for access and edge routers to implement feature-rich network applications with wire-speed processing guarantees. Because of the hierarchical organizations specially designed for network circumstances, access latency of DRAM is totally hidden and the number of off-chip memory accesses can also be reduced. We implement this architecture based on a simplified OpenRISC processor core in an Altera Stratix EP1S20B672 FPGA. Time analysis shows that this memory subsystem achieves an operating frequency of over 200MHz, with approximately 2% LEs and 1% memory resources.

Ternary content-addressable memory (TCAM) is widely used in high-speed route lookup engines. However, restricted by the memory access speed, the route lookup engines for next-generation terabit routers demand exploiting parallelism among multiple TCAMs. Traditional parallel methods always incur excessive redundancy and high power consumption. We propose An original TCAM-based IP lookup scheme that achieves an ultra high lookup throughput and a high utilization of the memory while being power efficient. In our multichip scheme, we devise a load-balanced TCAM table construction algorithm together with an adaptive load balancing mechanism. The power efficiency is well controlled by decreasing the number of TCAM entries triggered in each lookup operation. Using 133 MHz TCAM chips and given 25% more TCAM entries than the original route table, the proposed scheme achieves a lookup throughput of up to 533 Mpps and is simple for ASIC implementation.

Many researchers have pointed out that using complex scheduling algorithms in input queuing switches with VOQ (Virtual Output Queuing) can achieve 100% throughput. But these algorithms are too complex to be implemented in hardware. In this paper, based on combined input/output queuing (CIOQ) switch fabrics, we propose a simple scheduling algorithm named OPRR (Outlet Priority Round Robin). For the synthetic workloads we consider, including uniform and bursty traffic models, the performance of OPRR in VOQ and single queue mode is evaluated respectively. Through the simulation results we show that 1) OPRR algorithm, coupled with a speedup of 2, can lead to performance very close to output queuing switches, and 2) under the same condition the single queue mode behaves almost identically to VOQ mode. These results are very useful to direct the design and implementation of switch fabrics in core routers.