MSFramework: Multi-stage similarity-based key flow identification in high-speed networks

Identifying key flows that closely match a target behavior signature is crucial for high-speed network tasks such as fine-grained service classification, targeted anomaly detection, and priority traffic engineering. Machine-learning-based approaches require multi-packet observation and non-trivial computation, making line-rate deployment challenging under strict memory budgets and high-throughput requirements. Similarity-based methods provide a lightweight, label-free alternative by comparing behavioral summaries directly, yet existing designs rely on per-flow state, leading to memory scaling linearly with concurrent flows and poor scalability in backbone routers or ISP environments handling millions of flows. We propose MSFramework, a multi-stage, memory-efficient architecture for scalable similarity-based key flow identification-addressing key challenges in preserving similarity-relevant structures, capturing multiplicity-aware similarity, and reconciling low-latency with memory overheads. It uses a progressive pipeline: a lightweight FastFilter discards dissimilar flows via coarse-grained behavioral sketches, followed by a high-precision AccurateFilter that performs fine-grained sketch-based similarity estimation only on a small candidate set. Both stages leverage a shared-state sketch with adaptive replacement to track massive flows without per-flow counters, supplemented by periodic low-rate off-chip updates to maintain a compact data-plane footprint. Evaluations on real-world backbone and enterprise traces show MSFramework achieves near-perfect precision and F1-scores, outperforming baselines by up to 40% in F1-score under the same tight memory constraints, while sustaining throughput suitable for high-speed network monitoring.