Priority-Aware Sampling for Differential Flow Spread Measurement in High-Speed Networks

Given switch's limited on-chip memory, many sketches have been proposed for efficient spread estimation over high-speed network streams. Nevertheless, existing methods ignore the truth that different types of flows exhibit varying error tolerance to measurement, thus necessitating administrators to prioritize ensuring the estimation accuracy for error-sensitive flows. In this paper, we investigate a new problem called <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Differential Flow Spread Measurement</i> and propose priority-aware sampling (PAS), a novel hybrid method to catch up with the line-rate of switches while estimating different types of flows with different accuracy requirements. In on-chip memory, we elaborately design a priority-aware filter that removes duplicate elements and memorizes as many high-priority elements as possible. This design enables reallocating on-chip resources from low-priority elements to higher-priority elements, thereby improving estimation accuracy for high-priority flows. Meanwhile, we deploy a one-access hash table to efficiently record distinct elements and provide unbiased spread estimation in real-time. Additionally, we demonstrate that our proposal is flexible and configurable for a variety of performance guarantees. We implement PAS in hardware using NetFPGA. The experimental results based on real Internet traces show that PAS reduces estimation errors for high-priority flows by 95.58%, 93.35%, 98.72%, and 31.83% compared to the vHLL, rSkt, SKJ and state-of-the-art (NDS), respectively, under uniform prioritization.