Efficient Lightweight Coordinated Sampling for Dynamic Flows: Theory and Implementation

As cyber-attacks on networks become stealthier, monitoring techniques relying on low-rate packet sampling may prove insufficient to detect attacks. While various methods, such as truncating packets, flow-based sampling, and adaptive sampling rates, have been proposed to enhance detection rates and ease capability limitations, it remains challenging to perform sufficient sampling at line speed and high rates at a single sampling point due to limited CPU or bandwidth capacity and fluctuating network traffic. To address these challenges, we propose CoordSamp, a system that distributes the sampling workload across multiple sampling points and coordinates their actions to avoid duplicate sampling of the same packet. This design enables scalable, resource-aware monitoring - particularly suited for dynamic, agentless cloud-based environments - relying solely on network-level deployment that can be dynamically assigned and adjusted by the provider. We develop a coordinated sampling algorithm on multiple P4-programmable switches and show that the algorithm ensures coordination among multiple sampling points for each flow, preventing duplicate samples, with negligible network overhead and real-time configurability. At its core, CoordSamp separates offline placement - the budgeted selection of sampling points - from online allocation - the capacity-aware assignment of sampling tasks - allowing practical deployment in hybrid networks that combine programmable and legacy switches. We formulate sampling point placement as budgeted maximum multi-coverage problems, solving them optimally in pseudo-polynomial time. Our system far outperforms those based on greedy placement along many key dimensions.