Towards Guaranteed Accuracy for Flow Spread Measurement with $(\epsilon, \beta)$-Nonduplicate Sampling

Per-flow spread measurement in high-speed networks is important to many practical applications. To fit in the limited on-chip memory, sketch-based solutions allow multiple flows to share space, causing inter-flow noise and thus sacrificing in accuracy. Recent progress on non-duplicate sampling creates a new direction of sampling-based solutions for spread estimation, which performs better than memory-sharing sketches. However, the current sampling-based solutions either use a system-wide sampling probability or lack the flexibility of setting the sampling probability dynamically and at per-flow level. This paper advances the theory and design of non-duplicate sampling by introducing a new$(\epsilon, \beta)$-RE accuracy model for spread estimation and a new$(\epsilon, \beta)$-nonduplicate sampling type, establishing their equivalency, proposing the idea of individualized per-flow sampling, and designing a novel algorithm based on this idea to implement$(\epsilon, \beta)$-nonduplicate sampling and thus achieving$(\epsilon, \beta)$-RE accuracy. Trace-driven experiments demonstrate that our new solution outperforms the best state of the art significantly in terms of maximum supported packet stream size under a given accuracy requirement or in terms of accuracy with the same packet stream size, and outperforms sketch-based solutions to spread estimation significantly in accuracy.