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.

Quantiles over data stream have been recognized to be an essential feature in network traffic. To provide accurate estimation results, current quantile estimation approaches are preconfigured according to traffic distributions such as log-normal and Pareto distributions. In most practical applications, however, the traffic distributions are not known a priori or are highly dynamic, disturbing estimation results. In this paper, we propose SplitSketch, a sketch-based mechanism that aims to accurately estimate quantiles over data stream without any prior knowledge of traffic distributions. SplitSketch adjusts its estimation granularity according to the changing process of the traffic distribution. The granularities with denser distribution will be recorded with the finer granularity to provide more accurate estimation results. Experimental results demonstrate that, compared to existing approaches, SplitSketch reduces the absolute error in quantile estimation by 59.1% for heavy-tailed distributions and 79.2% for general distributions.