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

A Fair Packet Sampling Algorithm Based on Different Counting Methods between Elephant and Mice Flows

作　　者：王晶[1] 汪斌强[1] 张震[1] 

机构地区：[1]国家数字交换系统工程技术研究中心郑州450002

出　　处：《电子与信息学报》2014年第10期2350-2356,共7页Journal of Electronics & Information Technology

基　　金：国家973计划项目(2012CB315901,2102CB315906,2011AA01A103)资助课题

摘　　要：针对一种草图指导公平抽样(SGS)算法对小流估计误差大的问题,该文提出一种基于大小流区分计数的包公平抽样算法(DCMFS),并给出哈希冲突对SGS算法估计误差影响的定量分析结果。DCMFS采用大小流区分计数器,对小流采用逐流精确计数,对大流采用哈希计数。理论分析及实际的数据仿真结果均表明,DCMFS算法对小流能够实现逐流精确统计,对大流的估计标准差接近公平抽样估计标准差理论值上限。算法采用不等长位宽计数器结构,保证其空间复杂度较SGS和自适应非线性抽样方法(ANLS)没有增加;引入计数器置换使得算法时间复杂度略有提高,但仍能满足10 Gbps线速处理要求。The previous fair packet sampling algorithm of Sketch Guided Sampling （SGS） has large estimation error for mice flows. A Fair packet Sampling algorithm based on Different Counting Methods between elephant and mice flows （DCMFS） is proposed, and the quantificational influence of hash collisions on estimation error of SGS is thoroughly analyzed. The key innovation is to use an elephant and mice flows differentiating counter to count the mice flows one by one and count the elephant ones by counting sketch. The theoretical analysis and evaluation on real traffic traces show that each mice flow can be estimated accurately by DCMFS and the elephant ones’ estimation error can reach the theoretical value of SGS. Due to the unequal length counter structure, DCMFS does not introduce much more counting space than SGS and Adaptive Non-Linear Sampling （ANLS）. Though the replacement of counters in DCMFS introduces more time complexity than SGS, it can still support the 10 Gbps line-speed processing.

关 键 词：互联网 网络流量测量 包公平抽样 哈希冲突 估计误差 大小流区分 

分 类 号：TP393.4[自动化与计算机技术—计算机应用技术]