APS: Adaptive Priority-Aware Sketch with Low Overhead for Heterogeneous Traffic

With the emergence of software-defined networking, sketch-based network measurements have been widely used to balance the tradeoff between efficiency and reliability. Recently, a class of priority-aware sketches has been developed to provide differentiated measurement accuracy for flows with different priorities. However, as the number of priorities increases, the overhead of these priority-aware sketches also increases, resulting in poor performance in scenarios with a high number of priorities. In this paper, we propose an adaptive priority sketch called Adaptive Priority-aware Sketch (APS) with low overhead, which utilizes priority-aware hashing to dynamically allocate a sufficient number of hash functions based on the priority of different flows. Experimental results show that APS improves throughput by up to 110% under the scenarios with large number of high-priority flows, while maintaining similar overall measurement accuracy under medium and low priority flow scenarios.