基于报文抽样的长流检测算法研究

发布时间：2018-10-17 11:02

【摘要】：长流检测对于网络安全、流量计费和带宽分配等具有重要意义。基于流测量的研究表明,网络中的流呈现很强的重尾特性,即大多数流只包含少数量的报文,而很小一部分流却携带较大数量的报文。长流的一个明显特征就是他们仅占用流数量的一小部分却占据了总流量的绝大部分。因此,长流检测可以更好的了解网络行为,对网络操作和网络管理也有重要帮助。本文提出了基于报文抽样的长流检测算法。第一种算法将Sample and Hold技术与CountingBloomFilter相结合,算法可以实现对长流流长度的准确估计,检测出网络中长流。第二种算法利用Sample and Hold与Counter Tree技术相结合,保证算法能在准确测量出长流流长度的同时减少算法的在线处理时间。为提高算法的可扩展性,在前两种算法的基础上分别加入报文抽样技术,构成两种新算法。这两种新算法首先对到达的报文按照某一概率进行抽样,使算法的内存访问次数减少,加快了算法的在线处理速度。本文使用不同地区采集到的真实的网络Trace进行实验,实验结果表明了本文介绍算法可以准确地检测出长流,而且占用较小存储空间,处理每个报文的时间开销也很小。因此四个算法都适用于高速网络。
[Abstract]:Long flow detection is of great significance for network security, traffic billing and bandwidth allocation. The research based on flow measurement shows that the flow in the network has a strong heavy-tailed characteristic, that is, most streams contain only a small number of packets, while a very small number of streams carry a large number of packets. An obvious feature of long flows is that they occupy only a small part of the flow but account for the vast majority of the total flow. Therefore, long flow detection can better understand the network behavior, and also has important help to network operation and network management. In this paper, a long flow detection algorithm based on packet sampling is proposed. The first algorithm combines Sample and Hold technology with CountingBloomFilter. The algorithm can estimate the length of long flow accurately and detect the long flow in the network. The second algorithm combines Sample and Hold and Counter Tree technology to ensure that the algorithm can accurately measure the length of long flow and reduce the on-line processing time of the algorithm. In order to improve the extensibility of the algorithm, two new algorithms are constructed by adding packet sampling technology to the first two algorithms. The two new algorithms first sample the incoming packets according to a certain probability, which reduces the number of memory access and speeds up the on-line processing of the algorithm. In this paper, the real network Trace collected from different regions is used to carry out experiments. The experimental results show that the proposed algorithm can accurately detect long streams, and takes up small storage space, and the time cost of processing each packet is also very small. Therefore, the four algorithms are suitable for high-speed networks.
【学位授予单位】：大连海事大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.06

【相似文献】