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.

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.

The ever-increasing quality of experience (QoE) demand for video streaming has prompted the integration of video super-resolution and multi-access edge computing networks (MEC). With super-resolution, the low-resolution frames can be reconstructed into high-resolution ones by edge node and end device collaboratively, which is beneficial in improving QoE. However, the existing works focus on designing video streaming strategies in single-user scenarios, which cannot be applied to multi-user scenarios due to the resource contention among users, as well as the huge solution space of coupled bitrate selection and workload share between edge-end. To fill this gap, we propose a collaborative video streaming strategy with super-resolution in multi-user MEC networks, named Co-Video, to maximize the average QoE by making optimal bitrate selection and workload share. We first formulate the problem as an optimization problem towards maximum average QoE, where the QoE incorporates playback delay, video quality, and smoothness. Then, we transform the optimization problem into a partially observable Markov decision process (POMDP) and exploit the Co-Video strategy based on the multi-agent soft actor-critic (MASAC) algorithm. Specifically, Co-Video utilizes the branching actor network to converge to good policy stably. Finally, trace-driven simulations on real-world bandwidth traces demonstrate that Co-Video outperforms the state-of-the-art baselines.

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

In mobile video streaming, the ever-increasing user expectations for Quality of Experience (QoE) have prompted the integration of video super-resolution and adaptive bitrate techniques on either the mobile device or the edge server. By reconstructing high-resolution frames from low-resolution frames that have been downloaded, both high video quality and a short rebuffer time can be enjoyed. However, the exiting methods merely leverage the computing resources of the edge server or mobile device, leaving significant room for further QoE improvement. In this paper, we present an adaptive Video Streaming system with Edge-Client collaborative Super-resolution, named VSECS, to enhance users' QoE by simultaneously utilizing the computing resources of both the edge server and mobile device to reconstruct high-resolution frames collaboratively. First, we deploy a large-scale super-resolution model on the edge server and a lightweight model on the mobile device. Then, we exploit the Asynchronous Advantage Actor-Critic (A3C) algorithm to make decisions regarding the download resolution, the reconstructed target resolution, and the workload share of the mobile device, considering the network bandwidth, computing resources, and reconstruction complexity of video tiles. Furthermore, we utilize the branching actor network to enable the agent to converge to good policy stably. Trace-driven simulations on real-world bandwidth traces demonstrate that our approach can improve QoE by up to 10% compared to the state-of-the-art video streaming solutions.

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.

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

Sketch is a compact data structure for network measurements. To achieve fast speed, it needs to be held in the on-chip memory (SRAM), which is very small. To enable the sketch fit into the on-chip memory, the product of counter size and number of counters must be below a certain limit. If we use small counters, e.g., 8 bits, some counters will overflow. If we use large counters, e.g., 16 bits per counter, the total number of counters will be small, each counter will be shared by more flows, leading to poor accuracy. To address this issue, we propose a generic technique: self-adaptive counters (SA Counter). When the value of the counter is small, it works as a normal counter. When the value of the counter is large, we increment it using a predefined probability, so as to represent a large value. Moreover, in SA Counter, the probability decreases when the value increases. This technique can significantly improve the accuracy of sketches. To verify the effectiveness of SA Counter, we apply SA Counter to three typical sketches, and conduct extensive experiments on one real dataset and one synthetic dataset. Experimental results show that, compared with the state-of-the-art, sketches using SA Counter improve the accuracy by up to 13.6 times.