Research On Sampling Algorithm In Network Traffic Measurement

By measuring the traffic and analyzing the operating conditions, network measurement provides a reference for network management, performance improvement and structural optimization. However, due to the arrival of the rapid development of high-speed Internet technology and the era of big data, the data of network is growing explosively, and capturing every packet of information or flow information to be stored and analyzed has become impossible Introducing the sampling technology into the flow measurement can effectively solve the bottleneck problem, and can greatly reduce the measurement data, so the sampling technology has become the focus of one of the elements of network traffic engineering.In this thesis we summarize the network traffic measurement theory, analyze the difficulty in measuring the current high-speed network environments, and point out the important role of sampling techniques in network measurement. Then we illustrate the related concepts of sampling technology, discuss several basic methods of sampling such as random sampling, systematic sampling and stratified sampling etc. and analyze the key technology such as hash algorithm, summary data structure in the sampling measurement. Finally, by studying the characteristics of the network, we combine the sampling technology and the Bloom filter of simple structure and rapid to find and match, to propose a flow detection algorithm based on LRU_CBF and a flow sampling algorithm based on tree Bloom filter. The performance analysis and simulation experiments show that the proposed algorithm can improve the measurement accuracy system resource utilization. The concrete research content is as follows:(1)Based on the systematic study of basic standard, Counting split Bloom filter type and other characteristics, this thesis combine the Counting Bloom Filter of superior performance and the classic page replacement algorithm LRU(Least Recently Used) strategy in the operating system to design a kind of crowd detection algorithm. The algorithm uses a two-tier structure, LRU first filtered out the crowd and CBF further judgment on the crowd, so that the "crowd filtering" and "herd judgment" to separate the two processes. This structure can simplify the data storage structure, reduce the space complexity, accurate detection of the flow, and improve the accuracy. Through simulation experiments, this thesis compare the proposed crowd detection algorithm based LRU_CBF with the two CBF algorithms; the algorithm in this thesis has higher accuracy and better resource utilization.(2)Expanding network size makes characteristics of network traffic becomes very complex, and single-level data structure can not meet the requirements of network measurement. This article in view of the present standard BF algorithm will counter overflow caused by defects in heavy traffic, we design a multi-level structure tree bloom filter. Each layer is a standard BF in improved filter, it map the bit of value of 1 to the leaf nodes, and map multi-level tree after the filter layer by layer. When traffic is bigger we can add new BF to prevent BF overflow and cause measurement error. We combine tree BF with stream sampling algorithm based packet, and apply it to the actual network traffic measurement, to reduce the number of measurements simultaneously and improve the measurement accuracy. By simulation, we compare the measurement error terms of this algorithm with other sampling algorithm based on Bloom filter, the analysis shows that the proposed algorithm in this thesis improves the accuracy of the sample, and reduce the space utilization.