Most existing outlier detection methods rely on a single and fine-grained data representation, making them vulnerable to noise and inefficient in capturing local anomalies. Granular-ball computing (GBC), as an emerging multi-granularity representation and computation framework, provides an effective means to address these issues. Meanwhile, shadow set theory offers a flexible mechanism using three-way decision to handle uncertainty and boundary fuzziness in data. The integration of GBC with shadow set theory combines the strengths of both frameworks, offering promising potential for outlier detection tasks. In this study, we propose a novel outlier detection based on shadowed granular-balls. Firstly, we propose an unsupervised granular-ball generation method with the principle of justifiable granularity. Then, we further present an outlier detection method, named three-way outlier detection based on shadowed granular-ball (3W-SGBD). 3W-SGBD introduces an unsupervised granular-ball generation strategy guided by local density clustering, and adaptively splits granular-balls through a dual-entropy-driven mechanism to better capture local anomalies. In addition, by partitioning each granular-ball into positive, negative, and boundary regions via shadow mapping, 3W-SGBD refines boundary areas to enhance detection accuracy. Finally, extensive comparative experiments are conducted with several state-of-the-art baseline methods on 16 public benchmark datasets. The results show that the effectiveness, efficiency, and robustness of the method proposed in this paper. The code is publicly available athttps://github.com/2257352568/3W-SGBD.

Although spectral clustering is capable of identifying clusters of arbitrary shapes, its high time and space complexity poses limitations in large-scale data clustering applications. To tackle this problem, researchers have proposed using anchor points to construct the similarity matrix, thereby reducing time and space complexity. However, current methods for generating anchor points do not fit the data well and are limited in approach. To improve upon existing anchor points generation methods, we proposes a pseudo-label-based anchor points generation approach and develops a fast spectral clustering algorithm for large-scale data, named FSC-PLGB. The algorithm first randomly selects r points as an initial granular-ball, applies K-Means on these points to obtain pseudo-labels, calculates the pseudo-purity of the granular-ball based on these pseudo labels, and then performs granular-ball division based on these pseudo-purity to generate anchor points. A similarity matrix is constructed between all sample points and anchor points, and finally, spectral clustering is applied to obtain the clustering results. The experimental results demonstrate that our proposed algorithm exhibits exceptional efficiency and significant superiority on large-scale datasets. The source code is available at https://github.com/DongdongCheng/FSC-PLGB.

Synchronization-induced congestion is a critical performance bottleneck in modern distributed machine learning (ML) training, where simultaneous gradient exchanges create bursty traffic patterns. Existing solutions, both reactive and proactive, struggle to balance throughput and latency in the presence of synchronized flows. We propose DeSync, a proactive traffic shaping scheme that introduces structured random delay to de-synchronize communication rounds. Evaluations with DCQCN, HPCC, DCTCP, and TIMELY demonstrate that DeSync significantly improves FCT, job completion times, and congestion metrics, enhancing existing CC mechanisms without specialized hardware.

Communication overhead is a major bottleneck in distributed AI training, particularly in multi-tenant environments, limiting GPU utilization. Existing job-level scheduling methods fail to address the varying urgency of individual communication operations. We propose Flux, a novel fine-grained scheduler that prioritizes communication operations based on their Urgency Score and job intensity. Our evaluation shows Flux improves GPU utilization by up to 10 % compared to state-of-the-art job-level algorithms. This demonstrates the significant advantage of fine-grained communication scheduling in multitenant AI clusters.

While Multi-CQF enables deterministic networking over wide-area networks(WANs) by decoupling transmission and reception, it introduces significant queuing delays. We propose Effective Phase Alignment (EPA), which mitigates queuing delay by adjusting transmission offsets to align the effective phase, defined as the phase difference between the sending and receiving windows. EPA lowers the upper bound of average queuing delay from 2T to 1.5T, and achieves T under perfect alignment.

Integrating Frame Replication and Elimination for Reliability (FRER) with Cyclic Queuing and Forwarding (CQF) in Time-Sensitive Networks (TSN) encounters redundancy failures and resource reservation inefficiencies due to length disparities across redundant paths. To address these challenges, we propose ReCQF, a Reliability-Enhanced CQF scheduling framework built on Multi-Instance CQF. ReCQF adaptively assigns redundant flows to multiple CQF queue pairs with specific cycles, effectively aligning transmission delays across redundant paths to ensure low delay and inter-path delay differences while significantly reducing resource reservations.

Despite Federated Learning (FL) employing gradient aggregation at the server for distributed training to prevent the privacy leakage of raw data, private information can still be divulged through the analysis of uploaded gradients from clients. Substantial efforts have been made to integrate local differential privacy (LDP) into the system to achieve a strict privacy guarantee. However, existing methods fail to take practical issues into account by merely perturbing each sample with the same mechanism while each client may have their own privacy preferences on privacy-sensitive information (PSI), which is not uniformly distributed across the raw data. In such a case, excessive privacy protection from private-insensitive information can additionally introduce unnecessary noise, which may degrade the model performance. In this work, we study the PSI within data and develop FedRE, that can simultaneously achieve robustness and effectiveness benefits with LDP protection. More specifically, we first define PSI with regard to the privacy preferences of each client. Then, we optimize the LDP by allocating less privacy budget to gradients with higher PSI in a layer-wise manner, thus providing a stricter privacy guarantee for PSI. Furthermore, to mitigate the performance degradation caused by LDP, we design a parameter aggregation mechanism based on the distribution of the perturbed information. We conducted experiments with text tamper detection on T-SROIE and DocTamper datasets, and FedRE achieves competitive performance compared to state-of-the-art methods.

The current Federated Recommendation System (FedRS) focuses on personalized recommendation services and assumes clients are personalized IoT devices (e.g., Mobile phones). In this paper, we deeply dive into new but practical FedRS applications within the joint venture ecosystem. Subsidiaries engage as participants with their users and items. However, in such a situation, merely exchanging item embedding is insufficient, as user bases always exhibit both overlaps and exclusive segments, demonstrating the complexity of user information. Meanwhile, directly uploading user information is a violation of privacy and unacceptable. To tackle the above challenges, we propose an efficient and privacy-enhanced federated recommendation for the joint venture ecosystem (FR-JVE) that each client transfers more common knowledge from other clients with a distilled user's \textit{rating preference} from the local dataset. More specifically, we first transform the local data into a new format and apply model inversion techniques to distill the rating preference with frozen user gradients before the federated training. Then, a bridge function is employed on each client side to align the local rating preference and aggregated global preference in a privacy-friendly manner. Finally, each client matches similar users to make a better prediction for overlapped users. From a theoretical perspective, we analyze how effectively FR-JVE can guarantee user privacy. Empirically, we show that FR-JVE achieves superior performance compared to state-of-the-art methods.

Multimodal federated learning (MMFL) has gained increasing popularity due to its ability to leverage the correlation between various modalities, meanwhile preserving data privacy for different clients. However, recent studies show that correlation between modalities increase the vulnerability of federated learning against Gradient Inversion Attack (GIA). The complicated situation of MMFL privacy preserving can be summarized as follows: 1) different modality transmits different amounts of information, thus requires various protection strength; 2) correlation between modalities should be taken into account. This paper introduces an information theory perspective to analyze the leaked privacy in process of MMFL, and tries to propose a more reasonable protection method \textbf{Sec-MMFL} based on assessing different information leakage possibilities of each modality by conditional mutual information and adjust the corresponding protection strength. Moreover, we use mutual information to reduce the cross-modality information leakage in MMFL. Experiments have proven that our method can bring more balanced and comprehensive protection at an acceptable cost.

This paper presents ZooRoute, a tenant-transparent, fast failure recovery service that requires no modifications to physical devices. ZooRoute leverages the overlay layer and enables traffic flows to bypass failures by altering source ports (srcPorts) in packet headers during encapsulation. To enable deployment in large-scale cloud networks, ZooRoute proposes: 1) On-demand probing to efficiently monitor a vast number of hosts while minimizing telemetry costs. 2) Table compression to record the states of numerous paths with limited on-chip resources. 3) A device-sensing mechanism to prevent unnecessary reconnections in stateful forwarding. Deployed in Alibaba Cloud for 18 months, ZooRoute has significantly improved network reliability, reducing cumulative outage time by 92.71%.

Cloud service providers increasingly adopt SmartNICs to offload data-plane services (e.g., DPDK and SPDK) and control-plane tasks (such as disk and NIC initialization). Our analysis of production environments reveals that data-plane services statically provision CPUs for peak load, resulting in 67.5% idle CPU cycles during 99% of their runtime in IaaS clouds, leading to wasted CPU resources. On the other hand, control-plane tasks fail to meet critical Service Level Objectives (SLOs), such as virtual machine startup time. Unfortunately, achieving control-plane SLO improvements through co-scheduling with idle data-plane services remains highly challenging, due to the combined effects of intrinsic scheduling latency and the substantial architectural complexity inherent to control-plane ecosystems.

Federated Recommendation System (FRS) usually offers recommendation services for users while keeping their data locally to ensure privacy. Currently, most FRS literature assumes that fixed users participate in federated training with personal IoT devices (e.g., mobile phones and PC). However, users may join incrementally, and retraining the entire FRS for each new participating user is unfeasible due to the high training costs and the limited global knowledge contribution from a small number of new users. To guarantee the quality service for these new users, we take a dive into the federated recommendation for cold-start users, a novel scenario where the new participating users can directly obtain a promising recommendation without comprehensive training with all participating users by leveraging both transferred knowledge from the converged warm clients and the knowledge learned from the local data.

Time-sensitive networking (TSN), essential in industrial networks for its promise of reliable and deterministic data transmission, faces deployment challenges due to the limitations of existing time-aware shaper (TAS)-based scheduling algorithms. Specifically, the size of the generated gate control lists (GCLs) is usually too large to be deployed in actual devices. To bridge the gap between theory and practice, we propose FlexTAS, a flexible and practical solution for TSN. The key insight behind FlexTAS is that relaxing gating does not introduce uncertainty, as long as nonoverlap reserved time slots are guaranteed. FlexTAS is comprised of two main components: first, a novel gating model deviates from the conventional TAS model by incorporating selective relaxation of gating at certain nodes; and second, a deep reinforcement learning-based engine to rapidly generate valid schedules. We build a real testbed and validate the effectiveness of our proposed solution. Our evaluation demonstrates that FlexTAS effectively controls the number of gate entries within the GCL capacity of devices, while simultaneously meeting the Quality of Service(QoS) requirements of time-triggered streams. It significantly reduces the number of GCL entries by 60% to 80%, and facilitates deployment in heterogeneous networks, thus offering a practical solution for TSN.

Network performance monitoring and troubleshooting are crucial yet challenging tasks in datacenter management. Despite the numerous solutions that have been proposed in recent years, their efforts are often hindered by high costs and unreliable failure localization, making it difficult to deploy them in real-world environments. In this paper, we presentLMon, a highly reliable and efficient system for monitoring and troubleshooting in datacenter networks. LMon utilizes the characteristic of ECMP hashing linearity to control probe packet routing, enabling the monitoring of targeted paths without any modification of underlying protocols and devices. Additionally, LMon leverages a lightweight probing technique to reduce monitoring overhead, as well as integrates the improved LASSO regression and hypothesis testing for higher accuracy and faster processing in link failure localization. We evaluate the performance of LMon in our testing environment. Compared to the monitoring system Pingmesh, LMon generates only one-third probes while maintaining 99% accuracy and 1% false negatives.

The virtual switch (vSwitch) serves as a fundamental element in cloud network, critical for high-performance and strongly isolated inter-VM forwarding in local and external networks. Similar to other multicore systems, a vSwitch with multiple cores also faces the issue of core load imbalance. As a major cloud provider, we pinpoint four cases of core load imbalance within the vSwitch in our cloud, stemming from unequal traffic distribution across virtual queues and RSS buckets, as well as from traffic patterns like heavy hitters and micro-bursts. To tackle the different load imbalance cases, we present vSwitchLB, a vSwitch load balance framework. Specifically, we introduce a load imbalance detection module, accompanied by dedicated techniques designed to address each specific type of imbalance. Our preliminary evaluation shows that vSwitchLB can accurately classify different load imbalances encountered in the vSwitch on our cloud and then prevent any single core of vSwitch from being flooded and overwhelmed.

Benefiting from high flexibility and probability of line-of-sight, deploying unmanned aerial vehicles (UAV s) as aerial access points has emerged as a promising solution for ensuring reliable wireless connectivity in crowded events. This paper introduces a UAV scheduling process adaptive to dynamic mobile network demand, including three phases. In the sensing phase, the user distribution is sensed, and user number thresholds are set to determine whether UAV assistance is needed. The planning phase presents an enhanced mean shift algorithm to find suitable locations to deploy UAVs with a dynamic bandwidth derived from the user distribution, the UAV's maximum capacity, and the UAV's maximum throughput. The deploying phase dispatches and recalls UAV s based on planning results. Comprehensive simulation experiments are conducted on OMNeT ++ using real-world data. Results show that the proposed process shows great adaptivity, with an efficiency increase of 18.7% and a fairness increase of 28.9 % compared to the existing related works on average.

The geographically distributed edge servers can naturally draw power from nearby renewable energy (RE) generators. Complemented by the dynamic scheduling of energy storage batteries, edge service providers (ESPs) can thus build low- or even zero-carbon edge computing systems. Nevertheless, the distributed and heterogeneous nature of edge computing systems, as well as the limited information sharing among ESPs, leads to a more complex battery planning problem than that in cloud computing. The unpredictability of RE resources further complicates the problem, making conventional model-based approaches ineffective. To this end, we propose a multi-agent deep reinforcement learning (MADRL) approach for the independent decision making of individual ESPs. Particularly, MADRL takes privacy into account by ensuring that no sensitive information is disclosed among ESPs. For better model training, we further customize the invalid action masking and develop action transformation techniques based on segmented linear optimization. Extensive experiments demonstrate that, with our proposed approach, the overall carbon emission of edge computing systems can be significantly reduced (by over 60%) while maintaining acceptable operation costs in battery scheduling.

For cyber-physical systems, the predictability of their physical behaviors needs to be ensured by the determinism of cyberspace. Response-time analysis (RTA) can theoretically provide this determinism by analyzing the temporal properties of demands. However, the state-space explosion problem makes it challenging to do exact and sustainable RTA for non-preemptive systems where both release jitter and execution time variation exist, particularly when the system has event-triggered (ET) jobs. To address this issue, we propose an ET-enabled RTA based on the schedule-abstraction graph and preliminarily verify its effectiveness and scalability.

Industrial networks require deterministic and reliable communication, which can be achieved by Time-Sensitive Networking (TSN), a set of standards that enable precise timing and synchronization of data transmission. However, TSN is susceptible to unexpected delays caused by device malfunction, interference or cyber attacks, which can have a domino effect and disrupt multiple data flows. To address this challenge, we propose RobustTSN, a framework that protects TSN against the domino effect of delayed frames and tolerates harmless accident frames using Per-Stream Filtering and Policing (PSFP) mechanism. We develop algorithms to calculate ingress filtering schedules based on local-safe delay and global-safe interval concepts, which decide whether to accept or discard out-of-schedule frames. We use a finite state machine to model the interaction between frames and evaluate frame safety. We build a software-defined networking based system to dynamically monitor network states and reconfigure device filtering after out-of-schedule transmission occurs. We conduct experiments on practical scenario topologies and large groups of random flows to demonstrate the effectiveness and efficiency of our framework.

App stores allow developers to globally distribute their apps to gain more users and attention. In the highly competitive market of app stores, developers need to cater to a large number of users spanning multiple countries. We posit that the characteristics of diverse geographical, linguistic, cultural, societal, and economic environments may impact the adoption of apps. In this paper, we take the first step to characterize popular apps across over 150 countries worldwide, and explore the potential correlations to a number of underlying factors including geography, language as well as cultural, societal, and economic dimensions. Our study is based on a longitudinal (one-year) dataset of daily app popularity from the iOS app stores, covering 154 regions around the world. We reveal that app popularity shows great diversity across the world, while similarities exist among countries that share geographical proximity and linguistic convergence. The differences in app popularity across regions can be further correlated with the cultural model and socioeconomic indices we adopt. On top of the dataset and findings, we implement a prediction task that contributes to app distribution, helping developers choose the right market to distribute and promote their apps. To the best of our knowledge, we are the first to attempt to provide a global understanding of the characteristics of app popularity across the mobile app ecosystem. Our observations can benefit stakeholders in the ecosystem, striving to improve app uptake.

Internet traffic bursts usually happen within a second, thus conventional burst mitigation methods ignore the potential of Traffic Engineering (TE). However, our experiments indicate that a TE system, with a sub-second control loop latency, can effectively alleviate burst-induced congestion. TE-based methods can leverage network-wide tunnel-level information to make globally informed decisions (e.g., balancing traffic bursts among multiple paths). Our insight in reducing control loop latency is to let each router make local TE decisions, but this introduces the key challenge of minimizing performance loss compared to centralized TE systems.

Apsara vSwitch (AVS) is a per-host deployed forwarding component for instance network connectivity in the Alibaba Cloud. To meet the growing performance demands, we accelerated AVS by adopting the most widely used "Sep-path" offloading architecture, which introduces a separate hardware data path to speed up popular traffic. However, the deployment results prove that it is difficult to bridge the gap in performance and programming flexibility of the software and hardware data paths, resulting in unpredictable performance and low iteration velocity.

In the domain of Time-Sensitive Networking (TSN), the quest for ultra-reliable low-latency communication is paramount. Current scheduling strategies, which hinge on strict isolation to ensure low latency and jitter, confront the challenges of high overhead in worst-case latency evaluation and consequent limitations in network flow capacity. This paper introduces an innovative framework that transcends traditional isolation constraints, thereby expanding the solution space and augmenting network schedulability. At the heart of this framework lies a novel latency jitter analysis method that assesses the viability of non-isolation scenarios with constant time complexity. This method underpins a heuristic scheduling algorithm that not only boasts the smallest time complexity among existing heuristics but also significantly increases the number of scheduled flows. Complementing this, we integrate a discrete time reference approach to hasten time-intensive scheduling operations, achieving an optimal balance between schedulability and runtime efficiency. The framework further incorporates a workload-shifting technique to enhance online scheduling responsiveness. It adeptly manages the variability in scheduling times caused by disharmonious flow periods, further bolstering the framework’s robustness. Experimental validations demonstrate that our framework can increase the scheduled flows up to 269%. It reduces scheduling runtime by up to 98.44% for medium-scale networks while maintaining a flat runtime growth curve, ensuring predictable performance in online scheduling scenarios.

Time Sensitive Networks (TSN), as an important representative of deterministic networks, provide low-latency and highly reliable communication services for the growing network applications that have strict requirements. Cyclic Queuing and Forwarding (CQF) is a well-known mechanism proposed by IEEE 802.1Qch for low-latency flow control of time-sensitive networks. It achieves bounded end-to-end delay and jitter transmission through a set of queues without complicated queue gating. However, most of the current work overlooks the widespread existence of multi-link rate networks in LANs and WANs, and the single-cycle CQF is unable to adjust different link rates, resulting in low bandwidth utilization and high latency. In this paper, we propose a novel scheduling approach named Multi-Cycle CQF (MCCQF) to solve the transmission problem in multi-link rate networks, aiming to reduce deterministic end-to-end delay and improve link bandwidth utilization. In addition, we formulate the scheduling constraints, being of guiding significance for designing the transmission of multi-link-rate networks, and we design an online scheduling algorithm based on it. We compare the proposed scheme with the single-cycle CQF online scheduling algorithm in hierarchical multi-link-rate networking scenarios, and the evaluation shows that our algorithm achieves better end-to-end ultra-low latency (38.9% reduction) with a smaller schedulability gap compared with single-cycle CQF. And we also improved the scheduleability based on MCCQF by utilizing internal offset.

The booming edge computing market that is supported by the edge cloud (EC) infrastructure has brought huge operating costs, mainly the energy cost, to edge service providers. The energy cost in form of electricity bills usually consists of energy charge and demand charge, and the demand charge based on peak power may account for a large proportion of the energy cost given a significant fluctuating power curve. In this work, we investigate the backup battery characteristics and electricity charge tariffs at ECs and explore the corresponding cost-saving potential. Specifically, we transform the backup battery group into distributed battery energy storage system (BESS) and strategically schedule the BESS to minimize the energy cost of service providers. We then propose a deep reinforcement learning (DRL) based approach to BESS charging/discharging in coping with the dynamic power demand and BESS state at each EC. To enable better decision-making and speed up agent training, we further design the customized invalid action masking (IAM) method and apply the prioritized experience replay (PER) scheme. The experiment results based on real-world EC power traces show that the proposed approach can reduce the demand charge and overall electricity bill by up to 27% and 13%, respectively.

5G and Industrial Internet are bringing a variety of applications with on-time and reliable demands. Cyclic queuing and forwarding (CQF), a well-known mechanism defined by IEEE 802.1 Qch in Time Sensitive Network (TSN), achieves deterministic end-to-end latency and jitter without complex gating calculations. However, most of the current work ignores the prevalence of hybrid networks with different link rates, resulting in low bandwidth utilization and high latency for single-cycle CQF. In this paper, we propose a multi-cycle CQF to address the transmission in multi-link-rate networking, reducing deterministic end-to-end latency and improving link bandwidth utilization. In addition, we formulate the scheduling constraints, being of guiding significance for designing the transmission of multi-link-rate networks, and we design an online scheduling algorithm based on it. We compare the proposed scheme with the single-cycle CQF online scheduling algorithm in hierarchical multi-link-rate networking scenarios, and the evaluation shows that our algorithm achieves better end-to-end ultra-low latency (38.9% reduction) with a smaller schedulability gap compared with single-cycle CQF.

Millions of apps in markets have made it difficult for mobile users to find fancy and high quality apps. Mobile app markets have deployed mechanisms to recommend apps to users. Apple usually features apps in the iOS App Store, and mobile users could see the featured apps as soon as they open the App Store. In general, getting apps featured is an achievement all developers strive towards and it is a common belief that getting app featured means that the app is becoming popular. However, the official app recommendation mechanism has not been characterized yet. To fill the void, we present a large-scale and longitudinal study of featured apps on iOS App Store. Specifically, we collaborate with our industry partner to monitor the iOS App Store and collect the daily featured apps in both the US and China, covering a span of over 1.5 years. Based on this comprehensive dataset, we characterize the featured apps from various dimensions and investigate the impact of app recommendation on app popularity. We have revealed a number of observations that are unknown to the community. Most importantly, we observe that although getting featured indeed has a positive effect for most apps, the duration of this effect is short-lived. In addition, there are times when the recommendations are ineffective, and we propose some potential reasons and tips for this. Our study can offer practical implications on app promotion to stakeholders in the mobile app ecosystem.

Ternary Content Addressable Memory (TCAM) is an essential hardware component in SDN-enabled switches, which supports fast lookup speed and flexible matching patterns. However, TCAM’s limited storage capacity has long been a scalability challenge to enforce fine-grained forwarding policies in SDN. Based on the observation of traffic locality, the rule-caching mechanism employs a combination of TCAM and Random Access Memory (RAM) to maintain the forwarding rules of large and small flows, respectively. However, previous works cannot identify large flows timely and accurately, and suffer from high computational complexity when addressing rule dependencies in TCAM. Worse still, TCAM only caches the forwarding rules of large flows but ignores the latency requirements of small flows. Small flows encounter cache-miss in TCAM and then will be diverted to RAM, where they have to experience slow lookup processes. To jointly optimize the performance of both high-throughput large flows and latency-sensitive small flows, we propose a hybrid rule-caching framework, H-Cache, to scale traffic-aware forwarding policies in SDN. H-Cache identifies large flows through a collaboration of learning-based and threshold-based methods to achieve early detection and high accuracy, and proposes a time-efficient greedy heuristic to address rule dependencies. For small flows, H-Cache establishes default paths in TCAM to speed up their lookup processes, and also reduces their TCAM occupancy through label switching and region partitioning. Experiments with both real-world and synthetic datasets demonstrate that H-Cache increases TCAM utilization by an average of 11% and reduces the average completion time of small flows by almost 70%.

Network performance monitoring and troubleshooting is a crucial but challenging task in datacenter management. Despite the numerous solutions that have been proposed in recent years, their efforts are often hindered by high costs and unreliable fault localization, making it difficult to deploy them in real-world environments. In this paper, we present LMon, a highly reliable and efficient system for monitoring and troubleshooting in datacenter networks. LMon utilizes the characteristic of ECMP hashing linearity to control the packet routing without any modification of the underlying protocols. Additionally, LMon leverages a lightweight probing technique to reduce monitoring overhead. Furthermore, the system integrates improved LASSO regression and statistical hypothesis testing for higher accuracy and faster processing in link failure localization. The effectiveness of LMon is demonstrated through its implementation and evaluation in ns-3 simulation. The results validate the reliability and efficiency of the system, making it a promising option for ensuring long-term network maintenance in datacenters.

With the advantages of high mobility and flexibility, unmanned aerial vehicles (UAVs) have recently deployed as aerial base stations (ABSs) to expand the network capacity [1, 2] and as relays to link users and nearby base stations [5], thus assisting wireless communication. In modern cities, where apparent peaks and valleys of travel exist, mobile networks demand change can be theatrical.

The IEEE 802.1 Time Sensitive Networking (TSN) task group is devoted to improving deterministic delay during data communication. To schedule traffic in TSN, Asynchronous Traffic Shaping (ATS) has been introduced to guarantee bounded maximum delays without complicated time synchronization, and Urgency Based Scheduler (UBS) becomes the default implementation for ATS. However, due to the traffic fluctuation, UBS cannot achieve best delay bounds if some parameters are not configured appropriately in real time. What is more, UBS needs to consumes excessive butter resources, which prevents TSN from being deployed in real world. To solve these problems, we propose Time Sensitive Queuing (TSQ), a novel ATS mechanism. TSQ lowers the difficulty of TSN deployment by removing the parameter that need to be configured in real time. In addition, to reduce the butter consumption, TSQ applies time-slot-based packet allocation mechanism as the enqueue strategy, and time-slot-based packet polling mechanism as the dequeue strategy, respectively. Our Network Calculus analysis shows that TSQ can provide bounded delays and up to 40% butter resource reduction compared to UBS. The extensive experiments implemented in ns-3 show that TSQ consumes 33% less butter resource compared to UBS.

The vSwitch, as a critical component for Virtual Machine (VM) network connectivity in cloud environments, has prompted increasing attention towards its forwarding performance. While software optimization schemes have limitations in meeting the expanding network capacity demands [11, 12, 15, 17, 18], hardware offloading architectures leveraging SoC, FPGA, and ASIC have been proposed to transfer the match-action workload [1, 3, 6, 7, 13, 16], addressing the growing need for network capacity.

Data stream processing has become a hot issue in recent years due to the arrival of big data era. There are three fundamental stream processing tasks: membership query, frequency query and Top-K query. While most existing solutions address these queries in fixed windows, this paper focuses on a more challenging task: answering these queries in sliding windows. While most existing solutions address different kinds of queries by using different algorithms, this paper focuses on a generic framework. In this paper, we propose a generic framework, namely Sliding sketches, which can be applied to many existing solutions for the above three queries, and enable them to support queries in sliding windows. We apply our framework to five state-of-the-art sketches for the above three kinds of queries. Theoretical analysis and extensive experimental results show that after using our framework, the accuracy of existing sketches that do not support sliding windows becomes much higher than the corresponding best prior art. We released all the source code at Github.

Edge-assisted Distributed Learning (EDL) is a popular machine learning paradigm that uses a set of distributed edge nodes to collaboratively train a machine learning model using training data. Most of existing works implicitly assume that the fixed amount of training data is pre-collected and dispatched from user devices to edge nodes. In real world, however, training data in edge nodes are collected from user devices through wireless networks, and the volume and distribution of training data in edge nodes could exhibit temporal and spatial fluctuations due to varying wireless situations (e.g., network congestion, link capacity variation). In this way, existing solutions suffer from slow convergence and low accuracy. In this paper, we propose SpongeTraining to achieve high efficiency and accuracy for online EDL. To accommodate to fluctuations in training data, SpongeTraining uses a buffer at each worker to store received training data and adaptively adjusts training batch size and learning rate of each worker based on training data extracted from the buffer. Experiment results based on real-world datasets show that SpongeTraining outperforms existing solutions by accelerating the training process up to 50% for reaching the same training accuracy.

Frequency estimation and top-k flows identification are fundamental problems in network traffic measurement. Sketch, as a basic probabilistic data structure, has been extensively investigated and used in different management applications. However, few of them is suitable for both estimating frequency and finding top-k flows due to the unbalanced distribution of real-world network streams. By introducing a pre-filtering stage to isolate elephant and mice flows, the recently proposed Augmented Sketch (ASketch) significantly improves accuracy for both tasks. However, it suffers from serious performance degradation because of frequent flow exchanges. In this paper, we propose Cuckoo Counter (CC), an adaptive structure that consists of several buckets organized in a specific way. The size of the entry in each bucket is carefully designed to match the actual distribution of streams. During processing, CC hashes a flow to buckets and uses the idea of cuckoo hashing to relocate the flow if an overflow or collision happens, which contributes to fully utilizing memory. Therefore, the replacement strategy helps CC precisely record elephant flows and cover more mice flows, and also guarantees the throughput. Extensive experimental results show that CC has the highest (Freq.) accuracy, excellent (Heavy hitter / change) accuracy, highest (Top-k) precision, and competitive throughput compared to the state-of-the-art. Specifically, CC improves the throughput and accuracy by around 1 and 2 orders of magnitude respectively compared to the well-known ASketch.

Most congestion control algorithms (CCAs) are designed for specific network environments. As such, there is no known algorithm that achieves uniformly good performance in all scenarios for all flows. Rather than devising a one-size-fits-all algorithm (which is a likely impossible task), we propose a system to dynamically switch between the most suitable CCAs for specific flows in specific environments. This raises a number of challenges, which we address through the design and implementation of Antelope, a system that can dynamically reconfigure the stack to use the most suitable CCA for individual flows. We build a machine learning model to learn which algorithm works best for individual conditions and implement kernel-level support for dynamically switching between CCAs. The framework also takes application requirements of performance into consideration to fine-tune the selection based on application-layer needs. Moreover, to reduce the overhead introduced by machine learning on individual front-end servers, we (optionally) implement the CCA selection process in the cloud, which allows the share of models and the selection among front-end servers. We have implemented Antelope in Linux, and evaluated it in both emulated and production networks. The results demonstrate the effectiveness of Antelope via dynamic adjusting the CCAs for individual flows. Specifically, Antelope achieves an average 16% improvement in throughput compared with BBR, and an average 19% improvement in throughput and 10% reduction in delay compared with CUBIC.

The popular OpenFlow virtual switch Open vSwitch (OVS) uses a variant of Tuple Space Search (TSS) for packet classification. Although it is easy for rule updates, the lookup performance is poor. By introducing partial trees into TSS, the recently proposed CutTSS improves the lookup performance of TSS. However, it is challenging to replace TSS in OVS for two reasons: (1) the hand-tuned partitioning heuristics are rule-set dependent; (2) the complex and irregular data structures make it difficult to be integrated and maintained in real systems. To address these issues, we propose HybridTSS, a recursive TSS scheme for fast packet classification in OVS, which exploits three novel ideas: (1) the recursive partitioning based on reinforcement learning balances global rule partitions with low training complexity; (2) a hybrid TSS scheme combining coarse-grained and fine-grained tuples suppresses tuple explosion in TSS; (3) a heterogeneous search algorithm consisting of TSS and linear search adapts to characteristics of rules at different scales for fast lookups. Using ClassBench, we show that, while immune from the main drawbacks of CutTSS, HybridTSS retains the update performance of TSS, and achieves almost an order of magnitude higher lookup performance than TSS, making it an ideal packet classification algorithm for OVS.

Adaptive forwarding is one unique architectural benefit of Named Data Networking (NDN). However, it suffers from high cost of realtime path performance measurement. We propose efficient measurement techniques in NDN’s adaptive forwarding. Specifically, we eliminate the longest prefix matching operation at each data retrieval by decoupling the measurement and the FIB, which is proved to achieve the same effectiveness of the measurement while saving operation costs when network conditions are stable.

FPGA has been recognized as an attractive acceler-ator for line-speed packet classification in SmartNIC due to its ability to reconfigure and provide massive parallelism. As a promising algorithmic approach that can fully exploit the FPGA characteristics, decision tree based packet classification on FPGA has been actively investigated in the past decade. However, most of them suffer from unbalanced tree structures with unpredictable depths under certain rule sets, so the potential of FPGA may not be brought into full play. Worse still, few of them can support efficient rule updates on-the-fly, which is highly required in virtualized data centers. To address these issues, we design and implement an efficient hardware ar-chitecture based on the recently proposed KickTree algorithm, which consists of multiple balanced trees with bounded depth. A strategy of multi-PE (processing element), parallel search, and serial update is adopted to decouple the search and update process. The parsing of multiple tree search results adopts a modular and hierarchical design, supporting architecture with various tree numbers. Additionally, incremental rule updates can be achieved simply by traversing all PEs in one pass, with little and bounded impact on rule searching. Experimental results on FPGA show that our design can achieve an average classification throughput of 182.6 MPPS and an average update throughput of 3.1 MUPS for various 100k-scale rule sets.

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.

Time-Sensitive Networking (TSN) is an emerging network architecture that provides bounded latency and reliable network services for time-sensitive applications. Since time-triggered flows in TSN are typically periodic, a concept of network cycle is widely used in both standards and academic researches. However, although network cycle has gained popularity, its rationale has not yet been analyzed systematically.In this paper, we mathematically evaluate the performance of several flow scheduling algorithms in terms of flow schedulability with and without employing network cycle. We observe that only when the network cycle is set to a proper value can the performance of flow scheduling be significantly improved. To better evaluate the scheduling effect, a novel assessment metric and a goal-based optimization algorithm are introduced. Our experiment results show that the network cycle-based algorithm can achieve a considerable improvement (40% - 170% improvement in the number of scheduled flows) compared to the ones with network cycle disabled.

Distributed gradient descent has been widely adopted in the machine learning field because considerable computing resources are available when facing the huge volume of data. Specifically, the gradient over the whole data is cooperatively computed by multiple workers. However, its performance can be severely affected by slow workers, namely stragglers. Recently, coding-based approaches have been introduced to mitigate the straggler problem, but they could hardly deal with the heterogeneity among workers. Besides, they always discard the results of stragglers causing huge resource waste. In this article, we first investigate how to tolerate stragglers by discarding their results and then seek to leverage the stragglers. For tolerating stragglers, we propose a heterogeneity-aware coding scheme that encodes gradients adaptive to the computing capability of workers. Theoretically, this scheme is optimal for stragglers tolerance. Relying on the scheme, we further propose an algorithm called DHeter-aware to exploit the gradients of stragglers which we called delayed gradients. Moreover, theoretical results characterized for DHeter-aware exhibits the same convergence rate as the gradient descent without delayed gradients. Experiments on various tasks and clusters demonstrate that our coding scheme outperforms all the state-of-the-art methods and the DHeter-aware further accelerates the coding scheme by achieving 25 percent time savings.

Rotation Region Proposal Networks (RRPN) are used to generate rotated proposals with the information of text angle for arbitrary oriented scene text detection (STD). However, the computational complexity of RRPN inference is relatively high compared with other methods, which makes it difficult for massive deployment. In this paper, the first full-stack FPGA-CPU heterogeneous system design of RRPN-based STD algorithm is proposed. A hardware/software partition method is presented to analyze and split the tasks to enhance the computation efficiency of hardware. The fast 2D Winograd algorithm and block floating point are utilized to reduce computation complexity while maintaining a relatively high precision. The implementation results show that the peak performance of MAC arrays in the proposed architecture reaches 655.4 GOPS and the energy efficiency achieves 64.9 GOPS/W. By fully exploiting the parallel and pipelined merits in the algorithms, the first hardware architectures for skew non-maximum suppression (S-NMS) layer and rotation region-of-interest (RRoI) polling layer are proposed. The throughput of the proposed hardware/software heterogeneous system achieves 40 times and 1.4 times improvements compared with CPU and GPU, respectively. Moreover, the comprehensive operating expense ratio of pure CPU, GPU, and the proposed system is 80.7:2.5:1, which indicates that it is suitable for massive deployment.

Federated Learning (FL) is a promising machine learning paradigm to cooperatively train a global model with highly distributed data located on mobile devices. Aiming to optimize the communication efficiency for gradient aggregation and model synchronization among large-scale devices, we propose a relay-assisted FL framework. By breaking the traditional transmission-order constraint and exploiting the broadcast characteristic of relay nodes, we design a novel synchronization scheme named Partial Synchronization Parallel (PSP), in which models and gradients are transmitted simultaneously and aggregated at relay nodes, resulting in traffic reduction. We prove that PSP has the same convergence rate as the sequential synchronization approaches via rigorous analysis. To further accelerate the training process, we integrate PSP with any unbiased and error-bounded compression technologies and prove that the convergence properties of the resulting scheme still hold. Extensive experiments are conducted in a distributed cluster environment with real-world datasets and the results demonstrate that our proposed approach reduces the training time up to 37 percent compared to state-of-the-art methods.

As datacenter network bandwidth keeps growing, proactive transport becomes attractive, where bandwidth isproactivelyallocated as “credits” to senders who then can send “scheduled packets” at a right rate to ensure high link utilization, low latency, and zero packet loss. Consequently, proactive solutions such as ExpressPass, NDP, Homa, etc., have been proposed recently. While promising, a fundamental challenge is that proactive transport requires at least one-RTT for credits to be computed and delivered. In this paper, we show such one-RTT “pre-credit” phase could carry a substantial amount of flows at high link-speeds, but none of existing proactive solutions treats it appropriately. We present Aeolus, a solution focusing on “pre-credit” packet transmission as a building block for proactive transports. Aeolus contains unconventional design principles such as scheduled-packet-first (SPF) that de-prioritizes the first-RTT packets, instead of prioritizing them as prior work. It further exploits the preserved, deterministic nature of proactive transport as a means to recover lost first-RTT packets efficiently. Aeolus is compatible with all existing proactive solutions and readily implementable with commodity switches. We have integrated Aeolus into ExpressPass, NDP and Homa, and shown, via both implementation and simulations, that the Aeolus-enhanced solutions deliver significant performance or deployability advantages. For example, it improves the average FCT of ExpressPass by 56%, cuts the tail FCT of Homa by$20\times $, while achieving similar performance as NDP without switch modifications.

OpenFlow switches are being deployed in SDN to enable a wide spectrum of non-traditional applications. As a promising alternative to brutal force TCAMs, FPGA-based packet classification is being actively investigated. However, none of the existing FPGA designs can achieve high performance on both search and update for large-scale rule sets. To address this issue, we propose TcbTree, an FPGA-based algorithmic scheme for packet classification. Specifically, at the algorithmic side, i) a two-stage framework consisting of heterogeneous algorithms is proposed, where most rules can be mapped into several balanced trees without rule replications, ii) for the remaining few rules, a centralized TSS (Tuple Space Search) architecture together with a real-time feedback scheme is designed to enhance the efficiency of TSS search on FPGA, and iii) a tree dilution method is designed to equalize rule distribution in trees, so that the latency of tree search can be reduced. At the hardware side, i) an efficient data structure set is designed to convert tree traversal to addressing process, which breaks the constraints of limited tree depth and imbalanced node distribution, and ii) distinct from fully pipelined designs, multiple levels of parallelism are efficiently explored with multi-core, multi-search-engine and coarse-grained pipelines herein. Experimental results using ClassBench show that, with the implementation of TcbTree on FPGA, the average classification throughputs for 1k, 10k, 32k and 100k rule sets achieve 788.8 MPPS, 404.3 MPPS, 237 MPPS and 41.8 MPPS, respectively, and the update throughput for all benchmark rule sets is above 1 MUPS.

Datacenter networks enable multiple paths between hosts to provide large bisection bandwidth. It requires load balancers to cope with network uncertainties such as traffic dynamics and topology asymmetry. Existing edge-based load balancing schemes are usually faced with the problem of limited network visibility. This article proposesMeet, a rack-level pooling based load-balancer deployed at the edge that can handle the aformentioned uncertainties.Meetutilizes both passive information as well as active probing to comprehensively sense the network conditions with relatively low cost.Meetdynamically reroutes flows effectively based on the visibility of the network condition.Meethas been tested with extensive flow-level simulations against state-of-the-art load balancers. It outperforms Hermes by up to 10% in the experiments, and outperforms others solutions such as DRILL by up to 50%.Meetrequires no modifications to the switches and is feasible to deploy at the edge.

To minimize a job's completion time, we need to minimize the completion time of its final stage's last task. Scheduling of machine slots and networks largely dominates the variable part of each task's duration. Finding an optimal schedule is NP-hard even for offline and simplified scenarios. Previous work does lead to improved performance with various strategies. State-of-the-art task placement and network scheduling efforts are largely disjunctive. Without joint optimization, they are sub-optimal and myopic in many scenarios. Task placement usually treats the network as a black box. Thus, we use prioritized bandwidth allocation among tasks making the network bothpredictableandefficientto achieve joint scheduling. With this feature, joint scheduling can be transformed into a specialbin-packing problem. Over this minimal yet power-enough abstraction, we propose PushBox to schedule data-parallel jobs in multi-tenant clusters. When designing the joint scheduling algorithm, we not only embrace the wisdom of prior art but also respect administrators’ fairness intent, which is so far largely ignored. We implement PushBox on Hadoop 3. PushBox performs persistently well on both a small testbed and a trace-driven simulator.

Network measurement provides operators an efficient tool for many network management tasks such as performance diagnosis, traffic engineering and intrusion prevention. However, with the rapid and continuous growth of traffic speed, it needs more computing and memory resources to monitor traffic in per-flow or per-packet granularity. Sample-based measurement systems (e.g., NetFlow, sFlow) have been developed to perform coarse-grained measurement, but they may miss part of records, especially for mice flows, which are important for some network management tasks (e.g., anomaly detection, performance diagnosis). To address these issues, data streaming algorithms such as hash tables and sketches have been introduced to balance the trade-off among accuracy, speed, and memory usage. In this article, we present a systematic survey of various data structures, algorithms and systems which have been proposed in recent years to perform fine-grained measurement for high-speed networks. We organize these methods and systems from a software-defined perspective. In particular, we abstract fine-grained network measurement into three-layer architecture. We introduce the responsibility of each layer and categorize existing state-of-the-art works into this architecture. Finally, we conclude the article and discuss the future directions of fine-grained network measurement.

As a promising alternative to TCAM-based solutions for packet classification, FPGA has received increasing attention. Although extensive research has been conducted in this area, existing FPGA-based packet classifiers cannot satisfy the burgeoning needs from OpenFlow, which demands large-scale rule sets and frequent rule updates. As a recently proposed hardware-specific approach, TabTree avoids rule replication and supports dynamic rule update. However, it still faces problems of unbalanced rule subset partition, unevenly distributed subtrees and excessive TSS leaf nodes when implemented on FPGA. In this paper, we propose a hardware-friendly packet classification approach called KickTree, which is elaborated by considering hardware properties. To take advantage of intrinsic parallelism of FPGA, KickTree adopts multiple balanced decision trees which can run simultaneously. The bit selection is more flexible which breaks the restriction of rule subset. Moreover, each subset size is strictly limited, leading to bounded and evenly-distributed

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.

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.

Most congestion control mechanisms are designed for specific network environments. Hence, there is no known algorithm that achieves uniformly good performance in all scenarios for all flows. Rather than devising such a one-size-fits-all algorithm, we propose a system to dynamically switch between the most suitable congestion control mechanisms for specific flows in specific environments. This raises a number of challenges, which we address through the design and implementation of Antelope, a system that can dynamically reconfigure to use the most suitable congestion control mechanism for an individual flow. We build a machine learning approach to learn which algorithm works best for individual conditions and implement kernel-level support for dynamically adjusting congestion control algorithms. We have implemented Antelope in Linux, and evaluated it in both emulated and production networks. We show that in WAN, DCN, and cellular networks, Antelope achieves an average 16% improvement in throughput compared with BBR; compared with Cubic, Antelope achieves an average 19% improvement in throughput and 10% reduction in delay.

The traffic of modern data centers exhibits long-tail distribution, in which massive delay-sensitive short flows and a small number of bandwidth-hungry long flows co-exist. These two types of flows could share same bottleneck links in the data center networks but request different or even opposite network requirements. Existing solutions try to realize a trade-off between the requirements of different flows by either prioritizing short flows or limiting the buffer used by long flows at switches or end-hosts. However, they do not consider the dynamic traffic change and suffer from performance degradation, resulted from severe queueing delay and massive packet drops for short flows under current First-In-First- Out (FIFO) queueing mechanism. In this paper, we propose a novel buffer management scheme at switches, called Cut-in Queue (CQ), to achieve both low latency for short flows and high throughput for long flows. Based on network status in real time, CQ prioritizes short flows by dynamically cutting the short flows’ packets into the head of long flows or evicting some enqueued long flows’ packets and enables high throughput for long flows in most of the cases. Evaluation of both DPDK testbed and NS2 simulations show that CQ outperforms state-of-the-art buffer management schemes by reducing flow completion time by up to 73%.

The mobile network operators are upgrading their network facilities and shifting to the 5G era at an unprecedented pace. The huge operating expense (OPEX), mainly the energy consumption cost, has become the major concern of the operators. In this work, we investigate the energy cost-saving potential by transforming the backup batteries of base stations (BSs) to a distributed battery energy storage system (BESS). Specifically, to minimize the total energy cost, we model the distributed BESS discharge/charge scheduling as an optimization problem by incorporating comprehensive practical considerations. Then, considering the dynamic BS power demands in practice, we propose a deep reinforcement learning (DRL) based approach to make BESS scheduling decisions in real-time. The experiments using real-world BS deployment and traffic load data demonstrate that with our DRL-based BESS scheduling, the peak power demand charge of BSs can be reduced by up to 26.59%, and the yearly OPEX saving for 2,282 5G BSs could reach up to US$185,000.

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.

Sketches, a type of probabilistic algorithms, have been widely accepted as the approximate summary of data streams. Compressing sketches is the best choice in distributed data streams to reduce communication overhead. The ideal compression algorithm should meet the following three requirements: high efficiency of compression procedure, support of direct query without decompression, and high accuracy of compressed sketches. However, no prior work can meet these requirements at the same time. Especially, the accuracy is poor after compression using existing methods. In this paper, we propose Cluster-Reduce, a framework for compressing sketches, which can meet all three requirements. Our key technique nearness clustering rearranges the adjacent counters with similar values in the sketch to significantly improve the accuracy. We use Cluster-Reduce to compress four kinds of sketches in two use-cases: distributed data streams and distributed machine learning. Extensive experimental results show that Cluster-Reduce can achieve up to 60 times smaller error than prior works. The source codes of Cluster-Reduce are available at Github anonymously[1].

In-air gesture control extends a touch screen and enables contactless interaction, thus has become a popular research direction in the past few years. Prior work has implemented this functionality based on cameras, acoustic signals, and Wi-Fi via existing hardware on commercial devices. However, these methods have low user acceptance. Solutions based on cameras and acoustic signals raise privacy concerns, while WiFi-based solutions are vulnerable to background noise. As a result, these methods are not commercialized and recent flagship smartphones have implemented in-air gesture recognition by adding extra hardware on-board, such as mmWave radar and depth camera. The question is, can we support in-air gesture control on legacy devices without any hardware modifications?

In-air gesture control extends a touch screen and enables contact-less interaction, thus has become a popular research direction in the past few years. Prior work has implemented this functionality based on cameras, acoustic signals, and Wi-Fi via existing hardware on commercial devices. However, these methods have low user acceptance. Solutions based on cameras and acoustic signals raise privacy concerns, while WiFi-based solutions are vulnerable to background noise. As a result, these methods are not commercialized and recent flagship smartphones have implemented in-air gesture recognition by adding extra hardware on-board, such as mmWave radar and depth camera. The question is, can we support in-air gesture control on legacy devices without any hardware modifications?

The scalability issue hinders the deployment of Software-Defined Networking (SDN) in the Wide Area Networks (WANs). Existing solutions have two issues: (1) network performance relies on complicated controller synchronization, which increases the complexity of network control; (2) fine-grained flow processing enables flexible flow control at the cost of high processing load on the controllers and high flow table occupancy on switches. In this paper, we propose a scalable routing solution named HybridFlow, which achieves a good load balancing performance using a single controller with low control overhead (i.e., flow routing and rerouting overhead). HybridFlow mainly employs two techniques: hybrid routing and crucial flow rerouting. Hybrid routing enabled by commercial SDN switches gives us opportunities to reduce the processing load of the controller by routing flows with the hybrid OpenFlow/OSPF mode. Thus, the majority of flows can be routed by OSPF without involving the controller. Crucial flow rerouting realizes load balancing by dynamically identifying crucial flows based on a new metric called Variation Slope and rerouting these flows with the hybrid OpenFlow/OSPF mode. The simulation based on the real traffic traces and network typologies shows that compared with the optimal solution, HybridFlow can achieve 87% of the optimal load balancing performance by rerouting 36% less flows on average.

360-degree video streaming shows great potential to revolutionize the streaming market, by providing much better immersive experience than standard video streams. However, its wide adoption is hindered by the surging demand of network bandwidth due to multi-screen video transmission. To reduce the bandwidth cost, one promising approach is to predict a user’s field of view (FoV), and then prefetch video tiles that a user will view a few seconds ahead. The challenge lies in that user behaviors cannot be properly captured with very limited information, especially the viewing time spent on each tile and the FoV switching behavior are hard to predict. In this paper, we propose a novel 360-degree video streaming algorithm calledTVG-Streamingto optimize user experiences by learning user view behaviors. Different from previous approaches, our idea is to exploit tile-view graphs (TVGs) generated by real user behaviors and accurately estimate the probability that each tile falls in the FoV. With the tile view probability, we can determine the bitrate of each tile for delivery and buffering with limited bandwidth budget so as to maximize users’ quality of experience (QoE). For evaluation, we conduct extensive experiments using real traces and the results show that our proposedTVG-Streamingalgorithm significantly outperforms other algorithms by at least 20% improvement in terms of users’ QoE.

One unique architectural benefit of Named Data Networking (NDN) is adaptive forwarding, i.e., the forwarding plane is able to observe past data retrieval performance and use it to adjust forwarding decisions for future Interests. To be effective, adaptive forwarding assumes thatInterest Routing Localityis related to Interests’ common name prefix, meaning that Interests sharing the same prefix are likely to follow a similar forwarding path within a short period of time. Since Interests can have multiple common prefixes with different lengths, the real challenge is determining which prefix length should be used in adaptive forwarding to record path performance measurements - we refer to this as thePrefix Granularity Problem. The longer the common prefix is, the better the Interest Routing Locality, and the larger the forwarding table. Given the limited FIB size, route names are designed to be considerably shorter than Interest names. Existing adaptive forwarding designs use route names to record path performance measurements, which looses forwarding adaptability as it promises in the event of partial network failures. In this work, we propose to dynamically aggregate and de-aggregate name prefixes in the forwarding table in order to use the prefixes that are the most appropriate given current network situation. In addition, to reduce the overhead of adaptive forwarding, we propose mechanisms to minimize the use of the longest prefix matching in Data packet processing. Simulations demonstrate that the proposed techniques can result in better forwarding decisions in the event of partial network failures with significantly reduced overhead.

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.

DNN inference is becoming prevalent for many real-world applications. Current machine learning frameworks usually schedule inference tasks with the goal of optimizing throughput under predictable workloads and task arrival patterns. Yet, inference workloads are becoming more dynamic with bursty queries generated by various video analytics pipelines which run expensive inference only on a fraction of video frames. Thus it is imperative to optimize the completion time of these unpredictable queries and improve customer experience.

Latent fingerprint reconstruction is a vital preprocessing step for its identification. This task is very challenging due to not only existing complicated degradation patterns but also its scarcity of paired training data. To address these challenges, we propose a novel generative adversarial network (GAN) based data augmentation scheme to improve such reconstruction. It translates the abundant clean fingerprints to their corresponding latent ones, only exploiting a small-scale latent dataset and an unpaired large-scale clean dataset, from which a large-scale paired clean-latent augmentation set is built for the reconstruction task. Specifically, our method models the distribution of the latent degradation patterns into a Gaussian one and generates latent fingerprints based on the sampled degradation patterns and clean fingerprints. Besides, we develop an auxiliary training procedure to stabilize training and further disentangle ridge structures and degradation patterns by regressing a latent fingerprint from its latent representation and its corresponding binarized fingerprint. Boosted by the proposed data augmentation, our reconstruction shows significant improvements in visual evaluation and fingerprint identification performance.

The pervasive low-battery anxiety (LBA) among modern mobile users has caused negative impacts on users' emotion and health, and such anxiety may directly lead to loss of customers in power-hungry applications, e.g., video streaming. Despite its importance, LBA has not been thoroughly investigated due to the difficulty in quantitatively measuring LBA. To fill the gap, we present a quantitative model to measure the LBA among mobile users and design a tailored mechanism to alleviate it via display energy saving in video streaming. In specific, we first conduct a large-scale user survey among 2000+ mobile users and strategically extract an empirical LBA model that captures the variation of user's anxiety degree along with the battery power draining. Then, by exploiting the emerging edge computing paradigm, we propose LPVS, a novel solution for low-power video streaming service at the network edge. It aims to minimize the LBA of mobile users, by integrating the extracted LBA model with the energy-saving image/video content transforming techniques. The emulation results using real-world video watching traces demonstrate that, LPVS can effectively alleviate mobile users' LBA and prolong the low-battery users' video watching time (i.e., customer retention) by 39%.

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%.

Image aesthetic assessment is challenging as it concerns various relative vague perceptual evaluations. A key factor among them is how to evaluate image layout, finding spatial importance in aesthetics. In this paper, we propose a spatial attentive image aesthetic assessment model to address that factor. Our method exploits the attention mechanism to learn the spatial attention map and aggregate the learned features according to it. This method preserves the image aspect ratio intrinsically, which is vital for image aesthetics as the ratio distortion usually degrades aesthetic evaluation. Numerical experimental results show that the proposed method gets the highest correlation performance with human annotation on a public benchmark, outperforming the existing state-of-arts.

Data stream processing has become a hot issue in recent years due to the arrival of big data era. There are three fundamental stream processing tasks: membership query, frequency query and heavy hitter query. While most existing solutions address these queries in fixed windows, this paper focuses on a more challenging task: answering these queries in sliding windows. While most existing solutions address different kinds of queries by using different algorithms, this paper focuses on a generic framework. In this paper, we propose a generic framework, namely Sliding sketches, which can be applied to many existing solutions for the above three queries, and enable them to support queries in sliding windows. We apply our framework to five state-of-the-art sketches for the above three kinds of queries. Theoretical analysis and extensive experimental results show that after using our framework, the accuracy of existing sketches that do not support sliding windows becomes much higher than the corresponding best prior art. We released all the source code at Github.

Existing traffic engineering (TE) solutions perform well for software defined network (SDN) in average cases. However, during peak hours, bursty traffic spikes are challenging to handle, because it is difficult to react in time and guarantee high performance even after failures with limited flow entries.We propose TED, a scalable TE system that can guarantee high throughput in peak hours. TED can quickly compute a group of maximum number of edge-disjoint paths for each ingress-egress switch pair. Such paths are suitable for well connected networks with unique edge capacity and TED is not limited to use only these paths. We design two methods to select paths under the limit of flow table size. We then input the selected paths to TED to minimize the maximum link utilization. In case of large traffic matrix making the maximum link utilization larger than 1, we input the utilization and the traffic matrix to the optimization of maximizing overall throughput under a new constrain. Thus we obtain a realistic traffic matrix, which has the maximum overall throughput and guarantees no traffic starvation. Experiments show that TED has much better performance for heavily-loaded SDN and has 10% higher probability to satisfy all (> 99.99%) the traffic after a single link failure for G-Scale topology than Smore under the same limit of flow table size.

As datacenter network bandwidth keeps growing, proactive transport becomes attractive, where bandwidth is proactively allocated as "credits" to senders who then can send "scheduled packets" at a right rate to ensure high link utilization, low latency, and zero packet loss. While promising, a fundamental challenge is that proactive transport requires at least one-RTT for credits to be computed and delivered. In this paper, we show such one-RTT "pre-credit" phase could carry a substantial amount of flows at high link-speeds, but none of existing proactive solutions treats it appropriately. We present Aeolus, a solution focusing on "pre-credit" packet transmission as a building block for proactive transports. Aeolus contains unconventional design principles such as scheduled-packet-first (SPF) that de-prioritizes the first-RTT packets, instead of prioritizing them as prior work. It further exploits the preserved, deterministic nature of proactive transport as a means to recover lost first-RTT packets efficiently. We have integrated Aeolus into ExpressPass[14], NDP[18] and Homa[29], and shown, through both implementation and simulations, that the Aeolus-enhanced solutions deliver signiicant performance or deployability advantages. For example, it improves the average FCT of ExpressPass by 56%, cuts the tail FCT of Homa by 20x, while achieving similar performance as NDP without switch modifications.

With the explosive growth of mobile devices at the edge of mobile social networks (MSNs), the amount of the content that needs to be transmitted is exploded. Traditional content delivery mechanisms leverage only local information to make routing decisions, which results in both high latency and low delivery rate. Software-defined networking (SDN) is a novel network paradigm, the design philosophy of which could be applied to MSN for improving the content delivery performance. In this article, the centralized control thought of SDN is introduced into MSN to efficiently process social information. The classical routing algorithm of BubbleRap is improved from the perspective of network density, which is the basis of designing the sparse and dense routing mechanisms for MSNs. In addition, flexibly switching between these two routing mechanisms is implemented by a discriminating scheme, achieving efficient yet adaptive routing. The experimental results show that the delivery ratio of sparse routing is up to 83%, and the dense routing could reach up to 93%.

Wireless communication demands increase sharply with the explosive growth of mobile devices. The communications mainly depend on the infrastructure-based networks, e.g., WLANs and cellular networks. However, such wireless connections may be unavailable in crowded areas (e.g., concert and conference hall) or interrupted by infrastructure failures caused by earthquake or tsunami. These promote the evolution of local communication systems over device-to-device communication, such as Bluetooth and Wi-Fi Direct (WFD). However, none of the existing studies construct a full-featured local communication system, and they do not consider how to support the user mobility either. In this article, we implement and evaluate the performance of a WFD-based local communication system. First, we improve the intragroup communication by the native implementation of WFD on the Android platform, and propose an application-layer forwarding solution for the intergroup communication, which can be applied to three or more connected groups. Then, we put forward a self-adaptive handover mechanism taking user mobility and node failures into account. To deal with the uncertainty in the handover decision procedure, a fuzzy-logic-based normalized quantitative decision algorithm (FNQD) with the weights derived from the fuzzy analytic hierarchy process (FAHP) is utilized. Finally, we evaluate the performance of the system through both simulation and experiment analysis. Results show that we can get a maximum throughput of 31.7 Mb/s for the intragroup communication and a maximum goodput of 4.76 Mb/s for the intergroup communication. What is more, mobile devices could perform various types of handover according to their roles and status, which could improve the robustness of the local communication system.

In-browser cryptojacking is an emerging threat to web users. The attackers can abuse the users' computation resources to perform cryptocurrency mining without obtaining their consent. Moreover, the new web feature -WebAssembly (Wasm)- enables efficient in-browser cryptocurrency mining and has been commonly used in mining applications. In this work, we use the dynamic Wasm instruction execution trace to model the behavior of different Wasm applications. We observe that the cryptocurrency mining Wasm programs exhibit very different execution traces from other Wasm programs (e.g., games). Based on our findings, we propose a novel browser-based methodology to detect in-browser Wasm-based cryptojacking.

Including JavaScript code from many different hosts is a popular practice in developing web applications. For example, to include a social plugin like the Facebook Like button, a web developer needs to only include a script from facebook.net in her/his web page. However, in a web browser, all the identifiers (i.e., variable names and function names) in scripts loaded in the same frame share a single global namespace. Therefore, a script can overwrite any of the global variables and/or global functions defined in another script, causing unexpected behavior. In this work, we develop a browser-based dynamic analysis framework, that monitors and records any writes to JavaScript global variables and global functions. Our tool is able to cover all the code executed in the run time. We detected 778 conflicts across the Alexa top 1K websites. Our results show that global name conflicts can indeed expose web applications to security risks.

With the development of data center networks, traditional TCP/IP cannot support the demand in data centers. Remote Direct Memory Access (RDMA) technology could improve the performance of DCN significantly because of high throughput and low latency. However, load balancing is a key issue in RDMA which has not been solved distribute. This paper will propose an algorithm to solve the load balance problem in RDMA on application layer without hardware changing. The main idea is to divide data to chunks and data chunks on multiple reachable paths for transmission. However, it is no trivial to find the optimal chunk size and the path number, some empirical values are found by varieties of experiments and tests. Moreover, the chunk allocation scheme also needs to consider the traffic condition in DCNs to find more free paths to transmit. We evaluate the algorithm in application layer with ns3 simulator. The experiment results show that with our algorithm the completion time can decrease 81.03% at most.

Modern data center applications need high throughput (40Gbps) and ultra-low latency (<;10us per hop), along with low CPU overhead. Remote Direct Memory Access (RDMA), which can be deployed in RDMA over commodity Ethernet (RoCEv2) protocol, has the potential to satisfy the requirements. RoCEv2 needs a lossless environment to achieve high performance. RoCEv2 provides Priority-based Flow Control (PFC) to prevent packet loss caused by buffer overflow. But packet loss can still happen in today’s data centers due to other reasons such as switch configuration error. There are two retransmission algorithms dealing with the packet loss recovery: Go-Back-0 and Go-Back-N. Unfortunately, by simply applying Go-Back-N algorithm to RoCEv2, the relative throughput will drop to nearly zero when the packet loss rate exceeds 1%. This is mainly caused by the improper triggering mechanism of generating NAK. This paper proposed an Improved Go-Back-N algorithm to solve this problem, which involves two mechanism. The Improved Go-Back-N is easy to be deployed in today’s data centers because it makes no changes on switches. It can improve the relative throughput to about 60% when the packet loss rate increases to 1%.

In addition to military applications, Unmanned Aerial Vehicles (UAVs) have attracted more and more attention in civilian applications such as the post-disaster relief assistance. Indeed, advantages including better line-of-sight (LOS), wider communication range and more flexible on-demand deployment make UAVs play a unique role in rescue and disaster scenarios. Emergency tasks assigned to UAVs such as people search and rescue usually require real-time responses, since it is a life-and-death matter regarding the post-disaster relief. Considering the limited computing resources and harsh energy supply replenishment for UAVs in the post-disaster relief operations, we in this paper propose a hybrid fog computing paradigm called H-FVFC that integrates UAVs and vehicular fog computing (VFC) to run the highly demanding tasks with strict latency requirements. An architecture of H-FVFC consisting of three layers is proposed and investigated in this paper, with hope to explore the possibilities of applying this computing paradigm to post-disaster relief operations. Experiments are carried out to evaluate the task offloading in H-FVFC compared to UAV-to-Cloud scheduling strategy. The results show that task offloading in the UAV-to-Vehicle way can significantly reduce the response latency. Issues not addressed in this paper are also discussed with purpose of providing some insights to the application of integration of UAV and fog-enabled vehicle in the post-disaster relief.

th for various services. Yet today’s widely used load balancing scheme, i.e., ECMP, may cause serious congestion when hash collision happens. Recent proposals either push load balancing function to a centralized controller or network edges. However, the centralized schemes are too slow for latency-sensitive flows, while the distributed schemes lack the global view and usually cannot make the best choices. In this paper, based on Software-Defined Networking (SDN), we present a new hybrid load balancing scheme called BLEND. It promotes the cooperation among network components and takes advantage of both global view and fast end-host action. BLEND aims to improve the throughput of big flows and reduce the latency of small and medium flows. It employs a controller to assign paths to big flows to achieve high throughput. In addition, in order to provide guidance for fast distributed load balancing decisions, the controller also calculates the optimal network delay thresholds for small and medium flows, while hosts utilize these thresholds to decide whether to change the current paths. BLEND is practical and easily deployable in the current data center networks. Comprehensive experiments demonstrate that BLEND outperforms both the centralized and distributed schemes and achieves at most 40% reduction in FCT and at most 2.8 times improvement in throughput.

Remote Direct Memory Access (RDMA) can be deployed in Content Delivery Networks (CDN) Points of Presence (PoPs) to avoid the high CPU overheads caused by traditional TCP/IP stacks. However, RDMA cannot surmount the drawbacks of the window-based conservative of TCP and is insensitive to Quality of Experience (QoE). Moreover, the requirement of lossless networks hinders the widespread application of RDMA. In this paper, we introduce the parallel multipoint-to-multipoint Request-Grant-Transfer (RGT) mode into RDMA to solve the aforementioned problems. Compared with traditional RGT mode, our scheme supports parallel Dynamic Adaptive Streaming over HTTP (DASH) chunk delivery, thereby improving throughput and reducing initial delays. We differentiate the importance of DASH chunks according to QoE-related properties. In this way, we reduce the response time of specific DASH chunks. We provide an efficient approach to select the optimal number of requests for partially traversing pending requests to reduce the overheads of Request stages. We perform comprehensive experiments to demonstrate that our scheme improves the throughput of CDN PoPs and enhances client QoE.

Monitoring mobile network performance is critical for optimizing the QoE of mobile apps. Until now, few studies have considered the actual network performance that mobile apps experience in a per-app or per-server granularity. In this paper, we analyze a two-year-long dataset collected by a crowdsourcing per-app measurement tool to gain new insights into mobile network behavior and application performance. We observe that only a small portion of WiFi networks can work in high-speed mode, and more than one-third of the observed ISPs still have not deployed 4G networks. For cellular networks, the DNS settings on smartphones can have a significant impact on mobile app network performance. Moreover, we notice that instant messaging (IM) and voice over IP (VoIP) services nowadays are not as performant as Web services, because the traffic using XMPP experiences longer latencies than HTTPS. We propose an automatic performance degradation detection and localization method for finding possible network problems in our huge, imbalanced and sparse dataset. Our evaluation and case studies show that our method is effective and the running time is acceptable.

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.

Existing flow scheduling schemes in Data Center Network (DCN) are designed mainly to minimize the flow complete time (FCT) of short flows and do not consider optimizing the FCT of latency-sensitive long flows (e.g. VR video streaming, interactive artificial intelligence question&answer stream). Besides, among these traffic scheduling schemes, the information-aware schemes (e.g. L2DCT, D2TCP) are hard to deploy in practice since they assume prior knowledge of flow information (e.g, flow size); and the information-agnostic scheme (i.e. PIAS), which is based on the premise that flow size is not known a priori, requires a central server, causing a poor scalability in large network scales. Given the limitations of existing solutions, in this paper, we propose a distributed information-agnostic flow scheduling scheme (DIAS), which minimizes the FCT of both short flows and latency-sensitive long flows. In DIAS, packets are forwarded complying with their priorities, which are determined based on packets wait-time that is defined as staying time in end hosts' send buffers, and the longer a packet stays in a send buffer, the lower its priority. Meanwhile, instead of utilizing a central server to collect traffic load information, each switch feeds traffic load information which is used to adjust the thresholds of determining packets priority back to end hosts via ACK packets. The experimental results in ns-3 simulator show that DIAS reduces FCT by up to 54.7% and 50.1 % over DCTCP and L2DCT, respectively. Besides, DIAS ensures a smaller FCT of latency-sensitive long flows and performs better than PIAS.

Software Defined Networking (SDN) simplifies network management by separating the control plane from the data plane in performance networks. However, the actual packet behaviors, conforming to the rules in the data plane flow tables, may violate the original policies in the controller due to the inconsistency between the data plane and control plane. To address this problem, we propose 2MVeri, a new framework for measuring the control-data plane consistency, defined as the consistency between the control plane policies and data plane rules. 2MVeri uses a Bloom filter and a two-dimensional vector as a tag which is inserted in the packet header and is updated in each switch that the packet traverses. By exploiting path information compressed in the tag, 2MVeri can verify the control-data plane consistency. Moreover, when verification fails, 2MVeri can localize the faulty switch. Evaluations conducted on a datacenter network with the fat tree topology k=4 demonstrate that 2MVeri achieves 100% accuracy in consistency verification and high fault localization performance.

Today's cloud networks are shared among many tenants. Bandwidth guarantees and work conservation are two key properties to ensure predictable performance for tenant applications and high network utilization for providers. Despite significant efforts, very little prior work can really achieve both properties simultaneously even some of them claimed so. In this paper, we present QShare, a comprehensive in-network solution to achieve bandwidth guarantees and work conservation simultaneously. QShare leverages weighted fair queuing on commodity switches to slice network bandwidth for tenants, and solves the challenge of queue scarcity through balanced tenant placement and dynamic tenant-queue binding. We have implemented a QShare prototype and evaluated it extensively via both testbed experiments and simulations. Our results show that QShare ensures bandwidth guarantees while driving network utilization to over 91% even under unpredictable traffic demands.

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.

The current inter-domain routing protocol, namely, the Border Gateway Protocol (BGP), cannot provide end-to-end (E2E) quality-of-service (QoS) guarantees. The main reason is that an autonomous system (AS) can only receive guarantees from its first hop ASes via service level agreements (SLAs). But beyond the first hop, QoS along the path from source to destination AS is not within the source AS's control regime. In this paper, we investigate the feasibility of providing high QoS-guaranteed E2E transit services by utilizing a (small) set of ASes/IXPs to serve as "brokers" to provide supervision, control and resource negotiation. Finding an optimal set of ASes as brokers can be formulated as a Maximum Coverage with B-dominating path Guarantee (MCBG) problem, which we prove to be NP-hard. To address this problem, we design a (1-e-1/4)-approximation algorithm and also an efficient heuristic algorithm when considering additional constraints (e.g., path length). Based on the current Internet topology, we discover a "3540-alliance" subset (accounting only 6.8%) of 52,079 ASes/IXPs, which can provide high QoS guarantees for 99.29% E2E connections.

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.

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 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.

Application Driven Network(ADN) is a new paradigm that provides on-demand differentiated services for applications. A physical network in ADN is sliced into various logically isolated sub-networks. Each network slice can have its own network architecture and protocol to serve one application exclusively. ADN enhances the user experience while keeping the resource efficiency by further imposing multiplexing among these logically isolated sub-networks.

For the development of new 5G systems to operate in bands up to 100 GHz, there is a need for accurate radio propagation models at these bands that currently are not addressed by existing channel models developed for bands below 6 GHz. This document presents a preliminary overview of 5G channel models for bands up to 100 GHz. These have been derived based on extensive measurement and ray tracing results across a multitude of frequencies from 6 GHz to 100 GHz, and this document describes an initial 3D channel model which includes: 1) typical deployment scenarios for urban microcells (UMi) and urban macrocells (UMa), and 2) a baseline model for incorporating path loss, shadow fading, line of sight probability, penetration and blockage models for the typical scenarios. Various processing methodologies such as clustering and antenna decoupling algorithms are also presented.

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.

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.

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/.

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.

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.

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.

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.

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.

In this paper, extended-cyclic-prefix OFDM (ECP-OFDM) is proposed to suppress the out-of-band (OOB) power due to discontinuity of consecutive OFDM symbols. Besides that effective CP length is increased, it shows the advantages of low implement complexity and good OOB suppression performance.

In this paper, a new peak-to-average power ratio (PAPR) reduction method, called adaptive weight peak-cancelling (AWPC), for orthogonal frequency division multiplexing (OFDM) systems is presented. The basic idea is to control the power distribution of clipping noise on the subcarriers, according to the error vector magnitude (EVM) requirements on each data block. This is superior to the conventional peak- cancelling method which can only introduce uniform interference on all data blocks no matter what EVMs are demanded. Moreover, the proposed AWPC can flexibly implement peak-cancelling and tone-reservation schemes simply by setting the weight of peak-cancelling signal. Numerical results show that PAPR can be reduced to 5dB while different EVM requirements due to M-PSK/QAM modulations are well satisfied.