一种基于数据流计数的概率衰落大业务流识别方法  

An Identification Method Combining Data Streaming Counting with Probabilistic Fading for Heavy-Hitter Flows

作　　者：李臻[1,2] 杨雅辉[1] 谢高岗[2] 覃光成[3] 

机构地区：[1]北京大学软件与微电子学院,北京102600 [2]中国科学院计算技术研究所,北京100190 [3]解放军理工大学通信工程学院,南京210007

出　　处：《计算机研究与发展》2011年第6期1010-1017,共8页Journal of Computer Research and Development

基　　金：国家"九七三"重点基础研究发展计划基金项目(2007CB310702);国家自然科学基金项目(60903208;61070237);中国科学院重大科研装备研制项目(YZ200824)

摘　　要：大业务流识别是网络监控、管理以及计费等的重要基础,网络管理者通常会对大业务流给予特别的关注.大业务流识别需要在一定识别精度的基础上有效降低资源消耗.基于PLC(probabilisticlossy counting)方法,提出了一种概率衰落的大业务流识别方法PFC(probabilistic fading counting).该方法吸取了数据流计数技术的优势,通过分析网络流量的幂律(power-law)特性和连续性,采取加快对表记录中非活动流移除力度的方式,在有效控制漏报和误报的同时,大幅度降低了存储资源开销,实现了在有限资源下对高速链路实时准确的大业务流识别.实验结果表明,与PLC方法相比,PFC方法在减小误报率的同时,存储资源开销平均降低60%以上.Identifying heavy-hitter flows in the network is of tremendous importance for many network management activities.Heavy-hitter flows identification is essential for network monitoring,management,and charging,etc.Network administrators usually pay special attention to these Heavy-hitter flows.How to find these flows has been the concern of many studies in the past few years.Lossy counting and probabilistic lossy counting are among the most well-known algorithms for finding Heavy-hitters.But they have some limitations.The challenge is finding a way to reduce the memory consumption effectively while achieving better accuracy.In this work,a probabilistic fading method combining data streaming counting is proposed,which is called PFC（probabilistic fading counting）.This method leverages the advantages of data streaming counting,and it manages to find the heavy-hitter by analyzing the power-low characteristic in the network flow.By using network＇s power-law and continuity,PFC accelerates the removal of non-active and aging flows in table records.So PFC reduces memory consumption,and decreases false positive ratio too.Comparisons with lossy counting and probabilistic lossy counting based on real Internet traces suggest that PFC is remarkably efficient and more accurate.Particularly,experiment results show that PFC has 60% lower memory consumption without increasing the false positive ratio.

关 键 词：大业务流 数据流计数 概率衰落 识别 方法 

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