1 算法分析与描述.doc

一种基于流数约减的非线性公平采样算法 李海莉1，史梦琳 （1国家数字交换系统工程技术研究中心，郑州450002；2. 郑州电力高等专学，郑州Adaptive Non-Linear Sampling）算法相比，AFS-RFN算法大幅降低存储开销；同时，将算法的公平性提高60%。算法具有良好的可扩展性和公平性。 关键词: 流量测量；均匀抽样；非线性；公平抽样 中图分类号: TP393　　　 文献标志码: A 文章编号：（作者可不填） Adaptive fair sampling based on reducing flow numbers LI Hai-li, SHI Meng-lin，ZHANG Zhen, GONG Yang-yang, GUO Wei, WANG Yu (National Digital Switching System Engineering Technological Research Center, Zhengzhou 450002, China) Abstract: Since present sampling methods have the shortcomings of non-scalability and low fairness, the paper proposed an algorithm called Adaptive Fair Sampling based on Reducing Flow Numbers (AFS-RFN). At first, AFS-RFN reduced the flow numbers by using the uniform sampling and got a sample flow set. Then, the packets belonged to the sample flow set were sampled fairly with the non-linear methods. The method controlled the flow numbers to account and guaranteed the accuracy of the information of flows. Compared with Adaptive Non-Linear Sampling (ANLS), the simulation demonstrates that the AFS-RFN algorithm saves large amount of memory overhead. At the same time, AFS-RFN improves the fairness by 60%, and has better scalability and fairness. Key words: traffic measurement; uniform sampling; non-linear; fair sampling 0 引言 网络流量测量将流量的各项指标量化，直观地描述当前网络流量的组成成分，反映网络当前的运行状况，在流量计费、流量识别、故障检测和网络安全等应用中起着极其重要的作用。由于网络上数据的增长速度远远超过存储器性能提高的速度，而目前没有容量大且速度快的存储器能够处理当前网络上的高速海量数据，因此，对每流进行统计成为一个巨大难题。为了能够获知网络上的各种统计信息，通过抽样对数据进行压缩是高速网络实时测量的一项重要手段。 传统的静态抽样算法以等概率p对链路上的数据包进行采样，能很好地保存包级流量信息，流信息统计的准确性随流的增大而提高，即小流的统计信息准确性低，大流的统计信息准确性高。考虑到网络的动态性，为合理利用存储和带宽资源，文献[1-4]分别针对不同的资源，自适应的改变抽样概率。这些算法虽然提高了资源的利用率，但却没有从根本上克服静态抽样算法对小流抽样准确度低的缺陷，导致并发流数目、流长分布等的流级统计信息不完整。同时目前流量测量的研究主要集中在大流检测[5-7]上，更加忽视小流的统计。研究表明[8]，网络上80%的流为小流。当前网络上的SYN Flood和DDOS攻击多是由单个或几个数据包组成的小数据流，对小流统计准确性的缺失导致系统没能及时发现网络异常事件，从而引起网络运行故障。因此，在准确统计大流用于统计计费的同时，提高小流抽样的准确性，对于网络安全和网络异常检测有着非常重要的作用。 提高数据流之间的公平性，需要提高小流抽样的准确性。文献[9]首次提出了牺牲大流抽样率并提高小流抽样率的基于图的抽样算法（Sketch Guided Sampling, SGS）