基于公平机制的网络测量抽样算法研究

作     者：董永吉 

作者单位：解放军信息工程大学 

学位级别：硕士

导师姓名：陈庶樵

授予年度：2009年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：网络流量分析 流量测量 分组公平抽样 哈希运算 统计计数 

摘      要：随着网络规模的迅速膨胀、新应用的不断涌现,系统级网络的可管理性和可控性越来越差,网络性能的可知性日趋复杂。为了应付日益复杂的网络,必须提出有效的网络测量方案,为当前网络稳健、可靠、高效的运行提出重要依据,同时这对于科学发展下一代网络具有极其重要的意义。 本文总结了网络测量的发展现状,结合国家863计划“十一五重大项目“新一代高可信网络总体技术相关课题的研究需求,分析了高速网络下流量测量的体系结构,重点研究了高速骨干网流量测量的前端处理算法及其工程实现技术。主要成果如下： 首先,提出了一种白适应公平抽样算法AFPS (Adaptive Fair Packet Sampling),解决了现有公平抽样算法SGS (Sketch Guided Sampling)需要预知实时流量进行抽样,工程难以实现的缺陷。该算法通过抽样的分组数来估计实时流量,降低了算法的实现难度,并根据该值来调整抽样比,使抽样比随流量变化而自适应调整,从而达到对各种流的公平抽样。 其次,提出了一种基于分段模式的统计计数结构CS (Counter Segment),避免了由于流量大小不均衡,造成均匀分配等长计数空间带来的资源浪费情况。该结构通过区分流量大小为每流分配计数器空间,使网络数据流根据其流量属性占用计数结构的不同段,在每两个计数段之间采用两个并行哈希函数建立映射关系。在保证一定的计数精度的同时,相对于均匀分配等长计数空间的方法,提高了存储空间利用率。 最后,设计了基于FPGA (Field Programmable Gate Array:现场可编程门阵列)的AFPS算法的实现方案。详细讨论了AFPS算法三个模块的实现方法,分析了各模块的资源占用情况。给出了实验测试的环境及方法,测试结果表明,基于FPGA实现的AFPS算法是可行的。