Network measurement sketches enable efficient traffic monitoring but require careful parameter configuration to balance accuracy and memory efficiency. We presentRA-Sketch, a unified framework for generating memory-optimal sketch configurations that satisfy user-defined error constraints across diverse network measurement tasks. Unlike existing approaches that rely on computationally intensive experimental testing, RA-Sketch introduces: 1)Poisson-distributed collision modelingto construct error predictors for both frequency-independent tasks (membership query, heavy-hitter detection, and super-spreader detection) and frequency-dependent tasks (flow size distribution, frequency estimation, and cardinality estimation), eliminating the need for empirical validation; 2) Ahierarchical search strategycombining power-of-two scaling and binary search, reducing iterations through optimized parameter initialization. RA-Sketch supports 10+ sketch architectures including Bloom Filter, Elastic Sketch, HeavyKeeper, MEC Sketch, MRAC, CM Sketch, CO Sketch, gSkt, rSkt1 among others. Evaluations on real-world network traces demonstrate: 1) up to 6–7 orders-of-magnitude faster configuration than benchmark-based methods; 2) Prediction errors are within 10% for heavy-hitter detection and super-spreader detection in most evaluated settings, while prediction errors for membership query, flow size distribution, frequency estimation, and cardinality estimation are close to zero; 3) Memory utilization approaches theoretical minima. The framework’sgenerality and efficiency enable real-time reconfiguration of sketches under dynamic network conditions.

Network measurement sketches enable efficient traffic monitoring but require careful parameter configuration to balance accuracy and memory efficiency. We present RA-Sketch, a framework for generating memory-optimal sketch configurations that satisfy user-defined error constraints across diverse network measurement tasks. Unlike existing approaches that rely on computationally intensive experimental testing, RA-Sketch introduces: 1) Poisson-distributed collision modeling to construct error predictors for both frequency-independent tasks (membership query, heavy-hitter detection) and frequency-dependent tasks (frequency/cardinality estimation), eliminating the need for empirical validation; 2) A hierarchical search strategy combining power-of-two scaling and binary search, reducing iterations through optimized parameter initialization. RA-Sketch supports 10+ sketch architectures including Bloom Filter, Elastic Sketch, HeavyGuardian, HeavyKeeper, CM/CO Sketch, gSkt, rSkt1 and so on. Evaluations on real-world network traces demonstrate: 1) 6–7 orders of magnitude faster configuration than benchmark-based methods; 2) Prediction errors ≤10% for heavy-hitter detection, while prediction errors for membership query, and frequency/cardinality estimation are close to zero; 3) Memory utilization approaches theoretical minima. The framework’s generality and efficiency enable real-time reconfiguration of sketches under dynamic network conditions.

Per-Flow cardinality measurement in high-speed networks is essential for network security and traffic analysis applications. Flow cardinality refers to the number of distinct elements within a flow, such as the number of unique destination IPs associated with a given source IP. While extensive research has been conducted on single-flow cardinality estimation, achieving accurate per-flow cardinality measurement with real-time performance and low memory overhead remains challenging in large-scale network environments, particularly given the highly skewed distribution of flow cardinalities where mouse flows with smaller cardinalities dominate, and elephant flows with larger cardinalities are fewer. This paper introduces MEC-Sketch, a memory-efficient cardinality estimation data structure that leverages the inherently skewed distribution of flow cardinalities in network traffic. MEC-Sketch employs a dual-component architecture: a heavy part utilizing a majority vote algorithm for precise super-spreader detection, and a light part implementing compact cardinality estimators for memory-efficient measurement of mouse flows. We address two fundamental technical challenges: (1) adapting the majority vote algorithms to operate with cardinality estimators that lack native support for real-time queries, and (2) implementing an effective mapping strategy between large estimators in the heavy part and small estimators in the light part during elephant-mouse flow separation. Comprehensive evaluations on real-world network traces demonstrate that MEC-Sketch significantly outperforms state-of-the-art solutions in terms of estimation accuracy, memory efficiency, and computational performance for both cardinality estimation and super-spreader detection tasks.

In-band Network Telemetry(INT) enables fine-grained telemetry by editing the packet header with the capability of programmable data plane to carry network status. However, INT could cause significant telemetry overhead without an effective system design. Existing measurement systems attempt to reduce this overhead by employing fixed-frequency INT sampling. Nonetheless, these methods lead to frequent measurements of network ports with large flows while neglecting ports with small flows for extended periods. In this paper, we introduce a lightweight passive telemetry system based on INT, called INTSelection. The core idea is to use a flow selection algorithm at the centralized controller so as to measure all active ports. Compared with the current method, INT-Selection reduces the bandwidth overhead by 58.2% and 2.7%.

Network traffic measurement is critical for effective network management. Sketch has been proven to be a promising network traffic measurement solution. Considering the skewed distribution of network traffic, where low-frequency mouse flows dominate and high-frequency elephant flows are fewer, recent sketch-based solutions employ hierarchical designs to enhance memory efficiency and accuracy. However, these solutions inevitably introduce additional challenges, including increased memory access overhead, severe hash collisions between elephant and mouse flows, and limited adaptability to dynamic network environments. In this paper, we propose LA-Sketch, an adaptive level-aware data structure. First, LA-Sketch employs a level-aware classifier to intelligently map each flow to its corresponding level, thereby reducing memory access overhead caused by hierarchical designs and mitigating hash collisions between elephant and mouse flows. Second, we introduce an adaptive counter configuration method that dynamically adjusts the number of counters at each level according to diverse network traffic distributions, which theoretically minimizes overall hash collisions. Finally, to adapt to the continuously changing network traffic characteristics, we propose an adaptive online training method that enables LA-Sketch's classifier to maintain high performance using only sketch query values for training, avoiding the significant overhead of massive traffic data collection. Extensive evaluations on two real-world network traces across five measurement tasks demonstrate that LA-Sketch outperforms state-of-the-art hierarchical sketches.

Network measurement is critical for various network applications, but scaling measurement techniques to the network-wide level is challenging for existing sketch-based solutions. In software switches, centralized deployment provides low resource usage but suffers from poor load balancing. In contrast, collaborative measurement achieves load balancing through flow distribution across software switches but requires high resource usage. This paper presents a novel distributed deployment framework that overcomes the limitations above. First, our framework is lightweight such that it splits sketches into segments and allocates them across forwarding paths to minimize resource usage and achieve load balancing. This also enables per-packet load balancing by distributing computations across software switches. Second, through a novel collaborative strategy, our framework achieves finer-grained flow distribution and further optimizes load balancing. Third, we further optimize load balancing by eliminating the mutual influence among forwarding paths. We evaluate the proposed framework on various network topologies and different sketches. Results indicate our solution matches the load balancing of collaborative measurement while approaching the low resource usage of centralized deployment. Moreover, it achieves superior performance in per-packet load balancing, which is not considered in previous deployment solutions.

In modern data centers and enterprise networks, software switches have become critical components for achieving flexible and efficient network management. Due to resource constraints in software switches, sketches have emerged as a promising approach for network traffic measurement. However, their accuracy is often impacted by hash collisions. Existing hash functions treat all collisions equally, failing to account for the differing impacts of collisions involving elephant flows versus mouse flows. We propose FSA-Hash, a novel flow-size-aware hashing scheme that separates elephant flows from each other and from mouse flows, minimizing the most detrimental collisions. FSA-Hash is designed based on two insights: separating elephant flows from mouse flows avoids overestimating mouse flows, while separating elephant flows from each other enables accurate heavy-hitter detection. We implement FSA-Hash using machine learning models trained on network traffic data (LFSA-Hash), and also design a lightweight online variant (OLFSA-Hash) that learns the hash model solely from sketch queries on the software switch, obviating traffic collection overheads. Evaluations across four sketches and two tasks demonstrate FSA-Hash’s superior accuracy over standard hash functions. Moreover, OLFSA-Hash closely matches LFSA-Hash’s performance, making it an attractive option for adaptively refining the hash model without monitoring traffic.

Network measurement is critical for various network applications, but scaling measurement techniques to the network-wide level is challenging for existing sketch-based solutions. Centralized sketch deployment provides low resource usage but suffers from poor load balancing. In contrast, collaborative measurement achieves load balancing through flow distribution across switches but requires high resource usage. This paper presents a novel lightweight distributed deployment framework that overcomes the limitations above. First, our framework is lightweight such that it splits sketches into segments and allocates them across forwarding paths to minimize resource usage and achieve load balancing. This also enables per-packet load balancing by distributing computations across switches. Second, our framework is also optimized for load balancing by coordinating between flows and enabling finer-grained flow distribution. We evaluate the proposed framework on various network topologies and different sketch deployments. Results indicate our solution matches the load balancing of collaborative measurement while approaching the low resource usage of centralized deployment. Moreover, it achieves superior performance in per-packet load balancing, which is not considered in previous deployment policies. Our work provides efficient distributed sketch deployment to strike a balance between load balancing and resource usage enabling effective network-wide measurement.

Network measurement plays a critical role in numerous network applications that rely on fundamental flow processing tasks such as frequency estimation, heavy hitter detection, and distribution estimation. Sketch has emerged as an efficient approach for network measurement due to its low overhead. However, most sketch-based solutions target static windows while enabling sliding window-based measurement remains an open challenge. This paper introduces two novel general frameworks applicable to diverse sketch models for sliding window-based network measurement: a traditional sliding window framework and a fine-grained flow-level framework. The traditional framework divides the window into parts and uses centralized flushing to remove expired parts. The flow-level framework tracks timestamps to maintain exact flow characteristics over one period, preventing truncation. To optimize memory usage, a bit-wise adaptive allocation algorithm allows dynamic borrowing of unused counter bits. The frameworks are evaluated on sketches for different flow processing tasks. Results show the frameworks are widely generalizable, reduce error substantially compared to existing approaches, and provide more efficient memory usage.