The design and evaluation of a terminal-matching adaptive sampling algorithm

Sampling is an important means of data reduction for traffic analysis in large-scale and high-speed networks. The uniform random sampling method is not sufficient for the analysis of short flows which can produce significant impact on the accuracy of anomaly detection. Many adaptive packet sampling algorithms have been proposed in the current literature to solve this issue. However, those algorithms cannot automatically adapt to the variety of hardware processing capabilities and traffic injection rate. To this end, this paper proposes a terminal-matching adaptive sampling algorithm, called Sketch Guided Adaptive Sampling (SGAS), by combining the schemes of segmented sampling and fair packet sampling. The theoretical analysis proves that the proposed SGAS can tune the output of sampling functions dynamically by considering several key parameters, such as the packet rate of data flow and the processing capability of terminal monitoring system, to maximize the utilization of hardware resources. Through comparing with existing related algorithms in realistic network environments, the proposed SGAS can effectively improve the accuracy of packet sampling, e.g., the error rate of flow size estimation.