Network traffic measurement is indispensable for many network management tasks. Time-series traffic pattern detection extends the benefits of traditional single-period flow measurement by revealing dynamic flow behaviors, but also yields higher complexity. When multiple patterns must be monitored simultaneously, building a separate sketch for each pattern is prohibitive since programmable switches typically allow only one resource-intensive sketch. In this paper, we propose PatternSketch, which enables general and dynamically reconfigurable time-series pattern detection within a single sketch. PatternSketch unifies the detection of diverse patterns with a Pattern Automaton and decomposes the pattern detection process into two phases in the data plane, while allowing operators to reconfigure the active set of monitoring patterns at runtime without taking the switch offline. Our implementation on an Intel Tofino switch demonstrates that PatternSketch can operate at line rate, detecting multiple patterns concurrently while using only tens of kilobytes of SRAM. This significantly reduces both computational and storage resource consumption compared to deploying multiple, pattern-specific sketches. Evaluations on four real-world datasets show that the hardware version of PatternSketch maintains over 90% F1 scores while simultaneously detecting six time-series patterns (three representative and three newly proposed) with as little as 200KB of memory.

Traffic measurement provides indispensable information to many applications in improving network performance. However, the limited on-chip resources face great challenges in measuring millions of flows simultaneously with high accuracy, and the highly skewed traffic distribution further worsens the performance. Although filtering the vast majority of small flows in advance can help to improve the measurement performance, existing filters have limitations in either filtering range or processing overhead. This paper proposes two efficient filters, including Swing-Size Filter for small-size flow filtering and Swing-Spread Filter for small-spread flow filtering. Both provide a flexible and extended filtering range for network traffic measurement. One key to our design is the use of signed counters whose values swing in positive and negative directions to cancel out small-size or small-spread flows, thereby enlarging the filtering range. We show that the proposed filters are highly effective in filtering small flows while keeping the advantages of low memory overhead and processing overhead. They support various measurement tasks and offer guaranteed bounds on the misreport rate. We implement our filters in both software and hardware, with the hardware version developed in P4 language on a programmable switch. Experiments based on real-world Internet traces show that our filters can reduce the flow size and flow spread estimation errors by an order of magnitude and support high throughput.

Spread measurement is an essential problem in high-speed networks with broad applications, such as anomaly detection and network telemetry. Network administrators typically need to concurrently monitor the spreads of different types of flows to detect various abnormal behaviors. Although many studies have designed memory-efficient structures, such as sketches, for a specific spread measurement task, they have to deploy multiple sketches to support multiple spread measurement tasks, resulting in significant memory and computational overhead. This paper proposes an efficient multi-task information compression method to simultaneously estimate differently defined flow spreads. We introduce multi-information sampling to capture multi-task spread information from each arriving packet by one pass and store it in off-chip memory, thereby conserving on-chip memory and computational resources. Additionally, we carefully designed a one-access multi-dimensional structure called Supercube to preserve as much spread information as possible while catching up with the line rate, thereby enhancing estimation accuracy. We implement our estimator in hardware using NetFPGA. Experiments based on real Internet traces show that our method reduces the ARE by 83.36% for spread estimation compared to rSkt (SOTA) with 300KB of on-chip memory and increases update throughput by 251.252-fold compared to Supersketch. All source codes are available athttps://github.com/Hanwen808/MIME.

Heavy hitter detection is a fundamental network measurement task that provides critical support for many network applications. However, achieving flexible and fast heavy hitter detection in massive network traffic is challenging. Existing works generally perform detection by tracking large flows that may become heavy hitters, but they struggle to accurately identify these large flows, leading to poor accuracy. In this paper, we propose an efficient detection algorithm called HeavyCuckoo, which shows high flexibility and fast processing. We track only those large flows likely to be heavy hitters, replacing small flows of limited use for detection by exploring the activity of flow arrivals. During replacement, we utilize a tailored Conservative Replacement strategy and a tailored Selective Cuckoo Hash strategy to avoid large flows from being replaced incorrectly. We conduct theoretical analyses of memory space complexity and time complexity, and provide the error bound for heavy hitter detection. Our proposed algorithm is evaluated on real-world Internet traffic traces. Experimental results show that, compared to the prior art, the algorithm improves the Fβ-score by 56.94% and achieves 1.4724 times throughput.

Spread estimation is an essential issue in high-speed networks with wide applications, such as network billing, quality of service, anomaly detection, etc. As a promising technique, sketch can efficiently estimate per-flow spread with only a small memory cost. Many studies focus on improving the performance of sketches. However, these works primarily focus on optimizing the counter level or sketch level without considering the scenario of multi-spread estimation, which is crucial for improving memory utilization and detecting anomalies. In this paper, we propose an efficient flow information compression algorithm based on the on-chip/off-chip hybrid framework to estimate multiple flow spreads. In the on-chip memory, we filter out non-duplicates and sample them to the off-chip space for recording. In the off-chip memory, we compress each sampled non-duplicate to a carefully designed bit-cube. When the measurement is finished, we separate corresponding KV-flows from a specific flow based on the user query. Then, we rebuild this flow to a subset group based on the duplicate number of each KV-flow. Finally, according to the Multi-set theory, we derive an accurate multi-spread estimate formula to solve this issue with a high throughput and small on-chip memory usage. Furthermore, we evaluate the performance of our proposed estimator using real Internet traffic traces downloaded from CAIDA. Experiments show that, compared to the state-of-the-art, our proposal achieves a 97.2% lower average relative error in per-destination source flow spread estimation with a tight on-chip memory, e.g., 320KB. And our proposed method achieves 31.86 higher processing throughput.