面向高速骨干网的网络流量测量关键技术研究

发布时间：2018-04-11 22:21

本文选题：流量测量 + 公平抽样　；参考：《解放军信息工程大学》2014年硕士论文

【摘要】：网络流量测量是认识和理解互联网运行行为、收集和分析网络协议运行性能、重新规划和优化网络结构并改善网络服务质量的重要手段。高速骨干网上的数据具有高速、海量的特点,为减轻流量测量系统中存储器和处理器的压力,面向高速骨干网的网络流量测量普遍采用部分流状态维护的方法,该方法包括数据抽取、流信息存储和查询以及超时流管理三部分。目前,主要存在以下三方面问题:1)现有抽样算法偏重于大流抽样,造成小流的统计结果准确性低,算法的公平性差;2)现有查询算法使用k次哈希以降低信息查询时的误判率,但是增加了算法的计算复杂度,导致算法的实时性差;3)缺乏结合大流保护和超时流表项及时删除的方法,导致现有超时流管理算法的实时性和准确性差。针对上述问题,论文依托国家863计划重大专项——“面向三网融合的统一安全管控网络”,对面向高速骨干网的网络流量测量关键技术展开研究。首先,针对现有抽样算法公平性差的问题,提出一种基于流数约减的公平抽样算法。然后,从信息的存储、查询和管理角度出发,提出基于二维空间地址和Sketch的查询算法和基于有区分LRU(least recent used)的超时流管理算法。本文主要研究内容如下:1、提出了一种基于流数约减的公平抽样算法(Adaptive Fair Sampling based on Reducing Flow Numbers,AFS-RFN)。基于降低空间复杂度并保证流公平抽样的原则,算法对新到达的分组,采取流数约减或非线性抽样的策略抽样,创建并维护样本流集合。性能分析和仿真结果表明,与ANLS(Adaptive Non-Linear Sampling)算法相比,AFS-RFN算法可处理速率为42.7Gbps链路上的流量测量任务,通过降低流数约减概率Pf,算法可适用于更高速率链路;并提高了算法的公平性。2、提出了基于二维空间地址和Sketch的查询算法(Two-Dimensional Space Address and Sketch,TDSAS)。基于提高查询实时性的原则,算法根据柯西不等式——两数之和与两数之积之间的关系,将信息的线空间查询扩展到面空间查询,通过将二维空间地址和二维数据结构Sketch结合存储和查询信息,降低算法查询时的计算复杂度。基于理论分析和仿真结果表明,在相同误判率的情况下,与CMS(Count-min Sketch)查询算法相比,TDSAS查询算法将算法的计算复杂度由O(d)降低至O(d),并将算法的实时性提高24.4%。3、提出了基于有区分LRU的超时流管理算法。基于降低大流漏判率并保证超时流实时删除的原则,设计一个由大流保护端(热端)和超时流处理端(冷端)构成的有区分LRU队列,根据其两端长度比l和区分新到分组应归属热端或冷端的阈值T,推导出流大小n和l与漏判率之间的关系式,并由n设置T值。理论分析和仿真结果表明,与传统LRU算法相比,根据该关系式合理设置T和l值,可将大流的漏判率降低一个数量级,同时可支持速率为40.9Gbps链路上流量的实时测量。
[Abstract]:Network traffic measurement is an important means to understand and understand the behavior of Internet, to collect and analyze the performance of network protocols, to replan and optimize the network structure and to improve the quality of service.The data of high-speed backbone network has the characteristics of high speed and mass. In order to reduce the pressure of memory and processor in the traffic measurement system, the method of partial stream state maintenance is widely used in network traffic measurement for high-speed backbone network.The method includes data extraction, stream information storage and query, and timeout flow management.At present, there are three main problems: 1) the existing sampling algorithms focus on the large stream sampling, which results in the low accuracy of the statistical results of the stream, and the poor fairness of the algorithm. 2) the existing query algorithms use k hashes to reduce the misjudgment rate when the information is queried.However, the computational complexity of the algorithm is increased, which leads to the lack of the method of combining the large flow protection and the timely deletion of timeout flow table items, which leads to the poor real-time and accuracy of the existing time-out flow management algorithms.In view of the above problems, the paper studies the key technology of network traffic measurement for high-speed backbone network based on the national 863 project, "the unified security management and control network for the integration of three networks".Firstly, aiming at the problem of poor fairness of the existing sampling algorithms, a fair sampling algorithm based on the reduction of the number of streams is proposed.Then, from the point of view of information storage, query and management, a query algorithm based on two-dimensional spatial address and Sketch and a time-out flow management algorithm based on differentiated LRU(least recent are proposed.The main contents of this paper are as follows: 1. An adaptive Fair Sampling based on Reducing Flow numbers (AFS-RFN) algorithm based on reduced stream number is proposed.Based on the principle of reducing the space complexity and ensuring fair sampling of the flow, the algorithm adopts the strategy of reducing the number of flows or nonlinear sampling to create and maintain the set of sample flows for the newly arrived packets.The performance analysis and simulation results show that compared with the ANLS(Adaptive Non-Linear sampling algorithm, the AFS-RFN algorithm can handle the traffic measurement task on the 42.7Gbps link, and the algorithm can be applied to the higher rate link by reducing the probability of the reduction of the flow number.The fairness of the algorithm is improved, and a two-dimensional Space Address and Sketchn algorithm based on 2-D spatial address and Sketch is proposed.Based on the principle of improving the real-time performance of the query, the algorithm extends the line space query of information to the surface space query according to the relation between the sum of two numbers and the product of two numbers.By combining two-dimensional spatial address and two-dimensional data structure Sketch to store and query information, the computational complexity of the algorithm is reduced.Based on the theoretical analysis and simulation results, it is shown that, in the case of the same error rate,Compared with the CMS(Count-min search algorithm, the computational complexity of the algorithm is reduced from LRU to Odetd, and the real-time performance of the algorithm is improved by 24.40.3. an algorithm of time-out flow management based on differentiated LRU is proposed.Based on the principle of reducing the large flow leakage rate and ensuring the real-time deletion of the time-out flow, a differentiated LRU queue is designed, which consists of a large stream protection end (hot end) and a time-out flow processing terminal (cold end).Based on the ratio of length of two ends to l and the threshold T which distinguishes that the new to the packet should be assigned to the hot or cold end, the relationship between the flow size n and l and the leakage rate is derived, and the T value is set by n.The theoretical analysis and simulation results show that compared with the traditional LRU algorithm, the leakage rate of large flow can be reduced by one order of magnitude according to the reasonable setting of T and l values, and the rate of real-time measurement on 40.9Gbps link can be supported.
【学位授予单位】：解放军信息工程大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.06

【参考文献】