Classes, as fundamental elements of Computer Vision, have been extensively studied within incremental learning frameworks. In contrast, tokens, which play essential roles in many research fields, exhibit similar characteristics of growth, yet investigations into their incremental learning remain significantly scarce. This research gap primarily stems from the holistic nature of tokens in language, which imposes significant challenges on the design of incremental learning frameworks for them. To overcome this obstacle, in this work, we turn to a type of token, gene, for a large-scale biological dataset—single-cell transcriptomics—to formulate a pipeline for gene incremental learning and establish corresponding evaluations. We found that the forgetting problem also exists in gene incremental learning, thus we adapted existing class incremental learning methods to mitigate the forgetting of genes. Through extensive experiments, we demonstrated the soundness of our framework design and evaluations, as well as the effectiveness of the method adaptations. Finally, we provide a complete benchmark for gene incremental learning in single-cell transcriptomics.

Identifying encrypted malicious traffic is a key challenge in network security. Although pre-training techniques based on self-supervised learning are a trend towards reducing dependence on labeled data, existing mainstream methods that directly apply the architecture of natural language processing and masked language modeling tasks have been shown to be "high sugar" by recent research. They may rely on specific "shortcuts" rather than robust traffic behavioral representations to achieve inflated performance. How to extract more robust and generalizable features from covert and sparse encrypted malicious traffic is a major challenge. Therefore, we propose SUGARLESS, a robust representation learning for encrypted malicious traffic identification. To depart from the BERT-based paradigm, we first propose a spatial-temporal contrastive learning as the pre-training task that aligns temporal and spatial modal features without using NLP-style objectives, encouraging the model to learn cross-modal traffic correlations between modalities. We also propose a traffic-specific prompt-tuning mechanism to bridge the gap between pre-training and downstream tasks. Meanwhile, we develop a spatial-temporal feature fusion module to maintain this alignment during fine-tuning. Experiments on two public malware traffic datasets show that SUGARLESS achieves the best precision, recall, and F1-score with competitive accuracy, improves the average F1-score by 9.26% over YaTC, and is more robust under packet loss and reordering.

Network traffic classification is significant for modern network security. The widespread use of encryption protocols, such as TLS, has resulted in fewer identifiable features of traffic, rendering encrypted traffic classification a challenging task. However, existing flow-level classification methods typically rely on the features of the first N packets. This fixed-length paradigm, truncating long flows and padding short flows with invalid data, is difficult to adapt to the dynamic distribution of traffic length, which limits robustness in interference environments such as packet loss. Considering this limitation, we propose DART, a robust encrypted traffic classification method via dynamic patch-level feature learning. We first design a robust feature representation method to improve robustness against interference, which divides a flow into multiple sub-flows named patches to extract patch-level features, replacing the interference-prone packet-by-packet sequence and significantly reducing the length of the feature sequence. We also propose a sample-adaptive dynamic inference mechanism in response to traffic heterogeneity. The input scale is adaptively selected based on traffic complexity, and simple samples are allowed to exit early in shallow layers, achieving a balance between accuracy and efficiency. The experimental results on two public malware traffic datasets demonstrate that DART exhibits excellent anti-interference robustness and improves classification accuracy by 6.59%-30.51%, while maintaining high classification efficiency compared to existing mainstream methods.

Offloading fast-path MegaFlows in Open vSwitch to hardware accelerators is a common approach for accelerating packet forwarding in modern cloud data centers. However, due to the limited capabilities of current hardware accelerators, existing solutions still rely on coarse-grained, best-effort offloading, which struggles with dynamic, large-scale traffic and results in inefficient resource utilization and limited performance gains. We present FlowTurbo, a self-adaptive, system-level offloading approach that implements hit-driven MegaFlow hardware offloading by jointly optimizing software rule scheduling and hardware rule lookup. The core innovations of FlowTurbo are threefold: (1) a traffic-aware, hit-driven MegaFlow offloading framework that selectively migrates hotspot wildcard rules to hardware; (2) a domain-specific, hardware-friendly sketch for MegaFlow rules that tracks rule hotness and enables the scheduler to make timely and precise offloading decisions; and (3) a domain-specific, algorithm-hardware co-designed packet classification accelerator that supports both line-rate rule matching and online rule updates. We implemented FlowTurbo on Open vSwitch and prototyped its hardware accelerator on a Xilinx Alveo U200. Evaluation using multiple real-world traffic traces shows that FlowTurbo achieves an average acceleration coverage of 89.4%, and the hardware accelerator delivers a maximum throughput of 400 MOPS while consuming only 3.3% of FPGA logic resources.

Web service administrators must ensure the stability of multiple systems by promptly detecting anomalies in Key Performance Indicators (KPIs). Achieving the goal of "train once, infer across scenarios" remains a fundamental challenge for time series anomaly detection models. Beyond improving zero-shot generalization, such models must also flexibly handle sequences of varying lengths during inference, ranging from one hour to one week, without retraining. Conventional approaches rely on sliding-window encoding and self-supervised learning, which restrict inference to fixed-length inputs. Large Language Models (LLMs) have demonstrated remarkable zero-shot capabilities across general domains. However, when applied to time series data, they face inherent limitations due to context length. To address this issue, we propose ViTs, a Vision-Language Model (VLM)-based framework that converts time series curves into visual representations. By rescaling time series images, temporal dependencies are preserved while maintaining a consistent input size, thereby enabling efficient processing of arbitrarily long sequences without context constraints. Training VLMs for this purpose introduces unique challenges, primarily due to the scarcity of aligned time series image-text data. To overcome this, we employ an evolutionary algorithm to automatically generate thousands of high-quality image-text pairs and design a three-stage training pipeline consisting of: (1) time series knowledge injection, (2) anomaly detection enhancement, and (3) anomaly reasoning refinement. Extensive experiments demonstrate that ViTs substantially enhance the ability of VLMs to understand and detect anomalies in time series data. All datasets and code will be publicly released at: https://anonymous.4open.science/r/ViTs-C484/.

To satisfy the unprecedented Quality of Experience (QoE) and stringent latency Service Level Agreements (SLAs) of emerging interactive applications, modern Content Delivery Networks (CDNs) are deploying massively decentralized edge nodes. However, this paradigm shift poses a significant challenge: optimal traffic scheduling fundamentally depends on acquiring real-time, full-coverage end-to-end path latency data to prevent SLA violations. Current measurement methods cannot scale to monitor every possible user-to-node path, and traditional prediction approaches (e.g., relying on additional segmented measurements or low-rank matrix decomposition) fail to achieve satisfactory accuracy on the resulting extremely sparse datasets. In this work, we present ADePT (Application Delay PredicTion), a novel data-driven causal inference framework that provides comprehensive and precise latency predictions without requiring additional measurements. By explicitly decoupling user-side temporal variations (e.g., last-mile congestion) and node-side spatial variations (e.g., core propagation delays), ADePT successfully extracts high-dimensional latent embeddings from limited measurement data to infer the end-to-end path latency for any potential scheduling decision. Evaluated on a massive real-world dataset from a leading edge CDN, ADePT reduces prediction errors by 19.6% and achieves a median absolute error of 4.3 ms. Consequently, integrating ADePT’s accurate predictions into CDN traffic scheduling significantly improves scheduling decisions, increasing the ratio of traffic meeting strict applications’ latency requirements by 1.66 × .

Packet classification is a fundamental operation in modern network systems, playing a central role in traffic management, security enforcement, and policy execution. While traditional algorithms have achieved low lookup latency in static scenarios, emerging applications impose more demanding requirements—not only fast lookup, but also high-frequency online updates and strong scalability. Existing approaches often struggle to handle large rule sets or support rules with an increasing number of matching fields, making them unsuitable for dynamic and large-scale network environments.In this work, we propose TupleChain for fast on-line update table lookup with multifaceted scalability.We group rules based on their masks, each maintained using a hash table, and explore the connections among rule groups to skip unnecessary hash probes for faster searches. We show via theoretical analysis and extensive experiments that the proposed scheme offers competitive computational complexity, strong scalability, and high performance in both search and update operations. TupleChain can process millions of packets per second, while simultaneously handling millions of on-line updates per second at the same time, and its lookup speed remains stable even when processing large flow table with 10 million rules or entries containing up to 100 match fields.

As deep learning (DL) continues to advance, effective feature extraction from large-scale data remains crucial for enhancing model performance. To leverage the advantages of the frequency domain, such as concentrated signal energy, prominent data features, and rich detailed characteristics, this paper proposes a novel frequency-domain feature extraction method. However, existing frequency component selection algorithms often struggle to adapt to diverse tasks, tend to yield only locally optimal solutions, and require prolonged processing times. To overcome these limitations, we introduce the Adaptive Fast Frequency Selection (AFFS) algorithm, which seamlessly integrates a frequency component selection factor layer into DL models to identify globally optimal frequency combinations suited to various downstream tasks. We further analyze the relationship between selected frequency components and model performance, providing theoretical guarantees regarding optimality, robustness, and generalization error bounds. Moreover, a fast selection procedure is developed to exploit the empirically observed rapid convergence of the selection-factor ranking, significantly accelerating the selection process. Extensive experiments on five datasets, ten DL models, and two subsequent tasks demonstrate that AFFS achieves superior performance: even when the input data size is reduced to only 10% of the original frequency features, model classification accuracy improves by approximately 1%, while the early stopping mechanism shortens the selection process by about 80%.

Mobile crowd sensing (MCS) has emerged as a promising sensing paradigm with the widespread adoption of smartphones. However, one of the key bottlenecks in MCS lies in the high sensing cost imposed on mobile users. To alleviate this burden, sparse sensing strategies are often employed, where data is collected from a limited number of locations and the remaining data is inferred by exploiting spatio-temporal correlations. Compared with vector-based inference approaches, matrix completion techniques can better capture two-dimensional correlations in the sensing data, thereby achieving higher recovery accuracy. Nevertheless, their performance degrades significantly when the actual sensing rate is low. In this paper, we propose a novel matrix-reshaping strategy that is applied prior to matrix completion to enhance recovery performance under sparse observations. We provide a theoretical analysis demonstrating that the reshaping process reduces the number of measurements required for successful matrix recovery. To validate our approach, we conduct extensive experiments using traditional matrix completion algorithms, deep learning models, and tensor completion methods on six real-world datasets. The results show that, to achieve the same level of recovery accuracy, our reshaped matrices consistently reduce the measurement overhead compared to their original ones.

Low-latency cloud rendering enables mobile users to experience high-quality, real-time 3D graphics but achieving low Motion-to-Photon (MTP) latency while maintaining smooth playback is a significant challenge. Our real-world measurement study identifies Receive-to-Composition (R2C) latency, caused by ineffective jitter buffer management, as the primary factor contributing to increased MTP latency. To address this, we introduce JitBright, a client-side optimization strategy that dynamically reduces MTP latency through adaptive jitter buffer management. By adjusting buffer levels based on smoothing playback probability and implementing proactive keyframe requests to mitigate frame dependency, JitBright minimizes both active and passive waiting times. Our large-scale evaluation, conducted over 591,000 sessions across diverse network conditions (WiFi, 4G, 5G) and device types, demonstrates significant improvements in user experience. JitBright reduces median R2C latency by up to 87.5%, increases the proportion of sessions meeting strict MTP latency requirements by 6%–27%, and decreases the video freeze rate from 2.4%–2.8% to 0.4%–1.0%.

Sparse network monitoring, a breakthrough technology for cost-effective network-wide monitoring, has garnered significant attention from researchers and network equipment providers. By measuring only a subset of paths and nodes, it leverages the network’s low-rank property to obtain comprehensive monitoring data. However, a previously unnoticed vulnerability called the"global diffusion vulnerability"poses a significant threat to sparse network monitoring. This vulnerability suggests that if a few measurement samples are tainted, the entire network monitoring data can become inaccurate, leading to potential network failures and adverse effects on routing and bandwidth allocation. This paper presents the first exploration of the"global diffusion vulnerability"to launch effective attacks on sparse network monitoring. Sparse monitoring often employs various imputation models to estimate unmeasured data and collects multiple perspectives of network-wide data over extended periods. The challenges in attacking sparse monitoring lie in designing perturbations that can impact all views of network-wide data over time, regardless of the specific imputation models, while remaining unobtrusive. To tackle these challenges, we propose ModelFreeUP, the first perturbation generation algorithm designed for sparse network monitoring. ModelFreeUP creates imputation model-free, universal, and unobtrusive perturbations that exert a significant influence on multiple perspectives of network-wide data over time. Our experiments demonstrate that ModelFreeUP effectively disrupts the sparse monitoring process, causing substantial deviations in the network-wide monitoring data at a relatively low attack cost. Furthermore, when the manipulated monitoring data is used for downstream routing tasks, it triggers 100% Maximum Link Utilization in the Abilene network, indicating network congestion or failure. By shedding light on these critical mismeasurement issues, our work emphasizes the need for robust countermeasures against adversarial attacks in the network monitoring domain.

Packet processing in modern routers and switches relies on rule matching, primarily performed by two core modules: IP prefix lookup for next-hop determination and packet classification for multi-field policy enforcement. However, most existing algorithms are rule-centric and assume uniform rule access, overlooking the highly skewed nature of real-world network traffic. Such mismatch between static rule organization and dynamic traffic behavior leads to inefficiency in both lookup and classification. To address this limitation, we propose a Traffic-aware Lookup and Forwarding (TLF) framework that leverages traffic measurement with lookup operations, enabling online adaptation to dynamic traffic patterns and frequent rule updates. Experimental results demonstrate that TLF provides 1.04×–3.37× speedups for lookup and forwarding over state-of-the-art algorithms, while substantially reducing both memory overhead and construction time. Furthermore, integrating TLF into Vector Packet Processor (VPP) and Open vSwitch (OVS) results in throughput improvements of 2.61× and 4.88×, respectively.

High-quality remote sensing imagery plays a vital role in environmental monitoring and disaster management. However, transmitting these images is challenging due to the unstable signal-to-noise ratio (SNR) and bandwidth limitations encountered in remote communications. Semantic communication, particularly deep learning-based methods, offers a promising solution by jointly optimizing source and channel coding to achieve data compression and noise resilience. Nevertheless, existing methods struggle to cope with varying channel noise and bandwidth, leading to unsatisfactory image reconstruction quality. To address these challenges, we propose a satellite-ground compression and transmission system called Adaptive Residual Joint Source-Channel Coding (ARJSCC), which is based on Deep Joint Source-Channel Coding (DeepJSCC). The ARJSCC system compresses remote sensing images into semantic information and residuals to achieve low overhead transmission and high-quality reconstruction. ARJSCC utilizes an attention module to adjust the semantic preference of the model for different SNRs, and deploys a variance-based position mask module to flexibly vary the semantic length and further compress it. These designs enable ARJSCC to automatically adapt to varying noise and bandwidth conditions. Moreover, for the residual, we apply BPG to compress it to reduce the transmission cost and design the corresponding enhancement module to recover its details from the noise-affected compressed residual. We experimentally compare our ARJSCC with the recent DeepJSCC-based wireless image transmission models in low-resolution dataset and high-resolution remote dataset under multiple wireless channel environments. The experimental results show that ARJSCC can achieve high reconstruction quality exceeding 44dB, and outperform the competitors by 4-6db even under low SNR and bandwidth environments.

Single-cell transcriptomics describes complex molecular features at the individual cell level, serving various roles in biological research, such as enhancing gene expression and predicting drug responses. Due to transcriptomic data structurally resembling sequential data, many researchers have trained numerous transformers on extensive transcriptomic datasets. However, they have consistently neglected to explore the intrinsic properties of the data and the appropriateness of their chosen model architecture. In this paper, we carefully investigate the nature of transcriptomics, identifying three overlooked problems: 1) long-tailed data problem, 2) model selection problem, and 3) evaluation problem. Consequently, by applying the weighted sampling strategy, we address the long-tailed data problem and achieve consistent improvement across all settings. By adapting different model structures to transcriptomic data, we discover that transformers are not the only option. By developing three downstream tasks and fair evaluation metrics, we establish a simple and comprehensive benchmark to validate the effectiveness of models for transcriptomics. Through extensive experiments, we clarify the misunderstandings in the traditional methods and provide competitive baselines, thereby paving the way for future research in this field.

FPGAs are gaining popularity in the cloud as accelerators for various applications. To make FPGAs more accessible for users and streamline system management, cloud providers have widely adopted the shell-role architecture on their homogeneous FPGA servers. However, the increasing heterogeneity of cloud FPGAs poses new challenges for this architecture. Previous studies either focus on homogeneous FPGAs or only partially address the portability issues for roles, while still requiring laborious shell development for providers and ad-hoc software modifications for users.

As deep learning-based website fingerprinting (WF) attacks become increasingly accurate, user privacy faces mounting risks. Existing defenses struggle with the discrete nature of packet direction sequences, rendering gradient-based optimization infeasible and leading to inefficient, heuristic-based perturbation solutions. We propose a novel defense framework that bridges this gap by introducing gradient---aligned offset vectors and a cosine similarity---based reward to evaluate and select perturbation candidates aligned with the gradient direction. We further design a parallel reward computation algorithm to improve efficiency and integrate it into GAPDiS, a universal perturbation generation method that combines gradient guidance with improved tabu search for global optimization. For practical deployment, GAPDiS supports both PT bridge and P4 switch implementations. Experiments on the AWF dataset show that GAPDiS reduces the classification accuracy of WF models from over 98% to below 7% with only 2.56% bandwidth overhead---achieving a 68.1% improvement over state-of-the-art methods.

360-degree video is a panoramic video technology designed to offer audience an immersive visual experience. In Motion Constrained Tile Set (MCTS)-based streaming schemes, the server only updates Field-Of-View (FOV) coordinates when codec generating keyframes, thus the keyframe interval significantly impacts FOV updates and interactivity. However, reducing the keyframe interval poses greater challenges for network transmission and encoding/decoding overhead. To address these issues, we design and implement AKI360, a 360-degree video streaming system with an Adaptive Keyframe Interval (AKI) mechanism along with Quantization Parameter (QP) adjustments. Extensive experiments show that AKI360 reduces the motion stall duration by 31% to 74% and FOV update interval by 78% to 86% comparing with the real-time approaches, and eliminates the blank area in the best-case comparing with the state-of-the-art pre-encoded approach. Meanwhile, AKI360 improves the video quality by up to 0.78 decrease in NIQE while maintaining comparable frame rate.

Matrix completion is a method for imputing missing data, typically based on the assumption of a low-rank structure. However, in practice, various factors can obscure this structure, leading to a perceived high-rank nature. Recently, a few studies begin to address high-rank data completion, their methods rely on specific hypothesis distributions that are often impractical to validate in real-world scenarios. Therefore, in this paper, we tackle high-rank data completion without any hypothesis distribution. Firstly, we theoretically demonstrate that the Radial Basis Function (RBF) kernel feature mapping has the capability to transform general high-rank data into low-rank data in a higher-dimensional feature space. Secondly, combining with the adaptive row and column neighbor information, a novel graph-based high-rank matrix completion algorithm is developed. Thirdly, experiments on four real datasets across three domains demonstrate that the proposed method reduces reconstruction error by up to 63% compared to the second-best method at the same missing rate. Furthermore, to achieve similar accuracy, it requires up to 40% fewer samples. Our code is released at https://github.com/shiqinyeah/Graph-HRMC.git.

Recent advances in lightweight time series forecasting models suggest the inherent simplicity of time series forecasting tasks. In this paper, we present CMoS, a super-lightweight time series forecasting model. Instead of learning the embedding of the shapes, CMoS directly models the spatial correlations between different time series chunks. Additionally, we introduce a Correlation Mixing technique that enables the model to capture diverse spatial correlations with minimal parameters, and an optional Periodicity Injection technique to ensure faster convergence. Despite utilizing as low as 1% of the lightweight model DLinear’s parameters count, experimental results demonstrate that CMoS outperforms existing state-of-the-art models across multiple datasets. Furthermore, the learned weights of CMoS exhibit great interpretability, providing practitioners with valuable insights into temporal structures within specific application scenarios.

Time series anomaly detection (TSAD) underpins real-time monitoring in cloud services and web systems, allowing rapid identification of anomalies to prevent costly failures. Most TSAD methods driven by forecasting models tend to overfit by emphasizing minor fluctuations. Our analysis reveals that effective TSAD should focus on modeling "normal" behavior through smooth local patterns. To achieve this, we reformulate time series modeling as approximating the series with smooth univariate functions. The local smoothness of each univariate function ensures that the fitted time series remains resilient against local disturbances. However, a direct KAN implementation proves susceptible to these disturbances due to the inherently localized characteristics of B-spline functions. We thus propose KAN-AD, replacing B-splines with truncated Fourier expansions and introducing a novel lightweight learning mechanism that emphasizes global patterns while staying robust to local disturbances. On four popular TSAD benchmarks, KAN-AD achieves an average 15% improvement in detection accuracy (with peaks exceeding 27%) over state-of-the-art baselines. Remarkably, it requires fewer than 1,000 trainable parameters, resulting in a 50% faster inference speed compared to the original KAN, demonstrating the approach’s efficiency and practical viability.

Network telemetry has seen an increasing trend of deploying approximate measurement algorithms (e.g., sketches) on programmable switches due to their ability to provide line-rate speed, high measurement accuracy, and low memory cost.Heap, a vital component of many of measurement algorithms, hinders their deployment because of the difficulties in incorporating it into pipelines.In this paper, we introduce PipHeap, a pipeline-friendly, binary-tree-based min heap that can enhance existing sketches without introducing additional errors.Through evaluation with real-world datasets, we demonstrate that PipHeap can reduce the error of these integrated algorithms by 33% to 97% (78% on average) under the same memory allocation.We have successfully implemented PipHeap and its combination with six different sketches in our testbed, and successfully extended other approximate algorithms (e.g.Space-Saving) onto programmable switch platforms.We have made all code associated available as open-source.

To approximate sums of values in key-value data streams, sketches are widely used in databases and networking systems.They offer high-confidence approximations for any given key while ensuring low time and space overhead.While existing sketches are proficient in estimating individual keys, they struggle to maintain this high confidence across all keys collectively, an objective that is critically important in both algorithm theory and its practical applications.We propose ReliableSketch, the first to control the error of all keys to less than Λ with a small failure probability Δ, requiring only 𝑂 (1 + Δ ln ln( 𝑁 Λ )) amortized time and 𝑂 ( 𝑁 Λ + ln( 1 Δ )) space.Furthermore, its simplicity makes it hardware-friendly, and we implement it on CPU servers, FPGAs, and programmable switches.Our experiments show that under the same small space, ReliableSketch not only keeps all keys' errors below Λ but also delivers competitive throughput among accuracy-oriented baselines, outperforming * Both authors contributed equally to this research.

The evolution of mobile networks toward ubiquitous connectivity envisioned by International Mobile Telecommunications-2030 has caused a surge in control plane traffic. A deep understanding of the control plane's internal characteristics and mechanisms is crucial for delivering optimal services. However, existing measurements often neglect the control plane or treat it as an opaque box, focusing on overall performance instead of its intrinsic characteristics.

Effective incident management in large-scale microservice systems demands both accurate anomaly detection (AD) and precise root cause localization (RCL) across heterogeneous data modalities. However, existing approaches often treat these tasks in isolation, resulting in redundant maintenance, delayed response, and the absence of shared diagnostic context. While recent efforts have explored unified frameworks to support both tasks, these approaches often suffer from high falsealarm rates due to cross-modal interference. To address these issues, we propose DeST, an unsupervised decoupled spatiotemporal framework that jointly performs anomaly detection and root cause localization. DeST proposes a multi-stage fusion strategy that decouples temporal and spatial feature learning to mitigate cross-modal interference and prevent cross-modal interference. Furthermore, it incorporates task-specific modal routing to direct learned representations to different tasks, enhancing both detection and localization accuracy. To ensure robustness against transient noise, DeST designs a Differential Multi-Scale Convolutional Network (DMCN) for noise-resistant temporal feature representation. We evaluate DeST on two real-world microservice benchmarks, where it achieves a perfect F1-score of $\mathbf{1. 0 0}$ for anomaly detection and outperforms existing methods in root cause localization accuracy. Ablation studies highlight the effectiveness of key components. Our unified framework reduces false alarms in anomaly detection and streamlines root cause localization, providing a robust and practical solution for microservice incident management.

Time-Sensitive Networking (TSN) is a fundamental technology for enabling deterministic communication in industrial Internet applications. Existing TSN traffic scheduling research primarily focuses on optimizing the scheduling of timetriggered (TT) flows to ensure low-delay transmission for these periodic and time-sensitive flows. However, another critical class of traffic exists in TSN that has received little attention-eventtriggered (ET) flows, such as sensor exception alarms. Unlike TT flows, ET flows exhibit higher time sensitivity and demand rapid response to ensure system security. Despite their importance, ET flows have been largely overlooked in prior studies. A few works only have explored dynamically expanding scheduling windows or sharing time slots to accommodate ET flows. However, these approaches treat ET flows as isolated events, neglecting the causal relationships between them. This oversight results in inefficient and unreliable ET flow transmission. To address this limitation, we propose GP-TSN, an event-triggered traffic scheduling framework based on causal inference. Firstly, GP-TSN introduces a Spatio-Temporal Graph Attention-based Hawkes Process (SGATPP) to model and mine event relationships, enabling the inference of future ET flows. Secondly, GP-TSN employs a geometric abstraction-based scheduling strategy to allocate slots for the inferred ET flows, ensuring compliance with TT/ET flow constraints. Additionally, a slot recycling mechanism is incorporated to minimize resource waste. By leveraging the causal dependencies among ET flows, GP-TSN enhances scheduling efficiency and improves the reliability of ET flow transmission. Experiments across four datasets demonstrate that SGATPP achieves superior event inference accuracy (F1-score up to 62.25 %). Moreover, under the condition of ensuring the transmission performance of TT flows, GP-TSN increases the number of ET flows transmitted with the minimum end-to-end delay by 1.7 to 9.7 x.

Mobile crowd sensing (MCS) has become a new paradigm for environment sensing. However, the sensing data often face the challenge of missing values, which can impact the performance of subsequent tasks. Although some deep learning-based imputation methods perform well, they still struggle with insufficient training data due to high missing rate and long-term missing data. To address these challenges, we propose a Historical Data-based Diffusion Imputation (HDDI) method. Unlike existing deep learning-based imputation methods, we design a historical data supplement module to match and fuse historical data to supplement the training data. Additionally, we propose a diffusion imputation module that utilizes the supplement training data to achieve high-accuracy imputation even under high missing rate and long-term missing scenarios. We conduct extensive experiments on four public datasets, the results show that our HDDI outperforms baseline methods across four datasets. Particularly, when the data missing rate is 90%, HDDI improves accuracy by 25.15% compared to the best baseline method in the random missing scenario, and by 13.64% in the long-term missing scenario.

Real-time video (RTV) systems place high demands on ultra low-latency (i.e., less than 100 ms). However, our large-scale measurements reveal that a significant portion of users still experience high video frame latency due to bandwidth jitters. Existing solutions attempt to mitigate this issue by lowering the sender's future video frame encoding bitrate. Nevertheless, as shown in our controlled experiments, they fail to drain existing packets queued on the bottleneck node (i.e., the 5G base station and Wi-Fi access point), still suffering from high tail latency as bandwidth decreases. In this paper, we propose Co-RTV, a collaborative RTV system that achieves predictable latency control. Specifically, Co-RTV enables endpoint-network collaboration between the bottleneck node and the sender. The collaboration speeds up the release of packets queued at the bottleneck node and facilitates accurate latency control at the RTV sender through scalable QoE-driven flow control. Extensive experiments in emulated networks and on a 5G testbed demonstrate the superior performance of Co-RTV, with tail latency reductions of 69.1% and 70.5%, respectively.

Packet classification is a critical component for accurately categorizing traffic in network systems. The efficiency of packet classification algorithms is primarily determined by two key factors: the classifier's data structure and the characteristics of the traffic being classified. While significant efforts have been made to optimize data structures, the potential of leveraging traffic characteristics remains underexplored. In this study, we revisit the network dataplane by integrating the network measurement module with the packet classification module. We propose an innovative Network-aware Packet Classification system (NPC) that utilizes sketch techniques to extract network traffic features. These features guide the construction of decision trees, enabling efficient and adaptable packet classification across diverse network environments. Experimental results demonstrate that the NPC achieves speedups ranging from 1.86× to 23.88× over state-of-the-art algorithms, while significantly reducing memory overhead and construction time, highlighting its practical value in real-world scenarios. Furthermore, integrating NPC into Open vSwitch (OVS) yields throughput improvements of 10.71× to 13.01× compared to the native OVS.

Access Control Lists (ACLs) are crucial for ensuring the security and integrity of modern cloud and carrier networks by regulating access to sensitive information and resources. However, previous software and hardware implementations no longer meet the requirements of modern datacenters. The emergence of FPGA-based SmartNICs presents an opportunity to offload ACL functions from the host CPU, leading to improved network performance in datacenter applications. However, previous FPGA-based ACL designs lacked the necessary flexibility to support different rulesets without hardware reconfiguration while maintaining high performance. In this paper, we propose HACL, a heterogeneous and adaptive architecture for decision-tree-based ACL engine on FPGA. By employing techniques such as tree decomposition and recirculated pipeline scheduling, HACL can accommodate various rulesets without reconfiguring the underlying architecture. To facilitate the efficient mapping of different decision trees to memory and optimize the throughput of a ruleset, we also introduce a heterogeneous framework with a compiler in CPU platform for HACL. We implement HACL on a typical SmartNIC and evaluate its performance. The results demonstrate that HACL achieves a throughput exceeding 260 Mpps when processing 100K-scale ACL rulesets, with low hardware resource utilization. By integrating more engines, HACL can achieve even higher throughput and support larger rulesets.

Detailed system operations are recorded in logs. To ensure system reliability, developers can detect system anomalies through log anomaly detection. Log parsing, which converts semi-structured log messages into structured data, is a crucial step in log anomaly detection and advanced program analysis and verification. Despite the availability of various log parsing tools, they generally suffer from low parsing accuracy and slow efficiency due to the ignorance of variable characteristics and the use of costly pairwise comparison methods. In this paper, we propose a TCMS framework to parse logs, consisting of two main technologies. First, by studying 16 public log datasets, we find that most log variable tokens are structured variable tokens. Based on this discovery, we propose a token conversion algorithm to improve parsing accuracy. This algorithm converts the changed parts in structured variable tokens into wildcards (‘$< *> $’), preventing these tokens from being directly identified as constant tokens. Second, to improve efficiency, we propose the LogMLCS algorithm, which intelligently constructs a graph to facilitate the extraction of common parts from multiple log messages at once, instead of using pairwise comparisons. Comprehensive experiments conducted on 16 log datasets reveal that our TCMS outperforms seven other parsing methods, achieving the highest parsing accuracy at the fastest speed. Furthermore, experimental results from running a log anomaly detection algorithm in conjunction with different log parsing methods demonstrate that TCMS significantly boosts detection accuracy. For instance, on the OpenStack dataset, our TCMS-facilitated log anomaly detection algorithm achieves a perfect F1-score, precision, and recall of 100% each, surpassing the best peer method by 32.2, 0.8, and 19.5 percentage points, respectively.

Detecting anomalous BGP (Border Gateway Protocol) messages is critical for securing inter-domain routing systems over autonomous system (AS)-level networks. The dynamic nature of routing policies, massive scale of global routes, and incomplete global topology visibility make BGP anomalies exceptionally challenging to identify—let alone trace back to malicious or misconfigured ASes. To effectively overcome these barriers, this paper proposesGraphBGP, a novel BGP anomaly detection method that dynamically constructs real-time AS-level topologies, achieves precise anomaly detection and classification, and accurately traces malicious or misconfigured ASes. Specifically, to address the evolving nature of BGP routing status,GraphBGPconstructs an attributed AS-level graph that dynamically integrates node and edge attributes. It intelligently tracks BGP updates to refresh this graph efficiently. Leveraging this enriched, up-to-date representation,GraphBGPemploys tailored detection and tracing models grounded in graph convolutional networks (GCNs), enabling precise anomaly identification and source tracing. Comprehensive experiments with real-world and synthetic datasets demonstrate thatGraphBGPachieves state-of-the-art anomaly detection accuracy while significantly reducing inference time, even under partial BGP network visibility. Furthermore,GraphBGPprecisely traces malicious or misconfigured ASes within a short time period of 7 milliseconds after anomaly detection, enabling rapid mitigation.

Sparse data gathering has become a promising solution for reducing measurement costs by leveraging the inherent sparsity of data. However, most existing approaches rely on low-dimensional models such as compressive sensing or matrix completion, which are limited in capturing complex high-dimensional structures. To overcome these limitations, we proposeTensorMon, a novel tensor-based sparse data gathering framework that introduces a cuboid sampling strategy to more effectively exploit multidimensional correlations. Unlike traditional entry-based or tube-based sampling, TensorMon introduces the innovative concept ofcuboid sampling. We further develop a lightweight sampling scheduling algorithm and a non-iterative inference algorithm to ensure efficient measurement planning and accurate reconstruction of unmeasured data. Theoretical analysis establishes a new performance bound for our sampling strategy, which is significantly lower than those in existing literature. To validate our theoretical findings, we conduct extensive experiments on four real-world datasets: two network monitoring datasets, a city-scale crowd flow dataset, and a road traffic speed dataset. Experimental results demonstrate that TensorMon achieves substantial reductions in measurement cost, delivers high inference accuracy, and ensures rapid data recovery, highlighting its effectiveness and practicality across diverse application scenarios.

Deep neural networks (DNNs) have made great breakthroughs and seen applications in many domains. However, the incomparable accuracy of DNNs is achieved with the cost of considerable memory consumption and high computational complexity, which restricts their deployment on conventional desktops and portable devices. To address this issue, low-rank factorization, which decomposes the neural network parameters into smaller sized matrices or tensors, has emerged as a promising technique for network compression. In this article, we propose leveraging the emerging tensor ring (TR) factorization to compress the neural network. We investigate the impact of both parameter tensor reshaping and TR decomposition (TRD) on the total number of compressed parameters. To achieve the maximal parameter compression, we propose an algorithm based on prime factorization that simultaneously identifies the optimal tensor reshaping and TRD. In addition, we discover that different execution orders of the core tensors result in varying computational complexities. To identify the optimal execution order, we construct a novel tree structure. Based on this structure, we propose a top-to-bottom splitting algorithm to schedule the execution of core tensors, thereby minimizing computational complexity. We have performed extensive experiments using three kinds of neural networks with three different datasets. The experimental results demonstrate that, compared with the three state-of-the-art algorithms for low-rank factorization, our algorithm can achieve better performance with much lower memory consumption and lower computational complexity.

The advent of Software Defined Networking (SDN) and Network Function Virtualization (NFV) has revolutionized the deployment of software-based routing and forwarding devices in cloud and network systems. Yet, the performance of IPv6 route lookup in these devices remains a significant challenge due to two main factors: 1) the longer IPv6 addresses, which hinder high-speed lookup, and 2) the huge IPv6 IP address space, necessitates adaptability to varied length-based prefix distributions across various network scenarios. Existing IP lookup algorithms fall short in addressing these IPv6-specific challenges. To address these challenges, this paper proposes a novel Heuristic Binary Search (HBS) scheme. Building on the classical “Binary Search on Prefix Lengths” scheme, HBS employs three innovative techniques to achieve adaptive and fast IPv6 lookups with incremental updates: 1) a heuristic binary search method for fast lookup; 2) a tree rotation method for dynamic adjustment of binary search tree shapes in response to changes in prefix distribution; and 3) the introduction of the Associated Marker List (AML), a new data structure aimed at facilitating rapid incremental prefix updates. Our theoretical proofs and comprehensive evaluations demonstrate HBS’s superiority in lookup performance, dynamic adaptability, update speed, and memory efficiency.

Network distance measurement is crucial for evaluating network performance, attracting significant research attention. However, conducting measurements for the entire network is exceedingly expensive and time-consuming, making the reduction of network distance measurement costs a top priority. The tensor completion method efficiently reduces measurement costs by utilizing a small amount of measured data to estimate the entire network’s distance data. Unfortunately, current tensor completion methods still suffer from issues such as complex sample selection, high measurement overhead, slow recovery, and low inference accuracy. To address the aforementioned challenges, we present an online network-wide distance measurement scheme. In this approach, continuous distance data are structured into sliding-window-based tensors. Our method incorporates a lightweight sample selection algorithm with a lowest sampling bound and a rapid, accurate unmeasured data inference algorithm. We have conducted extensive experiments using four real network distance datasets and two citywide crowd flow datasets. The empirical evaluations demonstrate the effectiveness of our approach, particularly in reducing measurement costs and enhancing data recovery accuracy.

Deep reinforcement learning (DRL) has been used in congestion control algorithms (CCAs) for its ability to adapt to different network environments. However, its effectiveness is often hindered by the limited availability of training data and constrained training scales. While it has been proved that combining rule-based (expert) CCAs as a guide for DRL (namely hybrid CCAs) can address this limitation, we show through experimental measurements that rule-based CCAs potentially restrict action exploration of DRL models and may cause the DRL models to overly rely on them for higher reward gains. To address this gap, this paper proposes Marten, a framework that improves the effectiveness of rule-based CCAs for DRL. Marten’s key innovations include an entropy-based dynamic exploration scheme that expands the exploration of DRL, and a reward adjustment scheme to prevent the DRL models’ over-reliance on experts in hybrid CCAs. We have implemented Marten in both simulation platform OpenAI Gym and deployment platform QUIC. Experimental results in both emulated and production networks demonstrate Marten can improve throughput by 0.31% and reduce latency by 12.69% on average compared to the state-of-the-art hybrid CCAs. Compared to BBR, Marten achieves a 2.79% increase in throughput and an 11.73% reduction in latency on average.

The surge in demand for latency-sensitive services has propelled network distance measurement to the forefront of networking research. Utilizing the low-rank structure of full network data, the tensor completion method can efficiently estimate network distance from partially sampled distance data measured from a small set of node pairs. However, its performance is affected by sampling algorithm limitations, including unreliability and high overhead in dynamic networks. To tackle these challenges, we propose tube-based sampling as an alternative to point-based sampling, utilizing a partition-based algorithm to incorporate randomness for improved reliability. Additionally, we introduce a Tube Length Identification Algorithm to dynamically adjust tube length based on network status, balancing scheduling overhead reduction with estimation accuracy. Experimental results on three real network distance datasets, compared against 13 baseline algorithms, demonstrate the high accuracy and low scheduling overhead of our approach.

Network traffic matrices often suffer from incompleteness and sparsity due to various factors, including network device policies and system limitations. The incompleteness can undermine the reliability and accuracy of network traffic monitoring services, negatively impacting downstream tasks such as network planning and fault diagnosis. Our focus is on network traffic data recovery, intending to infer missing traffic data from partial measurements accurately. Although tensor completion algorithms are quite effective in recovering traffic data, existing models often overlook cross-domain traffic relationships and fail to account for the order and distribution of traffic, leading to reduced recovery accuracy. To overcome these limitations, we propose a new contrastive tensor completion model that utilizes pairwise joint embedding. This model employs innovative techniques, including a cross-domain embedding module to avoid information homogeneity and enhance model expressiveness, a contrastive module to preserve the order and distribution of traffic volumes, and an injective interaction module to map entry embeddings into the numerical space, ensuring convergence and retaining the original numerical distribution. Experiments on three real-world network traffic datasets show that our model significantly reduces the error in missing traffic data recovery compared to other existing models while maintaining traffic order and distribution.

Accurately detecting traffic anomalies becomes increasingly crucial in network management. Algorithms that model the traffic data as a matrix suffers from low detection accuracy, while the work using the tensor model often assumes the tensor is regular without considering that network nodes may dynamically join in or leave, which will fail in a practical network with the change of node set as a result of mobility and churn behaviors. We propose a novel Tensor Recovery scheme in a Dynamic Network (TRDN) with traffic data modeled as a practical irregular tensor for accurate anomaly detection. To take advantage of correlations among small tensors, each formed with a short time duration to capture more hidden information in the data for higher detection accuracy, we propose several novel techniques: 1) a new joint tensor factorization model to capture the characteristic shared by the common nodes of small tensors, 2) a tensor partition algorithm to identify the data that can be applied to train the shared parameters efficiently, and 3) a bar-based algorithm that partitions nodes into the minimum number of no-overlapping subsets to form the shared tensor model. Extensive experiments on two Internet traffic data sets, Abilene and GÈANT, demonstrate the effectiveness of the proposed TRDN.

Deep learning has made remarkable progress across many domains, enabled by the capabilities of over-parameterized neural networks with increasing complexity. However, practical applications often necessitate compact and efficient networks because of device constraints. Among recent low-rank decomposition-based neural network compression techniques, Tucker decomposition has emerged as a promising method which effectively compresses the network while preserving the high-order structure and information of the parameters. Despite its promise, designing an efficient Tucker decomposition approach for compressing neural networks while maintaining accuracy is challenging, due to the complexity of setting ranks across multiple layers and the need for extensive fine-tuning. This paper introduces a novel accuracy-aware network compression problem under Tucker decomposition, which considers both network accuracy and compression performance in terms of parameter size. To address this problem, we propose an efficient alternating optimization algorithm that iteratively solves a network training sub-problem and a Tucker decomposition sub-problem to compress the network with performance assurance. The proper Tucker ranks of multiple layers are selected during network training, enabling efficient compression without extensive fine-tuning. We conduct extensive experiments, implementing image classification on five neural networks using four benchmark datasets. The experimental results demonstrate that, without the need for extensive fine-tuning, our proposed method significantly reduces the model size with minimal loss in accuracy, outperforming baseline methods.

IP lookup aims at identifying the longest prefix match within routing tables to determine the forwarding path for packets. The increase in IPv6 address length makes IP lookup particularly difficult, requiring more efficient lookup mechanisms to handle the expanded address space and ensure the timely and accurate routing of packets. Existing IPv6 lookup algorithms focus on constructing efficient data structures to enhance lookup performance. However, given the inherent characteristics of network traffic distribution and the varying hit probabilities of nodes within the lookup structure, there is still room for optimization. Our study introduces a new IPv6 routing lookup scheme that utilizes the characteristics of network traffic to guide the construction of lookup data structures. Experimental results indicate that the lookup performance of the traffic-adaptive algorithm is 1.1 to 2.2 times that of conventional algorithms. Additionally, our work designs a traffic-adaptive routing system, which includes an adaptive cache structure capable of responding to dynamic changes in network traffic. The throughput of our proposed system is 1.7 to 2.8 times that of systems implementing only basic algorithms.

Open vSwitch (OvS) has been widely used in cloud networks in view of its programmability and flexibility. However, we observe a huge performance drop when it loads practical cloud networking services (e.g., tunneling and firewalling). Our further analysis reveals that the root cause lies in the gap between the needs of supporting various selections of packet header fields and the one-size-fits-all data path in the vanilla OvS. Motivated by this, we design Hoda, a high-performance OvS dataplane with multiple specialized data paths. Specifically, Hoda constructs the specialized parser and microflow cache for each OpenFlow program so as to achieve lightweight parsing and caching. We also propose a configurable version of Hoda that introduces configuration knobs in the data path to ease specialization. The experiments with real-life OpenFlow rules show that Hoda achieves up to 1.7× speed up over the state-of-the-art OvS and 1.5× speed up over mSwitch. Hoda has also been deployed in a large cloud to serve various online services; the A/B test in the cloud reveals a 20% request process time reduction for Ngnix services.

Through providing cheap rack and network hosting services, third-party internet data centers (IDCs) have gained significant popularity among cloud service providers. Real-time monitoring of the quality of the IDC network and proactively alarming is crucial to guaranteeing the reliability of cloud services. The prevailing approach to addressing this problem involves utilizing active probes and making evaluations based on the results of single-link or multi-link probing. However, the existing efforts still tend to generate a significant number of unnecessary alerts, resulting in enormous operational costs. For this reason, we first build a large-scale distributed ping-based dial test system that enables monitoring the quality of the IDC network in a many-to-one probe mode. We develop an efficient exporter tool based on the standard Prometheus' data interface to ensure real-time and precise measurement data collection. To quickly and accurately detect potential network issues, we also design a multi-step heuristic-based fault detection and alarm method. Furthermore, we propose a comprehensive alarm life-cycle model based on the results of multi-link probing to guide alarm management in production practice. This system has been successfully deployed in the production environment of Sangfor company's managed cloud for over a year, enabling proactive diagnosis of hundreds of IDC gateway IP addresses. The actual statistical results indicate a significant improvement in the mean time to repair (MTTR) for IDC network failures, reducing it from a few hours to just a few minutes. The average daily number of alarms generated by this system is less than 15, decreasing approximately 85 % compared to before. The alarm accuracy exceeds 95 % and the false negative rate is less than 2 % ■

Tensor data is widely used in fields such as smart grids, cloud systems, and deep learning. As the scale of this data increases, storage and transmission costs rise significantly. Many tensor data exhibit low-rank structures, offering the potential for data compression through low-rank decomposition techniques. Tucker decomposition, a typical low-rank decomposition technique, achieves data compression and interpretability by capturing complex data correlations and representing the original tensor with a compact core tensor and factor matrices. However, the compression ratio provided by Tucker decomposition is often insufficient, particularly for large-scale tensors. To tackle this issue, we propose a robust low-rank tensor compression method that leverages Tucker decomposition with quantization and coding. Initially, we establish a robust Tucker decomposition framework that decomposes the low-rank tensor into a core tensor and factor matrices using well-designed Tucker rank-setting rules. This framework effectively handles noise and missing values. Subsequently, we conduct an in-depth analysis of the numerical characteristics of the core tensor and factor matrices within the Tucker decomposition framework. Based on their distinct characteristics, we design tailored quantization and coding schemes to compress the core tensor and factor matrices, respectively, thereby significantly improving the compression ratio of Tucker decomposition while maintaining high accu-racy. Through extensive experiments on four publicly available datasets (which can form 3 or 4 order tensors), we demonstrate that our approach can achieve compression ratios$4\times-10\times$higher than the best competitor, with recovery errors improved by 8% - 42%.

Sketch has been widely used in the field of large-scale data stream processing. However, common fixed-counter algorithms such as Count-Min Sketch have to allocate larger counters, which wastes a lot of memory due to the high skewness of real-world data streams. To reduce memory usage, we propose to dynamically adjust the counter size that matches the distribution of the data stream. We introduce BitMatcher, a fast global-adjusting algorithm that automatically adjusts the counter to the appropriate size to match the data stream. During stream processing, BitMatcher identifies items hashed into a bucket based on isolated fingerprints. If it overflows, BitMatcher changes the flag bits in the bucket and dynamically increases or shrinks the size of some counters in a fine-grained manner. BitMatcher can also relocate a cold item in the bucket with the idea of cuckoo hashing to preserve the potential hot item while achieving global load balancing. Through the above way of dealing with overflow caused by skewed data, BitMatcher precisely manipulates allocated bits and maximizes memory utilization. The experiments show that BitMatcher has high throughput and can outperform SOTA by up to 4 orders of magnitude in terms of accuracy. We also deployed BitMatcher on several platforms, showing its software and hardware scalability.

RDMA over Converged Ethernet (RoCEv2) employs Priority-based Flow Control (PFC) for a lossless fabric to maintain high performance. However, PFC can cause Deadlocks, which pauses traffic and potentially leads to severe exceptions for applications. Existing solutions solve deadlocks at a considerable cost, resulting in degradation of end-to-end network performance.We present Roundabout, a data plane scheme designed to detect and resolve deadlocks with minimal side effects. We first analyze how switches in different states contribute to deadlocks. Based on the analysis, we design an election-based distributed detection scheme that efficiently and robustly identifies deadlocks. By exploiting buffer configuration redundancy, we develop an innetwork collaborative packet scheduling scheme that forwards deadlocked packets to their destinations in a lossless manner, facilitating natural deadlock resolution. Additionally, we implement a barrier mechanism to ensure in-order packet delivery to the receiver. Both analysis and experiments demonstrate that Roundabout effectively detects and resolves deadlocks while minimizing side effects to the network, making it an ideal enhancement for PFC switches.

Distributed sparse deep learning has been widely used in many Internet-scale applications. Network communication is one of the major hurdles for training performance. In-network gradient aggregation on programmable switches is a promising solution for speeding up the performance. Nevertheless, existing in-network aggregation solutions are designed for the dense deep training, and fall short when used for the sparse training. To address this gap, we present Zebra based on our key observation on the extremely biased update frequency of parameters in distributed sparse deep training. Specifically, Zebra offloads only the aggregation for “hot” parameters that are updated frequently onto programmable switches. To enable this offloading and achieve high aggregation throughput, we propose solutions to address the challenges related to hot parameter identification, parameter orchestration and gradient aggregation as well as system reliability. We implemented Zebra on Intel Tofino switches and integrated it with PS-lite. Finally, we evaluate Zebra's performance through extensive experiments and show that it can speed up the gradient aggregation by$1.5 \sim 4 \times$and the end-to-end performance by$1.4 \sim 2.6 \times$.

Efficient and accurate parsing of unstructured logs is crucial for anomaly detection, root cause localization, and log compression. Although many existing works have made good progress relying on Large Language Models (LLMs) and prompt engineering techniques, most of them require a certain degree of labeling or few-shot prompts, which limits their applicability in large-scale real-time heterogeneous log environments. To tackle this issue, we develop LogGenius, a novel unsupervised log parsing framework. It initially enriches the diversity of the parsed logs by leveraging generative LLMs with zero-shot prompts. It then employs an unsupervised parsing model on the augmented log data to accomplish log parsing. In order to alleviate the impact of potential hallucination issues caused by generative LLMs, we conduct a meticulous analysis and summarize the biases inherent in LLMs when directly applying them to generate diversified logs. Building upon these insights, we propose an effective log diversity augmentation algorithm to mitigate the aforementioned concerns.We thoroughly evaluate LogGenius based on various open-source system runtime log datasets and a new alarm log dataset from a commercial cloud production environment. The experimental results demonstrate that LogGenius can improve the parsing accuracy by up to about 30%, and the parsing accuracy in unseen logs by up to about 100%, compared to the state-of-the-art unsupervised-based methods.

As the demand for online video content drives up bandwidth costs for content providers (CPs), there have been efforts to integrate cost-effective techniques to mitigate their bandwidth expenditure (e.g. using set-top boxes to share content). However, the use of such resources requires considerable effort to balance cost vs. user-perceived quality of service. This paper serves as a first step to quantify this trade-off. We collect and analyze data from a major CP that serves millions of users per day using both traditional CDN resources and alternative cheaper resources. Our analysis reveals that introducing cheaper alternative resources does not always yield anticipated cost savings and may lead to a reduction in quality of experience for users. We provide insights into the reasons behind these issues and propose strategies for better utilization of alternative network resources. We work with a major CP to deploy our proposals, and offer insights on how to better leverage different kinds of bandwidth resources for improved cost-efficiency and streaming delivery.

Log parsing involves extracting appropriate templates from semi-structured logs, providing foundational information for downstream log analysis tasks such as anomaly detection and log comprehension. Initially, the task of log parsing was approached by domain experts who manually designed heuristic rules to extract templates. However, the effectiveness of these manual rules deteriorates when certain characteristics of a new log dataset do not conform to the pre-designed rules. To address these issues, introducing large language models (LLM) into log parsing has yielded promising results. Nevertheless, there are two limitations: one is the reliance on manually annotated templates within the prompt, and the other is the low efficiency of log processing. To address these challenges, we propose a self-evolving method called SelfLog, which, on the one hand, uses similarpairs extracted by LLM itself in the historical data to act as the prompt of a new log, allowing the model to learn in a self-evolution and labeling-free way. On the other hand, we propose an N-Gram-based grouper and log hitter. This approach not only improves the parsing performance of LLM by extracting the templates in a group-wise way instead of a log-wise way but also significantly reduces the unnecessary calling to LLMs for those logs whose group template is already extracted in history. We evaluate the performance and efficiency of SelfLog on 16 public datasets, involving tens of millions of logs, and the experiments demonstrate that SelfLog has achieved state-of-the-art (SOTA) levels in 0.975’s GA, and 0.942’s PA. More importantly, without sacrificing accuracy, the processing speed has reached a remarkable 45,000 logs per second.

Time series anomaly detection (TSAD) has gained significant attention due to its real-world applications to improve the stability of modern software systems. However, there is no effective way to verify whether they can meet the requirements for real-world deployment. Firstly, current algorithms typically train a specific model for each time series. Maintaining such many models is impractical in a large-scale system with tens of thousands of curves. The performance of using merely one unified model to detect anomalies remains unknown. Secondly, most TSAD models are trained on the historical part of a time series and are tested on its future segment. In distributed systems, however, there are frequent system deployments and upgrades, with new, previously unseen time series emerging daily. The performance of testing newly incoming unseen time series on current TSAD algorithms remains unknown. Lastly, the assumptions of the evaluation metrics in existing benchmarks are far from practical demands. To solve the above-mentioned problems, we propose an industrial-grade benchmark TimeSeriesBench. We assess the performance of existing algorithms across more than 168 evaluation settings and provide comprehensive analysis for the future design of anomaly detection algorithms. An industrial dataset is also released along with TimeSeriesBench.

Large-scale cloud services frequently experience incidents that can have a significant impact on their stability. Incident triage is a critical process that assigns incidents to dedicated teams for resolution. However, traditional rule-based methods, commonly employed in various systems, have limitations due to a finite set of rules that necessitate continuous updates, leading to suboptimal performance. Current state-of-the-art approaches primarily rely on textual information, utilizing classifiers or unsupervised clustering. Unfortunately, the abundance of textual information, combined with considerable noise, presents a significant challenge to the accuracy of these methods. To tackle these challenges, we introduce COMET, an innovative system that utilizes an AutoExtractor to filter out non-critical logs and employs a Large Language Model (LLM) for keyword extraction. This approach effectively mitigates the complexity arising from disordered textual information. Additionally, COMET incorporates significant domain knowledge during keyword extraction, enhancing the LLM’s comprehension of the text. We deployed COMET on multiple cloud services within Microsoft, where it has operated continuously for over six months. Offline and online evaluations have shown that COMET achieves enhanced accuracy and reduced Time to Mitigation (TTM).

Microservice architecture has become a predominant paradigm in the software industry. This architecture necessitates robust end-to-end testing to ensure seamless integration of all components before deployment. Rapidly pinpointing issues when test cases fail is crucial for enhancing software development efficiency. However, in testing environments, the available trace is often sparse, and the system is continuously upgrading, which renders existing microservice-based root cause analysis (RCA) ineffective. To address these challenges, we propose SparseRCA. By assessing the abnormality of the exclusive latency, SparseRCA directly determines the probability of the root cause, solving the challenge of not being able to fully obtain the fault propagation information, such as call relationships in sparse trace scenarios. At the same time, by reconstructing the exclusive latency using the decoupled atomic span units, it solves the problem of latency prediction for new traces caused by frequent upgrades. We evaluate SparseRCA on real-world datasets from a large e-commerce system’s testing environment, where it demonstrates significant improvements over existing models. Our findings underscore the effectiveness of SparseRCA in addressing the challenges of RCA in microservice testing environments.

In large-scale online service systems, numerous Key Performance Indicators (KPIs), such as service response time and error rate, are gathered in a time-series format. KPI Anomaly Detection (KAD) is a critical data mining problem due to its widespread applications in real-world scenarios. However, KAD faces the challenges of dealing with KPI heterogeneity and noisy data. We propose KAD-Disformer, a KPI Anomaly Detection approach through Disentangled Transformer. KAD-Disformer pre-trains a model on existing accessible KPIs, and the pre-trained model can be effectively "fine-tuned" to unseen KPI using only a handful of samples from the unseen KPI. We propose a series of innovative designs, including disentangled projection for transformer, unsupervised few-shot fine-tuning (uTune), and denoising modules, each of which significantly contributes to the overall performance. Our extensive experiments demonstrate that KAD-Disformer surpasses the state-of-the-art universal anomaly detection model by 13% in F1-score and achieves comparable performance using only 1/8 of the finetuning samples saving about 25 hours. KAD-Disformer has been successfully deployed in the real-world cloud system serving millions of users, attesting to its feasibility and robustness. Our code is available at https://github.com/NetManAIOps/KAD-Disformer.

Domain Name System (DNS) converts domain names into IP addresses. The specific IP it returns to a client has significant implications for optimizing user experiences on web services. The establishment of Content Distribution Networks (CDNs) facilitates the spread of content across diverse cache servers, thereby enabling quick responses to user requests. But not all distributed Internet services have sufficient budget or resources to deploy CDN servers. For these services, is there a cost-efficient way to enhance users’ access experience to them? In this paper, we build a data-driven DNS resolver system named ActiveDNS. We conduct a historical analysis of billions of DNS request-response logs from a public DNS resolver. Inspired by these findings, we probed dozens of public DNS servers to obtain available IPs behind carefully selected target domain names and measure their performance metrics. We built a domain ip performance database of 2.9 million records that can be easily incorporated into the open-source DNS framework BIND via DLZ technology. ActiveDNS has been deployed in real-world scenarios and the evaluations reveal promising results. Compared to currently used DNS resolver, the 75th service round-trip time (RTT) for the IP returned by ActiveDNS decreased from 67 ms to 43 ms.

Increasing bandwidth demands of mobile video streaming pose a challenge in optimizing the Quality of Experience (QoE) for better user engagement. Multipath transmission promises to extend network capacity by utilizing multiple wireless links simultaneously. Previous studies mainly tune the packet scheduler in multipath transmission, expecting higher QoE by accelerating transmission. However, since Adaptive BitRate (ABR) algorithms overlook the impact of multipath scheduling on throughput prediction, multipath adaptive streaming can even experience lower QoE than single-path. This paper proposes Chorus, a cross-layer framework that coordinates multipath scheduling with adaptive streaming to optimize QoE jointly. Chorus establishes two-way feedback control loops between the server and the client. Furthermore, Chorus introduces Coarse-grained Decisions, which assist appropriate bitrate selection by considering the scheduling decision in throughput prediction, and Finegrained Corrections, which meet the predicted throughput by QoE-oriented multipath scheduling. Extensive emulation and real-world mobile Internet evaluations show that Chorus outperforms the state-of-the-art MPQUIC scheduler, improving average QoE by 23.5% and 65.7%, respectively.

Low-latency cloud rendering services use high-performance servers to provide mobile device users with exquisite graphics and convenient access experiences. Due to the complexity of the system and the diversity of impacting factors, identifying system bottlenecks has become a significant challenge. To demystify system performance, we build an online cloud rendering system to measure the latency distribution of its key components.

Time series Anomaly Detection (AD) plays a crucial role for web systems. Various web systems rely on time series data to monitor and identify anomalies in real time, as well as to initiate diagnosis and remediation procedures. Variational Autoencoders (VAEs) have gained popularity in recent decades due to their superior de-noising capabilities, which are useful for anomaly detection. However, our study reveals that VAE-based methods face challenges in capturing long-periodic heterogeneous patterns and detailed short-periodic trends simultaneously. To address these challenges, we propose Frequency-enhanced Conditional Variational Autoencoder (FCVAE), a novel unsupervised AD method for univariate time series. To ensure an accurate AD, FCVAE exploits an innovative approach to concurrently integrate both the global and local frequency features into the condition of Conditional Variational Autoencoder (CVAE) to significantly increase the accuracy of reconstructing the normal data. Together with a carefully designed "target attention" mechanism, our approach allows the model to pick the most useful information from the frequency domain for better short-periodic trend construction. Our FCVAE has been evaluated on public datasets and a large-scale cloud system, and the results demonstrate that it outperforms state-of-the-art methods. This confirms the practical applicability of our approach in addressing the limitations of current VAE-based anomaly detection models.

Network telemetry, characterized by its efficient push model and high-performance communication protocol (gRPC), offers a new avenue for collecting fine-grained real-time data. Despite its advantages, existing network telemetry systems lack a theoretical basis for setting measurement frequency, struggle to capture informative samples, and face challenges in setting a uniform frequency for multi-metric monitoring. We introduce FineMon, an innovative adaptive network telemetry scheme for precise, fine-grained, multi-metric data monitoring. FineMon leverages a novel Two-sided Frequency Adjustment (TFA) to dynamically adjust the measurement frequency on the Network Management System (NMS) and infrastructure sides. On the NMS side, we provide a theoretical basis for frequency determination, drawing on changes in the rank of multi-metric data to minimize monitoring overhead. On the infrastructure side, we adjust the frequency in real-time to capture significant data fluctuations. We propose a robust Enhanced-Subspace-based Tensor Completion (ESTC) to ensure accurate recovery of fine-grained data, even with noise or outliers. Through extensive experimentation with three real datasets, we demonstrate FineMon's superiority over existing schemes in reduced measurement overhead, enhanced accuracy, and effective capture of intricate temporal features.

Robust PCA is a popular anomaly detection technique and has been widely used in many applications. Although Robust PCA is promising, it is usually designed in a two-order matrix form, which is inferior to the tensor that can capture multilinearity features of data. Moreover, the detection accuracy under Robust PCA further suffers due to its sensitivity to the rank parameter which is hard to set in practice and the limitation of PCA method in capturing the non-linear feature in the data. To address the issues, we propose a Robust Tensor Convolutional Autoencoder (RTCAE) where the autoencoder instead of SVD is exploited to recover the normal data from the corrupted measurement tensor data. However, directly exploiting deep autoencoder may suffer from the problem of high memory consumption and computation overhead due to the large number of parameters used in autoencoder. To make our anomaly detection lightweight, we further design a Light Convolutional Autoencoder (LightCAE) which contains a compressed autoencoder by exploiting tensor factorization to largely compress the parameters while significantly reducing the computation complexity. We conduct extensive experiments on three real data traces to compare the performance of our proposed schemes (RTCAE and lightCAE) with that of seven baseline algorithms. The experiment results demonstrate that our proposed RTCAE achieves the highest anomaly detection accuracy. Moreover, our LightCAE requires over 60 times smaller memory storage than that required in RTCAE while achieving the similar anomaly detection accuracy.

Traffic sensor networks are widely applied in smart cities to monitor traffic in real-time and record huge volumes of traffic data. Exploiting such data to forecast future traffic conditions have the potential to enhance the decision-making capabilities of intelligent transportation systems, which attracts widespread attention from both industries and academia. Among them, network-wide prediction based on graph convolutional neural networks(GCN) has become mainstream. It models the spatial dependencies of sensors in a graph with a pre-defined Laplacian matrix based on the distances among sensors. However, understanding spatio-temporal traffic patterns is quite challenging as there is a huge difference in terms of traffic patterns during different periods or in different regions. In addition, the actual data collected can be polluted due to unavoidable data loss from severe communication conditions or sensor failures. Considering these issues, we propose a novel dynamic multiview spatial-temporal prediction framework which takes into consideration various factors, including local/global, short/long term spatio-temporal dependencies and their dynamic changes. To comprehensively track the dynamic spatio-temporal dependencies among traffic data, we creatively design two different modules to perceive the changes in traffic patterns. We first propose a dynamic Laplacian matrix learning module based on our theoretical derivation to estimate the Laplacian matrix of the graph for GCN timely. We creatively incorporate tensor decomposition into this module, where real-time traffic data are decomposed into a global component that is stable and depends on long-term temporal-spatial traffic relationships and a local component that captures the traffic fluctuations. We also design a self-attention based module to dynamically assign a weight to each part in traffic data. The spatio-temporal features from multiple views are deeply fused by a feature fusion module. The forecasting performance is evaluated with 5 real-time traffic datasets. Experiment results demonstrate that our framework can consistently outperform the state-of-the-art baselines and be more robust under noisy environments.

Video streaming is the most important mobile application today. To improve users’ quality of experience (QoE), the client player runs adaptive bitrate (ABR) algorithms that dynamically select the bitrate for video chunks based on throughput or delivery time predictions. This paper aims to design an accurate predictor for mobile adaptive streaming by investigating all its components, including input features, output target, and mapping function. We construct the first theoretical framework that reveals potential factors affecting chunk throughput and delivery time. To verify this framework, we provide formulation analysis and measurement observations based on 2500+ video sessions collected in real-world mobile networks. We find that previous works have failed to achieve accurate prediction due to overlooking the impact of the transport mechanism and application behavior on throughput. Furthermore, we show that throughput is a better target for data-driven predictors than delivery time, due to the long-tailed distribution of delivery time. Based on the above, we propose Lumos, a decision-tree-based throughput predictor that can be integrated into various ABR algorithms. Extensive experiments in real-world mobile Internet show that Lumos achieves high prediction accuracy and improves the QoE of MPC by 6.3%, and MPC+Lumos outperforms Pensieve by 19.2%.

Packet level measurement in the data plane provides a microscopic view of the network’s state. Although advances in programmable switches and routers make it possible to measure the Sequence of Packet Lengths and Arrival Times (SPLT) in the data plane, collecting this information remains challenging due to limited storage, processing resources, and bandwidth. To address this issue, we propose MES, which Measures and Encodes Simultaneously the packet length and timestamp when each packet passes through the Network Processor (NP) in the switch/router. We design the packet length compression and timestamp compression algorithms to be lightweight and implement the designed algorithms using simple operations supported by the network processor, while taking into account the computation constraints of the NP. Through extensive experiments on five packet traces, we demonstrate that our MES achieves high precision SPLT measurements (up to 99.82% cosine similarity) while reducing storage and bandwidth overhead by up to 87%. Simulations conducted on the BMV2 P4 software switch demonstrate that our designed SPLT measurement mechanism imposes little impact on network throughput and delay.

Layer-3 load balancing is a key topic in the networking field. It is well acknowledged that flowlet is the most promising solution because of its good trade-off between load balance and packet reordering. However we find its one significant limitation: it makes the forwarding paths of flows unpredictable. To address this limitation this paper presents BurstBalancer a simple yet efficient load balancing system with a sketch named BalanceSketch. Our design philosophy isdoing less changesto keep the forwarding path of most flows fixed which guides the design of BalanceSketch and our balance operations. We have fully implemented BurstBalancer in a small-scale testbed built with Tofino switches and conducted both large-scale event-level (NS-2) and ESL (electronic system level) simulations. Our results show that BurstBalancer achieves 5%$\sim$35% smaller FCT than LetFlow in symmetric topology and up to 30× smaller FCT in asymmetric topology while 58× fewer flows suffer from path changing. All related codes are open-sourced at GitHub

In network distance measurement, how to estimate the whole network distance data from partially observed samples has attracted lots of attention because of its significance for network performance evaluation. Matrix completion becomes the most effective approach. However, the two-dimension matrix can only capture the spatial features in the network distance data while ignoring the temporal features. To conquer the problem, few recent studies begin to model the network distance data as a three-dimension tensor and propose tensor completion approaches for distance estimation. Although promising, existing tensor completion approaches still suffer the problem of low recovery accuracy and high measurement cost because they ignore the history priority information. To fully utilize both spatial and temporal features hidden in the distance data, this paper formulates a novel History Priority Enhanced Tensor Completion (HPETC) for distance estimation as a weighted tensor nuclear norm minimization problem where the weight is defined based on the history subspaces information. To solve the weighted tensor nuclear norm minimization problem, we firstly transform it into a factorization-based Frobenius norm minimization problem to avoid costly T-SVD computations, and then propose an iterative algorithm to solve the transformed problem. We further derive a theoretical sampling bound that is lower than the existing sampling bound, thus leads a lower measurement cost. We demonstrate the effectiveness of the proposed algorithm by conducting extensive experiments using two real network distance datasets. The result shows that the proposed algorithm can not only improve the estimation accuracy but also reduce the sampling complexity compared to the state-of-the-art approaches.

Accurately identifying IoT device types is crucial for IoT security and resource management. However, existing traffic-based device identification algorithms incur high measurement, storage, and computation costs, as they continuously need to capture, store, and parse device traffic. To overcome these challenges, we propose an innovative framework that employs a discontinuous traffic measurement strategy, reducing the number of packets captured, stored, and parsed. To ensure accurate identification, we introduce several novel techniques. First, we propose a graph neural network-based tensor completion model to estimate missing traffic features in unmeasured time slots. Our model can utilize historical information to flexibly and efficiently estimate missing features. Second, we propose a convolutional neural network-based classifier for device identification. The classifier utilizes traffic features and node embeddings learned from the tensor completion model to achieve precise device identification. Through extensive experiments on real IoT traffic traces, we demonstrate that our framework achieves high accuracy while significantly reducing costs. For instance, by capturing only 30% of the packets, our framework can identify devices with a high accuracy of 0.9558. Moreover, compared to current tensor completion methods, our method can estimate missing values with higher accuracy and achieve a 1.53-fold speedup over the next-fastest baseline.

The rapid expansion of the Internet of Things (IoT) has led to growing concerns about the security of IoT devices. A crucial aspect of ensuring their security is IoT device identification, which involves pinpointing the specific type of device. Existing solutions, however, either necessitate complex feature engineering or struggle to handle the ever-increasing number of new devices in open IoT environments. To tackle these challenges, this paper introduces GraphIoT, a lightweight IoT device detection method based on graph classifiers. GraphIoT leverages lightweight flow information, such as packet length, direction, and timestamp, to create an IoT Device Traffic Graph Representation (IoT-DTGR). This representation offers a comprehensive view of IoT device flows while preserving features in bidirectional IoT Device-Gateway interactions. By transforming the IoT device detection problem into a graph classification problem, GraphIoT employs a powerful Graph Neural Network that takes into account both node and edge features, as well as subgraph structures in IoT-DTGRs, to classify graphs and consequently identify device types. Additionally, the paper proposes an incremental learning framework called CL-GraphIoT that continuously learns features of new IoT device flows without forgetting previously learned device features. This is achieved through two strategies: parameter sharing and sample replaying. The paper gathers a real-world dataset from 18 IoT devices and conducts experiments on two datasets: the gathered real-world dataset and an open-source dataset covering 21 IoT device types. The experimental results demonstrate that both GraphIoT and CL-GraphIoT outperform state-of-the-art methods, achieving high accuracy in device detection with fast processing speed.

The advent of Software Defined Networking (SDN) and Network Function Virtualization (NFV) has revolutionized the deployment of software-based routing and forwarding devices in modern network architectures. However, IPv6 route lookup remains a substantial performance bottleneck in these software-based devices due to two key challenges: (1) the longer addresses and prefixes, which hinder high-speed IPv6 lookup, and (2) the larger address space of IPv6 necessitates adaptability to varied length-based prefix distributions across various network scenarios. Current trie-based methods like SAIL and Poptrie have enhanced IPv4 lookup, but they struggle with adaptive and fast IPv6 lookup due to their fixed search scheme from short to long prefixes. To overcome these challenges, we propose a novel Heuristic Binary Search (HBS) scheme to achieve adaptive and fast IPv6 lookup. HBS refines the traditional "Binary Search on Prefix Lengths" scheme by incorporating two key techniques: (1) a heuristic binary search method for accelerated lookup and (2) a tree rotation method for dynamic adjustment of binary search tree shapes in response to changes in prefix distribution. Our evaluation of HBS demonstrates its superiority in terms of lookup throughput, update speed, memory efficiency, and dynamic adaptability.

Many mobile devices are usually equipped with multiple interfaces, providing the opportunity of using multipath transport protocols such as Multipath TCP (MPTCP) to boost performance. The multipath congestion control algorithm (CCA) in MPTCP plays a vital role in achieving high performance and multipath fairness in mobile environments where the paths are often heterogeneous and dynamic. Such environments are very challenging for existing one-size-fits-all CCAs to achieve high performance while ensuring multipath fairness. In this paper, we present a novel framework, Disco, to dynamically select the most appropriate CCAs for MPTCP subflows at runtime according to the perceived network condition. Extensive experiments show that compared with existing multipath CCAs, the proposed solution can improve the average throughput by 19% – 25% and reduce the average queuing delay by up to 21 % while it barely does harm to multipath fairness.

Network monitoring systems struggle with the issue that the measurement data is incomplete, with only a subset of origin-destination (OD) pairs or time slots observed, due to the high deployment and measurement cost. Recent studies show that the missing data can be inferred from partial measurements using neural network models and tensor methods. However, these recovery approaches fail to achieve accuracy, adaptability and high speed, simultaneously. In this paper, we propose RecMon, a deep learning-based data recovery system that satisfies the above three criteria. A global spatio-temporal attention mechanism and a data augmentation algorithm are proposed to improve the recovery accuracy. A semi-supervised learning-based scheme is devised for fast and effective model updates. We conduct extensive experiments on three real-world datasets to compare RecMon with four state-of-the-art methods in terms of online recovery performance. The experimental results show that RecMon can adapt to the latest state of the network and accurately recover network measurement data in less than 100 milliseconds. When 90% of the data is missing, the recovery accuracy of RecMon improves over the strongest baseline method by 22.7%, 16.0%, and 8.2% in the three datasets, respectively.

Monitoring Key Performance Indicators (KPIs) and detecting anomalies in online service systems is critical. However, choosing the right KPI anomaly detection algorithm and appropriate hyperparameters presents a challenge. Conventional Automated Machine Learning (AutoML) struggles to address this because the hold-out dataset lacks labels and its loss doesn’t reliably reflect anomaly detection accuracy. To address the above challenges, this paper introduces AutoKAD, an AutoML framework designed to solve the combined algorithm selection and hyperparameter optimization problem for unsupervised KPI Anomaly Detection. We propose a label-free universal objective function, inspired by the Local Outlier Factor (LOF), for evaluating AutoML trials. Additionally, we improve the acquisition function and designs a cluster-based warm start strategy to enhance exploration effectiveness and efficiency. The experimental results on three real-world datasets show that our approach outperforms the SOTA model selection algorithm by 11% in F1-score and achieves comparable performance (99%) with theoretically optimal results. We believe that AutoKAD can greatly improve the deployment feasibility of existing anomaly detection algorithms in real-world systems. Our code is anonymously released at https://github.com/NetManAIOps/AutoKAD.

With the development of cloud applications, large monolithic services have been replaced by loosely-coupled and single-purpose microservices. To improve localization performance, deep learning techniques have been widely used for root cause analysis. Existing research focuses on performance, yet the lack of interpretability creates key barriers to applying deep learning models in practice. This paper presents Grace, an interpretable root cause localization framework. Our work has three aims. First, to more accurately localize root causes using a Spatial-Temporal Graph Convolutional Network (STGCN). To the best of our knowledge, we are the first to apply an STGCN in the domain. Second, to design an interpreter that helps engineers to understand the system decision (beyond the simple binary black-box result). Third, we apply our interpreter to two real cases, which replaces expert knowledge to help build prior knowledge for fault type diagnosis. Our results show that Grace consistently achieves improvements over other state-of-the-art models by 4%-140%.

Existing anomaly detection approaches based on deep-learning just could simultaneously dig out key information from two dimensions in the traces, metrics or logs. Besides, they just output simple binary result, which ignores the key artificial statement information in the log. In this paper, we propose Triple, an interpretable anomaly detection approach based on deep learning for microservice system. More importantly, Triple aims to help engineers to establish trust in the system decision from key metrics and the artificial statements in logs. Triple leverages graph representation to describe the complicated dependency relationship in the traces with the logs and metrics embedded into the node features. Based on the graph representation, Triple trains a Spatial-Temporal Graph Convolutional Network(STGCN) to capture the key information and generate decision boundary by deep SVDD, which detects the system's anomaly. In addition, we design an interpreter to transfer the simple binary result into a humanly understandable result, including log, metrics and trace, to facilitate engineers' understanding and handling of the incoming incident. Our work has four aims. First, to the best of our knowledge, we are the first to simultaneously apply three data sources to finish anomaly detection in the domain. Second, we design a new anomaly detection method that is an STGCN based on SVDD. Third, we design an interpreter that makes the decision not only a simple binary result. The interpretable result could capture the key artificial statement information in the log and assist engineers in incident troubleshooting. Finally, we design a series experiments to validate our method's effectiveness in the real-world system's dataset. Our results show that Triple consistently achieves improvements over other state-of-the-art models by 11%-65%.

Network measurement is critical to many network applications. There are mainly two kinds of flow-level measurement tasks: 1) packet accumulation tasks and 2) packet loss tasks. In practice, the two kinds of tasks are often required at the same time, but existing works seldom handle both. In this paper, we design ChameleMon to support the two kinds of tasks simultaneously. The key design of ChameleMon is to shift measurement attention as network state changes, through two dimensions of dynamics: 1) dynamically allocating memory between the two kinds of tasks; 2) dynamically monitoring the flows of importance. To realize the key design, we propose a key technique, leveraging Fermat's little theorem to devise a flexible data structure, namely FermatSketch. FermatSketch is dividable, additive, and subtractive, supporting the two kinds of tasks. We have implemented a ChameleMon prototype on a testbed with a Fat-tree topology. We conduct extensive experiments and the results show ChameleMon supports the two kinds of tasks with low memory/bandwidth overhead, and more importantly, it can automatically shift measurement attention as network state changes.

Massive key performance indicators (KPIs) are monitored as multivariate time series data (MTS) to ensure the reliability of the software applications and service system. Accurately detecting the abnormality of MTS is very critical for subsequent fault elimination. The scarcity of anomalies and manual labeling has led to the development of various self-supervised MTS anomaly detection (AD) methods, which optimize an overall objective/loss encompassing all metrics' regression objectives/losses. However, our empirical study uncovers the prevalence of conflicts among metrics' regression objectives, causing MTS models to grapple with different losses. This critical aspect significantly impacts detection performance but has been overlooked in existing approaches. To address this problem, by mimicking the design of multi-gate mixture-of-experts (MMoE), we introduce CAD, a Conflict-aware multivariate KPI Anomaly Detection algorithm. CAD offers an exclusive structure for each metric to mitigate potential conflicts while fostering inter-metric promotions. Upon thorough investigation, we find that the poor performance of vanilla MMoE mainly comes from the input-output misalignment settings of MTS formulation and convergence issues arising from expansive tasks. To address these challenges, we propose a straightforward yet effective task-oriented metric selection and p&s (personalized and shared) gating mechanism, which establishes CAD as the first practicable multi-task learning (MTL) based MTS AD model. Evaluations on multiple public datasets reveal that CAD obtains an average F1-score of 0.943 across three public datasets, notably outperforming state-of-the-art methods. Our code is accessible at https://github.com/dawnvince/MTS_CAD.

As Internet applications continue to scale up, microservice architecture has become increasingly popular due to its flexibility and logical structure. Anomaly detection in traces that record inter-microservice invocations is essential for diagnosing system failures. Deep learning-based approaches allow for accurate modeling of structural features (i.e., call paths) and latency features (i.e., call response time), which can determine the anomaly of a particular trace sample. However, the point-wise manner employed by these methods results in substantial system detection overhead and impracticality, given the massive volume of traces (billion-level). Furthermore, the point-wise approach lacks high-level information, as identical sub-structures across multiple traces may be encoded differently. In this paper, we introduce the first Group-wise Trace anomaly detection algorithm, named GTrace. This method categorizes the traces into distinct groups based on their shared sub-structure, such as the entire tree or sub-tree structure. A group-wise Variational AutoEncoder (VAE) is then employed to obtain structural representations. Moreover, the innovative "predicting latency with structure" learning paradigm facilitates the association between the grouped structure and the latency distribution within each group. With the group-wise design, representation caching, and batched inference strategies can be implemented, which significantly reduces the burden of detection on the system. Our comprehensive evaluation reveals that GTrace outperforms state-of-the-art methods in both performances (2.64% to 195.45% improvement in AUC metrics and 2.31% to 40.92% improvement in best F-Score) and efficiency (21.9x to 28.2x speedup). We have deployed and assessed the proposed algorithm on eBay's microservices cluster, and our code is available at https://github.com/NetManAIOps/GTrace.git.

Cloud computing provides a new paradigm to offer flexible IT infrastructures. In IaaS clouds, tenants deploy software-defined networking (SDN) policies to simplify network management and customize network behaviors. However, programming SDN networks is error-prone no matter using low-level APIs or high-level programming languages. Specifically, SDN policies may contain misconfigurations that do not break the pre-defined network invariants (e.g., black holes), but either degrade the deployment efficiency or mistakenly translate tenants intents. Prior studies for checking either traditional access control policies or network-wide invariants, are thus fail to detect these misconfigurations. To address this gap, this paper presents PMM, a misconfiguration checking tool for compositional SDN that works at the data plane of cloud networks. We first propose a new data structure, minimal interval set, to represent the match patterns of rulesets. This representation serves the basis for composition algebra construction and misconfiguration checking. We then propose the principles, algorithms and also optimisations for fast and accurate checking. We finally implement PMM in Covisor. Experiments with both real-world rulesets and synthetic rulesets show that PMM can detect misconfigurations of SDN policies in cloud networks within hundreds of milliseconds.

Mobile Live Streaming (MLS) services are one of the most popular types of mobile apps. They involve a (often amateur) user broadcasting content to a potentially large online audience via unreliable networks. Nevertheless, we still lack a deep understanding of MLS user behavior that is critical for optimizing MLS systems, despite some active measurements on viewer-side behavior. Using detailed logs obtained from a major MLS provider, this paper first conducts an in-depth measurement study of both viewer-side and broadcaster-side behavior. Key findings include large wasteful uploads, strong viewing locality, and traffic dominance of loyal viewers. Specifically, 33.3% of uploads go unwatched, and the viewership of broadcasters tends to be localized. Inspired by our findings, we propose EDGEOPT– a centralized control center for MLS services for optimizing both the first-mile and the last-mile transmission in MLS. Specifically, EDGEOPT reduces wasteful uploading by 71% through adaptive uploading and enhances the replay quality of popular video segments by 10% via highlights retransmission. EDGEOPT also uses a learning-based content pre-fetching scheme that boosts the viewing startup by 29.5% and offloads at most 80% of the viewing workload from the edge servers with peer-assisted delivery.

By deploying virtualized network elements (hosts, switches, routers, links, etc.) on clusters of commodity machines, distributed network emulations (DNE) closely mimic the behaviors of network systems and provide real-time interactions and analysis for network service management. However, DNE encounters scalability challenges when faced with large network topologies. These challenges can be boiled down to the assignment problem: to which physical machine each virtualized network element should be assigned so that the largest possible network topology can be emulated? In this paper, we tackle this problem from an algorithmic perspective. We first propose TBR (topology balancing relaxation) as the relaxation of the assignment problem. TBR tries to maintain a balance of the hardware resource consumption, by minimizing the maximum inter-machine bandwidth. We further develop TBS (topology balancing solver), which combines mathematical techniques with multi-level algorithms to solve TBR efficiently. We integrate TBR and TBS into MaxiNet, a famous distributed network emulator. Experimental results show that with the same available physical resources, TBR and TBS can improve emulation scalability by up to$4.7\times $compared to baselines.

Network trouble shooting, failure location, and anomaly detection rely heavily on network traffic measurement data. Due to the lack of measurement infrastructure, the high measurement cost, and the unavoidable transmission loss, network monitoring systems suffer from the problem that the network traffic data are incomplete. This article models the traffic data as a tensor to exploit its strong ability of feature extraction to recover the missing data. Different from traditional tensor completion which relies on tensor factorization, we design a novel Deep Adversarial Tensor Completion (DATC) scheme based on Deep Learning (DL) techniques. DATC is the first scheme that exploits the data reconstruction ability of autoencoder and the power of adversarial training from Generative Adversarial Networks to infer the missing data. Despite that DL techniques achieve great success in the image field, designing an algorithm based on DL techniques to recover the traffic data with missing entries faces additional challenges due to the skewed distribution and the sparsity of traffic data. To conquer these challenges, we propose the use of two techniques, adversarial training and missing data aware convolution. These techniques help DATC to learn the complex features of the traffic data and infer the missing data following the data distribution of traffic data. Our extensive experimental results using two public real-world network traffic datasets and running both offline and online demonstrate that DATC can achieve significantly better recovery accuracy while capturing the data distribution of the traffic data even when the sampling ratio is very low.

Detecting anomalous traffic is a crucial task for network management. Although many anomaly detection algorithms have been proposed recently, constrained by their matrix-based traffic data model, existing algorithms often suffer from low detection accuracy. To fully utilize the multi-dimensional information hidden in the traffic data, this paper uses the tensor model for more accurate Internet anomaly detection. Only considering the low-rank linearity features hidden in the data, current tensor factorization techniques would result in low anomaly detection accuracy. We propose a novel Graph-based Tensor Recovery model (Graph-TR) to well explore both low-rank linearity features as well as the non-linear proximity information hidden in the traffic data for better anomaly detection. We encode the non-linear proximity information of the traffic data by constructing nearest neighbor graphs and incorporate this information into the tensor factorization using the graph Laplacian. Moreover, to facilitate the quick building of neighbor graph, we propose a nearest neighbor searching algorithm with the simple locality-sensitive hashing (LSH). Besides only detecting random anomalies, our algorithm can also effectively detect structured anomalies that appear as bursts. We have conducted extensive experiments using Internet traffic trace data Abilene and GÈANT. Compared with the state of art algorithms on matrix-based anomaly detection and tensor recovery approach, our Graph-TR can achieve higher Accuracy and Recall.

Network measurements provide critical inputs for a wide range of network management. Existing network-wide monitoring methods face the challenge of incurring a high measurement cost. Some recent studies show that network-wide measurement data such as end-to-end latency and flow traffic, have hidden spatio-temporal correlations and thus low-rank features. Taking advantage of the low-rank feature, enlightened by tensor model's strong capability of information representation and extracting, this paper studies a novel sparse measurement scheduling problem which selects a proportion of Origin and Destination (OD) pairs to take measurements in the future time slots, while ensuring the data of the remaining un-measured OD pairs be accurately inferred through tensor completion. It is challenging to find the optimal sampling points (OD pairs) without knowing the structure of the future data and also infer the un-measured data in the presence of noise in the measurement samples. To conquer the challenges, we propose several techniques: a tripartite graph to illustrate the relationship between sample locations and tensor factorization, a graph-based sample selection algorithm, and a graph-based robust tensor completion algorithm. We have conducted extensive experiments based on two real network latency monitoring traces (PlanetLab and Harvard) and two other network monitoring traces (including a traffic trace Abilene and a throughput trace WS-Dream). Our results demonstrate that, even with a sampling ratio of less than 5%, our scheme can accurately obtain the complete network-wide monitoring data by inferring the missing ones based on the samples taken. To achieve similar recovery performance, the best peer tensor completion algorithm needs a significantly larger number of samples, with the sampling ratio up to 25-150 times ours.

Network traffic anomaly detection is critical for advanced network applications. However, network traffic monitoring data arrive in a streaming fashion and could be infinite, which makes the offline algorithms that attempt to store the entire stream monitoring data for analysis not scalable. To well utilize the strong ability of tensor model, we use a tensor to represent the prior non-anomalous traffic matrices and propose a novel unsupervised anomaly detection framework that can be used to detect anomalies in a streaming fashion by making only one pass over the data while utilizing limited storage. In the framework, we propose a succinct tensor sketch to maintain, in a streaming model, the subspace that can well represent all prior non-anomalous data detected. Using the subspace, anomalies in each new incoming traffic monitoring data can be quickly detected based on a simple outlier score calculation. Further, we prove that the tensor sketch is mergeable. Exploiting this property, we propose a distributed anomaly detection framework in which the distributed node only needs to upload its succinct tensor sketch instead of the raw monitoring data to the central node to calculate the global subspace of the whole network, which greatly saves the transmission cost. We theoretically prove that our tensor sketch based anomaly detection algorithm compares favorably with the offline approach which calculates the subspace based on expensive global Singular Value Decomposition (SVD). The experimental results demonstrate the effectiveness and efficiency of our approach over other popular online anomaly detection algorithms.

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.

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.

A large volume of logs provides a reliable data source for online services. For instance, 5G, Big 5G or Beyong 5G cloud core network and its User Plane Functions require analysis built on massive log storage. The storage cost of log data remains a problem for the industry. Compressing the logs before archives remains the most popular way to reduce it. However, structured logs, which usually present in tabular format, and unstructured logs, which build on variable templates, have to use different compression strategies. Using log parsers can eliminate this difference by converting unstructured logs into structured ones. Based on this idea, we introduce our universal efficient parser-based log compression approach LogDAC. It also uses a divide-and-conquer preprocess strategy to improve the compatibility with successive dictionary-based general compressors. The evaluation against both structured and unstructured public datasets show a solid improvement up to 45.4% and 489.53% of compression ratio respectively, compared with existing parser-based compressors.

Layer-3 load balancing is a key topic in the networking field. It is well acknowledged that flowlet is the most promising solution because of its good trade-off between load balance and packet reordering. However, we find its one significant limitation: it makes the forwarding paths of flows unpredictable. To address this limitation, this paper presents BurstBalancer, a simple yet efficient load balancing system with a sketch, named BalanceSketch. Our design philosophy is doing less changes to keep the forwarding path of most flows fixed, which guides the design of BalanceSketch and balance operations. We have fully implemented BurstBalancer in a small-scale testbed built with Tofino switches, and conducted large-scale NS-2 simulations. Our results show that BurstBalancer achieves 5%∼35% smaller FCT than LetFlow in symmetric topology and up to 30× smaller FCT in asymmetric topology, while 58× fewer flows suffer from path changing. All related codes are open-sourced at Github22https://github.com/BurstBalancer/Burst-Balancer.

On top of the Resource Public Key Infrastructure (RPKI), the Route Origin Authorization (ROA) creates a cryptographically verifiable binding of an autonomous system to a set of IP prefixes it is authorized to originate. By their design, ROAs can protect the inter-domain routing system against prefix and sub-prefix hijacks. However, inappropriate configurations bring in vulnerabilities to other types of routing security attacks. As such, the state-of-the-art approach implements the minimal-ROA principle, eliminating the risk of using ROAs at the cost of system scalability. This paper proposes the hanging ROA, a novel bitmap-based encoding scheme for ROAs, that not only ensures strong security, but also significantly improves system scalability. According to the performance evaluation with real-world data sets, the hanging ROA outperforms the state-of-the-art approach 2.4 times in terms of the compression ratio, and it can reduce the cost of a router to synchronize all validated ROA payloads by 44.5% ~ 64.7%.

ABR algorithms dynamically select the bitrate of chunks based on the network capacity. To estimate the network capacity, most ABR algorithms use throughput prediction while recent works start to leverage delivery time prediction. We in this paper examine all components of the predictor for ABR algorithms, i.e., input features, mapping function and output target. We build an automated video streaming measurement platform, and collect extensive dataset under various network environments, containing 2500+ video sessions. Through analysis, we find that most of previous works failed to achieve accurate prediction due to ignoring how application behavior influences application throughput, e.g., the strong correlation between chunk size and throughput. Then we identify underlying factors affecting this correlation, and consider them as features for more accurate prediction. Moreover, we show that throughput is a better target for data-driven predictors than delivery time in terms of prediction error, due to the long tail distribution of delivery time. Based on those above, we propose a decision-tree-based throughput predictor, named Lumos, which acts as a plug-in for ABR algorithms. Extensive experiments in real-world Internet demonstrate that Lumos achieves high prediction accuracy and improves the QoE of ABR algorithms when integrated into them.

Recovery of missing network monitoring data is of great significance for network operation and maintenance tasks such as anomaly detection and traffic prediction. To exploit historical data for more accurate missing data recovery, some recent studies combine the data together as a tensor to learn more features. However, the need of performing high cost data decomposition compromises their speed and accuracy, which makes them difficult to track dynamic features from streaming monitoring data. To ensure fast and accurate recovery of network monitoring data, this paper proposes NMMF-Stream, a stream-processing scheme with a context extraction module and a generation module. To achieve fast feature extraction and missing data filling with a low sampling rate, we propose several novel techniques, including the context extraction based on both positive and negative monitoring data, context validation via measuring the Pointwise Mutual Information, GRU-based temporal feature learning and memorization, and a new composite loss function to guide the fast and accurate data filling. We have done extensive experiments using two real network traffic monitoring data sets and one network latency data set. The experimental results demonstrate that, compared with three baselines, NMMF-Stream can fill the newly arrived monitoring data very quickly with much higher accuracy.

Various congestion control (CC) algorithms have been designed to target specific scenarios. To automate this process, researchers have begun to use machine learning to automatically control the congestion window. These, however, often rely on heavyweight learning models (e.g., neural networks). This can make them unsuitable for resource-constrained mobile devices. On the other hand, lightweight models (e.g., decision trees) are often incapable of reflecting the complexity of diverse mobile wireless environments. To address this, we present Muses, a learning-based approach for generating lightweight congestion control algorithms. Muses relies on imitation learning to train a universal (heavy) LSTM model, which is then used to extract (lightweight) decision tree models that are each targeted at an individual environment. Muses then dynamically selects the most appropriate decision tree on a per-flow basis. We show that Muses can generate high throughput policies across a diverse set of environments, and it is sufficiently light to operate on mobile devices.

Due to the bulkiness and sophistication of the Distributed Deep Learning (DDL) systems, it leaves an enormous challenge for AI researchers and operation engineers to analyze, diagnose and locate the performance bottleneck during the training stage. Existing performance models and frameworks gain little insight on the performance reduction that a performance straggler induces. In this paper, we introduce MD-Roofline, a training performance analysis model, which extends the traditional rooftine model with communication dimension. The model considers the layer-wise attributes at application level, and a series of achievable peak performance metrics at hardware level. With the assistance of our MD-Roofline, the AI researchers and DDL operation engineers could locate the system bottleneck, which contains three dimensions: intra-GPU computation capacity, intra-GPU memory access bandwidth and inter-GPU communication bandwidth. We demonstrate that our performance analysis model provides great insights in bottleneck analysis when training 12 classic CNNs.

Network-wide monitoring is important for many network functions. However, monitoring data are often incomplete due to the need of sampling to reduce high measurement cost, system failure, and unavoidable transmission loss under severe communication. Instead of only targeting to estimate all missing monitoring data entries with a small set of measurement samples, we study a new order-preserved monitoring data estimation problem to accurately estimate the missing data entries while preserving the data entries’ order in the dataset. We propose a novel order-preserved tensor completion model that integrates both the low rank property and the order information into a joint learning problem to estimate the missing data. With well designed non-convex function to directly approximate the tensor rank and order-preserved constraint under the linear self-recovery method, our model can not only more accurately capture the low-rank property of monitoring data to increase the estimation performance of missing data, but also can capture the order information in monitoring data to ensure the estimation accuracy. Extensive experiments using four real datasets demonstrate that compared with the state-of-the-art tensor completion algorithms, our proposed algorithm can provide more accurate estimation and keep the value order of recovered entries to more effectively retrieve top-k large entries.

Packet classification is the most essential component for switches and firewalls to perform network functions. In Software Defined Network, the growing scale of traffic requires the packet classification algorithm to perform high-speed lookup. Even though a lot of algorithms are proposed, the lookup performance is still the bottleneck because of the inefficient and unscientific schemes to cut rules and split trees. In this paper, we propose a novel decision-tree-based algorithm PextCuts. First, to efficiently cut rules, PextCuts applies one pext CPU instruction to select discontiguous bits rather than contiguous bits. Second, to scientifically split trees, PextCuts applies the dynamic programming method to split each field into multiple sizes rather than large and small sizes. Compared to ten representative algorithms, PextCuts has the highest lookup speed with the minimal numbers of average memory accesses, maximal memory accesses, and tree height simultaneously. It also consumes the least memory cost and the shortest construction time. For the state-of-the-art algorithm ByteCuts, PextCuts achieves 2.1x lookup speed with only 57% memory cost and 10% construction time. In addition, we implement PextCuts in DPDK to perform packet classification with optional fields and achieve 3.0x lookup speed.

The millimeter wave technology which provides the throughput of multi-gigabit per second is one of the key technologies for 5G/B5G communications. However, an optimal interaction between the transport layer protocols and the highly fluctuating millimeter wave networks is extremely challenging and lacks in-depth exploration in actual networks. In this paper, we examine and discuss the performance of several TCP congestion control algorithms in the real 60 GHz millimeter wave environment, and inspect the improvement of TCP performance over mmWave hybrid networks by TCP proxies in single-flow and multi-flows scenarios. Our results reveal severe adaptation problems associated with these congestion control algorithms over millimeter wave networks and the effectiveness of TCP proxies for the utilization of millimeter wave hybrid networks.

Distributed Deep Learning (DDL) is widely used to accelerate deep neural network training for various Web applications. In each iteration of DDL training, each worker synchronizes neural network gradients with other workers. This introduces communication overhead and degrades the scaling performance. In this paper, we propose a recursive model, OSF (Scaling Factor considering Overlap), for estimating the scaling performance of DDL training of neural network models, given the settings of the DDL system. OSF captures two main characteristics of DDL training: the overlap between computation and communication, and the tensor fusion for batching updates. Measurements on a real-world DDL system show that OSF obtains a low estimation error (ranging from 0.5% to 8.4% for different models). Using OSF, we identify the factors that degrade the scaling performance, and propose solutions to effectively mitigate their impacts. Specifically, the proposed adaptive tensor fusion improves the scaling performance by 32.2%∼ 150% compared to the constant tensor fusion buffer size.

This paper revisits the opportunities of using WiFi offloading for Vehicle to Internet (V2I) communication, and how this has changed over the last decade. With the rollouts of provider-managed WiFi networks that are more structured and operate under authenticated regimes, WiFi offloading, or use of available (roadside) WiFi networks for V2I data communication, has different opportunities and challenges. To study the current landscape,we develop a system (X-Fi), which efficiently selects, associates to, authenticates with, and performs WiFi offloading for V2I communication with these networks, and a tool (X-Perf), which illustrates opportunities of WiFi offloading available today in these networks, with measurements and experiments across four metro areas across three continents over 22 months. Our results indicate the feasibility of achieving 1 GB/hour application goodput, an order of magnitude higher than the number provided by open WiFi networks in the past, which can take a significant load away from alternative communication paths for V2I systems. Moreover, we provide several implications on transport protocols and WiFi deployments to shed light on the use of such WiFi networks for V2I communication.

Mobile crowdsensing (MCS) has become a new paradigm for the environment sensing. However, the sparse sensory data prevent the practical and large-scale deployment of MCS systems. Recent studies have demonstrated that the matrix factorization is an effective technique which can estimate the missing sensory data entries based on a small set of observed data entries. However, there could be multiple sensory data sets with each regarded as a different view on the environment. Applying current matrix factorization individually to each data set, the recovery performance will be low as some data sets do not have enough observed data entries thus enough information. By partitioning the parameters involved in matrix factorization, we design some novel regularizations to encode the similarities among different data sets and specific knowledge in the single data set. Based on the regularizations, we propose one basic multiview matrix factorization (MVMF) model and one neural MVMF (NMVMF) model to combine multiple sensory data sets to mutually reinforce the estimation of each single data set. The extensive experimental results demonstrate that, with the help of other data sets, our models can estimate the missing entries in the data set with a very low sampling ratio accurately while the other five baseline algorithms cannot.

Multi-set membership query is a fundamental issue for network functions such as packet processing and state machines monitoring. Given the rigid query speed and memory requirements, it would be promising if a multi-set query algorithm can be designed based on Bloom filter (BF), a space-efficient probabilistic data structure. However, existing efforts on multi-set query based on BF suffer from at least one of the following drawbacks: low query speed, low query accuracy, limitation in only supporting insertion and query operations, or limitation in the set size. To address the issues, we design a novel B h sequence-based Bloom filter (B h BF) for multi-set query, which supports four operations: insertion, query, deletion, and update. In B h BF, the set ID is encoded as a code in a B h sequence. Exploiting good properties of B h sequences, we can correctly decode the BF cells to obtain the set IDs even when the number of hash collisions is high, which brings high query accuracy. In B h BF, we propose two strategies to further speed up the query speed and increase the query accuracy. On the theoretical side, we analyze the false positive and classification failure rate of our B h BF. Our results from extensive experiments over two real datasets demonstrate that B h BF significantly advances state-of-the-art multi-set query algorithms.

Home security cameras (HSCs) are becoming increasingly important in protecting people’s household property and caring for family members. As an emerging type of home IoT devices, HSCs are distinct from traditional IoT devices in that they are often installed in intimate places, detecting movements constantly. Such close integration with users’ daily life may result in distinct user behavioral patterns and privacy concerns. To explore this, we perform a detailed measurement study based on a large-scale service log dataset from a major HSC service provider. Our analysis reveals unique usage patterns of HSCs, including significant wasted uploads, asymmetrical upload and download traffic, skewed user engagement, and limited watching locations. We further identify three types of privacy risks in current HSC services using both passive logs and active measurements. These risks can be exploited by attackers, through observing only the traffic rates of HSCs, to infer the working state of cameras and even the daily activity routine in places where the camera is installed. Moreover, we find the premium users who pay an extra fee are especially vulnerable to such privacy inferences. We propose countermeasures from the perspectives of susceptible users and HSC providers to mitigate the risks.

Open vSwitch (OVS) is a widely used virtual switch designed to provide virtual network capabilities in virtualized environments. As the core of OVS, the packet classification task is time-consuming with the implementation of Tuple Space Search (TSS), a classical hash table-based algorithm that can achieve fast rule updating but at the cost of the reduced packet classification throughput. However, because of the central role of OVS in a virtualized environment, its performance is of utmost importance and we need mechanisms that can achieve high update rate along with high packet classification throughput. In this paper, we compare the performance of several classification algorithms and show that Tuple Merge Relaxation (TMR) is able to achieve the highest sustainable classification throughput while dealing with updates. After integrating it into OVS and evaluating its in vivo performance, we observe that TMR-OVS can achieve up to$24.7\times $higher throughput compared with native OVS. Moreover, we show that TMR-OVS is also effective against Tuple Space Explosion attack effectively and maintains OVS throughput under this attack.

The Sketch is a compact data structure useful for network measurements. However, to cope with the high speeds of the current data plane, it needs to be held in the small on-chip memory (SRAM). Therefore, the product of the counter size and the number of counters must be below a certain limit. With small counters, some will overflow. With large counters, the total number of counters will be small, but each counter will be shared by more flows, leading to poor accuracy. To address this issue, we propose a generic technique:self-adaptive counters (SEAD Counter). When the value of the counter is small, it works as a standard counter. When the value of the counter is large however, we increment it using a predefined probability, so as to represent this large value. Moreover, in the SEAD Counter, the probability decreases when the value increases. We show that this technique can significantly improve the accuracy of counters. This technique can be adapted to different circumstances. We theoretically analyze the improvements achieved by the SEAD Counter. We further show that our SEAD Counter can be extended to three typical sketches and Bloom filters. We conduct extensive experiments on three real datasets and one synthetic dataset. The experimental results show that, compared with the state-of-the-art, sketches using the SEAD Counter improve the accuracy by up to 13.6 times, while the Bloom filters using SEAD Counter can reduce the false positive rate by more than one order of magnitude.

In network-wide monitoring, finding the large monitoring data entries is a fundamental network management function. However, the retrieval of large entries is extremely difficult and challenging as a result of incompleteness of network measurement data. Enlightened by tensor model’s strong capability of information representation and extraction, we model the network-wide monitoring data as a 3-way tensor. With tensor completion, the retrieval can be performed after recovering all missing entries. However, this not only incurs an extremely high cost when the tensor is large, but is also unnecessary. Instead, to quickly retrieve large entries at low cost, we transform the large entry retrieving problem to a cosine similarity searching problem, and propose two algorithms: 1) Quickly reordering the factor vectors based on Locality Sensitive Hashing (LSH) hash table so that vectors with small cosine distances are placed in the same hash bucket; 2) Quickly finding the similar vector of a queried one that the two together determine a large entry without incurring the high cost of recovering all entries through the dot products. In the process of LSH table building and similarity query, several novel techniques are proposed, including LSH table representation with the LSH forest, good hash table building to support the flexible search of cosine similarity, and bit-shifting-based quick similarity query. Our experimental studies on 4 real world datasets indicate that our technique is at least up to 60 times faster than the approach based on direct tensor completion.

Programmable switches are recently used for accelerating data-intensive distributed applications. Some computational tasks, traditionally performed on servers in data centers, are offloaded into the network on programmable switches. These tasks may require the support of on-the-fly floating-point operations. Unfortunately, programmable switches are restricted to simple integer arithmetic operations. Existing systems circumvent this restriction by converting floats to integers or relying on local CPUs of switches, incurring extra processing delayed and accuracy loss. To address this gap, we propose NetFC, a table-lookup method to achieve on-the-fly in-network floating-point arithmetic operations nearly without accuracy loss. Specifically, NetFC utilizes logarithm projection and transformation to convert the original huge table enumerating all operands and results into several much smaller tables that can fit into the data plane of programmable switches. To cope with the table inflation problem on 32-bit floats, we also propose an approximation method that further breaks the large tables into smaller ones. In addition, NetFC leverages two optimizations to improve accuracy and reduce on-chip memory consumption. We use both synthetic and real-life datasets to evaluate NetFC. The experimental results show that the average accuracy of NetFC is above 99.9% with only 448KB memory consumption for 16-bit floats and 99.1% with 496KB memory consumption for 32-bit floats. Furthermore, we integrate NetFC into two distributed applications and two in-network telemetry systems to show its effectiveness in further improving the performance.

Locality Sensitive Hashing (LSH) is widely adopted to index similar data in high-dimensional space for approximate nearest neighbor search. Demanding applications (e.g. web search) mean that LSH must exhibit low response times and high throughput. To achieve this, they tend to load balance between multiple machines. However, as the scale of concurrent queries and the volume of data grow, large numbers of index messages are required. Hence, the network is a key bottleneck. To address this gap, we propose NetSHa, which exploits the computational capacity of programmable switches. Specifically, we introduce a heuristic sort-reduce approach to drop potentially poor candidate answers while preserving search quality. Then, NetSHa aggregates good candidate answers from different index messages when transmitting them. Through this, it reduces the network communication cost. Furthermore, we introduce a best-effort replacement mechanism to improve its concurrency. We implement NetSHa on a Barefoot Tofino programmable switch and evaluate it using 7 real-world datasets. The experimental results show that NetSHa reduces the packet volume by$4\sim 10$times and improves the search efficiency by least 3× in comparison with typical LSH-based distributed search frameworks.

In many network security systems, network packets will be archived with no loss for the purpose of forensic, troubleshooting and so on. In order to achieve fast retrieval for these stored packets, index is essential. However, with the rapid increase of network link bandwidth, indexing network traffic traces is facing the challenges of index construction speed, index storage overhead and retrieval efficiency. In this paper, we propose an efficient index scheme for packet index, named Compact-Index, that not only effectively reduces the storage cost of index, but also greatly improves index insertion rate and retrieval efficiency. Experimental results show that our scheme can achieve 7.14Mpps index insertion rate for IPv4 traffic and 6.11Mpps index insertion rate for IPv6 traffic, and supports millisecond scale response to most queries. In addition, the average space cost of index is only about 5% of the raw network traffic. All the experimental results above indicate that Compact-Index significantly outperforms the existing state-of-art index schemes.

Identifying network anomaly detection is important since they may carry critical information in circumstances such as a burst of intrusions, privacy theft, system damage and fraudulent activities. In recent years, there are many detection methods for network anomalies are proposed, however, a single model always faces the problems of over or under-fitting, high bias and variance. An improved method is to comprehensively use the results of multiple models and then reform the final predictions. This paper introduces an ensemble model, which is a powerful technique to increase accuracy on network anomaly detection. By combining three base models Xgboost, LightGBM and Catboost into one anomaly detector, we successfully detect different DDOS-smurf and Probing activities. This ensemble model is verified on ZYELL-NCTU net traffic, which is a large-scale dataset for read-world network anomaly detection. All code are open source in Github and can be directly run on Colab Jupyter Notebook.

Programmable switches are recently used for accelerating data-intensive distributed applications. Some computational tasks, traditionally performed on servers in data centers, are offloaded to the network on programmable switches. These tasks may require the support of on-the-fly floatingpoint operations. Unfortunately, the computational capacity of programmable switches is limited to simple integer arithmetic operations. To address this issue, prior approaches either adopt a float-to-integer method or rely on local CPUs of switches, incurring accuracy loss and delayed processing.To this end, we propose NetFC, a table-lookup method to achieve on-the-fly in-network floating-point arithmetic operations nearly without accuracy loss. NetFC adopts a divide-and-conquer mechanism that converts the original huge table into several much smaller tables that are operated by the built-in integer operations. NetFC further leverages a scaling-factor mechanism for improving computational accuracy, and a prefix-based lossless table compression method to reduce memory consumption. We use both synthetic and real-life datasets to evaluate NetFC. The experimental results show that the average accuracy of NetFC is above 99.94% with only 448KB memory consumption. Furthermore, we integrate NetFC into Sonata [12] for detecting Slowloris attack, yielding significant decrease of detection delay.

Due to high network measurement cost, network-wide monitoring faces many challenges. For a network consisting of n nodes, the cost of one time network-wide monitoring will be O(n2). To reduce the monitoring cost, inspired by recent progress of matrix completion, a novel sparse network monitoring scheme is proposed to obtain network-wide monitoring data by sampling a few paths while inferring monitoring data of others. However, current sparse network monitoring schemes suffer from the problems of high measurement cost, high computation complexity in sampling scheduling, and long time to recover the un-sampled data. We propose a novel block matrix completion that can guarantee the quality of the un-sampled data inference by selecting as few as m = O(nr ln(r)) samples for a rank r N × T matrix with n = max{N,T}, which largely reduces the sampling complexity as compared to the existing algorithm for matrix completion. Based on block matrix completion, we further propose a light weight sampling scheduling algorithm to select measurement samples and a light weight data inference algorithm to quickly and accurately recover the un-sampled data. Extensive experiments on three real network monitoring data sets verify our theoretical claims and demonstrate the effectiveness of the proposed algorithms.

Network applications, such as network state tracking and forecasting, anomaly detection, and failure recovery, require complete network monitoring data. However, the monitoring data are often incomplete due to the use of partial measurements and the unavoidable loss of data during transmissions. Tensor completion has attracted some recent attentions with its capability of exploiting the multi-dimensional data structure for more accurate un-measurement/missing data inference. Although conventional tensor completion algorithms can work well when the application data follow the symmetric normal distribution, it cannot well handle network monitoring data which are highly skewed with heavy tails. To better follow the data distribution for more accurate recovery of the missing entries with large values, we propose a novel expectile tensor completion (ETC) formulation and a simple yet efficient tensor completion algorithm without hard-setting parameters for easy implementation. From both experimental and theoretical ways, we prove the convergence of the proposed algorithm. Extensive experiments on two real-world network monitoring datasets demonstrate the effectiveness of the proposed ETC.

Locality Sensitive Hashing (LSH) is widely adopted to index similar data in high-dimensional space for approximate nearest neighbor search. With the rapid increase of datasets, recent interests in LSH have moved to the implementation of distributed search systems with low response time and high throughput. However, as the scale of the concurrent queries and the volume of available data grow, large amounts of index messages still need to be transmitted to centralized servers for the candidate answer reducing and resorting. Hence, the network remains the bottleneck in distributed search systems.To address this gap, we turn our efforts to the network itself and propose NetSHa. NetSHa exploits the in-network computational capacity provided by programmable switches. Specially, NetSHa designs a sort-reduce approach to drop the potential poor candidate answers and aggregates the good candidate answers on programmable switches, while preserving the search quality. We implement NetSHa on Barefoot Tofino switches and evaluate it using 3 datasets (i.e., Random, Wiki and Image). The experimental results show that NetSHa reduces the packet volume by 10 times at most and improves the search efficiency by 3x at least, in comparison with typical LSH-based distributed search frameworks.

Similarity (distance) measurement among network features (e.g. IP address, MAC address, port number, and protocol, etc.) based on network logs is a critical step for data mining in intrusion detection, anomaly prediction, and log analysis. A practical approach is necessarily accurate, fast, and incremental due to the dynamic network environment. However, existing solutions fail to satisfy these demands simultaneously. Therefore, we propose a novel unsupervised network feature embedding approach: Network Vector (NeVe). It learns the similarity from context information by introducing a natural language processing algorithm GloVe. Since the network data is more timeliness with an almost infinite corpus size, we adjust the algorithm to adapt the input data format and design a fast scalable online update mechanism. Our evaluation demonstrates that NeVe can achieve the highest accuracy with minimal time consumption (13 ~ 15 times faster) compared with the state-of-the-art approach.

Time series forecasting is very important and plays critical roles in many applications. However, making accurate forecasting is a challenge task due to the requirements of learning complex temporal and spatial patterns and combating noise during the feature learning. To address the challenge issues, we propose TEGMNet, a Tensor projection Embedding and Gated Memory Network for multivariate time series forecasting. To more accurately extract local features and reduce the influence of noise, we propose to amplify the data using several data transformation techniques based on MDT (Multi-way delay embedding transform) and TFNN (tensor factorized neural network) to transform the original 2D matrix data to low dimensional 3D tensor data. The local features are then extracted through convolution and LSTM upon the 3D tensor. We also design a long-term feature extraction module based on the structure of gated memory network, which can largely enhance the longterm pattern feature learning ability when the multivariate time series has complex long-term dependencies with dynamic-period patterns. We have done extensive experiments by comparing our TEGMNet with 7 baseline algorithms using 4 real data sets. The experiment results demonstrate that TEGMNet can achieve very good prediction performance even through the data are polluted with noise.

Packet classification is one of the core components in Software Defined Network (SDN) systems, e.g., Open vSwitch. However, the current packet classification algorithm Tuple Space Search (TSS), which is implemented in SDN systems, has low lookup speed and can be attacked. Although some algorithms that support incremental updates are proposed to improve the lookup speed, e.g., TupleMerge and PartitionSort, but are not general and scalable to apply in SDN systems and replace TSS. In this paper, we propose a general, scalable, and high-performance packet classification algorithm MultilayerTuple. MultilayerTuple reduces the number of tuples by splitting the prefix lengths of rules into ranges in each layer, then creates the next layer to replace the long rule chain recursively. The experimental results demonstrate that compared to TSS, TupleMerge, and PartitionSort, MultilayerTuple achieves 21.8x, 2.1x, 2.2x lookup speed and 2.3x, 12.3x, 8.5x update speed. Furthermore, we have implemented MultilayerTuple in the OpenFlow table and MegaFlow cache of Open vSwitch, and it achieves 16.0x and 10.2x lookup speed than TSS. Especially when TSE attack happens, MultilayerTuple can effectively defend against it.

Network-wide monitoring is important for many network functions. Due to the need of sampling to reduce high measurement cost, system failure, and unavoidable data transmission loss, network monitoring systems suffer from the incompleteness of network monitoring data. Different from the traditional network monitoring data estimation problem which aims to infer all missing monitoring data entries with incomplete measurement data, we study a challenging problem of inferring the top-$k$largest monitoring data entries. The recent study shows it is promising to more accurately interpolate the missing data with a 3-D tensor compared to that based on a 2-D matrix. Taking full advantage of the multilinear structures, we apply tensor completion to first recover the missing data and then find the top-$k$data entries. To reduce the computational overhead, we propose a novel discrete tensor completion model which uses binary codes to represent the factor matrices. Based on the model, we further propose three novel techniques to speed up the whole top-$k$entry inference process: a discrete optimization algorithm to train the binary factor matrices, bit operations to facilitate quick missing data inference, and simplifying the finding of top-$k$largest entries with binary code partition. In our discrete tensor completion model, only one bit is needed to represent the entry in the factor matrices instead of a real value (32 bits) needed in traditional tensor completion model, thus the storage cost is reduced significantly. To quickly infer the top-$k$largest data entries when measurement data arrive sequentially, we also propose a sliding window based online algorithm using the discrete tensor completion model. Extensive experiments using five real data sets and one synthetic data set demonstrate that compared with the state of art tensor completion algorithms, our discrete tensor completion algorithm can achieve similar top-$k$entry inference accuracy using significantly smaller time and storage space.

Packet classification is a critical component in network appliances. Software Defined Networking and cloud computing update the rulesets frequently for flexible policy configuration. Tuple Space Search (TSS), implemented in Open vSwitch (OVS), achieves fast rule updating at the sacrifice of the classification rate. In TSS, each tuple is managed by a hash table and classifying a packet needs to go through all hash tables. Merging tuples can reduce the number of hash tables, but inevitably increases the hash conflicts that may even worsen the classification performance in some cases. No existing algorithm meets the need of both fast packet classification and online rule updating. In this paper, we propose Convolutional Neural Network (CNN)-based Range Partition (CRP) to achieve fast packet classification and online update simultaneously. CRP exploits CNN-based image recognition to quickly partition tuples into range spaces upon the change of ruleset distribution, which reduces hash operations while avoiding rule overlapping caused by hashing many rules to the same location of the hash table. Experimental results demonstrate that CRP achieves$3.2\times $classification speed and$4.2\times $update speed on average compared with state-of-the-art algorithms. We also implement CRP in OVS. The throughput of CRP-OVS is$10\times $that of native OVS.

Software-Defined Networking (SDN) facilitates net-work innovations with programmability. However, programming the network is error-prone no matter using low-level APIs or high-level programming languages. That said, SDN policies deployed in networks may contain misconfigurations. Prior studies focus on either traditional access control policies or network-wide states, and thus are unable to effectively detect potential misconfigurations in SDN policies with bitmask patterns and complex action behaviorsTo address this gap, this paper first presents a new data structure, minimal interval set, to represent the match patterns of rulesets. This representation serves the basis for composition algebra construction and fast misconfiguration checking. We then propose the principles and algorithms for fast and accurate con-figuration verification. We finally implement a misconfiguration checking tool in Covisor with optimisations to further reduce the overhead. Experiments with synthetic and random rulesets show its fitness for purpose.

Distributed deep learning (DDL) uses a cluster of servers to train models in parallel. This has been applied to a multiplicity of problems, e.g. online advertisement, friend recommendations. However, the distribution of training means that the communication network becomes a key component in system performance. In this paper, we measure the Alibaba's DDL system, with a focus on understanding the bottlenecks introduced by the network. Our key finding is that the communications overhead has a surprisingly large impact on performance. To explore this, we analyse latency logs of 1.38M Remote Procedure Calls between servers during model training for two real applications of high-dimensional sparse data. We reveal the major contributors of the latency, including concurrent write/read operations of different connections and network connection management. We further observe a skewed distribution of update frequency for individual parameters, motivating us to propose using in-network computation capacity to offload server tasks.

Monitoring the performance of a large network is very costly. Instead, a subset of paths or time intervals of the network can be measured while inferring the remaining network data by leveraging their spatiotemporal correlations. The quality of missing data recovery highly relies on the inference algorithms. Tensor completion has attracted some recent attentions with its capability of exploiting the multi-dimensional data structure for more accurate missing data inference. However, current tensor completion algorithms only model the three-order interaction of data features through the inner product, which is insufficient to capture the high-order, nonlinear correlations across different feature dimensions. In this paper, we propose a novel Neural Tensor Completion (NTC) scheme to effectively model three-order interaction among data features with the outer product and build a 3D interaction map. Based on which, we apply 3D convolution to learn features of high-order interaction from the local range to the global range. We demonstrate this will lead to good learning ability. We conduct extensive experiments on two real-world network monitoring datasets, Abilene and WS-DREAM, to demonstrate that NTC can significantly reduce the error in missing data recovery. When the sampling ratio is low at 1%, the recovery error ratios on the testing data are around 0.05 (Abilene) and 0.13 (WS-DREAM) when using NTC, but are 0.99 (Abilene) and 0.99 (WS-DREAM) using the best current tensor completion algorithms, which are 21 times and 8 times larger.

Once considered a luxury, Home Security Cameras (HSCs) are now commonplace and constitute a growing part of the wider online video ecosystem. This paper argues that their expanding coverage and close integration with daily life may result in not only unique behavioral patterns, but also key privacy concerns. This motivates us to perform a detailed measurement study of a major HSC provider, covering 15.4M streams and 211K users. Our study takes two perspectives: (i) we explore the per-user behaviour, identifying core clusters of users; and (ii) we build on this analysis to extract and predict privacy-compromising insight. Key observations include a highly asymmetrical traffic distribution, distinct usage patterns, wasted resources and fixed viewing locations. Furthermore, we identify three privacy risks and explore them in detail. We find that paid users are more likely to be exposed to attacks due to their heavier usage patterns. We conclude by proposing simple mitigations that can alleviate these risks.

Anomaly diagnosis is a critical task for building a reliable cloud system and speeding up the system recovery form failures. With the increase of scales and applications of clouds, they are more vulnerable to various anomalies, and it is more challenging for anomaly troubleshooting. System logs that record significant events at critical time points become excellent sources of information to perform anomaly diagnosis. Never-theless, existing log-based anomaly diagnosis approaches fail to achieve high precision in highly concurrent environments due to interleaved unstructured logs. Besides, transient anomalies that have no obvious features are hard to detect by these approaches. To address this gap, this paper proposes LogSayer, a log pattern-driven anomaly detection model. LogSayer represents the system state by identifying suitable statistical features (e.g. frequency, surge), which are not sensitive to the exact log sequence. It then measures changes in the log pattern when a transient anomaly occurs. LogSayer uses Long Short-Term Memory (LSTM) neural networks to learn the historical correlation of log patterns and applies a BP neural network for adaptive anomaly decisions. Our experimental evaluations over the HDFS and OpenStack data sets show that LogSayer outperforms the state-of-the-art log-based approaches with precision over 98%.

Software switches are being deployed in SDN to enable a wide spectrum of non-traditional applications. The popular Open vSwitch uses a variant of Tuple Space Search (TSS) for packet classifications. Although it has good performance on rule updates, it is less efficient than decision trees on lookups. In this paper, we propose a two-stage framework consisting of heterogeneous algorithms to adaptively exploit different characteristics of the rule sets at different scales. In the first stage, partial decision trees are constructed from several rule subsets grouped with respect to their small fields. This grouping eliminates rule replications at large scales, thereby enabling very efficient pre-cuttings. The second stage handles packet classification at small scales for non-leaf terminal nodes, where rule replications within each subspace may lead to inefficient cuttings. A salient fact is that small space means long address prefixes or less nesting levels of ranges, both indicating a very limited tuple space. To exploit this favorable property, we employ a TSS-based algorithm for these subsets following tree constructions. Experimental results show that our work has comparable update performance to TSS in Open vSwitch, while achieving almost an order-of-magnitude improvement on classification performance over TSS.

The attacks, faults, and severe communication/system conditions in Mobile Crowd Sensing (MCS) make false data detection a critical problem. Observing the intrinsic low dimensionality of general monitoring data and the sparsity of false data, false data detection can be performed based on the separation of normal data and anomalies. Although the existing separation algorithm based on Direct Robust Matrix Factorization (DRMF) is proven to be effective, requiring iteratively performing Singular Value Decomposition (SVD) for low-rank matrix approximation would result in a prohibitively high accumulated computation cost when the data matrix is large. In this work, we observe the quick false data location feature from our empirical study of DRMF, based on which we propose an intelligent Light weight Low Rank and False Matrix Separation algorithm (LightLRFMS) that can reuse the previous result of the matrix decomposition to deduce the one for the current iteration step. Depending on the type of data corruption, random or successive/mass, we design two versions of LightLRFMS. From a theoretical perspective, we validate that LightLRFMS only requires one round of SVD computation and thus has very low computation cost. We have done extensive experiments using a PM 2.5 air condition trace and a road traffic trace. Our results demonstrate that LightLRFMS can achieve very good false data detection performance with the same highest detection accuracy as DRMF but with up to 20 times faster speed thanks to its lower computation cost.

Gaining a full knowledge of end-to-end network performance is important for some advanced network management and services. Although it becomes increasingly critical, end-to-end network monitoring usually needs active probing of the path and the overhead will increase quadratically with the number of network nodes. To reduce the measurement overhead, matrix completion is proposed recently to predict the end-to-end network performance among all node pairs by only measuring a small set of paths. Despite its potential, applying matrix completion to recover the missing data suffers from low recovery accuracy and long recovery time. To address the issues, we propose MC-GPU to exploit Graphics Processing Units (GPUs) to enable parallel matrix factorization for high-speed and highly accurate Matrix Completion. To well exploit the special architecture features of GPUs for both task independent and data-independent parallel task execution, we propose several novel techniques: similar OD (origin and destination) pairs reordering taking advantage of the locality-sensitive hash (LSH) functions, balanced matrix partition, and parallel matrix completion. We implement the proposed MC-GPU on the GPU platform and evaluate the performance using real trace data. We compare the proposed MC-GPU with the state of the art matrix completion algorithms, and our results demonstrate that MC-GPU can achieve significantly faster speed with high data recovery accuracy.

Monitoring the performance of a large network would involve a high measurement cost. To reduce the overhead, sparse network monitoring techniques may be applied to select paths or time intervals to take the measurements, while the remaining monitoring data can be inferred leveraging the spatial-temporal correlations among data. The quality of missing data recovery, however, highly relies on the specific inference technique adopted. Tensor completion is a promising technique for more accurate missing data inference by exploiting the multi-dimensional data structure. However, data processing for higher dimensional tensors involves a large amount of computation, which prevents conventional tensor completion algorithms from practical application in the presence of large amount of data. This work takes the initiative to investigate the potential and methodologies of performing parallel processing for high-speed and high accuracy tensor completion over Graphics Processing Units (GPUs). We propose a GPU-accelerated parallel Tensor Completion scheme (GPU-TC) for accurate and fast recovery of missing data. To improve the data recovery accuracy and speed, we propose three novel techniques to well exploit the tensor factorization structure and the GPU features: grid-based tensor partition, independent task assignment based on Fisher-Yates shuffle, sphere facilitated and memory-correlated scheduling. We have conducted extensive experiments using network traffic trace data to compare the proposed GPU-TC with the state of art tensor completion algorithms and matrix-based algorithms. The experimental results demonstrate that GPU-TC can achieve significantly better performance in terms of two relative error ratio metrics and computation time.

Sketches are probabilistic data structures designed for recording frequencies of items in a multi-set. They are widely used in various fields, especially for gathering Internet statistics from distributed data streams in network measurements. In a distributed streaming application with high data rates, a sketch in each monitoring node “fills up” very quickly and then its content is transferred to a remote collector responsible for answering queries. Thus, the size of the contents transferred must be kept as small as possible while meeting the desired accuracy requirement. To obtain significantly higher accuracy while keeping the same update and query speed as the best prior sketches, in this article, we propose a new sketch - the Slim-Fat (SF) sketch. The key idea behind the SF-sketch is to maintain two separate sketches: a larger sketch, the Fat-subsketch, and a smaller sketch, the Slim-subsketch. The Fat-subsketch is used for updating and periodically producing the Slim-subsketch, which is then transferred to the remote collector for answering queries quickly and accurately. We also present the error bound as well as an accurate model of the correct rate of the SF-sketch, and verify their correctness through experiments. We implemented and extensively evaluated the SF-sketch along with several prior sketches. Our results show that when the size of our Slim-subsketch and of the widely used Count-Min (CM) sketch are kept the same, our SF-sketch outperforms the CM-sketch by up to 33.1 times in terms of accuracy (when the ratio of the sizes of the Fat-subsketch and the Slim-subsketch is 16:1). We have made all source codes publicly available at Github [“Source code of SF sketches,” [Online]. Available: https://github.com/paper2017/SF-sketch].

The power consumption of IT equipment is always being a big challenge for data centers. The research communities are attempting to solve this problem, by employing various of energy-aware tasks scheduling or VMs consolidation policies. It is crucial for these policies to figure out the major parameters that affect power consumption and their correlation. In this paper, we first identify the major parameters using real cloud services' workload and power consumption data. An important observation is that the parameters are strongly interdependent and the importance of individual parameters varies in different cloud services. Nevertheless, existing power consumption models are unable to fully capture this feature and thus lack generalization. To address this gap, we propose Lapem that adopts a Long Short-term Memory network for power consumption estimation. Lapem further uses an attention mechanism to achieve stable performance and improve generalization. The experimental results demonstrate that Lapem estimates power consumption with a relative error of as low as 2%-5%. More importantly, in comparison with the state-of-the-art models, Lapem reduces the estimation error by more than 23% when generalizing to new cloud services.

Multi-Tenancy (MT) is critical for Network Function Virtualization (NFV) platform as it reduces the cost of having network services by sharing expensive server resource among customers. This is especially critical for memory and CPU intensive services like Network Intrusion Prevention System (NIPS). In this work, we explore the issue of deploying a large-scale virtualized NIPS service on a commercial NFV platform. We observe that the scalability of NIPS service is not good when based on independent Virtual Machines (VMs). We propose a Multi-Tenant Aho-Corasick state machine data structure (MT-AC) and adapt it into NIPS to solve the issue. One MT-AC based NIPS service simultaneously checks traffic belonging to different tenants against a merged ruleset. The MT-AC data structure is very efficient as it eliminates the redundancies among tenants' signatures during the rulesets merging. Experimental results with real-world ruleset show that, in comparison with an independent VM-based solution, the MT-AC based NIPS service can support 2 to 4 times more tenants. Moreover, the throughput and latency performance of MT-AC based NIPS engine only degrades by 1%, when the tenant count increases from 8 to 128. The results validate that, the proposed MT-AC based NIPS service on NFV platform can support a large amount of tenants with a very low cost.

Traffic anomaly detection is critical for advanced Internet management. Existing detection algorithms usually work off-line and cannot timely detect anomalies. They also suffer from high cost for storage and computation. Although online and accurate traffic anomaly detection is very important, it very difficult to achieve. We propose to utilize tensor model to well exploit the multi-dimensional information hidden in the traffic data for more accurate online Internet anomaly detection. We decouple the tensor recovery problem to iteratively solve two sub problems, a tensor factorization sub-problem and an anomaly detection sub-problem. To reduce the high cost for computation and storage involved in tensor factorization, we propose two lightweight techniques to effectively derive factor matrices of tensor in the current window and iteration, taking advantage of tensor decomposition results of the previous window and iteration. We have done extensive experiments using two real traffic traces to compare with three tensor based algorithms and three matrix based algorithms. The experiment results demonstrate that our online anomaly detection algorithm can achieve the same anomaly detection accuracy as that of the best offline tensor based algorithm, but at 6100 times faster speed and with very low storage cost.

With the proliferation of smartphones, a novel sensing paradigm called Mobile Crowd Sensing (MCS) has emerged very recently. However, the attacks and faults in MCS cause a serious false data problem. Observing the intrinsic low dimensionality of general monitoring data and the sparsity of false data, false data detection can be performed based on the separation of normal data and anomalies. Although the existing separation algorithm based on Direct Robust Matrix Factorization (DRMF) is proven to be effective, requiring iteratively performing Singular Value Decomposition (SVD) for low-rank matrix approximation would result in a prohibitively high accumulated computation cost when the data matrix is large. In this work, we observe the quick false data location feature from our empirical study of DRMF, based on which we propose an intelligent Light weight Low Rank and False Matrix Separation algorithm (LightLRFMS) that can reuse the previous result of the matrix decomposition to deduce the one for the current iteration step. Our algorithm can largely speed up the whole iteration process. From a theoretical perspective, we validate that LightLRFMS only requires one round of SVD computation and thus has very low computation cost. We have done extensive experiments using a PM 2.5 air condition trace and a road traffic trace. Our results demonstrate that LightLRFMS can achieve very good false data detection performance with the same highest detection accuracy as DRMF but with up to 10 times faster speed thanks to its lower computation cost.

Finding top- k elephant flows is a critical task in network measurement, with applications such as congestion control, anomaly detection, and traffic engineering. Traditional top- k flow detection problem focuses on using a small amount of memory to measure the total number of packets or bytes of each flow. Instead, we study a challenging problem of inferring the top- k elephant flows in a practical system with incomplete measurement data as a result of sub-sampling for scalability or data missing. The recent study shows it is promising to more accurately interpolate the missing data with a 3-D tensor compared to that based on a 2-D matrix. Taking full advantage of the multilinear structures, we apply tensor completion to first recover the missing data and then find the top- k elephant flows. To reduce the computational overhead, we propose a novel discrete tensor completion model which uses binary codes to represent the factor matrices. Based on the model, we further propose three novel techniques to speed up the whole top- k flow inference process: a discrete optimization algorithm to train the binary factor matrices, bit operations to facilitate quick missing data inference, and simplifying the finding of top- k elephant flows with binary code partition. In our discrete tensor completion model, only one bit is needed to represent the entry in the factor matrices instead of a real value (32 bits) needed in traditional tensor completion model, thus the storage cost is reduced significantly. Extensive experiments using two real traces demonstrate that compared with the state of art tensor completion algorithms, our discrete tensor completion algorithm can achieve similar data inference accuracy using significantly smaller time and storage space.

A major factor that prevents the large scale deployment of Mobile Crowd Sensing (MCS) is its sensing and communication cost. Given the spatio-temporal correlation among the environment monitoring data, matrix completion (MC) can be exploited to only monitor a small part of locations and time, and infer the remaining data. Rather than only taking random measurements following the basic MC theory, to further reduce the cost of MCS while ensuring the quality of missing data inference, we propose an Active Sparse MCS (AS-MCS) scheme which includes a bipartite-graph-based sensing scheduling scheme to actively determine the sampling positions in each upcoming time slot, and a bipartite-graph-based matrix completion algorithm to robustly and accurately recover the un-sampled data in the presence of sensing and communications errors. We also incorporate the sensing cost into the bipartite-graph to facilitate low cost sample selection and consider the incentives for MCS. We have conducted extensive performance studies using the data sets from the monitoring of PM 2.5 air condition and road traffic speed, respectively. Our results demonstrate that our AS-MCS scheme can recover the missing data at very high accuracy with the sampling ratio only around $11%$, while the peer matrix completion algorithms with similar recovery performance requires up to 4-9 times the number of samples of ours for both the data sets.

Dual-band WiFi which supports both 2.4 GHz and 5 GHz has been widely deployed, aiming to expand wireless capacity, and eliminate serious interference in 2.4 GHz. As the proportion of dual-band APs and clients increase enormously, how to select which band to access to achieve considerable user experience is becoming essential in wireless network. Clients' native decisions that tend to prefer 5 GHz will consequently cause serious interference in 5 GHz and leave 2.4 GHz notably idle. Through analyzing a unique dataset in the wild, we quantitatively study the impact of various WiFi factors on the wireless delay. We propose a decision tree approach to intelligent access selection that decides which band to access dynamically according to prior learned schemes. A prototype of the access selection system named LazyAS, which only requires modification at AP side, is realized and deployed in a production WiFi network. Evaluation results demonstrate that LazyAS reduces the 90th percentile of wireless delay in the production WiFi network from 32 ms to 12 ms.

The inference of the network traffic data from partial measurements data becomes increasingly critical for various network engineering tasks. By exploiting the multi-dimensional data structure, tensor completion is a promising technique for more accurate missing data inference. However, existing tensor completion algorithms generally have the strong assumption that the tensor data have a global low-rank structure, and try to find a single and global model to fit the data of the whole tensor. In a practical network system, a subset of data may have stronger correlation. In this work, we propose a novel localized tensor completion model (LTC) to increase the data recovery accuracy by taking advantage of the stronger local correlation of data to form and recover sub-tensors each with a lower rank. Despite that it is promising to use local tensors, the finding of correlated entries faces two challenges, the data with adjacent indexes are not ones with higher correlation and it is difficult to find the similarity of data with missing tensor entries. To conquer the challenges, we propose several novel techniques: efficiently calculating the candidate anchor points based on locality-sensitive hash (LSH), building sub-tensors around properly selected anchor points, encoding factor matrices to facilitate the finding of similarity with missing entries, and similarity-aware local tensor completion and data fusion. We have done extensive experiments using real traffic traces. Our results demonstrate that LTC is very effective in increasing the tensor recovery accuracy without depending on specific tensor completion algorithms.

TCP is an important factor affecting user-perceived performance of Internet applications. Diagnosing the causes behind TCP performance issues in the wild is essential for better understanding the current shortcomings in TCP. This paper presents a TCP flow performance analysis framework that classifies causes of TCP stalls. The framework forms the basis of a tool that we use to analyze packet-level traces of three services (cloud storage, software download, and web search) deployed by a popular service provider. We find that as many as 20% of the flows are stalled for half of their lifetime. Network-related causes, especially timeout retransmissions, dominate the stalls. A breakdown of the causes for timeout retransmission stalls reveals that double retransmission and tail retransmission are among the top contributors. The importance of these causes depends however on the specific service. Based on these observations, we propose smart-retransmission time out (S-RTO), a mechanism that mitigates timeout retransmission stalls through careful and gentle aggression for retransmission. S-RTO is evaluated in a controlled network and also in a production network. The results consistently show that it is effective at improving TCP performance, especially for short flows.

Offloading computation intensive applications to mobile cloud is promising for overcoming the problems of limited computational resources and energy of mobile devices. However, without considering the competition relationship of mobile users and cloudlets in the mobile cloud computing system, existing studies lack an incentive mechanism for the system to achieve efficient application offloading and cloud resource provisioning. In this paper, we design MPTMG, a Multi-dimensional Pricing mechanism based on Two-sided Market Game. We propose three types of prices: a multi-dimensional price corresponding to multi-dimensional resource allocation, a penalty price to encourage fair and high quality cloud services, and a benefit discount factor to motivate more even provisioning of resources on different dimensions in the cloud. Based on these prices, we propose a distributed price-adjustment algorithm for efficient resource allocation and QoS-aware offloading scheduling. We prove that the algorithm can converge in a finite number of iterations to the equilibrium core allocation at which the mobile cloud system achieves the Pareto efficiency by maximizing the total system benefit. To the best of our knowledge, this is the first paper that applies economic theories and pricing mechanisms to manage application offloading in mobile cloud systems. The simulation results demonstrate that our proposed pricing mechanism can significantly improve the system performance.

Name lookup is a core function of the Named Data Networking (NDN) forwarding plane. It performs a name-based longest prefix match lookup against a large amount of variable-length, hierarchical name prefixes. NDN name lookup suffers a scalability challenge and needs to satisfy three key requirements: high-speed lookups, low memory cost, and fast updates. However, no existing work satisfies these requirements. Hash-based linear search schemes achieve fast updates and low memory cost but not high-speed lookups. Binary search (BS) schemes achieve high-speed lookups but slow updates with high memory cost. In this paper, we propose CBS, a hash-based counting binary search scheme for scalable high-speed NDN name lookup. CBS achieves fast updates and low memory cost, while sustaining high-speed lookups. The key to CBS is using a counter for each slot in a hash table to keep track of the number of markers that direct a search to find longer matching prefixes. This design not only allows fast updates by incrementing and decrementing counters, but also reduces the additional memory cost. Our experimental results demonstrate that CBS outperforms BS in update throughput, memory cost, and lookup throughput.

Ensuring transmission survivability is a crucial problem for high-speed networks. Path protection is a fast and capacity-efficient approach for increasing the availability of end to end connections. The emerging SDN infrastructure makes it feasible to provide diversity routing in a practical network. For more robust path protection, it is desirable to provide an alternative path that does not share any risk resource with the active path. We consider finding the SRLG-Disjoint paths, where a Shared Risk Link Group (SRLG) is a group of network links that share a common physical resource whose failure will cause the failure of all links of the group. Since the traffic is carried on the active path most of time, it is useful that the weight of the shorter path of the disjoint path pair is minimized, and we call it Min-Min SRLG-Disjoint routing problem. The key issue faced by SRLG-Disjoint routing is the trap problem, where the SRLG-disjoint backup path (BP) can not be found after an active path (AP) is decided. Based on the min-cut of the graph, we design an efficient algorithm that can take advantage of existing search results to quickly look for the SRLG-Disjoint path pair. Our performance studies demonstrate that our algorithm can outperform other approaches with a higher routing performance while also at a much faster speed.

Packet forwarding is the foundation of network communications. Internet routers forward packets by matching the packet destination address against the prefixes in the forwarding information base. Due to the emergence of cloud computing and network function virtualization, more and more applications require high-bandwidth low-latency IPv6 networks. However, most of the current IP lookup algorithms in practice are designed for IPv4 addresses and hard to scale to IPv6 addresses. In this paper, we first propose a novel data structure called hierarchical balanced search tree (Hi-BST). The compact and scalable data structure built can be stored in on-chip memory. On the basis of Hi-BST, we present a fast IPv6 lookup algorithm and prefix update algorithms. In the worst case, our algorithm can achieve fast lookup and update with the time that is proportional to the logarithm of the number of prefixes. Experiments using real FIBs give an integrated evaluation. Compared with the state-of-the-art algorithms, our algorithm achieves a fast lookup with realtime updates, which is 1.33 ~6.78 times that of the comparison algorithms respectively. Moreover, Hi-BST saves 4.3% 79.0% memory footprint of the comparison algorithms respectively.

Tensor completion can be applied to fill in the missing data, which is import for many data applications where the data are incomplete. To infer the missing data, existing tensor-completion algorithms generally assume that the tensor data have global low-rank structure and apply a single model to fit the overall observed data through the global optimization. However, there are different correlation levels among application data, thus the ranks of some sub-tensors can be even lower relative to that of the large tensor. Fitting a single model to all data will compromise the performance of data recovery. To increase the accuracy in missing data recovery, we propose to apply local tensor completion (Local-TC) to recover data from sub-tensors, with each containing data of higher correlations. Although promising, as the tensor data are only organized logically, it is difficult to determine the relationship among data. We propose to exploit locality-sensitive hash (LSH) to quickly find the data correlation and reorganize tensor data, based on which data entries with high correlations are put into the same sub-tensor. The experiment results demonstrate that Local-TC is very effective in increasing the recovery accuracy.

Efficient algorithmic solutions for multi-field packet classification have been a challenging problem for many years. This problem is becoming even worse in the era of Software Defined Network (SDN), where flow tables with increasing complexities are playing a central role in the forwarding plane of SDN. In this paper, we first conduct an unprecedented in-depth reasoning on issues that led to the unsuccess of the major quests for scalable algorithmic solutions. With the insights obtained, we propose a practical framework called CutSplit, which can exploit the benefits of cutting and splitting techniques adaptively. By addressing the central problem caused by uncontrollable rule replications suffered by the major efforts, CutSplit not only pushes the performance of algorithmic packet classification more closely to hardware-based solutions, but also reduces the memory consumption to a practical level. Moreover, our work achieves low pre-processing time for rule updates, a problem that has long been ignored by previous decision-trees, but is becoming more relevant in the context of SDN due to frequent updates of rules. Experimental results show that using ClassBench, CutSplit achieves a memory reduction over 10 times, as well as 3x improvement on performance in terms of the number of memory access on average.

Detecting anomalous traffic is a crucial task of managing networks. Many anomaly detection algorithms have been proposed recently. However, constrained by their matrix-based traffic data model, existing algorithms often suffer from low detection accuracy. To fully utilize the multi-dimensional information hidden in the traffic data, this paper takes an initiative to investigate the potential and methodologies of performing tensor factorization for more accurate Internet anomaly detection. Only considering the low-rank linearity features hidden in the data, current tensor factorization techniques would result in low anomaly detection accuracy. We propose a novel Graph-based Tensor Recovery model (Graph-TR) to well explore both low rank linearity features as well as the non-linear proximity information hidden in the traffic data for better anomaly detection. We encode the non-linear proximity information of the traffic data by constructing nearest neighbor graphs and incorporate this information into the tensor factorization using the graph Laplacian. Moreover, to facilitate the quick building of neighbor graph, we propose a nearest neighbor searching algorithm with the simple locality-sensitive hashing (LSH). We have conducted extensive experiments using Internet traffic trace data Abilene and GEANT. Compared with the state of art algorithms on matrix-based anomaly detection and tensor recovery approach, our Graph-Trcan achieve significantly lower False Positive Rate and higher True Positive Rate.

Like IP lookup in the traditional networking, name lookup is a key technology for packet forwarding in the named data networking (NDN). However, unlike fixed-length IP addresses, such hierarchical names are of variable and unlimited length in theory. Both the large-scale name prefix database and high-frequency name update bring unprecedented challenges to the high-performance packet forwarding in the NDN. However, most existing approaches have drawbacks, such as the complex structure, the frequent memory access, and the time-consuming encoding, which make them difficult to meet these requirements. In this paper, we propose CoDE, an effective name lookup approach, to achieve both fast name lookup and update using conflict-driven encoding. CoDE has the following features: 1) The compact and scalable data structure can be stored in the cache; 2) The efficient index can fast locate the possible names and thus significantly speed up the name lookup and prefix update; and 3) The conflict-driven mechanism can greatly reduce the number of name components to be encoded. Experiments using real name prefix databases give an integrated evaluation. Compared with the state-of-the-art algorithms, CoDE achieves a high-performance name lookup which is an order of magnitude faster than the other algorithms on average and performs a fast prefix update which is twenty times that of the other algorithms on average. Moreover, CoDE saves at least half memory footprint of that of the other algorithms.

Web tracking plays a crucial role in the Web ecosystem. It relies on third-party tracking domains collecting user information for various applications such as advertisement and analytics. With the massive growth of the Internet, understanding tracking and its geographical roots is of strategic importance. The goal of this paper is to propose a thorough investigation of web tracking inside China taking advantage of a large dataset (1011records) containing two days of full DNS access from a major ISP providing both mobile and landline ADSL. Our results show that a power law applies on the traffic of both sites and trackers with a handful of trackers, 26, representing 90% of tracking activity. We then show that although most first-party sites accessed from China are owned by Chinese corporations, large proportion of trackers belong to US ones. This raises concerns about the analytics industry in China, and more generally shed new lights on the international data flows, the interdependency of the main actors, and the complexity of the threats for both people and states.

DNS is a critical component of Internet architecture. Almost all applications, in particular web based applications that constitute the large majority of current Internet traffic, leverage heavily on DNS. This makes DNS based measurements a promising tool for understanding global properties of Internet traffic, e.g., sites audience, traffic matrix. However, using passive DNS traces from local DNS servers is challenging because of DNS caching and NATs. The goal of this paper is twofold. First, we show how to correct the bias due to DNS cache and the wide use of NATs, to extract meaningful traffic information from DNS traces. The techniques are then used and validated over a large dataset (1011records) containing two days of full DNS access from a major ISP providing both mobile and landline ADSL in China. Second, we focus on the tracking activity and show that although most sites accessed from China belong to Chinese corporations, most trackers belong to US ones. Mobile and ADSL platforms are alike.

Video providers heavily rely on geographically distributed content distribution networks (CDNs) to place video content as close to users as possible, with an aim of improving video quality and avoiding single point of failure at the server side. The effectiveness of CDNs is mostly dependent on the content consumption patterns. Currently, video providers are offering access to content from different platforms (e.g., mobile devices and PC clients), which might result in distinct video content consumption patterns and finally affect the efficiency of CDN caching. Nevertheless, the access type effect on Internet videos is not well understood. In this paper, using a data set consisting of 26 million video requests of a large-scale commercial video-on-demand system, we study the effect of three main access types, i.e., proprietary software on PC clients, Web browser, and mobile apps. Several observations suggest that access types should be considered carefully in CDN design. In particular, the user engagement, user interests in content, and video popularity dynamics patterns, three important factors for video caching, vary remarkably in the three access types. Leveraging off our findings, we propose an access type-aware CDN caching system that associates a cache for each access type and also several optimizations, including partial caching of videos based on chunk-level caching, cross-platform read-only cache access, and prefiltering of the least popular videos. Trace-driven simulations demonstrate that the access type-aware CDN caching achieves high cache hit rate and, more importantly, greatly reduces the disk load that is measured by the number of cache replacement operations.

Matrix completion has emerged very recently and provides a new venue for low cost data gathering in Wireless Sensor Networks (WSNs). Existing schemes often assume that the data matrix has a known and fixed low-rank, which is unlikely to hold in a practical system for environment monitoring. Environmental data vary in temporal and spatial domains. By analyzing a large set of weather data collected from 196 sensors in ZhuZhou, China, we reveal that weather data have the features of low-rank, temporal stability, and relative rank stability. Taking advantage of these features, we propose an on-line data gathering scheme based on matrix completion theory, named MC-Weather, to adaptively sample different locations according to environmental and weather conditions. To better schedule sampling process while satisfying the required reconstruction accuracy, we propose several novel techniques, including three sample learning principles, an adaptive sampling algorithm based on matrix completion, and a uniform time slot and cross sample model. With these techniques, our MC-Weather scheme can collect the sensory data at required accuracy while largely reducing the cost for sensing, communication, and computation. We perform extensive simulations based on the data traces from weather monitoring and the simulation results validate the efficiency and efficacy of the proposed scheme.

Software-defined networking envisions the support of multiple applications collaboratively operating on the same traffic. Policies of applications therefore require composition into a rule list that represents the union of application intents. In this context, ensuring the correctness and efficiency of composition for match fields as well as the associated actions is the fundamental requirement. Prior work however focuses only on the composition of match fields and assumes simple concatenation for action composition. We show in this paper that simple concatenation can result in incorrect behavior and inefficiency of packet processing. To address this issue, we formalize the action composition problem and propose two graph-based computation models to facilitate efficient composition of action lists. Our proposed approach has been integrated into the CoVisor code base and the evaluation results show its fitness for purpose.

Ternary content addressable memories (TCAMs) are frequently used for fast matching of packets against a given ruleset. While TCAMs can achieve fast matching, they are plagued by high update costs that can make them unusable in a high churn rate environment. We present, in this paper, a systematic and in-depth analysis of the TCAM update problem. We apply partial order theory to derive fundamental constraints on any rule ordering on TCAMs, which ensures correct checking against a given ruleset. This theoretical insight enables us to fully explore the TCAM update algorithms design space, to derive the optimal TCAM update algorithm (though it might not be suitable to be used in practice), and to obtain upper and lower bounds on the performance of practical update algorithms. Having lower bounds, we checked if the smallest update costs are compatible with the churn rate observed in practice, and we observed that this is not always the case. We therefore developed a heuristic based on ruleset splitting, with more than a single TCAM chip, that achieves significant update cost reductions (1.05~11.3×) compared with state-of-the-art techniques.

Sampling social graphs is critical for studying things like information diffusion. However, it is often necessary to laboriously obtain unbiased and well-connected datasets because existing survey algorithms are unable to generate well-connected samples, and current random-walk based unbiased sampling algorithms adopt rejection sampling, which heavily undermines performance. This paper proposes a novel random-walk based algorithm which implements Unbiased Sampling using Dummy Edges (USDE). It injects dummy edges between nodes, on which the walkers would otherwise experience excessive rejections before moving out from such nodes. We propose a rejection probability estimation algorithm to facilitate the construction of dummy edges and the computation of moving probabilities. Finally, we apply USDE in two real-life social media: Twitter and Sina Weibo. The results demonstrate that USDE generates well-connected samples, and outperforms existing approaches in terms of sampling efficiency and quality of samples.

Dual-band WiFi which supports both 2.4GHz and 5GHz has been widely deployed, aiming to expand wireless capacity and eliminate serious interference in 2.4GHz. Thus, how to select which band to access to achieve considerable user experience is becoming essential in wireless network. Clients' native decision that always prefers 5GHz will consequently cause serious interference in 5GHz and leave 2.4GHz notably idle. Through analyzing a unique dataset in the wild, we quantitatively study the impact of various WiFi factors on the wireless delay. We propose a decision tree approach for intelligent access selection that decides which band to access dynamically according to prior learned schemes. A prototype of the access selection system named LazyAS, which only requires modification at AP side, is realized and deployed in production WiFi network. Evaluation results demonstrate that our proposed LazyAS reduces the 90th percentile of wireless delay in the production WiFi network from 32ms to 12ms.

A sketch is a probabilistic data structure that is used to record frequencies of items in a multi-set. Sketches have been applied in a variety of fields, such as data stream processing, natural language processing, distributed data sets etc. In this paper, we propose a new sketch, called Slim-Fat (SF) sketch, which has a much smaller memory footprint for query while supporting updates. The key idea behind our proposed SF-sketch is to maintain two separate sketches: a small sketch called Slimsubsketch and a large sketch called Fat-subsketch. The Slimsubsketch enables fast and accurate querying. The Fat-subsketch is used to assist the insertion and deletion from Slim-subsketch. We implemented and evaluated SF-sketch along with several prior sketches and compared them side by side. Our experimental results show that SF-sketch significantly outperforms the most commonly used CM-sketch in terms of accuracy. The full version is provided at arXiv.org [12].

Software-Defined Networking (SDN) provides network administrators opportunities to control network devices more simply and easily than in traditional networking. However, heterogeneity in switch hardware, especially in forwarding pipeline architecture, renders the task of network application developers and network administrators tedious, by hampering portability across switch models. In this paper, we propose FlowConvertor, an algorithm capable of converting rules from any forwarding pipeline to any other different forwarding pipeline, as long as both pipelines offer compatible operations. More precisely, FlowConvertor is an online algorithm that operates on flow updates issued to the origin pipeline and computes the corresponding updates for the target pipeline in real time. Performance evaluation shows that the latency introduced by FlowConvertor on the path between the SDN controller and the target switch is of the order of 1ms in most cases, and is thus acceptable for practical deployment.

The inference of the network traffic matrix from partial measurement data becomes increasingly critical for various network engineering tasks, such as capacity planning, load balancing, path setup, network provisioning, anomaly detection, and failure recovery. The recent study shows it is promising to more accurately interpolate the missing data with a three-dimensional tensor as compared to interpolation methods based on two-dimensional matrix. Despite the potential, it is difficult to form a tensor with measurements taken at varying rate in a practical network. To address the issues, we propose Reshape-Align scheme to form the regular tensor with data from dynamic measurements, and introduce user-domain and temporal-domain factor matrices which takes full advantage of features from both domains to translate the matrix completion problem to the tensor completion problem based on CP decomposition for more accurate missing data recovery. Our performance results demonstrate that our Reshape-Align scheme can achieve significantly better performance in terms of two metrics: error ratio and mean absolute error (MAE).

Detecting anomalous traffic is a critical task for advanced Internet management. The traditional approaches based on Principal Component Analysis (PCA) are effective only when the corruption is caused by small additive i.i.d. Gaussian noise. The recent Direct Robust Matrix Factorization (DRMF) is proven to be more robust and accurate in anomaly detection, but it incurs a high computation cost due to its need of singular value decomposition (SVD) for low-rank matrix approximation and the iterative use of SVD execution to find the final solution. To enable the anomaly detection for large traffic matrix with the use of DRMF, we formulate the low-rank matrix approximation problem as a problem of searching for the subspace to project the traffic matrix with the minimum error. We propose a novel approach, LSH-subspace, for fast low-rank matrix approximation. To facilitate the matrix partition for the quick search of the subspace, we propose several novel techniques: a multi-layer locality sensitive hashing (LSH) table to reorder the OD pairs based on LSH function, a partition principle to guide the partition to minimize the projection error, and a lightweight algorithm to exploit the sparsity of the outlier matrix to update the LSH table at low overhead. Our extensive simulations based on real trace data demonstrate that our LSH-subspace is 3 times faster than DRMF with high anomaly detection accuracy.

NFV together with SDN promises to provide more flexible and efficient service provision methods by decoupling the network functions (NFs) from the physical network topology and devices, but requires the real-time and automatic composition and verification for service function chain (SFC). However, most of SFCs today are still typically built through manual configuration processes, which are slow and error prone. In this paper, we present a novel SFC composition framework, called Automatic Composition Toolkit (ACT). It aims to automatically detect the dependencies and conflicts between NFs, so as to compose and verify SFCs before they are enforced on the physical infrastructure.

In SDN-based WLAN, controller needs to collect the state info of Mobile Nodes (MNs) like received signal strength indicator (RSSI) for handoff. In such scenarios, high sampling rate facilitates handoff, but it also easily leads to system overhead thus limits access scale of MN. Besides, dynamical adjustment of transmit power of access point (AP) leads to the distinctive signal coverage. Existing handoff algorithms that directly use the uplink RSSI as handoff condition would result in significant throughput decay of MN. Also in indoor deployment RSSI may varies much, large variation of RSSI result in unstable handoff. To address the issues, we design a variable sampling rate mechanism, then filter sampling RSSI and propose a handoff algorithm for distinctive signal coverage scenarios. Our sampling mechanism uses a finite state machine (FSM) to adjust the sampling rate by MN on all nearby APs. Our handoff algorithm uses Kalman filter to achieve stable and trend-reflecting uplink RSSI estimation, then estimate downlink signal noise ratio (SNR) difference between potential and current AP. We implement our algorithm and deployed a test-bed for extensive experiments. Results show our sampling mechanism could achieve sampling quantity decrease by 60%; compared to mean filter based approach, our handoff algorithm improves throughput by 10-50% in distinctive signal coverage scenarios. Besides, handoff frequency decreased by about 60%, indicating a more stable handoff decision.

As Wi-Fi networks are becoming insecurely denser, frame loss and the consequent throughput degradation are much more profound, due to severe interference in dense networks. Pre- vious works propose to exploit multi-radio diversity to improve loss resilience. However, they are far from practical because of their incompatibility with the Wi-Fi standard, high deployment cost and large processing delay. In this work, we propose Musubi, which is a practical and low cost solution for exploiting multi- radio diversity. Furthermore, Musubi does not require client-side modification, thus it is totally compatible with the legacy Wi-Fi standard. Musubi leverages flexibility and programmability of the growingly-popular Software- Defined-Network (SDN) based WLAN, and incorporates capture effect and redundancy packet elimination, so as to handle the specific challenges raised in loss resilience. Compared with a state- of-the-art solution, in theory analysis, Musubi achieve 15% jitter decrease with only 0.8% throughput decrease, when frame loss rate is 20%. We implemented deployed and evaluated Musubi. Experiment results show that Musubi reduces frame loss by 70% and achieves throughput gain up to 1.4amp;#x000D7; as well as packet delay decreasing by 34% compared with the legacy Wi-Fi.

In mobile live streaming systems, users have fairly limited interactions with streaming objects due to the constraints coming from mobile devices and the event-driven nature of live content. The constraints could lead to unique user behavior characteristics, which have yet to be explored. This paper investigates over 9 million access logs collected from the PPTV live streaming system, with an emphasis on the discrepancies that might exist when users access the live streaming catalog from mobile and nonmobile terminals. We observe a much higher likelihood of abandoning sessions by mobile users and examine the structure of abandoned sessions from the perspectives of time of day, channel content, and mobile device types. Surprisingly, we find relatively low abandonment rates during peak-load time periods and a notable impact of mobile device type (i.e., Android or iOS) on the abandonment behavior. To further capture the intrinsic characteristics of user behavior, we develop a series of models for session duration, user activity, and time dynamics of user arrivals/departures. More importantly, we relate the model parameters to physical and real-life meanings. The observations and models shed light on a video delivery system, telco-content delivery networks, and mobile applications.

Affected by hardware and wireless conditions in WSNs, raw sensory data usually have notable data loss and corruption. Existing studies mainly consider the interpolation of random missing data in the absence of the data corruption. There is also no strategy to handle the successive missing data. To address these problems, this paper proposes a novel approach based on matrix completion (MC) to recover the successive missing and corrupted data. By analyzing a large set of weather data collected from 196 sensors in Zhu Zhou, China, we verify that weather data have the features of low-rank, temporal stability, and spatial correlation. Moreover, from simulations on the real weather data, we also discover that successive data corruption not only seriously affects the accuracy of missing and corrupted data recovery but even pollutes the normal data when applying the matrix completion in a traditional way. Motivated by these observations, we propose a novel Principal Component Analysis (PCA)-based scheme to efficiently identify the existence of data corruption. We further propose a two-phase MC-based data recovery scheme, named MC-Two-Phase, which applies the matrix completion technique to fully exploit the inherent features of environmental data to recover the data matrix due to either data missing or corruption. Finally, the extensive simulations with real-world sensory data demonstrate that the proposed MC-Two-Phase approach can achieve very high recovery accuracy in the presence of successively missing and corrupted data.

Detecting anomalous traffic is a critical task for advanced Internet management. Many anomaly detection algorithms have been proposed recently. However, constrained by their matrix-based traffic data model, existing algorithms often suffer from low accuracy in anomaly detection. To fully utilize the multi-dimensional information hidden in the traffic data, this paper takes the initiative to investigate the potential and methodologies of performing tensor factorization for more accurate Internet anomaly detection. More specifically, we model the traffic data as a three-way tensor and formulate the anomaly detection problem as a robust tensor recovery problem with the constraints on the rank of the tensor and the cardinality of the anomaly set. These constraints, however, make the problem extremely hard to solve. Rather than resorting to the convex relaxation at the cost of low detection performance, we propose TensorDet to solve the problem directly and efficiently. To improve the anomaly detection accuracy and tensor factorization speed, TensorDet exploits the factorization structure with two novel techniques, sequential tensor truncation and two-phase anomaly detection. We have conducted extensive experiments using Internet traffic trace data Abilene and GÈANT. Compared with the state of art algorithms for tensor recovery and matrix-based anomaly detection, TensorDet can achieve significantly lower false positive rate and higher true positive rate. Particularly, benefiting from our well designed algorithm to reduce the computation cost of tensor factorization, the tensor factorization process in TensorDet is 5 (Abilene) and 13 (GÈANT) times faster than that of the traditional Tucker decomposition solution.

Set queries are fundamental operations in computer networks. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a shifting bloom filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF-based set data structures allocate additional memory to store auxiliary information. We further extend our shifting framework from BF-based data structures to sketch-based data structures, which are widely used to store multiplicities of items. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries.

Smartphones have become an important component of everyday's life. They store a large amount of users' private and sensitive information like contacts, GPS location, messages and interests. Privacy issues are a growing concern for the phone users. However, despite an existing rich literature in privacy leakage on mobile network measurement, our empirical knowledge of users' private leakage is relatively limited. In this work, we present a large scale and comprehensive investigation spanning over 9 months of users' private information leakage that consisted of monitoring 180K popular apps coming from 50+ Chinese AppStores. In order to do this, we used a customized platform that can monitor the execution of applications running over Android system to observe in vivo privacy leakage of applications. Our key findings are that: (1) Accessing users' private information is very common among mobile apps, i.e. over 90% of apps accesses some kind of user private information, and to our surprise, almost 95% apps claimed access to private information without concretely accessing them (2) We analyzed different category of Apps and observed slight differences in the pattern of access to private information among different categories (3) Downloading apps from big Appstores does not necessarily mean safer and more private apps. We observe that local Chinese shop and Google Play generate similar observations.

Vehicles equipped with various types of sensors can act as mobile sensors to monitor the road conditions. To speed up the information collection process, the monitoring data can be shared among vehicles upon their encounters to facilitate drivers to find a good route. The vehicular network experiences intermittent connectivity as a result of the mobility, which makes the inter-vehicle contact duration a scarce resource for data transmissions and the support of monitoring applications over vehicular networks a challenge. We propose a novel compressive sensing (CS)-based scheme to enable efficient decentralized context sharing in vehicular delay tolerant networks, called CS-Sharing. To greatly reduce the data transmission overhead and speed up the monitoring processing, CS-sharing exploits two techniques: sending an aggregate message in each vehicle encounter, and quick collection of information taking advantage of data sharing and the sparsity of events in vehicle networks to significantly reduce the number of measurements needed for global information recovery. We propose a novel data structure, and an aggregation method that can take advantage of the random and opportunistic vehicle encounters to form the measurement matrix. We prove that the measurement matrix satisfies the Restricted Isometry Property (RIP) property required by the CS technique. Our results from extensive simulations demonstrate that CS-Sharing allows vehicles in a large network to quickly obtain the full context data with the successful recovery ratio larger than 90%.

NFV together with SDN provides the flexibility for NFs in the way that they are deployed and managed. The flexibility enables dynamical scale in and scale out through migrating in-process flows among NFs. Due to stateful packet processing in NFs, flow migration has to guarantee loss-free and order-preserving for both flow states and packets. Existing frameworks closely coupled state transfer and packets migration, and thus fail to achieve safe and efficient migration with low overhead. This paper presents our design and implementation of a distributed flow migration framework, Transparent Flow Migration (TFM). TFM completely decouples the state transfer and packets migrations. The decoupling allows us to optimize the two processes separately and run them in parallel. TFM implements various optimizations through the TFM box, a shim layer providing transparent packet migration to NFs. Our evaluation shows that TFM guarantees loss-free and order-preserving for both scale-in and scale-out flow migration, and outperforms existing approaches with 3× smaller migration time. Besides, TFM uses small overhead and has very limited impacts on throughput of live TCP flows.

In Search Engine Marketing (SEM), “third-party” partners play an important intermediate role by bridging the gap between search engines and advertisers in order to optimise advertisers' campaigns in exchange of a service fee. In this paper, we present an economic analysis of the market involving a third-party broker in Google AdWords and the broker's customers. We show that in order to optimise his profit, a third-party broker should minimise the weighted average Cost Per Click (CPC) of the portfolio of keywords attached to customer's ads while still satisfying the negotiated customer's demand. To help the broker build and manage such portfolio of keywords, we develop an optimisation framework inspired from the classical Markowitz portfolio management which integrates the customer's demand constraint and enables the broker to manage the tradeoff between return on investment and risk through a single risk aversion parameter. We then propose a method to augment the keywords portfolio with relevant keywords extracted from trending and popular topics on Twitter. Our evaluation shows that such a keywords-augmented strategy is very promising and enables the broker to achieve, on average, four folds larger return on investment than with a non-augmented strategy, while still maintaining the same level of risk.

The inference of traffic volume of the whole network from partial traffic measurements becomes increasingly critical for various network engineering tasks, such as traffic prediction, network optimization, and anomaly detection. Previous studies indicate that the matrix completion is a possible solution for this problem. However, as a two-dimension matrix cannot sufficiently capture the spatial-temporal features of traffic data, these approaches fail to work when the data missing ratio is high. To fully exploit hidden spatial-temporal structures of the traffic data, this paper models the traffic data as a 3-way traffic tensor and formulates the traffic data recovery problem as a low-rank tensor completion problem. However, the high computation complexity incurred by the conventional tensor completion algorithms prevents its practical application for the traffic data recovery. To reduce the computation cost, we propose a novel Sequential Tensor Completion algorithm (STC) which can efficiently exploit the tensor decomposition result for the previous traffic data to deduce the tensor decomposition for the current data. To the best of our knowledge, we are the first to apply the tensor to model Internet traffic data to well exploit their hidden structures and propose a sequential tensor completion algorithm to significantly speed up the traffic data recovery process. We have done extensive simulations with the real traffic trace as the input. The simulation results demonstrate that our algorithm can achieve significantly better performance compared with the literature tensor and matrix completion algorithms even when the data missing ratio is high.

The popularity of smart phones fosters the growth of Proximity-based Mobile Social Networking (PMSN). Although some profile matching approaches have been proposed to facilitate a user to find another user that shares his/her interest in the proximity, these approaches usually model the matching problem as a Private Set Intersection problem or a Private Set Intersection Cardinality problem and require high complexity of computation. Different from current studies, to facilitate more effective building of PMSNs, we propose a novel similarity metric to evaluate the common interests of mobile users by considering the time-dependent features of their interests. To calculate the metric in a low cost and privacy- protection way, we propose a novel time-dependent bloom filter to encode the time-dependent interest and a novel probabilistic algorithm to estimate the time- dependent similarity metric based on the bloom filter. Based on the proposed BF-based profile matching approach, we further propose InterestMatch, a novel distributed mobile communication system to facilitate more efficient social networking among strangers in the physical proximity. We have done extensive experiments on real-world phones, our experiment results demonstrate that our approach is promising for facilitating mobile social interactions in the physical proximity due to its low complexity and consequently low power consumption.

Summary Although IPv6 has been standardized more than 15 years ago, its deployment is still very limited. China has been strongly pushing IPv6, especially due to its limited IPv4 address space. In this paper, we describe measurements from a large Chinese academic network, serving a significant population of IPv6 hosts. We show that despite its expected strength, China is struggling as much as the western world to increase the share of IPv6 traffic. To understand the reasons behind this, we examine the IPv6 applicative ecosystem. We observe a significant IPv6 traffic growth over the past 3 years, with P2P file transfers responsible for more than 80% of the IPv6 traffic, compared with only 15% for IPv4 traffic. Checking the top websites for IPv6 explains the dominance of P2P, with popular P2P trackers appearing systematically among the top visited sites, followed by Chinese popular services (e.g., Tencent), as well as surprisingly popular third‐party analytics including Google. Finally, we compare the throughput of IPv6 and IPv4 flows. We find that a larger share of IPv4 flows get a high‐throughput compared with IPv6 flows, despite IPv6 traffic not being rate limited. We explain this through the limited amount of HTTP traffic in IPv6 and the presence of Web caches in IPv4. Our findings highlight the main issue in IPv6 adoption, that is, the lack of commercial content, which biases the geographic pattern and flow throughput of IPv6 traffic. Copyright © 2014 John Wiley & Sons, Ltd.

The prevalence of Internet video streaming challenges the design and operation of modern networks. Content centric networking (CCN) has been proposed to address the challenges through ubiquitous in-network caching. While the expected benefits include higher performance and lower bandwidth consumption, CCN introduces new privacy issues at layer 3. This is because adversaries could infer the content consumed by others by checking cached data in routers. In this paper, we first analyze the design space to improve both caching performance and cache privacy for video delivery in CCN. In light of the observation that these two metrics need to be balanced, we propose CodingCache. It adopts network coding and random forwarding to exploit the potentials of multipath routing in CCN to improve both the diversity of cached content along different paths and the anonymity set for consumers. We evaluate CodingCache through extensive experiments based on a real-world topology and a unique data set of video access logs from a large-scale commercial video service. Our results demonstrate that, compared with the existing CCN strategies, CodingCache is able to increase the cache hit rate while also improve the use of caches across the network, together with reasonable cache privacy.

Set queries are fundamental operations in computer systems and applications. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a Shifting Bloom Filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF based set data structures allocate additional memory to store auxiliary information. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries.

Content-centric networking (CCN) is a promising framework to rebuild the Internet's forwarding substrate around the concept of content. CCN advocates ubiquitous in-network caching to enhance content delivery, and thus each router has storage space to cache frequently requested content. In this work, we focus on the cache allocation problem, namely, how to distribute the cache capacity across routers under a constrained total storage budget for the network. We first formulate this problem as a content placement problem and obtain the optimal solution by a two-step method. We then propose a suboptimal heuristic method based on node centrality, which is more practical in dynamic networks with frequent content publishing. We investigate through simulations the factors that affect the optimal cache allocation, and perhaps more importantly we use a real-life Internet topology and video access logs from a large scale Internet video provider to evaluate the performance of various cache allocation methods. We observe that network topology and content popularity are two important factors that affect where exactly should cache capacity be placed. Further, the heuristic method comes with only a very limited performance penalty compared to the optimal allocation. Finally, using our findings, we provide recommendations for network operators on the best deployment of CCN caches capacity over routers.

TCP is an important factor affecting user-perceived performance of Internet applications. Diagnosing the causes behind TCP performance issues in the wild is essential for better understanding the current shortcomings in TCP. This paper presents a TCP flow performance analysis framework that classifies causes of TCP stalls. The framework forms the basis of a tool that is publicly available to the research community. We use our tool to analyze packet-level traces of three services (cloud storage, software download and web search) deployed by a popular Chinese service provider. We find that as many as 20% of the flows are stalled for half of their lifetime. Network-related causes, especially timeout retransmission, dominate the stalls. A breakdown of the causes for timeout retransmission stalls reveals that double retransmission and tail retransmission are among the top contributors. The importance of these causes depends however on the specific service. We also propose S-RTO, a mechanism that mitigates timeout retransmission stalls. S-RTO has been deployed on production front-end servers and results show that it is effective at improving TCP performance, especially for short flows.

Named Data Networking (NDN) shifts the communication paradigm from the quest of where the content is to what content is to be consumed. In such a new Internet architecture, transmission control mechanisms are of particular importance and have to be carefully designed to enable efficient data transmission. Existing work advocates the use of TCP-like reactive mechanisms for NDN transmission control. In this paper, we show that the statefull and adaptive forwarding properties of NDN makes proactive and efficient mechanisms for transmission control possible. We achieve this by using Explicit Congestion Notifications (ECN), which explicitly notify content consumers about network conditions through the communication path. Specifically, we propose an ECN-based proactive interest-sending rate control mechanism, which aims to achieve a high link utilisation for fast data transmission as well as a low packet dropping rate. To have a globally optimal data transmission, we further propose a smart forwarding mechanism, which locally utilises network-wide information to select the forwarding paths for individual flows. Extensive packet-level simulations in ndnSIM demonstrate that the ECN-based approach, coupled with smart forwarding, outperforms TCP-like reactive mechanisms in terms of link utilisation, packet dropping rate and flow completion time.

End-to-end network monitoring is essential to ensure transmission quality for Internet applications. However, in large-scale networks, full-mesh measurement of network performance between all transmission pairs is infeasible. As a newly emerging sparsity representation technique, matrix completion allows the recovery of a low-rank matrix using only a small number of random samples. Existing schemes often fix the number of samples assuming the rank of the matrix is known, while the data features thus the matrix rank vary over time. In this paper, we propose to exploit the matrix completion techniques to derive the end-to-end network performance among all node pairs by only measuring a small subset of end-to-end paths. To address the challenge of rank change in the practical system, we propose a sequential and information-based adaptive sampling scheme, along with a novel sampling stopping condition. Our scheme is based only on the data observed without relying on the reconstruction method or the knowledge on the sparsity of unknown data. We have performed extensive simulations based on real-world trace data, and the results demonstrate that our scheme can significantly reduce the measurement cost while ensuring high accuracy in obtaining the whole network performance data.

Video delivery performance is the main factor that affects Internet video quality. Characterizing the video delivery performance, especially the delivery throughput, can help content providers as well as Internet service providers (ISPs) in system optimization and network planning. Based on a unique dataset consisting of 20 million video download speed measurements , this paper comprehensively studies the video delivery throughput of a large-scale commercial video-on- demand (VoD) system. We observe that user speed exhibits a large variation over time of day as well as across provincial locations. In particular, the worst performance of day is 30% lower than the peak performance . The analysis also reveals that video download speed has a notable impact on Internet video quality, which in turn influences user engagement . The impact, however, becomes limited when the speed increases beyond a certain threshold, which is mostly dependent on the video encoded bitrates. We further examine the interaction between Internet infrastructure and video delivery throughput using the linear regression model and find that crossing the ISP or regional network border yields 15-20% speed loss. Based on these observations , we finally evaluate the potential of edge caching and hybrid CDN-P2P in the improvement of video download performance and video quality.

Application Layer Distributed Denial of Service (ALDDoS) attacks have been increasing rapidly with the growth of Botnets and Ubiquitous computing. Differentiate to the former DDoS attacks, ALDDoS attacks cannot be efficiently detected, as attackers always adopt legitimate requests with real IP address, and the traffic has high similarity to legitimate traffic. In spite of that, we think, the attackers' browsing behavior will have great disparity from that of the legitimate users'. In this paper, we put forward a novel user behavior-based method to detect the application layer asymmetric DDoS attack. We introduce an extended random walk model to describe user browsing behavior and establish the legitimate pattern of browsing sequences. For each incoming browser, we observe his page request sequence and predict subsequent page request sequence based on random walk model. The similarity between the predicted and the observed page request sequence is used as a criterion to measure the legality of the user, and then attacker would be detected based on it. Evaluation results based on real collected data set has demonstrated that our method is very effective in detecting asymmetric ALDDoS attacks.

Matrix completion has emerged very recently and provides a new venue for low cost data gathering in WSNs. Existing schemes often assume that the data matrix has a known and fixed low-rank, which is unlikely to hold in a practical monitoring system such as weather data gathering. Weather data varies in temporal and spatial domain with time. By analyzing a large set of weather data collected from 196 sensors in ZhuZhou, China, we reveal that weather data have the features of low-rank, temporal stability, and relative rank stability. Taking advantage of these features, we propose an on-line data gathering scheme based on matrix completion theory, named MC-Weather, to adaptively sample different locations according to environmental and weather conditions. To better schedule sampling process while satisfying the required reconstruction accuracy, we propose several novel techniques, including three sample learning principles, an adaptive sampling algorithm based on matrix completion, and a uniform time slot and cross sample model. With these techniques, our MC-Weather scheme can collect the sensory data at required accuracy while largely reduce the cost for sensing, communication and computation. We perform extensive simulations based on the real weather data sets and the simulation results validate the efficiency and efficacy of the proposed scheme.

We observe that a same rule set can induce very different memory requirement, as well as varying classification performance, when using various well known decision tree based packet classification algorithms. Worse, two similar rule sets, in terms of types and number of rules, can give rise to widely differing performance behaviour for a same classification algorithms. We identify the intrinsic characteristics of rule sets that yield such performance differences, allowing us to understand and predict the performance behaviour of a rule set for various modern packet classification algorithms. Indeed, from our observations, we are able to derive a memory consumption model and an offline algorithm capable of quickly identifying which packet classification is suited to a give rule set. By splitting a large rule set in several subsets and using different packet classification algorithms for different subsets, our Smart Split algorithm is shown to be capable of configuring a multi-component packet classification system that exhibits up to 11 times less memory consumption, as well as up to about 4× faster classification speed, than the state-of-art work [20] for large rule sets. Our Auto PC framework obtains further performance gain by avoiding splitting large rule sets if the memory size of the built decision tree is shown by the memory consumption model to be small.

The widespread availability of smart mobile terminals along with the ever increasing bandwidth capabilities has promoted the popularity of mobile Internet video systems. Understanding the geographic features of mobile content consumption is of an extreme importance for the design and the performance optimization of a mobile video delivery system. This paper is a first step towards characterization of the geographic patterns of a large-scale commercial mobile video-on-demand (VoD) system, by measuring both uniformity and intensity of geographic interests on videos. In particular, we identify a geographical concentration effect of views for individual videos, which is however dependent on video popularity. We also analyze the temporal evolution trends of the geographic popularity which reveal distinct behavior of popular and non-popular videos. While the set of locations that contribute to most of the views of non-popular videos largely varies, the daily geographic popularity distribution of popular videos closely follows the distribution of global traffic and remains stable. We also examine the impact of content type and viewing sources on the geographic features of mobile videos consumption, and the correlation between content similarity and geographic locality. Finally, we provide insights into the implications of our findings.

Protocol feature words are byte subsequences within traffic payload that can distinguish application protocols, and they form the building blocks of many constructions of deep packet analysis rules in network management, measurement, and security systems. However, how to systematically and efficiently extract protocol feature words from network traffic remains a challenging issue. Existing n-gram approaches simply break pay-load into equal-length pieces and are ineffective in capturing the hidden statistical structure of the payload content. In this paper, we propose ProWord, an unsupervised approach that extracts protocol feature words from traffic traces. ProWord builds on two nontrivial algorithms. First, we propose an unsupervised segmentation algorithm based on the modified Voting Experts algorithm, such that we break payload into candidate words according to entropy information and provide more accurate segmentation than existing n-gram approaches. Second, we propose a ranking algorithm that incorporates different types of well-known feature word retrieval heuristics, such that we can build an ordered structure on the candidate words and select the highest ranked ones as protocol feature words. We compare ProWord and existing n-gram approaches via evaluation on real-world traffic traces. We show that ProWord captures true protocol feature words more accurately and performs significantly faster.

With the fast development of Internet, the size of routing table in the backbone router continues to grow rapidly. Forwarding Information Base (FIB), which is derived from routing table, is stored in line-card to conduct routing lookup. Since the line-card's memory is limited, it would be worthwhile to compress the FIB for consuming less storage. Therefore, various FIB compression algorithms are proposed [2-7]. However, there is no well-presented mathematical support for the feasibility of the FIB compression solution, nor any mathematical derivation to prove the correctness of these algorithms. To address these problems, we propose a universal mathematical method based on the Group2theory. By defining a Group representing the Longest Prefix Matching Rule (LPM), the bound of the worst case of FIB compression solution can be figured out. Furthermore, in order to guarantee the ultimate correctness of FIB compression algorithms, Routing Table Equation Test (RTET) is proposed and implemented to verify the equivalence of the two routing tables before and after compression by traversing the 32-bit IP address space.

Bloom Filter is a widely used data structure in computer science. It enables memory efficient and fast set membership queries. Bloom filter-based solutions have been proposed in the past decade for lookup in forwarding tables of backbone routers [2]. However, the main shortcomings of using Bloom Filters for lookup lie in the absence of support for deletion operations that are needed to update the forwarding tables. Counting Bloom Filter supporting deletion has therefore to be used, increasing significantly the memory requirement. Moreover, Counting Bloom Filter suffers from both false positive and false negative. In this paper, we propose to solve the issue with deletion of Bloom Filters by using a Withdrawal To annOuncement (WTO) mapping that replaces withdrawal with announcements, transforming deletions into additions or record changes. Experimental evaluation show that the proposed techniques improve largely the performance of Bloom Filter used for forwarding lookup and open way for the use of Bloom Filters in real operational settings.

The Forwarding Information Base (FIB) of backbone routers has been rapidly growing in size. An ideal IP lookup algorithm should achieve constant, yet small, IP lookup time and on-chip memory usage. However, no prior IP lookup algorithm achieves both requirements at the same time. In this paper, we first propose SAIL, a Splitting Approach to IP Lookup. One splitting is along the dimension of the lookup process, namely finding the prefix length and finding the next hop, and another splitting is along the dimension of prefix length, namely IP lookup on prefixes of length less than or equal to 24 and IP lookup on prefixes of length longer than 24. Second, we propose a suite of algorithms for IP lookup based on our SAIL framework. Third, we implemented our algorithms on four platforms: CPU, FPGA, GPU, and many-core. We conducted extensive experiments to evaluate our algorithms using real FIBs and real traffic from a major ISP in China. Experimental results show that our SAIL algorithms are several times or even two orders of magnitude faster than well known IP lookup algorithms.

Protocol feature words are byte subsequences within traffic payload that can distinguish application protocols, and they form the building blocks of many constructions of deep packet analysis rules in network management, measurement, and security systems. However, how to systematically and efficiently extract protocol feature words from network traffic remains a challenging issue. Existing approaches like those based on n-gram or Common String (CS), which simply breaks payload into equal-length pieces or attempts to find a frequent itemset, are ineffective in capturing the hidden statistical structure of the payload content. In this paper, we propose ProWord, an unsupervised approach that extracts protocol feature words from traffic traces. ProWord builds on two nontrivial algorithms. First, we propose an unsupervised segmentation algorithm based on the modified Voting Experts algorithm, such that we break payload into candidate words according to entropy information and provide more accurate segmentation than existing n-gram and CS approaches. Second, we propose a ranking algorithm that incorporates different types of well-known feature word retrieval heuristics, such that we can build an ordered structure on the candidate words and select the highest ranked ones as protocol feature words. We compare ProWord and existing prior approaches via evaluation on real-world traffic traces. We show that ProWord captures true protocol feature words more accurately and performs significantly faster.

As network link rates are being pushed beyond 40 Gb/s, IP lookup in high-speed routers is moving to hardware. The ternary content addressable memory (TCAM)-based IP lookup engine and the static random access memory (SRAM)-based IP lookup pipeline are the two most common ways to achieve high throughput. However, route updates in both engines degrade lookup performance and may lead to packet drops. Moreover, there is a growing interest in virtual IP routers where more frequent updates happen. Finding solutions that achieve both fast lookup and low update overhead becomes critical. In this paper, we propose a hybrid IP lookup architecture to address this challenge. The architecture is based on an efficient trie partitioning scheme that divides the forwarding information base (FIB) into two prefix sets: a large disjoint leaf prefix set mapped into an external TCAM-based lookup engine and a small overlapping prefix set mapped into an on-chip SRAM-based lookup pipeline. Critical optimizations are developed on both IP lookup engines to reduce the update overhead. We show how to extend the proposed hybrid architecture to support virtual routers. Our implementation shows a throughput of 250 million lookups per second (equivalent to 128 Gb/s with 64-B packets). The update overhead is significantly lower than that of previous work, the memory consumption is reasonable, and the utilization ratio of most external TCAMs is up to 100%.

Regular expression (RegEx) matching is a core function of deep packet inspection in modern network devices. Previous TCAM-based RegEx matching algorithms a priori assume that a deterministic finite automaton (DFA) can be built for a given set of RegEx patterns. However, practical RegEx patterns contain complex terms like wildcard closure and repeat character, and it may be impossible to build a DFA with a reasonable number of states. This results in prior work to being infeasible in practice. Moreover, TCAM-based RegEx matching is required to scale to a large-scale set of RegEx patterns. In this paper, we propose a compressed finite automaton implementation called (CFA) for scalable TCAM-based RegEx matching. CFA is designed to reduce TCAM space by using three compression techniques: transition, character, and state compressions. Experiments on realistic RegEx pattern sets show CFA highly outperforms previous solutions in terms of TCAM space, matching throughput, and TCAM power consumption.

Network Intrusion Detection Systems (NIDSes) face significant challenges coming from the relentless network link speed growth and increasing complexity of threats. Both hardware accelerated and parallel software-based NIDS solutions, based on commodity multi-core and GPU processors, have been proposed to overcome these challenges. This work explores new parallel opportunities afforded by many-core processors for high performance, scalable and inexpensive NIDS. We exploit the huge many-core computational power by adopting a hybrid parallel architecture combining data and pipeline parallelism. We also design a hybrid load balancing scheme, using both ruleset and flow space partitioning. Furthermore, the proposed design leverages particular features of the processor to break the bottlenecks. We have integrated the open source NIDS Suricata into our proposed design and evaluated its performance with synthetic traffic. The prototype exhibits almost linear speedup and can handle up to 7.2 Gbps traffic with 100-bytes packets.

Content-Centric Networking (CCN) is a promising framework for evolving the current network architecture, advocating ubiquitous in-network caching to enhance content delivery. Consequently, in CCN, each router has storage space to cache frequently requested content. In this work, we focus on the cache allocation problem: namely, how to distribute the cache capacity across routers under a constrained total storage budget for the network. We formulate this problem as a content placement problem and obtain the exact optimal solution by a two-step method. Through simulations, we use this algorithm to investigate the factors that affect the optimal cache allocation in CCN, such as the network topology and the popularity of content. We find that a highly heterogeneous topology tends to put most of the capacity over a few central nodes. On the other hand, heterogeneous content popularity has the opposite effect, by spreading capacity across far more nodes. Using our findings, we make observations on how network operators could best deploy CCN caches capacity.

Virtual routers are increasingly being studied, as an important building block to enable network virtualization. In a virtual router platform, multiple virtual router instances coexist, each having its own FIB (Forwarding Information Base). In this context, memory scalability and route updates are two major challenges. Existing approaches addressed one of these challenges but not both. In this paper, we present a trie merging approach, which compactly represents multiple FIBs by a merged trie and a table of next-hop-pointer arrays to achieve good memory scalability, while supporting fast incremental updates by avoiding the use of leaf pushing during merging. Experimental results show that storing the merged trie requires limited memory space, e.g., we only need 10MB memory space to store the merged trie for 14 full FIBs from IPv4 core routers, achieving a memory reduction by 87% when compared to the total size of the individual tries. We implement our approach in an SRAM (Static Random Access Memory)-based lookup pipeline. Using our approach, an on-chip SRAM-based lookup pipeline with 5 external stages is sufficient to store the 14 full IPv4 FIBs. Furthermore, our approach can guarantee a minimum update overhead of one write bubble per update, as well as a high lookup throughput of one lookup per clock cycle, which corresponds to a throughput of 251 million lookups per second in the implementation.

In this paper, we study the process of information diffusion in a microblog service developing Galton-Watson with Killing (GWK) model. Microblog services offer a unique approach to online information sharing allowing microblog users to forward messages to others. We describe an information propagation as a discrete GWK process based on Galton-Watson model which models the evolution of family names. Our model explains the interaction between the topology of the social graph and the intrinsic interest of the message. We validate our model on dataset collected from Sina Weibo and Twitter microblog. Sina Weibo is a Chinese microblog web service which reached over 100 million users as for January 2011. Our Sina Weibo dataset contains over 261 thousand tweets which have retweets and 2 million retweets from 500 thousand users. Twitter dataset contains over 1.1 million tweets which have retweets and 3.3 million retweets from 4.3 million users. The results of the validation show that our proposed GWK model fits the information diffusion of microblog service very well in terms of the number of message receivers. We show that our model can be used in generating tweets load and also analyze the relationships between parameters of our model and popularity of the diffused information. To the best of our knowledge, this paper is the first to give a systemic and comprehensive analysis for the information diffusion on microblog services, to be used in tweets-like load generators while still guaranteeing popularity distribution characteristics.

Bloom filters are space-efficient data structures for fast set membership queries. Counting Bloom Filters (CBFs) extend Bloom filters by allowing insertions and deletions to support dynamic sets. The performance of CBFs is critical for various applications and systems. This paper presents a novel approach to building a fast and accurate data structure called Multiple-Partitioned Counting Bloom Filter (MPCBF) that addresses large-scale data processing challenges. MPCBF is based on two ideas: reducing the number of memory accesses from k (for k hash functions) in the standard CBF to only one memory access in the basic MPCBF-1 case, and a hierarchical structure to improve the false positive rate. We also generalize MPCBF-1 to MPCBF-g to accommodate up to g memory accesses. Our simulation and implementation in MapReduce show that MPCBF outperforms the standard CBF in terms of speed and accuracy. Compared to CBF, at the same memory consumption, MPCBF significantly reduces the false positive rate by an order of magnitude, with a reduction of processing overhead by up to 85.9%.

Deep Packet Inspection (DPI) module in Intrusion Detection Systems (IDSes) consists of two components: Pre-filter and Rule Verification (RV). Pre-filter adopts Multi-Pattern Matching (MPM) engine to filter out the vast majority of benign packets and then leave a few suspicious packets with false positives into RV component. These false positives are due to the scanning process in the pre-filter: it detects the traffic in a single pass against a set of fingerprints, which are extracted from the given ruleset by selecting only a small portion of the patterns in each signature. RV component precisely checks the suspicious packets and eliminates these false positives. The performance of DPI module is related to the extracted fingerprint set. An efficient fingerprint set should improve the pre-filter throughput, and at the same time decrease the count of checking activities in RV component. We show in this paper that these two requirements cannot be simultaneously satisfied in the existing fingerprint extraction strategies. Pre-filter performance greatly benefits from smaller fingerprint set because of the more compact MPM engine. But RV component suffers from the higher rate of false positives caused by the smaller fingerprint set. We optimally trade off these two requirements with a new extraction method in this work. Through analysing a small amount of training traffic in the initial phase, our strategy gives each fingerprint candidate an empirical weight for the subsequent extraction. Experimental results obtained by integrating our proposed method into the Snort IDS show that our strategy improves the IDS average throughput by at least 69% over the latest real ruleset and real traffic.

The scalability of routing architectures for large networks is one of the biggest challenges that the Internet faces today. Greedy routing, in which each node is assigned a locator used as a distance metric, recently received increased attention from researchers and is considered as a potential solution for scalable routing. In this paper, we propose LMD - a Local Minimum Driven method to compute the topology-based locator. As opposed to previous work, our algorithm employs a quasigreedy and self-organized embedding method, which outperforms similar decentralized algorithms by up to 20% in success rate. To eliminate the negative effect of the “quasi” greedy property - transfer routes longer than the shortest routes, we introduce a two-stage routing strategy, which combines the greedy routing with source routing. The greedy routing path discovered and compressed in the first stage is then used by the following source-routing stage. Through extensive evaluations, based on synthetic topologies as well as on a snapshot of the real Internet AS topology, we show that LMD guarantees 100% delivery rate on large networks with a very low stretch.

Packet classification has been studied extensively in the past decade. While many efficient algorithms have been proposed, the lack of deterministic performance has hindered the adoption and deployment of these algorithms: the expensive and power-hungry TCAM is still the de facto standard solution for packet classification. In this work, in contrast to proposing yet another new packet classification algorithm, we present the first steps to understand this unpredictability in performance for the existing algorithms. We focus on decision-tree based algorithms in this paper. In order to achieve the predictability, we firstly revisit the classical and many state-of-art packet classification algorithms. Through a detailed analysis, we conclude that two features of ruleset usually dominate the performance results: 1) the uniformity of the range distribution in different dimensions of the rules; 2) the existence and the number of “orthogonal structure” and wildcard rules in the ruleset. We conduct experiments to show the correctness of these observations, and discribe some potential applications for those results. Our work provides some insight to make the packet classification algorithms a credible alternative to the TCAM-only solutions.

User-generated content (UGC) video systems by definition heavily depend on the input of their community of users and their social interactions for video diffusion and opinion sharing. Nevertheless, we show in this paper, through measurement and analysis of YouKu, the most popular UGC video system in China, that the social connectivity of its users is very low. These observations are consistent with what was reported about YouTube in previous works. As a UGC system can achieve a larger audience through improved connectivity, our findings motivate us to propose a mean to enhance the users' connectivity by taking benefit of friend recommendation. To this end, we assess two similarity metrics based on users' interests that are derived from their uploads and favorites tagging of videos, to evaluate the interest similarity between friends. The results consistently show that friends share to a great extent common interests. Two friend recommendation algorithms are then proposed. The algorithms use public information provided by users to suggest potential friends with similar interests as measured by the similarity metrics. Experiments on our gathered YouKu dataset demonstrate that the social connectivity can be greatly enhanced by our friend proposition set and that users can access a larger set of interesting videos through the recommendations.

As the key building block for enabling network virtualization, virtual routers have attracted much attention recently. In a virtual router platform, multiple virtual router instances coexist, each with its own FIB (Forwarding Information Base). The small amount of high-speed memory in a physical router platform severely limits the number of FIBs supported, which leads to a scalability challenge. In this paper, we present a method towards TCAM (Ternary Content Addressable Memory) based scalable virtual routers, through a merged data structure that enables the sharing of prefixes from several FIBs in TCAMs. Based on this data structure, we propose two approaches to merge multiple FIBs in TCAMs, paving the way for scalable virtual routers. Experimental results show that, by using the two approaches for storing 14 full IPv4 FIBs, the TCAM memory requirement can be reduced by about 92% and 82% respectively, compared with the conventional approach of treating FIBs as independent entities.

In recent years, there has been a growing interest in multi/many core processors as a target architecture for high performance software router. This is a clear difference from the previous trend to use dedicated network processors and hardware components. Because of its key position in routers, hardware IP lookup implementation has been intensively studied with TCAM and FPGA based architecture. However, increasing interest in software implementation has also been observed. In this paper, we evaluate the performance of software only IP lookup on a many core chip, the TILEPro64 processor. For this purpose we have implemented two widely used IP lookup algorithms, DIR-24-8-BASIC and Tree Bitmap. We evaluate the performance of these two algorithms over the TILEPro64 processor with both synthetic and real-world traces. After a detailed analysis, we propose a hybrid scheme which provides high lookup speed and low worst case update overhead. Our work shows how to exploit the architectural features of TILEPro64 to improve the performance, including many optimization in both single-core and parallelism aspects. Experiment results show by using only 18 cores, we can achieve a lookup throughput of 60Mpps (almost 40Gbps) with low power consumption, which demonstrates great performance potentials in many core processor.

In this work, we aim to analyze and compare interaction patterns in different types of social platforms. To this end, we measured Renren, the largest online social network in China, and Sina Weibo, the most popular microblog service in China. We model the interaction networks as unidirectional weighted graphs in light of the asymmetry of user interactions. Following this model, we first study the basic interaction patterns. Then, we examine whether weak ties hypothesis holds in these interaction graphs and analyze the impacts on information diffusion. Furthermore, we model the temporal patterns of user interactions and cluster users based on the temporal patterns. Our findings demonstrate that although users in the two platforms share some common interaction patterns, users in Sina Weibo are more popular and diverse. Moreover, analysis and simulation results show that Sina Weibo is a more efficient platform for information diffusion. These findings provide an in-depth understanding of interaction patterns in different social platforms and can be used for the design of efficient information diffusion.

While there are several ways for video finding in UGC (user generated content) video systems, video search is still the number one source of video views in aggregation. In this paper, we propose to use peer-assisted search to alleviate the server burden caused by video search. To this end, we have measured and analyzed YouKu, the largest UGC video system in China. With a large dataset, we have found non-power law distribution of video popularity, low replication level for popular videos, skewed user activity and interest locality. Based on the findings, we design two-layer hierarchical semantic overlay structures to implement peer-assisted search for UGC video systems. A novel search algorithm called WISE is proposed to guide queries quickly to the semantically relevant clusters by visiting a very small fraction of nodes. Simulations using the YouKu trace demonstrate that WISE is effective and helpful to assist the search in UGC video systems. To the best of our knowledge, this is the first work to study peer-assisted search in UGC.

In this paper, we examine mobile users' behavior and their corresponding video viewing patterns from logs extracted from the servers of a large scale VoD system. We focus on the analysis of the main discrepancies that might exist when users access the VoD system catalog from WiFi or 3G connections. We also study factors that might impact mobile users' interests and video popularity. The users' behavior exhibits strong daily and weekly patterns, with mobile users' interests being surprisingly spread across almost all categories and video lengths, independently of the connection type. However, by examining the activity of users individually, we observed a concentration of interests and peculiar access patterns, which allows to classify the users and thus better predict their behavior. We also find a skewed video popularity distribution and then demonstrate that the popularity of a video can be predicted using its very early popularity level. We further analyzed the sources of video viewing and found that even if search engines are the dominant sources for a majority of videos, they represent less than 10% (resp. 20%) of the sources for the highly popular videos in 3G (resp. WiFi) network. We report that both the type of connections and mobile devices in use have an impact on the viewing time and the source of viewing. Based on our findings, we provide insights and recommendations that can be used to design intelligent mobile VoD systems and help improving personalized services on these platforms.

As network link rates are being pushed beyond 40 Gbps, IP lookup in high-speed routers is moving to hardware. The TCAM (Ternary Content Addressable Memory)-based IP lookup engine and the SRAM (Static Random Access Memory)-based IP lookup pipeline are the two most common ways to achieve high throughput. However, route updates in both engines degrade lookup performance and may lead to packet drops. Moreover, there is a growing interest in virtual IP routers where more frequent updates happen. Finding solutions that achieve both fast lookup and low update overhead becomes critical. In this paper, we propose a hybrid IP lookup architecture to address this challenge. The architecture is based on an efficient trie partitioning scheme that divides the Forwarding Information Base (FIB) into two prefix sets: a large disjoint leaf prefix set mapped into an external TCAM-based lookup engine and a small overlapping prefix set mapped into an on-chip SRAM-based lookup pipeline. Critical optimizations are developed on both IP lookup engines to reduce the update overhead. We show how to extend the proposed hybrid architecture to support virtual routers. Our implementation shows a throughput of 250 million lookups per second (MLPS). The update overhead is significantly lower than that of previous work and the utilization ratio of most external TCAMs is up to 100%.

In this paper we propose FPC - a Force-based layout and Path Compressing routing schema for scale-free network. As opposed to previous work, our algorithm employs a quasi-greedy but self-organized and configuration-free embedding method - force-based layout. In order to eliminate the negative influences of the “quasi” greedy property, we present a two-stage routing strategy, which combines the greedy routing with source routing. The greedy routing path discovered and compressed in a first stage is then used by the following source-routing stage. The detailed evaluation based on synthetic topologies as well as on a real Internet AS topology shows that: FPC guarantees 100% delivery rates on scale-free networks with an attractive low stretch (e.g. less than 1.2 on the real Internet AS topology).

Traffic flow measurement is of great importance to ISPs for various network engineering tasks. An interesting problem is that how to determine the minimum number of links by monitoring which one can obtain the traffic flows of the whole ISP network. Previous works view the problem as Vertex Cover problem. They suffer from high time complexity and redundant monitoring. Different from these works, we study the problem from the perspective of edges and propose two models. The first model, Extended Edge Cover model, can determine the minimum set of monitored links, which are 30% less than that of previous works. The second model, shared-path model, is more suitable when the monitoring resources are limited but one still wants to measure a large part of the networks. Using this method, one can measure 85% of the network by monitoring 5% of links. Finally, we evaluate the performance of the two models through extensive simulations. The experimental results show the effectiveness and robustness of the two models.

Unbiased sampling of online social networks (OSNs) makes it possible to get accurate statistical properties of large-scale OSNs. However, the most used sampling methods, Breadth-First-Search (BFS) and Greedy, are known to be biased towards high degree nodes, yielding inaccurate statistical results. To give a general requirement for unbiased sampling, we model the crawling process as a Markov Chain and deduce a necessary and sufficient condition, which enables us to design various efficient unbiased sampling methods. To the best of our knowledge, we are among the first to give such a condition. Metropolis-Hastings Random Walk (MHRW) is an example which satisfies the condition. However, walkers in MHRW may stay at some low-degree nodes for a long time, resulting considerable self-loops on these nodes, which adversely affect the crawling efficiency. Based on the condition, a new unbiased sampling method, called USRS, is proposed to reduce the probabilities of self-loops. We use the dataset of Renren, the largest OSN in China, to evaluate the performance of USRS. The results have demonstrated that USRS generates unbiased samples with low self-loop probabilities, and achieves higher crawling efficiency.

This paper presents a novel offset encoding scheme for memory-efficient IP address lookup, called Offset Encoded Trie (OET). Each node in the OET contains only a next hop bitmap and an offset value, without the child pointers and the next hop pointers. Each traversal node uses the next hop bitmap and the offset value as two offsets to determine the location address of the next node to be searched. The on-chip OET is searched to find the longest matching prefix, and then the prefix is used as a key to retrieve the corresponding next hop from an off-chip prefix hash table. Experiments on real IP forwarding tables show that the OET outperforms previous multi-bit trie schemes in terms of the memory consumption. The OET facilitates the far more effective use of on-chip memory for faster IP address lookup.

The social connections among users have significant impacts on UGC video systems. The goal of this paper is to study the social connectivity of such systems by measuring YouKu, the most popular UGC video system in China. We have collected 627 thousand user profiles, 3 million social connections and 13.6 million videos' information. The analysis results have shown that the social connectivity is extremely weak and there are a considerable proportion of friend pairs sharing common semantic interests. These facts motivate us to enhance the connectivity by recommending semantically relevant users as friends. We thus propose a friend recommendation algorithm which locates potential friends quickly and accurately through the links to related videos, a unique feature of YouKu and similar sites. We apply the algorithm on our dataset of YouKu and evaluate it through one-hop video search. The social connectivity is greatly enhanced and the number of matched videos on friends is greatly increased. To the best of our knowledge, this work is the first to identify the semantic relevance of friend pairs in UGC video systems and to study the friend recommendation.

With the advancement of multi-core processor, it is highly desired to use parallel design to improve the IDS throughput in nowadays. However, existing parallel schemes often fail to achieve linear speedup in IDS. The throughput even deteriorates severely for some network traffics. Hence, exploring and addressing the problems have become one of the most urgent issues in parallel IDS. In this work, an IDS model adopting software pipeline is developed as the test bed of parallel performance evaluation. The contribution of this paper is two-fold. First, we explore the performance of parallel IDS through substantive experiments and quantitative analyses. We find Heavy Rule Fingerprint (HRF) in the pre-filter, which has not been mentioned in previous papers as we know, causes severe performance deterioration mentioned in existing studies. The experiments illustrate that the time consumption on HRF in parallel system is at least 6-7 times longer than that in normal system. Second, we propose a new fingerprint extraction strategy to deal with HRF. Experimental results show that the throughput deterioration is resolved completely and the throughput is enhanced by 45% by integrating our proposed method into the test bed and with making use of DARPA evaluation dataset.

Massive data dissemination is often disrupted by frequent join and departure or failure of client nodes in a peer-to-peer (P2P) network. We propose a new churn-resilient protocol (CRP) to assure alternating path and data proximity to accelerate the data dissemination process under network churn. The CRP enables the construction of proximity-aware P2P content delivery systems. We present new data dissemination algorithms using this proximity-aware overlay design. We simulated P2P networks up to 20,000 nodes to validate the claimed advantages. Specifically, we make four technical contributions: 1). The CRP scheme promotes proximity awareness, dynamic load balancing, and resilience to node failures and network anomalies. 2). The proximity-aware overlay network has a 28-50 percent speed gain in massive data dissemination, compared with the use of scope-flooding or epidemic tree schemes in unstructured P2P networks. 3). The CRP-enabled network requires only 1/3 of the control messages used in a large CAM-Chord network. 4) Even with 40 percent of node failures, the CRP network guarantees atomic broadcast of all data items. These results clearly demonstrate the scalability and robustness of CRP networks under churn conditions. The scheme appeals especially to web-scale applications in digital content delivery, network worm containment, and consumer relationship management over hundreds of datacenters in cloud computing services.

Locality-aware BitTorrent (BT) systems reduce the inter-ISP traffic by providing peers with physically close neighbors. However, they still rely on randomized optimistic unchoking, leaving a design space for performance improvement. In this paper, we propose a biased optimistic unchoking mechanism called PicBou. In PicBou, a typical peer prefers to optimistically unchoke the neighbors that are physically close to it or have file pieces rarely replicated among its internal neighbors. The PicBou enables peers in the same ISPs to cooperatively get missing pieces in a prompt way, and share pieces among internal neighbors once the pieces have been downloaded into the ISPs. This feature greatly reduces the content distribution time and saves the backbone bandwidth consumption. The PicBou is simple and can be easily integrated in current locality-aware BT systems. We evaluate the performance through extensive simulations. The results show that PicBou reduces the content distribution time of locality-aware BT systems by about 20% and cuts down the inter-ISP traffic by 19-36%.

Identifying heavy-hitter traffic flows efficiently and accurately is essential for Internet security, accounting and traffic engineering. However, finding all heavy-hitters might require large memory for storage of flows information that is incompatible with the usage of fast and small memory. Moreover, upcoming 100Gbps transmission rates make this recognition more challenging. How to improve the accuracy of heavy-hitters identification with limited memory space has become a critical issue. This paper presents a scalable algorithm named Mnemonic Lossy Counting (MLC) that improves the accuracy of heavy-hitters identification while having a reasonable time and space complexity. MLC algorithm holds potential candidate heavy-hitters in a historical information table. This table is used to obtain tighter error bounds on the estimated sizes of candidate heavy-hitters. We validate the MLC algorithm using real network traffic traces, and we compared its performance with two state-of-the-art algorithms, namely Lossy Counting (LC) and Probabilistic Lossy Counting (PLC). The results reveal that: 1) with same set of parameters and memory usage, MLC achieves between 31.5% and 6.67% fewer false positives than LC and PLC. 2) MLC and LC have a zero false negative ratio, whereas 38% of the cases PLC has a non-zero false negatives and PLC can miss up to 4.4% of heavy-hitters. 3) MLC has a slightly lower memory cost than LC during the first few windows and its memory usage decreases with time, when PLC memory usage declines sharply. 4) MLC has similar runtime than LC, and smaller time than PLC.

BitTorrent, one of the most popular peer-to-peer file sharing applications, accounts for a large proportion of the total Internet traffic. While its appearance benefits the content distributors and users, the traffic injected into the network backbone has become a great challenge for the ISPs. In this paper, we study traffic shaping in BitTorrent-like applications to improve traffic locality and enable fast data delivery. To this end, a piece complementary index is introduced based on the piece demand between peer nodes. Then, we propose an efficient and adaptive neighbor selection scheme (ACNS). According to ACNS, each node self-adaptively chooses the most complementary peers to connect with and download file pieces, rather than having a fixed number of outside neighbors. Our scheme can be integrated with the BitTorrent protocol by slight modifications, and requires no additional infrastructure provided by ISPs. Experimental results based on extensive simulations have shown the effectiveness of ACNS. Compared with the fixed biased neighbor selection scheme, ANCS cuts down the cross-ISP traffic by more than 31% and improves the download rate by about 15%.

In Peer-to-peer (P2P) IPTV networks, jitter rate is one of the most important metrics for Quality of Service. In this paper, we develop a new approach to estimate jitter rate during playback. Unlike traditional approaches that focus on the download speed, our method relies on the distribution of peer download latencies. We demonstrated how to apply the proposed methodologies in a real-life environment. We report simulation results over a P2P IPTV network with 5 seeds and 2,000 clients. Experimental results not only validated the theoretical projections, but also show that our model captures impacts of many design factors. It is thus suggested to use the proposed method as a guiding tool to design P2P IPTV networks with low jitter rate.

In P2P multicast applications, membership management protocols are the basic utilities. In this context, gossip-based protocols have emerged as attractive ones for that they are highly reliable, scalable and simple. Existing gossip-based membership protocols either ignore the underlying topology and the heterogeneity nature of peer nodes or consume lots of control overhead. In this paper, first, we present a modified scalable membership protocol, MSCAMP, to account for node heterogeneity. Then a DHT-aid, gossip-based heterogeneous peer-to-peer membership protocol, called DIGOM, is proposed. DIGOM groups nearby nodes into clusters and takes advantage of MSCAMP as an intra-cluster membership protocol. A DHT structure is built to aid node subscription and inter-cluster link building. From the theoretical analysis and simulation results, both the inter-and intra-cluster fanout in DIGOM can satisfy the requirements for reliable dissemination. Specially, DIGOM achieves a good quality of load balance and requires no synchronization.

Traffic metrics at application level are critical for protocol research, abnormity detection, accounting and network operation. There are great challenges to identify packets at application level since dynamic protocol ports and packet encryption are deployed popularly. There are several different methods of traffic identification being proposed in recently research for corresponding applications. It is impossible to identify traffic with any one method alone. A methodology of online traffic identification at application level named multi-phases identification (MPI) based on packet and flow is proposed in this paper. There are two stages in the methodology. The traffic classification is based on packet characteristic in the first stage and based on flow feature in the second stage to correct the results in the first stage. There are several advantages in MPI: (1) these existing traffic identification methods can be easily integrated into MPI to improve the identification accuracy, (2) the corresponding new identification method for the new application can be inserted into MPI feasibly with scripts of the identification rule, and (3) efficiency of identification can be improved with the mechanism of adaptive justification for the sequence of methods and implemented on multi-CPUs platform. MPI has been implemented a general purpose CPU platform with OC-48 POS and 10 GE network interface. Experiment on an OC-48 POS backbone link shows MPI is accurate and effective for traffic identification.

P2P networks are considered to be the most important development for next generation Internet infrastructure. They always consist of large numbers of cooperative but dynamic member nodes. For these system to be effective, an efficient membership protocol is critical. This paper presents RLM which mainly focuses on locality-aware membership protocol in unreliable and heterogeneous P2P systems. RLM forms member nodes in a ring-based structure. Each node has a neighbor list whose length is proportional to its capacity. Member nodes self-adaptively optimize their neighborhood relations in terms of degree and link latency. To increase robustness, each node also has a successor list that consists of successor nodes down the ring. The successor list is with length of logarithm of the system size on average. Both the neighbor list and successor list are constructed in decentralized ways. Theoretical analysis and intensive simulations have shown the effectiveness of RLM. Specially, while the fault resilience is comparable to that of SCAMP in Ganesh, A.J., et al, (2003), RLM achieves up to 54.5% latency reduction.

More and more emerging P2P applications require support for multi-source data dissemination. However, existing schemes on data dissemination are either only suitable for single source systems or inefficient in terms of delivery delay or message redundancy. This paper presents REM, a reliable and efficient multi-source data dissemination scheme. REM organizes member nodes in a ring-based structure which is reliable, locality-aware and heterogeneity-aware. An undirected delivery tree is built on top of the overlay and used by all nodes. Data messages are first flooded on the overlay and then delivered on the tree. Thus, REM combines the advantages of flooding-based scheme and tree-based scheme. We analyze the reliability, average hop complexity and redundancy rate theoretically and evaluate the performance by simulations. Specially, in large scale systems, compared with a randomized scheme, REM reduces the average delivery delay by about 25% while the redundancy rate is reduced from about 16% to 1%.

DDoS attack is one of the major threads of todaypsilas Internet. Defense against spoofed IP addresses is an efficiency way to mitigate the damage caused by DDoS attacks. HCF proposed by Haining Wang et al. can throttle most attacks while the filter being trained entirely. However, due to the growing of applications current network carried, the network trafficpsilas behavior has taken much more changes. It makes the training of HCF much more difficult to be entirely so the effectiveness of HCF decreased seriously. In this paper, a lightweight online method for mitigating DDoS attacks based on TTL bucket and host threatening index is proposed. Experimental results show that the proposed method significantly reduced false negative rate cause by high dynamic traffics.

Membership protocols are the basic utilities for P2P multicast applications. Existing membership protocols always assume a homogeneous environment or bring non-negligible overhead to optimize the overlay topology. In this paper, we propose SAP2P, a self-adaptive and locality-aware P2P membership protocol for heterogeneous systems. SAP2P periodically optimizes the overlay in terms of node degree and link latency. In SAP2P, the degrees of member nodes are proportional to their capacities and neighbors are always physically close. To reduce the control overhead, SAP2P uses landmark based scheme to evaluate link latencies and takes advantage of a Markov chain based method to adoptively vary the optimization periods. Simulation study shows that SAP2P can achieve good qualities in terms of load balancing and locality awareness with relatively smaller overhead, while it still responds quickly to node churn. Specially, compared with randomized membership protocols, SAP2P achieves up to 53.7% latency reduction.

Rogue Access Points (RAPs) pose serious security threats to local networks. An analytic model of prior probability distribution of Segmental TCP Jitter (STJ) is deduced from the mechanism of IEEE 802.11 MAC Distributed Coordinated Function (DCF) and used to differentiate the types of wire and WLAN connections which is the crucial step for RAPs detecting. STJ as the detecting metric can reflect more the characteristic of 802.11 MAC than ACK-Pair since it can eliminate the delay caused by packet transmission. The experiment on an operated network shows the average detection ratio of the algorithm with STJ is more than 92.8% and the average detection time is less than 1s with improvement of 20% and 60% over the detecting approach of ACK-Pair respectively. Farther more no WLAN training trace is needed in the detecting algorithm.

Consistency maintenance mechanism is necessary for the emerging Peer-to-Peer applications due to their frequent data updates. Centralized approaches suffer single point of failure, while previous decentralized approaches incur too many duplicate update messages because of locality-ignorant structures. To address this issue, we propose a scalable and efficient consistency maintenance scheme for heterogeneous P2P systems. Our scheme takes the heterogeneity nature into account and forms the replica nodes of a key into a locality-aware hierarchical structure, in which the upper layer is DHT-based and consists of powerful and stable replica nodes, while a replica node at the lower layer attaches to a physically close upper layer node. A d-ary update message propagation tree (UMPT) is dynamically built upon the upper layer for propagating the updated contents. As a result, the tree structure does not need to be maintained all the time, sav-ing a lot of cost. Through theoretical analyses and comprehensive simulations, we examine the efficiency and scalability of this design. The results show that, compared with previous designs, especially locality-ignorant ones, our approach is able to reduce the cost by about 25-67 percent.

Due to the capacity restriction of traffic measurement system, an accurate and efficient sampling method is highly demanded. Uniform packet sampling is the simplest technique for reducing the amount of packets that the network monitoring system has to process, but it can't estimate smaller traffic flows which contribute almost more than 80% of the whole traffic flows and are important prompts for network anomaly detection. In this paper, we develop a new packet sampling methodology based on SGS (sketch guided sampling) method called "feedback and resources guided sampling" (FRGS). Our FRGS scheme takes the measurement system capacity as an important parameter to adjust sampling probability, and a feedback of the flow sizes estimation instead of data streaming algorithm is used to save resources. Force sampling is also adopted to increase the accuracy of estimation of smaller flows. Experiments results show that FRGS method is more accurate than the SGS method under limited resources for estimating flow sizes. The accuracy of our scheme has improved nearly 10 times than SGS.

Mobile IPv6 (MIPv6) is proposed to enable network applications to continuously operate at the required quality of service in the wire or wireless IP network. Handover latency of MIPv6 is the main cause of packet loss and performance degradation and is too long for real-time and throughput-sensitive applications. Enhancement of basic MIPv6 with respect to handover latency has been studied widely. A L3 handover procedure can be divided into four phases: Movement Detection, CoA Configuration, Home agent Registration and Route Optimization. The latencies in different handover phases have been measured in an operated wireless LAN (WLAN) in order to determine the performance bottleneck of handover. The effect of handover latency on the sliding window of TCP and application layer protocol is also parsed with experiment. Further more, we modify the MIPv6 implementations of Linux on mobile node and home agent to verify the potential of performance improvement for MIPv6 protocol. The experiment result can help the enhancement of MIPv6 and application development.

Bloom filters allow membership queries over sets with allowable errors. It is widely used in databases, networks and distributed systems and it has great potential for distributed applications where systems need to share information about available data. However, the false positive errors are unavoidable, and the false positive rate increases intolerantly along with the date set expanding. To solve the scalability problem of Bloom filters, this paper presents a new design of a scalable Bloom filter (SBF) for an expanding data set. The SBF keeps a low false positive rate by adding Bloom filter vectors with double length when necessary. The paper proposes algorithms for element insertion and query operation of SBF by employing the H3class of universal hash functions. Theoretical and experimental results demonstrate that the new SBF provides false positive rate as low as 21.3% of the dynamic Bloom filter presented before and the querying CPU time increasing with logarithmic rather than linear. Therefore, the proposed SBF outperforms other current scalable Bloom filters significantly.

Replication and caching have been deployed widely in current P2P systems. In update-allowed P2P systems, a consistency maintenance mechanism is strongly demanded. Several solutions have been proposed to maintain the consistency of P2P systems. However, they either use too much redundant update messages, or ignore the heterogeneity nature of P2P systems. Moreover, they propagate updated contents on a locality-ignorant structure, which could consume unnecessary backbone bandwidth and delay the convergence of consistency maintenance. This paper presents a locality-aware consistency maintenance scheme for heterogeneous P2P systems. Taking the heterogeneity nature, we form the replica nodes into a locality-aware hierarchical structure: the upper layer is DHT-based and a node in the lower layer attaches to a physically close node in the upper layer. An efficient update tree is built dynamically upon the upper layer to propagate the updated contents. Theoretical analyses and simulation results demonstrate the effectiveness of our scheme. Specially, experiment results show that, compared with gossip-based scheme, our approach reduces the cost by about one order of magnitude.

Complexity and diversity of Internet traffic are constantly growing. Networking researchers become aware of the need to constantly monitor and reevaluate their assumptions in order to ensure that the conceptual models correctly represent reality. Using the dataset collected by NetTurbo from three different bidirectional OC-48 links in metro area networks at the two biggest ISPs of China, this paper carefully investigates the self-similar characteristics of traffic from different aspects. In contrast to the previous results which have been widely accepted, this paper shows that for the aggregated traffic and the TCP and UDP traffic whether the self-similarity exists is uncertain. Further, break down by the application category, only the traditional and uncategorized traffic are self-similar while the others are not. However, on the view of the individual application of each category, it seems that traffic of every application exhibits self-similarity. To the best of our knowledge, this paper firstly provides the experimental evidence showing that aggregating different groups of self-similar traffic series could generate a traffic series which is either self-similar or non-self-similar.

In structured P2P system, DHT abstraction and the heterogeneity of node capacity could result in a load imbalance problem. Existing load balancing approaches have two limitations. First, they do not take the link latency into account when moving loads, thus loads may be transferred between two nodes with large link latency. Second, they heavily rely on some nodes of fixed logical locations in the system, which could overload these nodes and make them vulnerable. This paper presents a distributed load balancing algorithm. Each peer node periodically aggregates local loads information based on local neighborhood information, and a heuristic algorithm is used when transferring loads from heavy nodes to light nodes. Our algorithm not only utilizes the proximate relationships of nodes in the physical networks, but also manages to achieve a good tradeoff between the quality of load balance and the load movement cost. The results of our intensive simulation experiments show that our algorithm can not only achieve a good load balance, but also save the bandwidth by more than 23%.

To develop an accurate parametric model for network characteristics is very difficult. We propose a fitting-based adaptive sampling methodology (FASM) trying to model some network metrics non-parametrically. The contributions of the paper are twofold: (1) adopting a piecewise linear function approximation scheme to provide more accurate approximation of the true metric model; (2) the statistical metric derived from the non-parametric model provides much more stable, lower variance and accurate estimation than other popular methodologies under the same sampling size. Experiments based on two measurement traces show that FASM dramatically reduces the number of samples while retaining the same approximating residual error than other methods.