Traffic engineering (TE) is becoming increasingly important in modern networks, as it can improve network performance by splitting traffic across paths. However, traditional TE solvers can be too slow for rapid changes, while recent machine learning (ML) solvers are fast but often fail to support dynamic network conditions, such as topology changes or link capacity changes. Moreover, they usually support only simple TE objectives that do not account for potential link overload, which makes them less practical. In this paper, we present KaeTE, an ML-based TE solver that supports dynamic network conditions and the throughput objective. The design of KaeTE leverages the convexity of the throughput objective. Specifically, KaeTE first makes the throughput objective strongly convex through regularization. KaeTE then adopts a learning-to-optimize (L2O)-inspired model to iteratively refine the dual variables. To ensure that the final TE solutions do not overload any link, KaeTE generates the final TE solutions and the corresponding throughput objective value through a constraint-aware loss function. Evaluations on both dynamic and static network conditions show that KaeTE consistently outperforms baselines in our evaluated settings.

In-network computing (INC) offers orders-of-magnitude performance gains for various applications. However, the existing pipeline-based switch architecture, though well-suited for stateless packet forwarding, imposes three constraints on stateful INC applications: (i) control-plane table management, (ii) scarce memory resources under per-stage layout, and (iii) a strict memory access model. To address these constraints, this paper provides a full-stack solution, covering a programmable chipset Solar-NP, a programming language NPC, and a complete toolchain XuanWu. First, Solar-NP adopts a run-to-completion-based (RTC-based) architecture with three new hardware features: data-plane table management, a hierarchical memory pool, and built-in data structures with atomic access guarantees. Second, to fully exploit the hardware features, our language NPC introduces a new abstraction, namely operation-action table (OAT), that allows table manipulations in the data plane. Finally, our XuanWu toolchain provides various utility software covering the complete workflow of developing, testing, debugging, and deployment. To show the power of our solution, we implement three types of INC cases, including in-network control, in-network telemetry, and in-network storage. Experimental results demonstrate that our solution allows more operations to be offloaded and achieves higher performance than today's pipeline-based solutions.

Current GPU Collective Communication Libraries (CCLs) employ predefined schedules optimized for stable environments. Their supported schedules and selection logic are fixed at communicator initialization, which fails to account for evolving runtime conditions, such as workload characteristics and hardware health status. Consequently, long-running GPU jobs experience suboptimal performance after hours or days of execution, which translates into longer job completion times and wasted GPU cluster resources. To address this problem, we present Theseus, a novel CCL backend that provides schedule-level runtime adaptivity. It admits user-defined schedules and selection policies. As runtime conditions change, Theseus selects suitable schedules using cluster-wide runtime attributes beyond CCL-internal metrics. Moreover, it hot-swaps from the previous schedule consistently across GPUs with low overhead. Theseus acts as a drop-in replacement to facilitate integration. We evaluate Theseus extensively on various GPU workloads with intuitive policies. Compared with NCCL, Theseus achieves up to 1.61X speedup of communication time in stable environments and 2.46X in dynamic environments. It improves end-to-end job completion time by up to 1.84X while incurring comparable or lower overhead.

Recent network telemetry solutions typically target programmable switches to achieve high performance and in-network visibility. They partition the packet stream into windows and then apply various stream processing techniques to summarize flow-level statistics. However, existing studies focus on the measurement within each window. Window management is still a missing piece due to the resource limitation of programmable switches. In this paper, we propose OmniWindow, a general and efficient window mechanism framework. OmniWindow splits the original window into fine-grained sub-windows such that the sub-windows can be merged into various window types. To deal with the resource restriction, OmniWindow carefully designs its data plane memory layout and proposes a window synchronization method. It also employs a collaborative architecture that can collect and reset stateful data in sub-windows within a limited time. We prototype OmniWindow on Tofino. We incorporate OmniWindow into a SOTA query-driven telemetry system and eight sketch-based telemetry algorithms. Our experiments demonstrate that OmniWindow enables these telemetry solutions to achieve higher accuracy than conventional window mechanism.

Sketches have proven to be useful for measuring traffic. They store measurement results in the registers of data plane switches. However, they suffer from the short of switch register resources, limiting their measurement accuracy.

To achieve dynamic network measurement, trends build sketches on eBPF to avoid service interruptions. However, existing eBPF-based sketches suffer from high CPU consumption, leading to poor throughput and high latency and making them hard to measure high-speed traffic. Optimizing their performance requires users to refactor codes based on each sketch’s characteristics on eBPF, which is highly complex and time-consuming.In this paper, we argue that users should write sketches without concerning low-level eBPF performance optimizations, with the deployment automatically activating cross-sketch performance optimizations. We present Carrera, a library that offers domain-specific optimizations for eBPF-based sketches. Our contributions are (1) systematically analyzing the performance bottlenecks of eBPF-based sketches through microbenchmarks, (2) identifying practical optimizations, including hardware offloading, SIMD-accelerated hashing, traffic-aware flow index caching, prefetched randomization, and active data collection, to address the identified bottlenecks in eBPF-based sketches, (3) evaluating these optimizations with state-of-the-art sketches and demonstrating that Carrera improves throughput by up to 65% and reduces latency by up to 93% via testbed experiments.

Network measurement is essential for cloud tenants in their virtual network management. However, existing measurement systems exhibit suboptimal resource efficiency while accommodating an increasing number of tenants with limited switch resources. To address this issue, this paper proposes FlowGram, a measurement framework to provide flow frequency estimation services for cloud tenants. FlowGram provides a user-friendly interface for tenants and automatically adjusts the memory allocation to meet the tenants' demands. In the data plane, FlowGram employs sketches on programmable switches to perform the measurement. In the control plane, FlowGram utilizes a precise error model of sketches and an efficient memory allocation algorithm that ensures the measurement errors are within the specified error bounds. We prototype FlowGram on programmable switches and commodity servers and conduct comprehensive experiments. Experiment results demonstrate that FlowGram outperforms the state-of-the-art system, achieving a 14 % higher task satisfaction rate while utilizing the same amount of resources.

Deploying data plane programs across the network is typically formulated as a mixed-integer programming task, leading to a long execution time. In response, existing studies carefully tailor heuristics for specific task properties such as objectives. However, they suffer from poor solution quality under dynamic task deployment since they overfit specific task properties. Recently, generative diffusion models have been widely adopted in network optimizations due to their strong adaptability and generalization. Accordingly, in this poster, we propose a diffusion model-based framework for data plane program deployment tasks. Our key idea is to leverage the reverse denoising process of diffusion models to react to dynamic task changes at runtime while maintaining high solution quality. Preliminary results on our testbed show that we reduce latency by 66.67% and resource overhead by 58.62% during dynamic deployment.

In network measurement, data plane switches measure traffic and report events (e.g., heavy hitters) to the control plane via control channels. The control plane makes decisions to process events. However, current network measurement suffers from two problems. First, when traffic bursts occur, massive events are reported in a short time so that the control channels may be overloaded due to limited bandwidth capacity. Second, only a few events are reported in normal cases, making control channels underloaded and wasting network resources. In this paper, we propose$\textsf {Escala}$to provide the elastic scaling of control channels at runtime. The key idea is to dynamically migrate event streams among control channels to regulate the loads of these channels.$\textsf {Escala}$offers two components, including an$\textsf {Escala}$monitor that detects scaling situations based on realtime network statistics, and an optimization framework that makes scaling decisions to eliminate overload and underload situations. We have implemented a prototype of$\textsf {Escala}$on Tofino-based switches. Extensive experiments show that$\textsf {Escala}$achieves timely elastic scaling while preserving high application-level accuracy.

In programmable networks, some networking systems coordinate data plane switches to perform in-network functions (e.g., in-band network telemetry). However, the vulnerabilities associated withinter-device coordinationremain largely unexplored and overlooked, which is highly concerning given the increasing popularity of this paradigm. In this paper, we identify three attack scenarios built upon such vulnerabilities, where attackers mislead the behaviors of networking systems. We implement 20 networking systems on Tofino-based switches and a simulator and test them against the identified attacks. Our experimental results show that our attacks severely disrupt the normal operation of these networking systems, e.g., the cache hit rate of NetCache drops by 38%. However, our analysis reveals that none of existing methods fully mitigate our attacks because they fail to verify the packets for inter-device coordination. To this end, we select characteristics from existing methods while addressing their limitations to design effective mitigation methods. Experimental results indicate that our methods perform well in mitigating our attacks and introduce acceptable overheads.

Skewed write-intensive key-value storage workloads are increasingly observed in modern data centers, yet they also incur server overloads due to load imbalance. Programmable switches provide viable solutions for realizing load-balanced caching on the I/O path, and hence implementing write-back caching in programmable switches is a natural approach to absorb frequent writes and improve write performance. However, enabling in-switch write-back caching is challenged by not only the strict programming rules and limited stateful memory of programmable switches, but also the need for reliable protection against data loss due to switch failures. We first propose FarReach, a new caching framework that supports fast, available, and reliable in-switch write-back caching. FarReach carefully co-designs both the control and data planes for cache management in programmable switches, so as to achieve high data-plane performance with lightweight control-plane management. We further extend FarReach into DistReach, which reduces the reliability maintenance overhead via distributed switch deployment. Our experimental results on a Tofino-switch testbed show that FarReach achieves a throughput gain of up to$6.6\times $over a state-of-the-art in-switch caching approach under skewed write-intensive workloads. Also, DistReach reduces the crash recovery time of FarReach by 77.4%.

Privacy preservation is critical for neural network inference, which often involves collaborative execution of different parties to make predictions on sensitive data based on sensitive neural network models. However, the expensive cryptographic operations of privacy preservation also pose performance chal-lenges to neural network inference. We address this performance-security tension by designing PP-Stream, a distributed stream processing system for high-performance privacy-preserving neural network inference. PP-Stream adopts hybrid privacy-preserving mechanisms for linear and non-linear operations of neural network inference. It treats inference data as real-time data streams, and parallelizes the inference operations across multiple pipelined stages that are executed by multiple servers and threads. It also solves the load-balanced resource allocation across servers and threads as an optimization problem. We prototype PP-Stream and show via testbed experiments that it achieves low inference latencies on various neural network models.

Traditional disk failure prediction approaches struggle to scale with data growth, as they treat data as a whole collection to obtain the global data view for preprocessing and training. Existing distributed machine learning and stream mining systems are designed to scale data processing, particularly for training. However, scaling disk failure prediction faces challenges in the scalability of preprocessing, including additional data movements from data collection to training, data inflation during preprocessing, and multiple-to-multiple data allocation. To address these challenges, we present SCALEDFP, a general framework for scaling disk failure prediction via multi-source stream mining based on three techniques: near-data preprocessing, random downsampling, and training data allocation. SCALEDFP scales disk failure prediction with the number of data sources. It achieves significant throughput gains of preprocessing and training with comparable prediction accuracy against a state-of-the-art disk failure prediction approach that collects data in a centralized place.

Federated Learning (FL) has been applied across diverse domains as a powerful technique but faces critical challenges in privacy protection. Secure aggregation and additive homomorphic encryption are two of the most commonly used cryptographic methods to protect model updates. To provide a strong privacy guarantee, both methods satisfy the additivity and require the integer form to encrypt model updates. However, they still suffer from a non-negligible overhead of the computation and communication. To mitigate such overhead, existing approaches of lossy compression (e.g., gradient compression) have been explored but exhibit the inapplicability of FL with additive cryptographic methods. In this paper, we propose FedSSA, a novel compression framework to reduce the overhead of additive cryptographic methods in FL based on two new techniques: (i) QSRHT Sketch, a sketch-based compression method that supports large compression ratios with a bounded error with the integer requirement, and (ii) periodic rehashing, which ensures the unbiasedness of QSRHT Sketch. Our evaluation shows that FEDSSA achieves a high compression ratio ($\times 160$) with a low model accuracy degradation (less than 5%). For additive homomorphic encryption, FEDSSA reduces the average computation time per round by up to 58.15 % compared to state-of-the-art compressor that support additive homomorphic encryption, with a low test accuracy drop (within 2.2 %).

Although the native RDMA interface allows for high throughput and low latency, its low-level abstraction raises significant programming challenges. Consequently, numerous systems encapsulate the RDMA interface into more user-friendly high-level abstractions such as Socket, MPI, and RPC. However, this ease of development often incurs considerable performance degradation. To address this trade-off, this paper introduces RB2, a high-performance RDMA-based Distributed Ring Buffer (DRB). RB2serves as a middle layer that effectively conceals the low-level details of the RDMA interface while also facilitating extension to other high-level abstractions.Nonetheless, it is non-trivial for DRBs to preserve the RDMA performance. We optimize the performance of RB2in three aspects. First, we perform micro-benchmarks to identify the pointer synchronization methods that are seemingly counter-intuitive but offer optimal performance improvements. Second, we propose an adaptive batching mechanism to alleviate the limitations of conventional fixed batching. Finally, we build an efficient memory subsystem using various optimization techniques. RB2outperforms SOTA designs by achieving 2.5 × to 7.5 × throughput while maintaining comparable tail latency for small messages.

Sketch-based traffic measurement is a crucial building block for monitoring traffic statistics and ensuring the quality of services of end-host applications. However, existing approaches for building sketches in end-hosts exhibit poor packet processing performance or high CPU consumption. In this paper, we propose MPU, which automatically offloads sketch-based measurement to the emerging hardware, DPU. MPU consists of a sketch analyzer that profiles sketch resource consumption and an optimization framework that formulates the offloading problem and maximizes sketch performance on DPU. We implement MPU on the NVIDIA BlueField DPU. Our testbed results indicate that MPU achieves 85% lower per-packet processing latency and 47% higher traffic measurement accuracy when compared to existing approaches.

Sketches are useful for network measurement thanks to their low resource overheads and theoretically bounded accuracy. However, their network-wide deployment suffers from the trade-off between optimality and scalability: (1) Most solutions rely on mixed integer linear programming (MILP) solvers to provide the optimal decisions. But they are time-consuming and can hardly scale to large-scale deployment scenarios. (2) While heuristics achieve scalability, they deteriorate resource and performance overheads. We propose Eagle, a framework that achieves scalable and near-optimal network-wide sketch deployment. Our key idea is to decompose network-wide sketch deployment into sub-problems. Such decomposition allows Eagle to (1) simultaneously optimize switch resource consumption and end-to-end performance (retaining optimality), and (2) incorporate time-saving techniques into sub-problem solving (achieving scalability). Compared to existing solutions, Eagle improves scalability by up to 255× with negligible loss of optimality. It has also saved administrators in a production network days of efforts and reduced the operation time from O(hour) to O(second).

Ensuring service availability in large-scale datacenters hinges on network monitoring. For monitoring quality, it is essential to attain sufficient coverage of all physical components. However, given the ever-evolving complexity of industrial environments, even measuring coverage metrics becomes challenging, let alone attaining sufficient coverage. In fact, insufficient coverage widely existed in our production datacenters and caused many missed failures.

To date, security researchers evaluate their solutions of mitigating distributed denial-of-service (DDoS) attacks via kernel-based or kernel-bypassing testing tools. However, kernel-based tools exhibit poor scalability in attack traffic generation while kernel-bypassing tools incur unacceptable monetary cost. We propose Excalibur, a scalable and low-cost testing framework for evaluating DDoS defense solutions. The key idea is to leverage the emerging programmable switch to empower testing tasks with Tbps-level scalability and low cost. Specifically, Excalibur offers intent-based primitives to enable academic researchers to customize testing tasks on demand. Moreover, in view of switch resource limitations, Excalibur coordinates both a server and a programmable switch to jointly perform testing tasks. It realizes flexible attack traffic generation, which requires a large number of resources, in the server while using the switch to increase the sending rate of attack traffic to Tbps-level. We have implemented Excalibur on a$64\times 100$Gbps Tofino switch. Our experiments on a$64\times 100$Gbps Tofino switch show that Excalibur achieves orders-of-magnitude higher scalability and lower cost than existing tools.

Network administrators usually realize network functions in data plane programs. They employ the network-wide program deployment that decomposes input programs into match-action tables (MATs) while deploying each MAT on a specific switch. Since MATs may be deployed on different switches, existing solutions propose the inter-switch coordination that uses the per-packet header space to deliver crucial packet processing information among switches. However, such coordination incurs non-trivial per-packet byte overhead, leading to end-to-end performance degradation. We propose, a framework that aims to minimize the per-packet byte overhead. The key idea is to formulate network-wide program deployment as a mixed-integer programming (MIP) problem with the objective of minimizing the per-packet byte overhead. Also, offers a greedy-based heuristic that solves the problem in a near-optimal and timely manner. We have implemented on Tofino switches. Compared to existing frameworks, decreases the per-packet byte overhead by 156 bytes while preserving end-to-end performance in terms of flow completion time and goodput.

In modern data center networks (DCNs), network-stack processing denotes a large portion of the end-to-end latency of TCP flows. So profiling network-stack latency anomalies has been considered as a crucial part in DCN performance diagnosis and troubleshooting. In particular, such profiling requires full coverage (i.e., profiling every TCP packet) and low overhead (i.e., profiling should avoid high CPU consumption in end-hosts). However, existing solutions rely on system calls or tracepoints in end-hosts to implement network-stack latency profiling, leading to either low coverage or high overhead. We propose Torp, a framework that offers full-coverage and low-overhead profiling of network-stack latency. Our key idea is to offload as much of the profiling from costly system calls or tracepoints to the Torp agent built on eBPF modules, and further to include a Torp handler on the ToR switch to accelerate the remaining profiling operations. Torp efficiently coordinates the ToR switch and the Torp agent on end-hosts to jointly execute the entire latency profiling task. We have implemented Torp on$32\times 100$Gbps Tofino switches. Testbed experiments indicate that Torp achieves full coverage and orders of magnitude lower host-side overhead compared to other solutions.

The programmable switch offers a limited capacity of packet header vector (PHV) words that store packet header fields and metadata fields defined by network functions. However, existing switch compilers employ inefficient strategies of encoding fields on PHV words. Their encoding wastes scarce PHV words and may result in failures when deploying network functions. In this paper, we propose Melody, a new framework that reuses PHV words for as many fields as possible to achieve resource-efficient PHV encoding. Melody offers a field analyzer and an optimization framework. The analyzer identifies which fields can reuse PHV words while preserving the original packet processing logic. The framework integrates analysis results into its encoding to offer the resource-optimal decisions. Also, to achieve timeliness at runtime, it provides a Greedy-based heuristic, which quickly solves PHV encoding and returns near-optimal results. We evaluate Melody with production-scale network functions. Our results show that Melody reduces the consumption of PHV words by up to 85%.

Programmable switches allow administrators to customize packet processing behaviors in data plane programs. However, existing solutions for program deployment fail to achieve resource efficiency and high packet processing performance. In this paper, we propose SPEED, a system that provides resource-efficient and high-performance deployment for data plane programs. For resource efficiency, SPEED merges input data plane programs by reducing program redundancy. Then it abstracts the substrate network into an one big switch (OBS), and deploys the merged program on the OBS while minimizing resource usage. For high performance, SPEED searches for the performance-optimal mapping between the OBS and the substrate network with respect to network-wide constraints. It also maintains program logic among different switches via inter-device packet scheduling. We have implemented SPEED on a Barefoot Tofino switch. The evaluation indicates that SPEED achieves resource-efficient and high-performance deployment for real data plane programs.

Network telemetry is essential for administrators to monitor massive data traffic in a network-wide manner. Existing telemetry solutions often face the dilemma between resource efficiency (i.e., low CPU, memory, and bandwidth overhead) and full accuracy (i.e., error-free and holistic measurement). We break this dilemma via a network-wide architectural design, which simultaneously achieves resource efficiency and full accuracy in flow-level telemetry for large-scale data centers. carefully coordinates the collaboration among different types of entities in the whole network to execute telemetry operations, such that the resource constraints of each entity are satisfied without compromising full accuracy. It further addresses consistency in network-wide epoch synchronization and accountability in error-free packet loss inference. We prototype in DPDK and P4. Testbed experiments on commodity servers and Tofino switches demonstrate the effectiveness of over state-of-the-art solutions.

With the explosive growth of data volume, distributed machine learning has become the mainstream approach for training deep neural networks. However, distributed machine learning incurs non-trivial communication overhead. To this end, various compression schemes are proposed to alleviate the communication volume among nodes. Nevertheless, existing compression schemes, such as gradient quantization or gradient sparsification, suffer from low compression ratios and/or high computational overheads. Recent studies advocate leveraging sketch techniques to assist these schemes. However, the limitations of gradient quantization and gradient sparsification remain. In this paper, we propose SK-Gradient, a novel gradient compression scheme that solely builds on sketch. The core component of SK-Gradient is a novel sketch namely FGC Sketch that is tailored for gradient compression. FGC Sketch precomputes the costly hash functions to alleviate computational overheads. Its simplified design makes it convenient for GPU acceleration. In addition, SK-Gradient leverages various techniques including selective gradient compression and periodic synchronization strategy to improve computational efficiency and compression accuracy. Compared with the state-of-the-art schemes, SK-Gradient achieves up to 92.9% reduction in computational overhead and up to 95.2% improvement in training speedups at the same compression ratio.

Stream processing is critical to data analytics. However, one important class of characteristics namely per-key distribution (i.e., the item distribution of every key) remains unsolved. Traditional stream processing methods such as sampling and histogram do not focus on per-key distribution. Though sketch is widely applied to deal with huge and high-speed streaming data, it mainly computes singular-value characteristics. However, per-key distribution needs to deal with multiple values for each key, which amplifies the needed resources.To this end, we present a novel sketch-based algorithm HistSketch for per-key distribution. Its key idea is to differentiate hot keys from infrequent keys and use different components to deal with them. For hot keys, HistSketch allocates dedicated counters. For infrequent keys, HistSketch allows counter sharing to alleviate memory usage. In addition, we propose two optimization mechanisms for HistSketch: the histogram shedding mechanism further reduces the storage overheads, while the equation-based decoding compensates for the error caused by counter sharing. Our evaluation compares HistSketch with nine state-of-the-art sketch-based solutions using five datasets. Our results show that HistSketch achieves both high accuracy and low resource usage.

To date, security researchers evaluate their solutions of mitigating denial-of-service (DDoS) attacks via kernel-based or kernel-bypassing testing tools. However, kernel-based tools exhibit poor scalability in attack traffic generation while kernel-bypassing tools result in unacceptable monetary cost. We propose Excalibur, a scalable and low-cost testing framework for DDoS defense solutions. The key idea is to leverage the programmable switch to perform testing tasks with Tbps-level scalability and low cost. Specifically, Excalibur coordinates both a server and a programmable switch to jointly perform testing tasks. It realizes flexible attack traffic generation, which requires a large number of resources, in the server while using the switch to increase the sending rate of attack traffic to Tbps-level. Our experiments on a 64×100Gbps Tofino switch show that Excalibur achieves orders-of-magnitude higher scalability and lower cost than existing tools.

The programmable switch offers a limited capacity of packet header vector (PHV) words that store packet header fields and metadata fields defined by network functions. However, existing switch compilers employ inefficient strategies of encoding fields on PHV words. Their encoding wastes scarce PHV words and may result in failures when deploying network functions. In this paper, we propose Melody, a new framework that reuses PHV words for as many fields as possible to achieve resource-efficient PHV encoding. Melody offers a field analyzer and an optimization framework. The analyzer identifies which fields can reuse PHV words while preserving the original packet processing logic. The framework integrates analysis results into its encoding to offer the resource-optimal decisions. We evaluate Melody with production-scale network functions. Our results show that Melody reduces the consumption of PHV words by up to 85%.

In programmable networks, some networking systems coordinate data plane switches to realize in-network functions (e.g., in-band network telemetry). However, the vulnerabilities of inter-device coordination are still largely unknown and neglected, which is highly concerning given the increasing popularity of this paradigm. In this paper, we identify three attack scenarios built upon such vulnerabilities, where attackers mislead the behaviors of networking systems that exploit inter-device coordination to execute in-network functions. We implement 20 existing networking systems on Tofino-based switches and a simulator, and attack these systems with the identified attacks. The experimental results indicate that our attacks significantly interfere with the normal operations of the selected networking systems, e.g., the cache hit rate of NetCache drops 38%. Our analysis also demonstrates that none of existing methods can fully mitigate our attacks since they fail to verify the packets for inter-device coordination.

Sketch algorithms have been widely deployed for network measurement as they achieve high accuracy with restricted resource usage. They store measurement results compactly in fixed-size counters. However, as sketch counters are skewed towards low values, higher bits in most counters remain zero. Such massive unused bits impair the space efficiency valued by sketch algorithms. Unfortunately, efforts to mitigate the issue either apply to specific algorithms or compromise accuracy. In this paper, we design BitSense, a novel optimization framework that integrates with existing sketch algorithms. The key idea is to regard higher bits in sketch counters as a sparse vector and leverage compressive sensing techniques to compress and restore counters. Further, BitSense provides a programming model to help developers easily realize sketch algorithms without dealing with the details of compression and recovery. Bit-Sense proposes an automatic approach for parameter configuration. It theoretically guarantees nearly zero error under the configuration. We have built a BitSense prototype in P4 and a software platform and integrated it with fourteen sketch solutions. Extensive experiments show that BitSense significantly reduces the memory usage of existing sketch solutions by 25%-80% while incurring little overhead and almost zero accuracy drop, outperforming five state-of-the-art optimization frameworks.

Recent network telemetry solutions typically target programmable switches to achieve high performance and in-network visibility. They partition the packet stream into windows and then apply various stream processing techniques to summarize flow-level statistics. However, existing studies focus on the measurement within each window. Window management is still a missing piece due to the resource limitation of programmable switches. In this paper, we propose OmniWindow, a general and efficient window mechanism framework. OmniWindow splits the original window into fine-grained sub-windows such that the sub-windows can be merged into various window types. To deal with the resource restriction, OmniWindow carefully designs its data plane memory layout and proposes a window synchronization method. It also employs a collaborative architecture that can collect and reset stateful data in sub-windows within a limited time. We prototype OmniWindow on Tofino. We incorporate OmniWindow into a SOTA query-driven telemetry system and eight sketch-based telemetry algorithms. Our experiments demonstrate that OmniWindow enables these telemetry solutions to achieve higher accuracy than conventional window mechanism.

In-band network telemetry (INT) enriches network management at scale through the embedding of complete device-internal states into each packet along its forwarding path, yet such embedding of INT information also incurs significant bandwidth overhead in the data plane. We propose DeltaINT, a general INT framework that achieves extremely low bandwidth overhead and supports various packet-level and flow-level applications in network management. DeltaINTbuilds on the insight that state changes are often negligible at most time, so it embeds the complete state information into a packet only when the state change is deemed significant. We propose two variants for DeltaINTthat trade between bandwidth usage and measurement accuracy, while both variants achieve significantly lower bandwidth overhead than the original INT framework. We theoretically derive the time/space complexities and the guarantees of bandwidth mitigation for DeltaINT. We implement DeltaINTin both software and P4. Our evaluation shows that DeltaINTsignificantly mitigates the bandwidth overhead, and the deployment in a Tofino switch incurs limited hardware resource usage.

In network function virtualization (NFV), network functions (NFs) are chained as a service function chain (SFC) to enhance NF management with low cost and high flexibility. Recent NFV solutions indicate that the packet processing performance of SFCs can be significantly improved by offloading NFs to programmable switches. However, such offloading requires a deep understanding of heterogeneous NF properties (e.g., NF resource consumption and NF performance behaviors) to achieve the maximum SFC performance. Unfortunately, none of existing solutions provide automatic analysis of these NF properties. Thus, network administrators have to manually examine the source codes of NFs and profile various NF properties by hand, which is extremely time-consuming and laborious. In this article, we propose LightNF, a novel system that simplifies NF offloading in programmable networks. LightNF automatically dissects comprehensive NF properties by means of code analysis and performance profiling while eliminating manual efforts. It then leverages its analysis results of NF properties in its SFC placement so as to make the performance-optimal offloading decisions. We have implemented LightNF on Tofino-based hardware programmable switches. We perform extensive experiments to evaluate LightNF with a real-world testbed and large-scale simulation. Our experiments show that LightNF outperforms existing solutions with an orders-of-magnitude reduction in per-packet processing latency and 9.5× improvement in SFC throughput.

Due to limited memory usage and provably high accuracy, sketches running on programmable switches have been commonly used by the literature for network measurement. However, their vulnerabilities are still largely unknown and neglected, which is highly concerning given the increasing popularity of network measurement. In this paper, we identify the Stalker attacks, where attackers aim to degrade the accuracy of sketches running on programmable switches. More precisely, attackers tamper with some sketch operations during sketch deployment atop programmable switches. At runtime, the tampered sketch will record highly inaccurate flow data, which degrades measurement accuracy. We implement Stalker attacks on Tofino switches. The results indicate that Stalker attacks significantly drop the accuracy of network management applications, e.g., reducing the F1 score of heavy hitter detection to zero. However, our analysis indicates that none of existing methods can detect Stalker attacks since they can hardly verify the correctness of sketch operations. Finally, we analyze potential defense mechanisms and identify challenges to enable further research in this context.

Modern large-scale online service providers typically deploy microservices into containers to achieve flexible service management. One critical problem in such container-based microservice architectures is to control the arrival rate of requests in the containers to avoid containers from being overloaded. In this article, we present our experience of rate limit for the containers in Alibaba, one of the largest e-commerce services in the world. Given the highly diverse characteristics of containers in Alibaba, we point out that the existing rate limit mechanisms cannot meet our demand. Thus, we design Noah, a dynamic rate limiter that can automatically adapt to the specific characteristic of each container without human efforts. The key idea of Noah is to use deep reinforcement learning (DRL) that automatically infers the most suitable configuration for each container. To fully embrace the advantages of DRL in our context, Noah addresses two technical challenges. First, Noah uses a lightweight system monitoring mechanism to collect container status. In this way, it minimizes the monitoring overhead while ensuring a timely reaction to system load changes. Second, Noah injects synthetic extreme data when training its models. Thus, its model gains knowledge on unseen special events and hence remains highly available in extreme scenarios. To guarantee model convergence with the injected training data, Noah adopts task-specific curriculum learning to train the model from normal data to extreme data gradually. Noah has been deployed in the production of Alibaba for two years, serving more than 50000 containers and around 300 types of microservice applications. Experimental results show that Noah can well adapt to three common scenarios in the production environment. It effectively achieves better system availability and shorter request response time compared with four state-of-the-art rate limiters.

Programmable switches empower stateful packet processing, in which incoming packets continuously update states in the data plane, while applications in the control plane read and write states. However, since the data plane and control plane are separated, a consistent view of states in both planes is required for stateful packet processing. Existing approaches suffer from either high latency or low accuracy. In this paper, we propose ApproSync, a framework that offers approximate state synchronization with low latency and high accuracy. To achieve low latency, ApproSync directly transfers states between switch ASICs and the control plane by bypassing switch operating systems. To achieve high accuracy, ApproSync utilizes the resources in the switch ASIC to realize rate control in state synchronization, such that it avoids potential state loss. It also bounds the divergence between the states in the data plane and that in the control plane under limited link capacity. We prototype ApproSync on Barefoot Tofino switches. The experimental results indicate that compared to existing approaches, ApproSync achieves order-of-magnitude latency reduction while maintaining high accuracy of state synchronization. Also, our experiments demonstrate that ApproSync provides significant latency benefits to existing network management applications and well preserves high application-level accuracy.

Recent efforts in network measurement place measurement tasks on programmable switches to measure high-speed traffic. These tasks extract flow data, i.e., events, from packets and send events to the control plane. However, the tasks may generate massive events in a short time. In this context, the links transferring events to the control plane and the control plane servers that handle events may be overloaded, i.e., control plane overload. None of existing solutions can eliminate control plane overload. In this paper, we propose MTP, a framework that eliminates control plane overload via careful measurement task placement. Our key idea is to allocate enough resources for each task during task placement to avoid control plane overload at runtime. For each task, MTP estimates its maximum possible rate of sending events to the control plane. Then its optimization framework addresses the resource restrictions of both switches and the control plane. The experiments on Tofino switches indicate that MTP outperforms existing solutions with higher accuracy in several use cases.

Finding hierarchical heavy hitters (HHHs) (i.e., hierarchical aggregates with exceptionally huge amounts of traffic) is critical to network management, yet it is often challenged by the requirements of fast packet processing, real-time and accurate detection, as well as resource efficiency. Existing HHH detection schemes either incur expensive packet updates for multiple aggregation levels in the IP address hierarchy, or need to process sufficient packets to converge to the required detection accuracy. We present MVPipe, an invertible sketch that achieves both lightweight updates and fast convergence in HHH detection. MVPipe builds on the skewness property of IP traffic to process packets via a pipeline of majority voting executions, such that most packets can be updated for only one or few aggregation levels in the IP address hierarchy. We show how MVPipe can be feasibly deployed in P4-based programmable switches subject to limited switch resources. We also theoretically analyze the accuracy and coverage properties of MVPipe. Evaluation with real-world Internet traces shows that MVPipe achieves high accuracy, high throughput, and fast convergence compared to six state-of-the-art HHH detection schemes. It also incurs low resource overhead in the Tofino switch deployment.

Superspreaders (i.e., hosts with numerous distinct connections) remain severe threats to production networks. How to accurately detect superspreaders in real-time at scale remains a non-trivial yet challenging issue. We present SpreadSketch, an invertible sketch data structure for network-wide superspreader detection with the theoretical guarantees on memory space, performance, and accuracy. SpreadSketch tracks candidate superspreaders and embeds estimated fan-outs in binary hash strings inside small and static memory space, such that multiple SpreadSketch instances can be readily merged to provide a network-wide measurement view for recovering superspreaders and their estimated fan-outs. We present formal theoretical analysis on SpreadSketch in terms of space and time complexities as well as error bounds. We further extend SpreadSketch with a fast and small data structure that filters out the packets of high-frequency connections from sketch processing, so as to improve the update performance of SpreadSketch while maintaining the accuracy guarantees. Trace-driven evaluation shows that SpreadSketch achieves higher accuracy and performance over state-of-the-art sketches and remains accurate in detecting real-world worms and DDoS attacks. Furthermore, we prototype SpreadSketch in P4 and show its feasible deployment in commodity hardware switches.

In modern networks, administrators realize their desired functions such as network measurement in several data plane programs. They often employ the network-wide program deployment paradigm that decomposes input programs into match-action tables (MATs) while deploying each MAT on a specific programmable switch. Since MATs may be deployed on different switches, existing solutions propose the inter-switch coordination that uses the per-packet header space to deliver crucial packet processing information among switches. However, such coordination introduces non-trivial per-packet byte overhead, leading to significant end-to-end network performance degradation. In this paper, we propose Hermes, a program deployment framework that aims to minimize the per-packet byte overhead. The key idea of Hermes is to formulate the network-wide program deployment as a mixed-integer linear programming (MILP) problem with the objective of minimizing the per-packet byte overhead. In view of the NP hardness of the MILP problem, Hermes further offers a greedy-based heuristic that solves the problem in a near-optimal and timely manner. We have implemented Hermes on Tofino-based switches. Our experiments show that compared to existing frameworks, Hermes decreases the per-packet byte overhead by 156 bytes while preserving end-to-end performance in terms of flow completion time and goodput.

Sketches enable efficient and fine-grained network measurement results with configurable resource-performance trade-offs. While sketch configurations are guided by theories, the current theoretical guidelines are either impractical or deficient for sketch configurations on emerging programmable switches. To better configure sketches on programmable switches, we (1) systematically analyze the limitations of sketch configuration guidelines on programmable hardware switches (i.e., unguided parameters, accuracy profiles, and resource budgets); (2) propose a generic and practical framework called SketchGuide to automate efficient sketch configurations on programmable switches; (3) implement SketchGuide on a Barefoot Tofino switch and compare SketchGuide to the state-of-the-art sketches by conducting extensive experiments. Our evaluations demonstrate that SketchGuide can automatically configure unguided parameters given resource budgets. SketchGuide reduces the hardware resource footprint by 52.92%-99.28% compared with current guidelines without impacting fidelity.

In data center networks (DCNs), host-side packet processing accounts for a large portion of the end-to-end latency of TCP flows. Thus, the profiling of host-side latency anomalies has been considered as a crucial part in DCN performance diagnosis and troubleshooting. In particular, such profiling requires full coverage (i.e., profiling every TCP packet handled by end-hosts) and low overhead (i.e., profiling should avoid high CPU consumption in end-hosts). However, existing solutions fully rely on end-hosts to implement host-side latency profiling, leading to low coverage or high overhead. In this paper, we propose Torp, a framework that offers full-coverage and low-overhead profiling of host-side latency. Our key idea is to offload profiling operations to top-of-rack (ToR) switches, which inherently offer full coverage and line-rate packet processing performance. Specifically, Torp selectively offloads profiling operations to the ToR switch based on switch limitations. It efficiently coordinates the ToR switch and end-hosts to execute the entire latency profiling task. We have implemented Torp on 32×100Gbps Tofino switches. Testbed experiments indicate that Torp achieves full coverage and orders of magnitude lower host-side overhead compared to other solutions.

In network measurement, data plane switches measure traffic and report events (e.g., heavy hitters) to the control plane via control channels. The control plane makes decisions to process events. However, current network measurement suffers from two problems. First, when traffic bursts occur, massive events are reported in a short time so that the control channels may be overloaded due to limited bandwidth capacity. Second, only a few events are reported in normal cases, making control channels underloaded and wasting network resources. In this paper, we propose Escala to provide the elastic scaling of control channels at runtime. The key idea is to dynamically migrate event streams among control channels to regulate the loads of these channels. Escala offers two components, including an Escala monitor that detects scaling situations based on realtime network statistics, and an optimization framework that makes scaling decisions to eliminate overload and underload situations. We have implemented a prototype of Escala on Tofino-based switches. Extensive experiments show that Escala achieves timely elastic scaling while preserving high application-level accuracy.

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

Packet delay is a consensual indicator of network conditions. High delay packets of a flow indicate that there may be network congestion or network anomalies. In this paper, we consider Intra-FlowPacketDelay (IFPD), which is defined as the time span between two adjacent packets of a flow. In particular, we aim to detect packets that exhibit high IFPD. The key challenge is to simultaneously achieve high detection accuracy and preserve low resource usage. Existing measurement approaches reduce resource overheads by injecting probe packets or sampling. However, they can only measure an average delay of some packets but fail to monitor delay behavior of every single packet. To this end, we propose a sketch-based approach. Unfortunately, existing sketch-based methods cannot be directly applied to our high IFPD detection problem. That is because traditional sketch algorithms require that the update operation is additive, while measuring IFPD needs to deal with timestamps, which is not additive. We address this issue in three aspects: (i) using fingerprints to mitigate hash conflicts; (ii) a conservative update method that only selects one bucket to update; (iii) a replacement strategy that keeps potential flows with high IFPD in the sketch. Our experiments on real world traces demonstrate that our solution identifies high IFPD with nearly 99% recall rate and 99% precision with 600 KB memory, which outperforms existing sketch-based solutions.

Existing blockchain systems suffer from low throughput and high payment latency. Payment channel networks (PCNs) such as the Lightning Network are proposed as a viable scaling solution. In PCNs, two participants can establish a payment channel to transfer funds without manipulating the blockchain. However, PCNs must route transactions between not directly connected participants on paths with sufficient funds. Since link capacities in PCNs vary as transactions are performed, it is hard to apply classical techniques to route PCN transactions directly. In this paper, we propose EPA-Route, a routing algorithm that aims to achieve both a high success rate and low transaction fees for PCNs. In addition, EPA-Route still maintains high performance and decentralization characteristics. In EPA-Route, every participant maintains a routing table. For every transaction, EPA-Route first probes possible paths based on the routing table and prunes useless paths at every hop to alleviate overheads. After a collection of paths obtained after probing and pruning, EPA-Route splits the transaction into several sub-transactions and allocates them to these paths. The allocation is formulated as an optimization problem to minimize transaction fees. Extensive experiments show that EPA-Route reduces up to 85 % transaction fees and maintains a comparable success rate as state-of-the-art algorithms.

In-band network telemetry (INT) enriches network management at scale through the embedding of complete device-internal states into each packet along its forwarding path, yet such embedding of INT information also incurs significant band-width overhead in the data plane. We propose DeltaINT, a general INT framework that achieves extremely low bandwidth overhead and supports various packet-level and flow-level applications in network management. DeltaINT builds on the insight that state changes are often negligible at most time, so it embeds a state into a packet only when the state change is deemed significant. We theoretically derive the time/space complexities and the bounds of bandwidth mitigation for DeltaINT. We implement DeltaINT in both software and P4. Our evaluation shows that DeltaINT reduces up to 93% of INT bandwidth, and its deployment in a Barefoot Tofino switch incurs limited hardware resource usage.

In programmable networks, measurement tasks are placed on programmable switches to keep pace with high-speed traffic. At runtime, programmable switches send events to the control plane for further processing. However, existing solutions for task placement overlook the limitations of control plane resources. Thus, excessive events may overload the control plane. In this paper, we propose MTP, a system that eliminates control plane overload via careful task placement. For each task, MTP analyzes its structure to estimate its maximum possible rate of sending events to the control plane. Then it builds an optimization framework that addresses the resource restrictions of both switches and the control plane. We have implemented MTP on Barefoot Tofino switches. The experimental results indicate that MTP outperforms existing solutions with higher accuracy across four real use cases.

In network function virtualization (NFV), network functions (NFs) are chained as a service function chain (SFC) to enhance NF management with high flexibility. Recent solutions indicate that the processing performance of SFCs can be significantly improved by offloading NFs to programmable switches. However, such offloading requires a deep understanding of NF properties to achieve the maximum SFC performance, which brings non-trivial burdens to network administrators. In this paper, we propose LightNF, a novel system that simplifies NF offloading in programmable networks. LightNF automatically dissects comprehensive NF properties (e.g., NF performance behaviors) via code analysis and performance profiling while eliminating manual efforts. It then leverages the analyzed NF properties in its SFC placement so as to produce the performance-optimal offloading. We have implemented a LightNF prototype. Our experiments show that LightNF outperforms state-of-the-art solutions with an orders-of-magnitude reduction in per-packet processing latency and 9.5× improvement in SFC throughput.

Machine learning for continuous data streams, or stream machine learning in short, is increasingly adopted in real-time big data applications. Fault tolerance is a critical requirement for stream machine learning applications in large-scale distributed deployment. However, existing reactive fault tolerance mechanisms, which trigger failure recovery upon the detection of failures, inevitably incur high recovery overhead and compromise the low-latency requirement of stream machine learning. We design StreamLEC, a stream machine learning system that leverages erasure coding to provide low-redundancy proactive fault tolerance for immediate failure recovery. StreamLEC supports general stream machine learning applications, and incorporates different techniques to mitigate erasure coding overhead. Evaluation on a local cluster and Amazon EC2 shows that StreamLEC achieves much higher throughput than both reactive fault tolerance and replication-based proactive fault tolerance, with negligible failure recovery overhead.

Computing per-key aggregation is indispensable in streaming data analysis formulated as two phases, an update phase and a recovery phase. As the size and speed of data streams rise, accurate per-key information is useful in many applications like anomaly detection, attack prevention, and online diagnosis. Even though many algorithms have been proposed for per-key aggregation in stream processing, their accuracy guarantees only cover a small portion of keys. In this paper, we aim to achieve nearly full accuracy with limited resource usage. We follow the line of sketch-based techniques. We observe that existing methods suffer from high errors for most keys. The reason is that they track keys by complicated mechanism in the update phase and simply calculate per-key aggregation from some specific counter in the recovery phase. Therefore, we present PR-Sketch, a novel sketching design to address the two limitations. PR-Sketch builds linear equations between counter values and per-key aggregations to improve accuracy, and records keys in the recovery phase to reduce resource usage in the update phase. We also provide an extension called fast PR-Sketch to improve processing rate further. We derive space complexity, time complexity, and guaranteed error probability for both PR-Sketch and fast PR-Sketch. We conduct trace-driven experiments under 100K keys and 1M items to compare our algorithms with multiple state-of-the-art methods. Results demonstrate the resource efficiency and nearly full accuracy of our algorithms.

We propose repair pipelining , a technique that speeds up the repair performance in general erasure-coded storage. By carefully scheduling the repair of failed data in small-size units across storage nodes in a pipelined manner, repair pipelining reduces the single-block repair time to approximately the same as the normal read time for a single block in homogeneous environments. We further design different extensions of repair pipelining algorithms for heterogeneous environments and multi-block repair operations. We implement a repair pipelining prototype, called ECPipe , and integrate it as a middleware system into two versions of Hadoop Distributed File System (HDFS) (namely, HDFS-RAID and HDFS-3) as well as Quantcast File System. Experiments on a local testbed and Amazon EC2 show that repair pipelining significantly improves the performance of degraded reads and full-node recovery over existing repair techniques.

Current stream processing systems (SPSs) suffer from the imbalanced load and limited parallelism due to skewed data distributions and imbalanced computational resources. We observed that the cause of these problems is current SPSs partition their workloads statically. To address this problem, we design a distributed stream processing system, Marabunta, for skewed stream processing. Marabunta performs dynamic scaling and load balancing automatically at runtime. Large partitions in a skewed data distribution can be processed in parallel or migrated to idle machines to achieve load balancing. Moreover, Marabunta uses a new execution model to accelerate the execution by increases the parallelism and the computational resources utilization. We implemented Marabunta in C++ and optimized it for modern hardware. Our evaluations on typical streaming workloads show that Marabunta achieves higher throughputs and better elasticity with both uniform and skewed datasets compared to the state-of-the-art SPSs, e.g., Flink and Heron.

Programmable switches empower network applications with line-rate packet processing performance by allowing the offloading of applications. However, the resource of a programmable switch is extremely limited, which significantly limits the application offloading. Existing solutions to the problem either provide poor efficiency or suffer from accuracy drop. In this paper, we propose SRA, a system that loosens switch resource constraints for application offloading via resource aggregation. SRA provides administrators with an intuitive compiler directive to customize application offloading by resource aggregation. According to compiler directives, it automatically places the program on the substrate network, while maintaining original packet processing logics. We implement a prototype of SRA in P4, and establish an experimental testbed consisting of three 32$\times$100 Gbps Barefoot switches. The experimental results indicate that SRA enhances two real-world applications with sufficient resources while maintaining high performance.

Smart Network Interface Cards (SmartNICs) have been widely used to accelerate software-based network functions (NFs). However, from the scope of a service chain, a careless selection of NFs to offload onto SmartNIC could severely degrade the performance due to frequent communications between CPU and SmartNIC. In this paper, we present SmartChain, a high performance and efficient framework that achieves optimal partition of service chains between SmartNIC and CPU. SmartChain consists of two logical steps. First, SmartChain analyzes the suitability of elements in a chain to run on SmartNIC to exploit its high performance. Besides, SmartChain also ensures the dependencies between elements. Second, as our key novelty, SmartChain models the service chain latency and resource constraints, and solves the partition problem with 0-1 integer linear programming. We implement a SmartChain prototype based on Netronome SmartNIC. Evaluation results show that when used in real world cases, SmartChain could reduce the service chain latency by up to 87% with throughput maintained compared with strawman solutions.

As network bandwidth has rapidly developed, due to the high occupancy of memory and bandwidth required, the Sketch structure is favored by some researchers due to its limited memory usage and simple operation. But the accuracy will decrease when the Sketch system occupies less memory space. Traditional sketch algorithms and some other specially designed algorithms and structures are striving to improve accuracy. However, with the flow rate rapidly increasing, the on-chip memory will be the bottleneck of the system. Our network measurement system achieve good results focusing more on the memory usage. We proposes a hybrid method, HybridSketch, which focuses on the memory and precision of the system with mixing two measurement methods by quantitatively analyzing, modeling and allocating appropriate memory space to each method to achieve better results. Experimental results show that our method can provide 10× improvement in terms of precision, moreover, HybridSketch can provide the same level of precision with achieving 24× improvement in terms of memory size.

We design a third-party DNS service named T2DNS. T2DNS serves client DNS queries with the following features: protecting clients from channel and server attackers, providing trustworthiness proof to clients, being compatible with the existing Internet infrastructure, and introducing bounded overhead. T2DNS’s privacy preservation is achieved by a hybrid protocol of encryption and obfuscation, and its service proxy is implemented on Intel SGX. We overcome the challenges of scaling the initialization process, bounding the obfuscation overhead, and tuning practical system parameters. We prototype T2DNS, and experiment results show that T2DNS is fully functional, has acceptable overhead in comparison with other solutions, and is scalable to the number of clients.

Programmable switches empower stateful packet processing, in which incoming packets continuously update states in the data plane, while applications in the control plane read and write states. However, as the data plane and control plane are separated, a consistent view of states in both planes is required for stateful packet processing. Existing approaches suffer from either high latency or low accuracy. In this paper, we propose ApproSync, a framework that offers approximate state synchronization with low latency and high accuracy. To achieve low latency, ApproSync directly transfers states between switch ASICs and the control plane by bypassing switch operating systems. To achieve high accuracy, ApproSync utilizes the resources in the switch ASIC to realize rate control in state synchronization, such that it avoids potential state loss. It also bounds the divergence between the states in the data plane and that in the control plane under limited link capacity. We prototype ApproSync on Barefoot Tofino switches. The experimental results indicate that compared to existing approaches, ApproSync achieves order-of-magnitude latency reduction while maintaining high accuracy.

Programmable switches allow network administrators to customize packet processing behaviors in data plane programs. However, existing solutions for program deployment fail to achieve resource efficiency and high packet processing performance. In this paper, we propose SPEED, a system that provides resource-efficient and high-performance deployment for data plane programs. For resource efficiency, SPEED merges input data plane programs by reducing program redundancy. Then it abstracts the substrate network into an one big switch (OBS), and deploys the merged program on the OBS while minimizing resource usage. For high performance, SPEED searches for the performance-optimal mapping between the OBS and the substrate network with respect to network-wide constraints. It also maintains program logics among different switches via inter-device packet scheduling. We have implemented SPEED on a Barefoot Tofino switch. The evaluation indicates that SPEED achieves resource-efficient and high-performance deployment for real data plane programs.

Advanced network management systems, including network measurement and traffic control, rely on a remote controller to make control decisions. However, this approach incurs a long control loop of a few seconds to minutes. Even if we switch to switch-local controller, the latency is still tens of milliseconds and is unacceptable for many latency-sensitive tasks. In this paper, we propose Martini, a general framework that supports measurement-based timely control. The key idea is to perform measurement, control decision, and control entirely in the switch data plane. This could shorten the control loop of management tasks that require timely control based on only locally measured statistics in the switch. First, Martini introduces a set of primitives to describe management tasks. Next, Martini provides an innovative network-wide task placement mechanism to exploit resources of all switches to accommodate massive management tasks. Finally, Martini provides a code library and a compiler to support measurement and control on a state-of-the-art switching ASIC. Evaluation results show that Martini can effectively support a wide range of fine-timescale management tasks such as microburst detection and fast load balancing by reducing the control loop from seconds to nanoseconds.

Superspreaders (i.e., hosts with numerous distinct connections) remain severe threats to production networks. How to accurately detect superspreaders in real-time at scale remains a non-trivial yet challenging issue. We present SpreadSketch, an invertible sketch data structure for network-wide superspreader detection with the theoretical guarantees on memory space, performance, and accuracy. SpreadSketch tracks candidate super-spreaders and embeds estimated fan-outs in binary hash strings inside small and static memory space, such that multiple SpreadSketch instances can be merged to provide a network-wide measurement view for recovering superspreaders and their estimated fan-outs. We present formal theoretical analysis on SpreadSketch in terms of space and time complexities as well as error bounds. Trace-driven evaluation shows that SpreadSketch achieves higher accuracy and performance over state-of-the-art sketches. Furthermore, we prototype SpreadSketch in P4 and show its feasible deployment in commodity hardware switches.

Network telemetry is essential for administrators to monitor massive data traffic in a network-wide manner. Existing telemetry solutions often face the dilemma between resource efficiency (i.e., low CPU, memory, and bandwidth overhead) and full accuracy (i.e., error-free and holistic measurement). We break this dilemma via a network-wide architectural design OmniMon, which simultaneously achieves resource efficiency and full accuracy in flow-level telemetry for large-scale data centers. OmniMon carefully coordinates the collaboration among different types of entities in the whole network to execute telemetry operations, such that the resource constraints of each entity are satisfied without compromising full accuracy. It further addresses consistency in network-wide epoch synchronization and accountability in error-free packet loss inference. We prototype OmniMon in DPDK and P4. Testbed experiments on commodity servers and Tofino switches demonstrate the effectiveness of OmniMon over state-of-the-art telemetry designs.

Fast detection of heavy flows (e.g., heavy hitters and heavy changers) in massive network traffic is challenging due to the stringent requirements of fast packet processing and limited resource availability. Invertible sketches are summary data structures that can recover heavy flows with small memory footprints and bounded errors, yet existing invertible sketches incur high memory access overhead that leads to performance degradation. We present MV-Sketch, a fast and compact invertible sketch that supports heavy flow detection with small and static memory allocation. MV-Sketch tracks candidate heavy flows inside the sketch data structure via the idea of majority voting, such that it incurs small memory access overhead in both update and query operations, while achieving high detection accuracy. We present theoretical analysis on the memory usage, performance, and accuracy of MV-Sketch in both local and network-wide scenarios. We further show how MV-Sketch can be implemented and deployed on P4-based programmable switches subject to hardware deployment constraints. We conduct evaluation in both software and hardware environments. Trace-driven evaluation in software shows that MV-Sketch achieves higher accuracy than existing invertible sketches, with up to 3.38× throughput gain. We also show how to boost the performance of MV-Sketch with SIMD instructions. Furthermore, we evaluate MV-Sketch on a Barefoot Tofino switch and show how MV-Sketch achieves line-rate measurement with limited hardware resource overhead.

Fast detection of heavy flows (e.g., heavy hitters and heavy changers) in massive network traffic is challenging due to the stringent requirements of fast packet processing and limited resource availability. Invertible sketches are summary data structures that can recover heavy flows with small memory footprints and bounded errors, yet existing invertible sketches incur high memory access overhead that leads to performance degradation. We present MV-Sketch, a fast and compact invertible sketch that supports heavy flow detection with small and static memory allocation. MV-Sketch tracks candidate heavy flows inside the sketch data structure via the idea of majority voting, such that it incurs small memory access overhead in both update and query operations, while achieving high detection accuracy. We present theoretical analysis on the memory usage, performance, and accuracy of MV-Sketch. Trace-driven evaluation shows that MVSketch achieves higher accuracy than existing invertible sketches, with up to 3.38× throughput gain. We also show how to boost the performance of MV-Sketch with SIMD instructions.

Like traditional IP networking, the emerging Software-Defined Networking (SDN) technology is vulnerable to sophisticated attacks against packets and their forwarding behaviors. However, existing proposals of packet forwarding verification for IP networking cannot be directly applied to the current SDN deployment due to the limited functionalities and resources in commercial off-the-shelf (COTS) SDN switches. We propose DYNAPFV, a dynamic packet forwarding verification mechanism that is capable of detecting various sophisticated attacks against packet forwarding. DYNAPFV leverages the controllability of SDN to examine both packets and flow statistics across a network of switches to detect violation of packet integrity and forwarding behaviors. To mitigate the verification overhead, DYNAPFV dynamically adjusts the rates of packet sampling and flow statistics collection based on the prior detection results in order to preserve the verification accuracy. Furthermore, DYNAPFV makes changes to the SDN controller only, and is directly deployable atop COTS SDN switches without modifications. We conduct theoretical analysis on the trade-off between performance and accuracy in our dynamic verification approach. We further prototype DYNAPFV using the open-source Floodlight controller, and evaluate our DYNAPFV prototype using Mininet simulations and hardware testbed experiments. DYNAPFV achieves over 97 percent of verification accuracy only with less than 5 percent of throughput degradation and less than 10 percent of additional forwarding delays.

When network is undergoing problems such as congestion, scan attack, DDoS attack, etc, measurements are much more important than usual. In this case, traffic characteristics including available bandwidth, packet rate, and flow size distribution vary drastically, significantly degrading the performance of measurements. To address this issue, we propose the Elastic sketch. It is adaptive to currently traffic characteristics. Besides, it is generic to measurement tasks and platforms. We implement the Elastic sketch on six platforms: P4, FPGA, GPU, CPU, multi-core CPU, and OVS, to process six typical measurement tasks. Experimental results and theoretical analysis show that the Elastic sketch can adapt well to traffic characteristics. Compared to the state-of-the-art, the Elastic sketch achieves 44.6 ~ 45.2 times faster speed and 2.0 ~ 273.7 smaller error rate.

When network is undergoing problems such as congestion, scan attack, DDoS attack, etc., measurements are much more important than usual. In this case, traffic characteristics including available bandwidth, packet rate, and flow size distribution vary drastically, significantly degrading the performance of measurements. To address this issue, we propose the Elastic sketch. It is adaptive to currently traffic characteristics. Besides, it is generic to measurement tasks and platforms. We implement the Elastic sketch on six platforms: P4, FPGA, GPU, CPU, multi-core CPU, and OVS, to process six typical measurement tasks. Experimental results and theoretical analysis show that the Elastic sketch can adapt well to traffic characteristics. Compared to the state-of-the-art, the Elastic sketch achieves 44.6 ∼ 45.2 times faster speed and 2.0 ∼ 273.7 smaller error rate.

Network measurement is challenged to fulfill stringent resource requirements in the face of massive network traffic. While approximate measurement can trade accuracy for resource savings, it demands intensive manual efforts to configure the right resource-accuracy trade-offs in real deployment. Such user burdens are caused by how existing approximate measurement approaches inherently deal with resource conflicts when tracking massive network traffic with limited resources. In particular, they tightly couple resource configurations with accuracy parameters, so as to provision sufficient resources to bound the measurement errors. We design SketchLearn, a novel sketch-based measurement framework that resolves resource conflicts by learning their statistical properties to eliminate conflicting traffic components. We prototype SketchLearn on OpenVSwitch and P4, and our testbed experiments and stress-test simulation show that SketchLearn accurately and automatically monitors various traffic statistics and effectively supports network-wide measurement with limited resources.

Network measurement remains a missing piece in today's software packet processing platforms. Sketches provide a promising building block for filling this void by monitoring every packet with fixed-size memory and bounded errors. However, our analysis shows that existing sketch-based measurement solutions suffer from severe performance drops under high traffic load. Although sketches are efficiently designed, applying them in network measurement inevitably incurs heavy computational overhead.

Fault tolerance is critical for distributed stream processing systems, yet achieving error-free fault tolerance often incurs substantial performance overhead. We present AF-Stream , a distributed stream processing system that addresses the trade-off between performance and accuracy in fault tolerance. AF-Stream builds on a notion called approximate fault tolerance , whose idea is to mitigate backup overhead by adaptively issuing backups, while ensuring that the errors upon failures are bounded with theoretical guarantees. Our AF-Stream design provides an extensible programming model for incorporating general streaming algorithms, and also exports only few threshold parameters for configuring approximation fault tolerance. Experiments on Amazon EC2 show that AF-Stream maintains high performance (compared to no fault tolerance) and high accuracy after multiple failures (compared to no failures) under various streaming algorithms.

WeChat is one of the most popular mobile messaging applications worldwide. However, due to the proprietary nature of WeChat, its characteristics and performance impact on cellular networks remain largely unexplored. This paper presents the first measurement study that dissects real-world WeChat traffic in a cellular network. We build ChatDissect, a protocol inference tool that infers the unique protocol formats and semantics of WeChat in a fine-grained manner. ChatDissect enables us to distinguish WeChat and its specific tasks from general network traffic traces. As a case study, we collect a real-world dataset from a commercial 3G cellular network in China and use ChatDissect to identify around 150K WeChat users with 16GB of WeChat payloads. We unveil the signatures, server architecture, and workflows of WeChat, and further analyze the activities of the extracted WeChat traffic.

Given the increasing volume and complexity of network traffic nowadays, network operators often leverage application-layer protocols to differentiate network traffic, so as to improve quality-of-service control, security protection, and resource profiling. We present ProGraph, a tool that accurately infers protocol message formats at both byte-level and bit-level granularities. Unlike existing approaches that mainly exploit statistical features across packets, ProGraph exploits intra-packet dependency among the values of different portions of a packet payload. It systematically constructs a graphical model that captures intra-packet dependency, using various techniques in graph theory and information theory. It also achieves several important design properties for real deployment, including fine-grained inference, protocol independence, simple parameterization, robustness to noisy training sets, and fast execution. We show via trace-driven evaluations that ProGraph achieves more accurate inference than existing approaches. We further show how ProGraph can be used for classifying traffic.

Real-time characterization of traffic anomalies, such as heavy hitters and heavy changers, is critical for the robustness of operational networks, but its accuracy and scalability are challenged by the ever-increasing volume and diversity of network traffic. We address this problem by leveraging parallelization. We propose LD-Sketch, a data structure designed for accurate and scalable traffic anomaly detection using distributed architectures. LD-Sketch combines the classical counter-based and sketch-based techniques, and performs detection in two phases: local detection, which guarantees zero false negatives, and distributed detection, which reduces false positives by aggregating multiple detection results. We derive the error bounds and the space and time complexity for LD-Sketch. We compare LD-Sketch with state-of-the-art sketch-based techniques by conducting experiments on traffic traces from a real-life 3G cellular data network. Our results demonstrate the accuracy and scalability of LD-Sketch over prior approaches.