一种基于大小流区分计数的公平抽样算法

发布时间：2017-09-02 10:27

  本文关键词：一种基于大小流区分计数的公平抽样算法

  更多相关文章： 互联网 网络流量测量 包公平抽样 哈希冲突 估计误差 大小流区分

【摘要】：针对一种草图指导公平抽样(SGS)算法对小流估计误差大的问题,该文提出一种基于大小流区分计数的包公平抽样算法(DCMFS),并给出哈希冲突对SGS算法估计误差影响的定量分析结果。DCMFS采用大小流区分计数器,对小流采用逐流精确计数,对大流采用哈希计数。理论分析及实际的数据仿真结果均表明,DCMFS算法对小流能够实现逐流精确统计,对大流的估计标准差接近公平抽样估计标准差理论值上限。算法采用不等长位宽计数器结构,保证其空间复杂度较SGS和自适应非线性抽样方法(ANLS)没有增加;引入计数器置换使得算法时间复杂度略有提高,但仍能满足10 Gbps线速处理要求。
【作者单位】： 国家数字交换系统工程技术研究中心;
【关键词】： 互联网 网络流量测量 包公平抽样 哈希冲突 估计误差 大小流区分
【基金】：国家973计划项目(2012CB315901,2102CB315906,2011AA01A103)资助课题
【分类号】：TP301.6;TP393.06
【正文快照】： 1引言互联网流量抽样技术是解决高速网络流量测量的有效途径[1],其在对数据分组进行抽样时充分考虑分组的流相关性,从而满足丰富多样的流量特性统计需求。目前流抽样方法大致可分为两类。第1类方法只对部分感兴趣的流进行逐包统计[2,3],如抽样保持(SH)和多级过滤器(MBF)[2]算

【相似文献】

中国期刊全文数据库 前10条

1 戴晓爱,唐能福,杨武年,刘汉湖;利用STL技术生成TIN模型的算法[J];测绘科学;2005年05期

2 冯炳根;追溯查索算法与子图同构判断问题[J];计算机研究与发展;1985年06期

3 周建钦;;超快速排序算法[J];计算机工程与应用;2006年29期

4 唐艳琴;张欣星;吴永芬;;链表中头结点的应用[J];现代计算机(专业版);2009年11期

5 苏丹;;《数据结构》课堂教学探讨与反思[J];商业经济;2007年08期

6 王玉英;陈平;苏e，

本文编号：778008