CAJ | 학술논문

针对一种草图指导公平抽样(SGS)算法对小流估计误差大的问题，该文提出一种基于大小流区分计数的包公平抽样算法(DCMFS)，并给出哈希冲突对SGS算法估计误差影响的定量分析结果。DCMFS采用大小流区分计数器，对小流采用逐流精确计数，对大流采用哈希计数。理论分析及实际的数据仿真结果均表明，DCMFS算法对小流能够实现逐流精确统计，对大流的估计标准差接近公平抽样估计标准差理论值上限。算法采用不等长位宽计数器结构，保证其空间复杂度较SGS和自适应非线性抽样方法(ANLS)没有增加；引入计数器置换使得算法时间复杂度略有提高，但仍能满足10 Gbps线速处理要求。
침대일충초도지도공평추양(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.