Research, Based On Bloom Filters Flow Sampling Algorithm

With the rapid development of Internet's expansion and diversification, network performance monitoring and management are strongly required. It is very important to understand network behaviors due to network management, network planning and network development. The network traffic measurement is an important direction of research in network measurement. Traffic measurement is the measurement and research for network traffic characteristics, statistical information, and abnormal events phenomenon. It is very helpful to solve the problem of network, protocol debugging, performance evaluation, etc.Firstly, research background of traffic measurement is analyzed, and the significance of traffic measurement is expatiated. Then, the traffic measurement method and the composition of traffic are introduced. Focuses on the method of traffic sampling, packet sampling and flow sampling are discussed in detail. By using the structure and principle of Bloom Filter, the definition of flow such as big flow is expatiated.According to the advantages of multi-judge and filter by layers of the Parallel filter and the Serial filter, a two-level filter structure based on the discussions on the difficulties of traffic measurement and on the analysis on these theories of traffic measurement is designed to catch big flows in the Internet. Because of the difficulties on 4-layer parallel setting of the Parallel filter and the inefficiency of setting step by step of the Serial filter, the design is based on the filter method of distinguish rather than location. It lowers the high false positive rate of the traditional big flow sampling method of Bloom Filters by reducing the setting frequency; moreover, it realizes the big flow sampling with less SRAM resources. The following three attempts on the structural frameworks and sampling algorithms are attempted:Firstly, the big flow sampling framework based on the two-levels filter is brought forward: the first lever realizes the initial filter of the flows on the Internet with a Bloom Filter, sampling the flows approximate to the big flow from the massive Internet flows; the second level realizes the filter of the approximate flows with a group of Bloom Filters and samples the needed flows from them. It filters the traffic information needed to be sampled from the high speed Internet flows step by step.Secondly, a corresponding BF2 algorithm is designed to lower the false positive situations by reducing setting frequency. The new arrived packets are distinguished by the second level filters, and then set by the first level ones, so that it reduces the setting frequency of the second level filter fundamentally and lowers the false positive rate of the big flow. Besides, by analyzing the false positive situation caused by the algorithm, the BF2 algorithm can identify and sample the big flows in the Internet with less time complexity and less space complexity, improving the executing efficiency.Thirdly, a timing refresh method is raised to lower the high false positive rate caused by long-time settings. It sets the refresh slot time of each level, pre-refresh before refreshing by setting the threshold value and the interval, trying to cut down the false positive situations created by the timing refresh. At last, an emulation experiment is acted to analog the Internet flows, proving the correctness and the high performance. The experimental results turn out that, compared with the traditional methods, the BF2 algorithm has lower false positive rate than the Parallel filter and the Serial filter.