Achieving Differentiated Flow Estimation With Priority-Adaptive Sketch

Sketch has gained wide deployment and application for approximate flow estimation, because of its ability to maintain good accuracy and high throughput with limited memory resources. However, most existing sketch approaches ignore the distinctions between flow priorities, though the high-priority flows are relatively scarce but hold significant information. Therefore, a class of priority-aware sketches has appeared recently to provide differentiated measurement accuracy for flows with different priorities. Unfortunately, it is challenging for these priority-aware sketches to strike a good balance between accuracy and throughput. To address this issue, we propose a priority-adaptive architecture PA-Sketch, which utilizes priority-aware hash to dynamically allocate appropriate numbers of hash functions for different flows according to their priorities. Moreover, to further achieve good accuracy in extremely small memory space, we introduce the priority-aware sampling into PA-Sketch. The test results show that PA-Sketch significantly improves accuracy while minimizing the hash overhead. Compared to the state-of-the-art priority-aware sketches, PA-Sketch reduces the ARE of high-priority flows by 86% and improves the F1 score by 1.83 times, meanwhile maintaining slight accuracy loss for low-priority flows.