Ruwen Zhang, Bo Liu, Zhang Sheng Xiang, Yida Chen, Hantao Zhao, Ding Ding, Jiahui Jin, Jiuxin Cao. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Logging network traffic plays a crucial role as it serves as the foundation for various network applications. As network scale continues to expand, contemporary network traffic becomes increasingly high-speed, high-volume, and dynamic. This growth poses challenges to traditional server-based solutions. In this paper, we proposeTitanLog, ahierarchicalandelasticlogging system designed specifically for large-scale network traffic. TitanLog utilizes thehierarchical loggingmethodology, which aims to identify the importance of each packet in real-time and log packet data of different importance at different levels. To enhance efficiency, we propose a co-design of the emerging programmable switch and the server, incorporating sketches and RDMA to boost performance. To achieve elasticity, we design mechanisms for run-time adjustments and monitoring for resource insufficiency. TitanLog possesses the capability to switch between these modes at run-time. We fully implement TitanLog on a testbed and conduct extensive evaluations. The experimental results demonstrate that TitanLog supports logging of 100Gbps traffic with a zero packet loss rate and reduces the log volume by up to 96.28%.

Frequent object mining has gained considerable interest in the research community and can be split into frequent item mining and frequent set mining depending on the type of object. While existing sketch-based algorithms have made significant progress in addressing these two tasks concurrently, they also possess notable limitations. They either support only software platforms with low throughput or compromise accuracy for faster processing speed and better hardware compatibility. In this paper, we make a substantial stride towards supporting frequent object mining by designing SandwichSketch, which draws inspiration from sandwich making and proposes two techniques including the double fidelity enhancement and hierarchical hot locking to guarantee high fidelity on both two tasks. We implement SandwichSketch on three platforms (CPU, Redis, and FPGA) and show that it enhances accuracy by$38.4\times$and$5\times$for two tasks on three real-world datasets, respectively. Additionally, it supports a distributed measurement scenario with less than a 0.01% decrease in Average Relative Error (ARE) when the number of nodes increases from 1 to 16.

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

A Sketch is an excellent probabilistic data structure, which records the approximate statistics of data streams. Linear additivity is an important property of sketches. This paper studies how to keep the linear property after sketch compression. Most existing compression methods do not keep the linear property. We propose TreeSensing, an accurate, efficient, and flexible framework to linearly compress sketches. In TreeSensing, we first separate a sketch into two parts according to counter values. For the sketch with small counters, we propose a technique called TreeEncoding to compress it into a hierarchical structure. For the sketch with large counters, we propose a technique called SketchSensing to compress it using compressive sensing. We theoretically analyze the accuracy of TreeSensing. We use TreeSensing to compress 7 sketches and conduct two end-to-end experiments: distributed measurement and distributed machine learning. Experimental results show that TreeSensing outperforms prior art on both accuracy and efficiency, which achieves up to 100× smaller error and 5.1× higher speed than state-of-the-art Cluster-Reduce. All related codes are open-sourced.

In this paper, we propose a generic sketch algorithm capable of achieving more accuracy in the following five tasks: finding top-$k$frequent items, finding heavy hitters, per-item frequency estimation, and heavy changes in the time and spatial dimension. The state-of-the-art (SOTA) sketch solution for multiple measurement tasks is ElasticSketch (ES). However, the accuracy of its frequency estimation has room for improvement. The reason for this is that ES suffers from overestimation errors in the light part, which introduces errors when querying both frequent and infrequent items. To address these problems, we propose a generic sketch, OneSketch, designed to minimize overestimation errors. To achieve the design goal, we propose four key techniques, which embrace hash collisions and minimize possible errors by handling highly recurrent item replacements well. Experimental results show that OneSketch clearly outperforms 12 SOTA schemes. For example, compared with ES, OneSketch achieves more than 10× lower Average Absolute Error on finding top-$k$frequent items and heavy hitters, as well as 48.3% and 38.4% higher F1 Scores on two heavy changes under 200 KB memory, respectively.

Sketch-based measurement has emerged as a promising solutions due to its high accuracy and resource efficiency. Prior sketches focus on measuring single flow keys and cannot support measurement on multiple keys. This work takes a significant step towards supporting arbitrary partial key queries, which aims to provide information for any key in the predefined range of possible flow keys. The designed system, CocoSketch, casts arbitrary partial key queries to the subset sum estimation problem and makes the theoretical tools for subset sum estimation practical. CocoSketch utilizes two techniques: (1) stochastic variance minimization to significantly reduce per-packet update delay, and (2) removing circular dependencies in the per-packet update logic to make the implementation hardware-friendly. This paper extends the conference version by discussing how CocoSketch adapts to new measurement requirements, including: (1) collecting the exact information of specified flow keys, and (2) distributed measurement. CocoSketch is implemented on five popular platforms (CPU, Open vSwitch, Redis, P4, and FPGA). Experiment results show that compared to baselines that use traditional single-key sketches, CocoSketch improves average packet processing throughput by$27.2\times $and accuracy by$10.4\times $when measuring six flow keys.

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

Sketch-based measurement has emerged as a promising alternative to the traditional sampling-based network measurement approaches due to its high accuracy and resource efficiency. While there have been various designs around sketches, they focus on measuring one particular flow key, and it is infeasible to support many keys based on these sketches. In this work, we take a significant step towards supporting arbitrary partial key queries, where we only need to specify a full range of possible flow keys that are of interest before measurement starts, and in query time, we can extract the information of any key in that range. We design CocoSketch, which casts arbitrary partial key queries to the subset sum estimation problem and makes the theoretical tools for subset sum estimation practical. To realize desirable resource-accuracy tradeoffs in software and hardware platforms, we propose two techniques: (1) stochastic variance minimization to significantly reduce per-packet update delay, and (2) removing circular dependencies in the per-packet update logic to make the implementation hardware-friendly. We implement CocoSketch on four popular platforms (CPU, Open vSwitch, P4, and FPGA) and show that compared to baselines that use traditional single-key sketches, CocoSketch improves average packet processing throughput by 27.2x and accuracy by 10.4x when measuring six flow keys.