Lightweight Coordinated Sampling for Dynamic Flows under Budget Constraints

As cyber-attacks on networks become more stealthy, monitoring techniques relying on low-rate packet sampling may prove insufficient to detect attacks. While various sampling methods have been proposed to address capacity limitations and enhance detection rates, achieving sampling at line speed at a single point remains challenging due to limited CPU or bandwidth capacity at sampling points. In this paper, we propose harnessing coordinating sampling across switches to create a unified system that can dynamically activate sampling points to meet sampling rate needs. We introduce and implement 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. We formulate sampling point placement as budgeted maximum multi-coverage problems, solving them optimally in pseudo-polynomial time. We show our system far outperforms those based on greedy algorithms along many key dimensions.