抽样在线网速检测

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2014,25(1):135153[doi:10.
13328/j.
cnki.
jos.
004445]http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel/Fax:+86-10-62562563高速网络流量测量方法周爱平1,2,程光1,2,郭晓军1,21(东南大学计算机科学与工程学院,江苏南京211189)2(教育部计算机网络和信息集成重点实验室(东南大学),江苏南京211189)通讯作者:周爱平,E-mail:apzhou@njnet.
edu.
cn摘要:高速网络流量测量是目前实施实时准确地监测、管理和控制网络的基础.
基于网络流量测量的应用,将网络流量测量分为抽样方法和数据流方法.
从不同的层次,将抽样方法分为分组抽样和流抽样,分别介绍了两类抽样方法;从测度角度介绍了数据流方法.
详细介绍了高速网络流量测量的常用数据结构,以及抽样、数据流方法在高速网络流量测量中的应用,比较了各种方法的优劣.
概述了高速网络流量测量技术的研究进展.
最后,就现有的网络流量测量方法的不足,对网络流量测量的发展趋势和进一步的研究方向进行了讨论.
关键词:网络流量测量;分组抽样;流抽样;数据流中图法分类号:TP393文献标识码:A中文引用格式:周爱平,程光,郭晓军.
高速网络流量测量方法.
软件学报,2014,25(1):135153.
http://www.
jos.
org.
cn/1000-9825/4445.
htm英文引用格式:ZhouAP,ChengG,GuoXJ.
High-Speednetworktrafficmeasurementmethod.
RuanJianXueBao/JournalofSoftware,2014,25(1):135153(inChinese).
http://www.
jos.
org.
cn/1000-9825/4445.
htmHigh-SpeedNetworkTrafficMeasurementMethodZHOUAi-Ping1,2,CHENGGuang1,2,GUOXiao-Jun1,21(SchoolofComputerScienceandEngineering,SoutheastUniversity,Nanjing211189,China)2(KeyLaboratoryofComputerNetworkandInformationIntegration,MinistryofEducation(SoutheastUniversity),Nanjing211189,China)Correspondingauthor:ZHOUAi-Ping,E-mail:apzhou@njnet.
edu.
cnAbstract:Trafficmeasurementinhigh-speednetworkisessentialfornetworkmonitoring,management,andcontrol.
Basedontheapplicationsofnetworktrafficmeasurement,thisstudydividesthemeasurementintosamplingmethodsanddatastreammethods.
Samplingmethodsarepartitionedintopacketsamplingandflowsampling,bothareintroduced.
Datastreammethodsareintroducedfromdifferentmetrics.
Thisstudyintroducesindetailthecommondatastructureandapplicationsbasedonsamplinganddatastreammethodsinhigh-speednetwork.
Drawbacksofdifferentmethodsareanalyzedandcompared.
Theresearchprogressofhigh-speednetworktrafficmeasurementtechnologyissummarized.
Finally,thelimitationofrecentnetworktrafficmeasurementmethods,theevolvingtrendofnetworktrafficmeasurement,andsomepossibledirectionsoffutureresearcharediscussed.
Keywords:networktrafficmeasurement;packetsampling;flowsampling;datastream近年来,随着互联网的快速发展和新应用的不断出现,很多研究机构和学者致力于研究开发对互联网实施监测和测量的技术,网络流量测量已被广泛应用于网络计费、流量工程、网络安全等领域[1].
随着网络链路速率基金项目:国家自然科学基金(60973123);国家重点基础研究发展计划(973)(2009CB320505);江苏省科技支撑计划——工业部分(BE2011173);江苏省"六大人才高峰"收稿时间:2013-03-22;修改时间:2013-05-13;定稿时间:2013-06-26;jos在线出版时间:2013-07-25CNKI网络优先出版:2013-07-2514:03,http://www.
cnki.
net/kcms/detail/11.
2560.
TP.
20130725.
1403.
003.
html136JournalofSoftware软件学报Vol.
25,No.
1,January2014的不断提高和网络数据流的急剧增加,当前在高速骨干网链路上,网络流量测量需要极高的计算和存储资源,从而给网络流量测量研究开发带来了技术挑战.
在高速链路上,处理每个分组需要纳秒级时间,例如在OC-768(40Gbps)链路上,设分组的平均大小为40B,则分组的平均处理时间为8ns.
传统的网络流量测量方法面临的主要问题是可扩展性,不能够适应高速网络环境.
美国已在高速网络实验床上开展了下一代高速计算机网络及其典型应用的研究,其他国家和地区也相继开展了下一代高速互联网络及其应用的研究,如英国、加拿大.
与国际同类研究相比,我国的下一代互联网的研究内容涵盖了高速互联网络涉及的大部分研究领域,包括基础设施、网络服务与网络应用,并取得了一定的理论与应用成果[2].
高速网络流量测量技术是下一代互联网研究的重要组成部分,成为网络测量的发展趋势之一.
目前,高速网络流量测量问题主要有3种解决方案:利用高性能的专用硬件,如TCAM,ASIC等,实现高速链路上网络流量的数据处理.
然而,高性能的硬件设备极其昂贵;利用抽样技术只对部分有代表性的网络流量数据进行采集处理,虽然降低了系统的负荷,但却存在较大的误差[3];利用数据流技术[4]对所有网络流量数据进行处理,有效地减少存储资源的需求,同时保持一定的准确性.
高速链路上持续到达的海量网络流量给网络流量测量与分析带来了极大的困难,因此需要采取一些可行的措施,既能够对网络流量数据进行缩减,又能够保留网络流量数据的特征信息.
根据网络流量测量的应用需求,数据缩减技术主要分为抽样和数据流两种.
抽样技术的目的是选择具有代表性的网络流量数据分组子集,通过该子集推断网络流量总体数据分组的特征信息.
数据流技术是将庞大的信息压缩到较小的存储空间并保持一定的精确度,数据流技术具有在线实时处理和有限存储空间的特性.
各种网络流量测量方法是针对具体的应用需求提出来的,具有一定的局限性,目前还没有一种通用的网络流量测量方法.
本文详细综述了近年来国内外主要的高速网络流量测量方法的研究进展.
第1节介绍网络测量方法的主要评价指标.
第2节介绍网络流量测量的抽样方法.
第3节介绍网络流量测量的数据流方法.
第4节介绍高速网络流量测量的数据结构.
第5节介绍抽样方法与数据流方法在网络流量测量中的应用.
第6节概述高速网络流量测量技术的研究成果.
第7节讨论现有的网络测量方法的不足、网络测量的发展趋势和可能的下一步的研究方向.
最后对全文进行总结.
1网络测量方法的评价指标高速网络测量技术主要从以下几个方面进行评估:实时性:反映网络测量技术能够在线地、快速地处理网络数据流的能力;准确性:反映网络测量技术能够估计网络数据流的能力;可扩展性:反映网络测量技术能够处理大量的网络数据流的能力;存储复杂性:反映网络测量技术准确估计网络数据流所需存储空间;计算复杂性:反映网络测量技术准确估计网络数据流所需处理开销,如内存访问、CPU.
目前,对这些评估指标进行量化还存在一定的困难.
为了能够有效验证现有的网络测量方法,本文主要介绍误报率、漏报率和检测率、无偏估计和相对误差、平均相对差和加权相对差以及熵和标准熵评价指标.
1.
1检测率、误报率和漏报率误报(falsepositive)是指正常事件被检测为异常事件.
真阴性(truenegative)是指正常事件被检测为正常事件.
令FP为误报数,TN为真阴性数,则误报率(falsepositiverate)为fFPRFPTN+=+.
漏报(falsenegative)是指异常事件被检测为正常事件.
真阳性(truepositive)是指异常事件被检测为异常事件.
令FN为漏报数,TP为真阳性数,则漏报率(falsenegativerate)为fFNRFNTP=+.
检测率(detectionrate)是指被检测为异常事件的异常事件数与实际异常事件总数的比率,则检测率为周爱平等:高速网络流量测量方法137dTPRFNTP=+.
由于Rd+Rf=1,因此实际应用中仅需考虑误报率与检测率.
1.
2无偏估计和相对误差网络测量中常用流长估计的无偏性评价估计精度.
如果[],Enn=则n是n的无偏估计(unbiasedestimation).
相对误差(relativeerror)表示为||/,nnn而实际应用中,常用离差系数表示相对误差,离差系数定义为流长估计的标准差与真实流长之比,即var().
nn1.
3平均相对差和加权平均相对差c网络测量中常用流长分布估计的平均相对差和加权平均相对差评价估计精度.
令ni为大小为i的流数,in为ni的估计,则相对差(relativedifference)表示为||2iiiinnrelativedifferencenn+=.
从而,平均相对差(meanrelativedifference)表示为11||2ziiiiinnmeanrelativedifferencennz==+∑.
平均相对差不适用于评价具有重尾特性的流长分布.
给每个流长估计的相对差分配一个权重,2iinn+则加权平均相对差(weightedmeanrelativedifference)为1111||2||222ziiiiiiiziiizziiiiiinnnnnnnnweightedmeanrelativedifferencennnn====++==++∑∑∑∑.
加权平均相对差适用于评价网络流长分布估计.
1.
4熵和标准熵在信息论中,熵是不确定性的度量.
令数据集X={x1,x2,…,xN},它的熵表示为21()log(),NiiiHXpp==∑其中,N表示数据集X中元素的个数,pi表示第i个元素发生的概率.
网络测量中,常用熵表示数据流中分组的随机性或差异性.
若数据流中分组是相同的,则数据流获得最小熵0;若数据流中所有分组是不同的,则数据流获得最大熵log2N.
为了比较熵估计,定义标准熵为212log()()logNiiinppHXN==∑.
标准熵的取值范围为[0,1].
2抽样方法抽样技术是指从原始流量数据中选择有代表性的分组子集,通过该分组子集推断原始流量数据的特征.
随着链路速率的提高和应用的多样化,巨大的网络流量给流量采集、传输、存储、分析都带来了巨大的压力.
为了解决高速网络被动测量问题,将抽样技术应用于高速网络流量测量,可在满足问题统计精度的条件下,减少用于测量、存储和处理的数据量.
在高速网络流量测量中,抽样方法实现受到技术和资源的限制,往往需要在抽样率和估计精度之间加以折138JournalofSoftware软件学报Vol.
25,No.
1,January2014中.
抽样采集使得系统的处理负荷大为减轻,具备较好的可扩展性,而且还能从样本特征参数反映出原始流量特征参数,具有一定的测量精度.
抽样数据除了可以对流量特征进行分析外,还在流量计费、性能特征测量、异常检测等领域广泛应用.
对于互联网中的流量,从分组和流的层次,抽样方法主要分为分组抽样和流抽样.
本节主要介绍这两类抽样方法.
2.
1分组抽样分组抽样(packetsampling)是指对构成网络流量的分组进行抽样,每个分组都是独立的,不考虑分组之间的相关性.
常用的分组抽样方法包括系统抽样、简单随机抽样和分层随机抽样:(1)系统抽样(systematicsampling)是指以固定的间隔抽取对象,在选择抽取第1个对象后,每隔N个对象选择下一个对象,如图1(a)所示.
系统抽样方法是一种广泛应用的抽样方法,但是系统抽样存在一定的周期性;(2)简单随机抽样(simplerandomsampling)是指以一定的概率抽样对象,如图1(b)所示.
每个对象被抽样的概率可以是相同的也可以是不同的,这种概率一般会遵循某种概率分布函数.
在流量测量中,常用的随机抽样方法分为简单随机抽样和随机增量抽样.
这两种随机增量抽样方法可以避免系统抽样的同步问题;(3)分层随机抽样(stratifiedrandomsampling)是指首先把总体分成若干层次或类型组,然后从各个层次中按一定的比例随机抽样.
这种分层可以是按照元素的排列顺序进行划分,如图1(c)所示,也可以按照元素的某个特征,如分组长度、协议类型等进行分层,然后分别进行抽样.
在流量测量中,常用的分层抽样为均匀分层随机抽样(uniformstratifiedradomsampling).
该方法可以保证抽样相对于元素的属性是无偏的,减少分组统计的误差,使得估计结果更接近于原始数据.
(a)系统抽样(b)简单随机抽样(c)分层随机抽样Fig.
1Threekindsofsamplingmethods图13类抽样方法由于网络流量具有自相似性特征,He等人[5]提出改进的系统抽样BSS(biasedsystematicsampling),与静态的系统抽样和简单随机抽样相比,提高了均值的估计精度,同时降低了抽样开销.
然而,大部分分组抽样方法均匀地选择分组,而没有考虑到分组的大小,从而使得网络测量获得一些不确定性,如流检测、估计精度、处理负荷等.
为了克服分组大小给抽样带来的不利影响,Raspall[6]提出了EBS(efficientbytesampling),以提高测量质量,使得测量精度更少地依赖于流量的特征,降低了测量开销.
2.
2流抽样流抽样(flowsampling)是指在测量时间内对网络流进行抽样,构成网络流量的分组并不是孤立的,它们是为了完成具体的应用而产生的,它们之间存在着一定的关联,流是体现这种关联的一种方式.
流抽样主要有两种抽样方式:先对分组进行抽样,再对分组进行流归并;先对分组进行流归并,再对流进行抽样.
流、分组的统计特性存在着完全不同的特点,流抽样和分组抽样的需求也不一样.
由于分组的大小是受传输技术限制的,其最大长度不会超过网络能够支持的最大值,但是流的大小却是不受影响的.
对于流量测量,采用哪种测量和抽样方法是由网络测量的目的决定的.
对于流量计费,关注流量的长度、大小,大流丢失会导致大量信息损失,因此需要保证大流被抽样;如果对所有的流按照相同的概率进行抽样,少量的大流信息很容易被漏掉.
然而对于异常监测,需要保留尽量多的流信息,如SYNFlooding,DoS攻击等通常由大量的小流构成.
抽样是降低内存消耗和分组处理时间的最广泛采用的方法之一.
由于最坏情况下资源使用是平均情况下资源使用的多个数量级,抽样率的静态选择存在一些问题.
SampledNetFlow需要配置一个静态的抽样率,该方周爱平等:高速网络流量测量方法139法的主要问题在于选择安全的参数,确保网络设备在不利的流量环境下持续地运行.
因此,抽样率是在最坏情况下设定的.
许多研究已经解决了动态选择抽样率的难题,通过自适应网络环境,克服设定静态抽样率的缺陷[7].
然而,自适应的抽样方法,如AdaptiveNetFlow(ANF)[7],还没有广泛地使用,主要原因在于,自适应的抽样方法需要消耗大量CPU资源,依赖于复杂的数据结构与算法,使得它们在网络硬件中的实施缺乏吸引力.
Sanjuàs-Cuxart等人[8]提出一种基于自适应流抽样的测量方法,该算法基于一个简单、随机的数据结构,该结构需要很小的分组开销,很容易参数化.
与之前的方法相比,该算法基于更加简单的算法,而且需要更少的硬件资源,因此适合于硬件实施.
为了降低小流的估计误差,概率计数器更新算法被提了出来,如ANLS[9],这些算法利用计数器值c的函数p(c)代替静态的抽样率p,因此抽样率根据抽样的分组数而变化.
然而,由于测量精度不仅受到抽样函数的影响,而且受到流长分布的影响,选择一个独立的静态抽样函数也是不够的.
因此,Ma等人[10]提出了SmartSelectionSampling(S3)方法,通过利用流长分布信息选择合适的抽样函数,能够调整抽样函数,获得更高的测量精度.
3数据流方法高速链路上网络流具有实时性、连续性、无界性等特点,从而决定了处理网络流的算法只对网络流执行一趟计算,而且只需要使用有限的计算和内存资源.
对这种网络流进行计算的算法必须满足以下条件:算法需要使用的空间必须足够小;处理和更新必须迅速、简单;对于查询必须有一定的准确度保证.
抽样技术在网络流量测量与分析中得到广泛应用.
尽管抽样方法产生了一个原始数据的代表子集,但是从抽样数据推断得到的网络流量统计信息存在一定的误差,不能确切地反映原始流量的特征.
数据流方法具有单遍扫描、有限的计算和内存资源等特点,是高速网络流量测量的重要方法.
随着计算机网络和通信技术的迅猛发展,数据流方法广泛应用于网络流量监控、商业交易和分析、传感器网络等领域.
数据流方法应用于近似测量高速链路上网络流量统计信息,如活跃流的总数、大流识别、流长分布、节点连接度和熵估计等.
本节从熵估计、流量和流矩阵估计、连接度估计测度方面介绍了数据流方法.
3.
1熵估计熵是网络测量中一个重要的测度.
网络流量的熵有助于许多网络监测应用,如异常检测[11].
在高速链路上流量的熵的测量需要低CPU和存储要求的准确算法.
由于处理能力和存储的限制,传统方法不适用于高速链路.
抽样方法能够降低处理和存储要求,适用于捕获一些流量统计信息,然而从抽样数据获得的估计可能存在较大的误差.
数据流算法对计算和存储要求相对较低,适用于高速链路上估计网络流量的熵[12].
在数据流算法中,流量的熵定义为22222111111logloglogloglog,nnnniiiiiiiiiiimmHmmmmmmmmmmm====∑∑∑∑其中,mi表示流中第i项的频数,m表示流的总项数,1.
niimm==∑令21log,niiiSmm==∑熵估计与频数矩估计[13]具有相似的结构,基于此,Lall等人[14]提出S的一个(ε,δ)近似算法,表示至少以1δ概率获得相对误差至多为ε的估计,即:Pr(||)1,XXXεδ≤≥其中,X是X的估计.
该算法利用著名的Alon-Matias-Szegedy频数矩估计算法的思想[13].
该数据流算法未考虑网络流量分布特征,然而网络流量分布具有重尾特性.
在此基础上,Lall等人[14]提出了另一种数据流算法,利用区分网络流中大流与小流的思想,通过分别估计大流、小流对熵的贡献,进一步提高熵估计的精度,同时减少存储空间.
前一种数据流算法使用的空间直接与估计量的方差成正比,通过筛选出高计数项,能够显著地减小估计量的方差和存储空间.
后一种数据流算法对抽样方法作了微小的改进,以小概率对每个位置抽样,而不是事先计算流中位置.
在流中某项被抽样之后,为该项维护准确的计数,类似于SampleandHold算法[15].
如果流中某项被抽样1次,则认为是小流,通过以前的算法计算小流的熵;如果流中某项被抽样多次,则认为是大流,估计大流的熵.
140JournalofSoftware软件学报Vol.
25,No.
1,January2014前一种数据流算法优于传统的抽样方法,给出熵的无偏估计,获得更低的估计误差,同时使用类似的存储开销;后一种数据流算法有效地分离大流和小流,提高了熵估计的精度.
OD(origin-destination)流的熵也是网络测量中一个重要的测度,该熵有助于掌握ISP网络内流量动力学.
估计网络内所有流的熵是非常有帮助的.
网络性能下降和服务中断,可能是由多种事件引起的,包括网络异常,如DDoS攻击、网络故障、flashcrowds以及计划的网络维护任务,如路由器IOS更新、客户迁移,这些事件以分布式方式发生.
检测这些事件和评价它们对网络服务的影响,需要从不同的位置来监控网络流量.
更重要的是,流量分布的变化在传统的流量矩阵上可能是完全不可见的.
然而,通过检查网络中每个OD流的熵,能够实时地捕获这些事件.
Zhao等人[16]提出一种数据流算法,解决了估计网络内所有OD流的熵难题.
3.
2流量与流矩阵估计流量矩阵表示测量区间内网络中每个OD对之间的分组数或字节数,流量矩阵的估计困难已经受到相当多的关注.
流量矩阵的准确估计有助于网络管理,如容量规划与预测、网络故障与可靠性诊断以及路由配置.
有时,流量矩阵对于一些流级应用仍是不足够的,如推断ISP的使用模式、检测路由摆动、链路故障、DDoS攻击以及Internetworms.
流矩阵表示网络中每个OD流之间的流量大小,与流量矩阵相比,流矩阵是更细粒度的,且更有助于流级应用.
流矩阵估计是另一个重要的难题,基于统计推断或分组抽样的流量矩阵估计算法不能获得高精度的估计.
为了满足高速链路上流量与流矩阵估计,Zhao等人[17]提出了两种数据流算法,即基于Bitmap的数据流算法和基于计数器数组的数据流算法.
基于Bitmap的数据流算法能够获得至少比之前的算法高一个数量级的流量矩阵估计;基于计数器数组的数据流算法获得比流量矩阵更细粒度的流矩阵估计.
这两种数据流算法能够处理高速链路(如40Gbps)上的网络流,产生比网络流小多个数量级的流量概要.
3.
3连接度估计主机连接度是与某台主机相连的其他主机的数量,它是网络流量测量与监控的一个重要测度.
超连接度主机是指在短时间内主机与其他主机之间存在大量不同的连接.
对快速网络安全监控而言,检测超连接度主机是最重要的任务之一.
例如,识别超连接度主机有助于检测端口扫描、蠕虫传播以及DDoS攻击,因为端口扫描和蠕虫传播是由在短时间内主机与不同目的主机建立大量的连接引起的,而DDoS攻击是大量的主机泛洪到一个目的主机所引起的.
在两个相连的区间内主机连接度的显著变化,也是监控网络流量的一个重要测度.
由于在高速网络环境下大量的网络流量数据和有限的处理能力,很难准确、实时地测量和监控高速链路上的网络流量.
高速链路上准确、实时地检测超连接度主机,是网络测量与网络安全中一个重要的难题,已经得到广泛的研究.
维护每个流状态的简单方法,不适用于高速链路上检测超连接度主机.
基于Hash的流抽样技术提供了一种分析与处理大量数据的可能有效的方法[18],然而该算法的准确性依赖于抽样率,高速链路上抽样率受到存储器的限制,从而不可能获得准确的主机连接度估计.
同时,在两个相连的区间内仅仅能够估计抽样主机的连接度变化,抽样技术不能准确地测量主机连接度的变化,从而不能准确地检测连接度发生显著变化的主机.
数据流方法广泛应用于主机连接度估计.
Guan等人[19]利用RCDS(reversibleconnectiondegreesketch)实时地测量和监控主机连接度和主机连接度的动态变化,能够准确、有效地检测超连接度主机或连接度发生显著变化的主机.
Wang等人[20]对该数据结构进行了改进,提出了一种检测超连接度节点或连接度发生显著变化节点的有效保留算法.
为了提高空间的利用率,Yoon等人[21]利用一组Hash函数从共享的位数组中随机地选择位,为每个节点建立虚拟Bitmap,通过每个主机对应虚拟Bitmap估计节点连接度.
虚拟索引方法VCDS(virtualconnectiondegreesketch)[22]估计高速链路上的节点连接度.
为了减少因共享而对主机的虚拟Bitmap所产生的噪声污染,通过过滤Bitmap来估计节点连接度.
4高速网络流量测量的数据结构数据结构是高速网络流量测量的重要组成部分,优化的数据结构有助于提高算法的执行效率和估计精度,降低计算和存储开销.
现有的数据结构主要包括Bitmap,HybridSRAM/DRAMCounter,BloomFilter,Count-Min周爱平等:高速网络流量测量方法141Sketch,CounterBraids,BRICK.
本节主要介绍这些数据结构及其应用.
4.
1BitmapBitmap是一个简单的数据结构,将某个域映射到位数组.
直接的Bitmap[23]是一种流数估计算法,利用Hash函数将流标识映射到Bitmap中的一位.
Bitmap初始化为0,当分组到达时,将该分组的流标识映射到Bitmap中的一位,并置该位为1.
属于同一流的所有分组映射到Bitmap中的同一位置,因此,无论每个流发送多少分组,每个流至多对应于Bitmap中的一位.
Bitmap中为1的位数作为流数的估计,由于存在Hash冲突,流数估计是不准确的.
基于Bitmap算法低估了实际的流数,使用离散区间的主要缺陷在于可能低估和不能频繁地报告.
基于TimestampVector算法[24]是基于Bitmap算法的扩展,保持了基于Bitmap的流数估计算法的速度快和内存小的优点.
在基于TimestampVector算法中,允许频繁报告实现了报告区间的分离,避免了流数低估问题,有效地提高了流数估计的精度.
由于上述两种流数估计算法中每个分组到达时需要多次访问内存、创建新的流记录、处理冲突需要消耗大量的内存资源,在高速网络环境中需要存储大量的流标识,从而需要使用大量的内存资源.
Hash表必须存储在DRAM中,访问DRAM的时间长于分组相继到达的时间间隔,流数估计算法必须能够及时处理高速网络中的每个到达的分组.
在直接的Bitmap的基础上,基于CountdownVector算法[25]在滑动窗口上估计流数,显著地减少了所需的内存和CPU资源,提高了流数估计的精度.
4.
2HybridSRAM/DRAMCounter在高速网络环境中如何有效地存储和维护大量的计数器,已经成为一个重要的研究方向,在网络性能监控、网络管理、入侵检测及流量工程等应用中也显得尤为重要.
随着数据流技术的发展,大量高速计数器的维护引起学者的广泛关注.
数据流算法将工作内存组织为一个概要数据结构(sketch),用来捕获尽可能与统计估计相关的信息.
对不同的统计估计需要不同的sketch,sketch由计数器数组构成,有一个共同的在线操作(hashandincrement).
在高速链路上,巨大的网络流量使得数据流算法需要大量的计数器,某些计数器取值较大,因此,计数器在低速DRAM的存储和维护不适用于高速链路,而计数器在高速SRAM中的存储和维护满足高速链路.
Shah等人[26]提出了HybridSRAM/DRAMCounter结构,在此基础上,该计数器结构在文献[27]中得到进一步的改进.
基于HybridSRAM/DRAM结构的两种算法在SRAM的使用上均获得了显著的减少,后者明显优于前者.
尽管后者比前者更简单、高效,但在计数器管理算法[27]的实施上比较复杂.
Zhao等人[28]所提出的新的HybridSRAM/DRAMCounter结构在SRAM使用上是最优的,具有极为简单的控制逻辑,该算法满足高速链路的速度和存储要求.
4.
3Count-MinSketchCount-MinSketch[29]是一个次线性空间数据结构.
Count-MinSketch由二维数组构成,它的宽为w,深为d,数组的每个元素表示一个计数,即count[1,1],…,count[d,w].
数组的每个元素初始化为0,d个相互独立的Hash函数被均匀、随机地选择.
当更新(it,ct)到达时,表项tia被更新,ct被增加到每行的一个计数,如图2所示.
计数器是由Hash函数hj决定的,表示为count[j,hj(it)]←count[j,hj(it)]+ct.
+ct+ct+ct+ctithjFig.
2StructureofCount-MinSketch图2Count-MinSketch的结构Count-MinSketch所需要的存储空间由一个二维数组和d个Hash函数构成,二维数组需要wd个字的存储142JournalofSoftware软件学报Vol.
25,No.
1,January2014空间,每个Hash函数需要2个字的存储空间.
Count-MinSketch允许在数据流概要中进行基本的查询,如点查询、范围查询和内积查询,同时也可以用于解决数据流中重要的难题,如查找分位数、识别大流.
利用Count-MinSketch解决这些难题,所需要的时间和空间界限显著提高.
Count-MinSketch相当简单,已经应用于数据流的变化检测之中.
Count-MinSketch的不足之处在于,无法用来计算数据流的熵.
4.
4BloomFilterBloomFilter[30]是一种简单、高效的随机数据结构,利用一个m位的数组表示一个集合S={x1,x2,…,xn},初始化为0.
BloomFilter使用k个独立的Hash函数h1,h2,…,hk,Hash函数的取值范围为{1,2,…,m},主要包括初始化、元素插入和元素查询过程,具体实施方法如图3所示.
对任意一个元素x∈S,Hash函数hi映射到数组的位置hi(x)就会被置为1(1≤i≤k).
如果一个位置多次被置为1,那么只有第1次会起作用.
在查询过程中,对y进行k次Hash,如果数组中所有hi(y)的位置都是1(1≤i≤k),则认为y∈S;否则,认为y不属于S.
对于一些应用,只要误报率足够低,则误报是可接受的,如图2所示中的查询过程,y1不是集合中的元素,y2属于这个集合或是一个误报.
随着网络测量中数据量的飞速增长和有限的计算空间,BloomFilter及其变体在网络测量中得到广泛应用[30].
BloomFilter有一些变化形式,如Space-CodeBloomFilter[31],CountingBloomFilter[32],CompressedBloomFilter[32],SpectralBloomFilter[33],GeneralizedBloomFilter[34].
Fig.
3DemonstrationsofBloomFilter图3BloomFilter示例Space-CodeBloomFilter(SCBF)利用BloomFilter对数据进行大量的压缩以降低存储要求,同时,它通过多个解析度的设计来保证根据压缩后的数据能够估计流量数据中每个流包含的分组数.
SCBF以低存储、计算复杂性获得了合理的测量精度.
Space-CodeBloomFilter采用多组Hash函数,每组包含多个Hash函数,并通过这些Hash函数对流的关键字进行Hash计算.
根据计算结果,BloomFilter中对应的位被置为1.
由于Hash函数是随机选择的,对于一个流,它的每个分组到来时可能会选择同一组Hash函数或不同组的Hash函数.
但从概率上看,如果一个流包含的分组越多,那么被它选择的Hash函数组越多,BloomFilter中也就有更多的对应位被置为1.
为了解决这个问题,可以采用多个Space-CodeBloomFilter,每个具有不同的解析度,即Multi-ResolutionSpace-CodeBloomFilter(MRSCBF),每个SCBF对某一范围值(流的大小)有较高的精度.
因此,对于任意大小的流,都有一个适合的SCBF,使得对它的估计达到一定精度.
在BloomFilter中,插入元素是容易的,而不能通过逆过程删除一个元素.
如果对元素进行k次Hash运算,将对应的位置为0,其他的元素可能也被Hash到该位置,因此,BloomFilter不再正确地反映集合的所有元素.
CountingBloomFilter[32]克服了BloomFilter的不足,在CountingBloomFilter中,每个记录不是一个单独的位,而是一个小的计数器.
当一个项被插入时,相应的计数器增加;当一个项被删除时,相应的计数器减小.
研究表明,宽度为4位的计数器应该足够满足大部分应用.
CompressedBloomFilter[35]降低了BloomFilter的误报率,同时减少了每个项传输的位数.
SpectralBloomFilter[33]使得BloomFilter存储近似的多重集,并且支持频数查询.
有效负载分配是BloomFilter在网络测量中的另一个应用领域,有效负载系统的优点直接与有效负载的实际源、目的的不确定性的减少量有关.
当前的互联网架构允许恶意的主机伪装源地址发动DoS攻击,IP回溯法是鉴别恶意主机的有效方法.
IP回溯法主要包括两种类型:以概率标记具有部分路径信息的分组;以000000000000010010101010x1x2010010101010y1y2.
.
.
.
.
.
InitInsertSearch周爱平等:高速网络流量测量方法143BloomFilter的形式存储分组概要,通过迭代检查邻近的路由器重建攻击路径.
GeneralizedBloomFilter(GBF)[34]解决了无状态的单包IP回溯问题,以牺牲漏报率为代价,利用内置的保护抵制BloomFilter被篡改.
BloomFilter及其变体广泛应用于多种网络系统,如Web代理与缓存、数据库服务器、路由器[30].
4.
5CounterBraids细粒度的网络测量要求网络设备以高速链路速率更新大量计数器.
简单的方法需要SRAM存储计数器和流-计数器关联规则,使到达的分组能够以链路速率更新相应的计数器,导致准确的流测量变得复杂且昂贵,促进了检测与测量大流的近似算法.
统计计数器设计的应用和困难已经引起研究人员的广泛关注.
两种主要方法是:利用HybridSRAM/DRAM结构准确地计数[27,28];利用流长分布的重尾特性近似计数[15].
Lu等人[36]提出一种计数器架构,即CounterBraids.
CounterBraids有一个分层的结构:第l层由深度为dl位的ml个计数器构成.
令总层数为L,在实际应用中,L=2.
状态位位于第1层计数器,对应的计数器首次溢出,状态位被置为1.
状态位占据额外的空间,但为信息传输解码器提供了有用的信息.
进一步减少了第2层计数器的数量,在空间上获得一种均衡.
在计数器与第1层计数器之间,以及第1层计数器与第2层计数器之间,利用相同的随机映射,如图4中虚线箭头所示.
Fig.
4Two-LayerCounterBraids图4两层CounterBraids通过随机图编织分层的计数器,解决了流测量的计数器空间和流-计数器的关联问题.
通过共享流间计数器,显著减少了存储空间.
利用随机图避免了流-计数器关联的存储.
CounterBraids是渐近最优的,该算法能够获得最大的压缩率.
一种低复杂度信息传输解码算法,能够以零误差恢复流长,从而可以在硬件中实施.
BraidsCounter的缺点在于不支持流长的瞬间查询.
4.
6BRICK为了能够适应高速网络,Ramabhadran等人[27]提出了HybridSRAM/DRAM计数器架构,显著减少了SRAM开销,但同时也导致了通过系统总线SRAM与DRAM之间流量增加的问题.
被动计数器满足许多网络监控应用,还有许多应用需要活跃计数器,计数器需要频繁地读出.
在网络数据流算法[15,17,29,37]中,当分组到达时,需要读出计数器值,然后采取下一步的操作.
为了有效地维护准确的活跃计数器,Zhao等人[17]提出一种新的计数器架构,即BRICK(bucketizedrankindexedcounters),完全在SRAM中构建,每秒能够处理大量的分组,也不会产生SRAM与DRAM之间的流量.
该架构在SRAM中有效地存储宽度变化的计数器数组,支持快速更新和查询,也能够在硬件或软件中实施.
被动计数器对许多网络监控应用是足够的,而一些应用需要维护活跃计数器.
例如,如果Count-MinSketch[29]应用到大流检测,对每个分组需要读出计数器值,因为该读数将决定一个流是否需要插入到优先队列中.
Stanojevic等人[38]鉴别维护活跃计数器的数据流算法,包括用于大流检测的MultistageFilters[15]、在线分层的大流识别算法[39].
准确的活跃计数器将会节省这些应用的存储开销.
BRICK的基本思想是基于统计复用.
把计数器数组分成计数器数目相等的组,每组的计数器随机地从计数器数组中选择.
因此,每组的计数器具有变化的宽度.
假设计数器数组中计数器的平均宽度为γ,根据大数定律,在绝大多数分组中,计数d1bitsd2bitsm1countersm2countersCounterBraidsStatusbitFlows144JournalofSoftware软件学报Vol.
25,No.
1,January2014器的总宽度接近γ与每组计数器数目的乘积.
实际上,基准方法很难在硬件中实施,主要有两个原因:能够容易随机访问任意的计数器;非前缀编码技术用变长度的符号代替计数器值,使得存储空间更小,同时导致访问与修改数据的开销更大.
BRICK以稍微多一点的总SRAM费用克服了这些困难.
BRICK的关键技术是索引策略,即rankindexing[40]与更新该数据结构对ASIC实施不仅是简单的,而且通过内置的指令得到当前处理器的支持,使得软件实施是有效的.
因此,该方法能够在硬件或软件中得以有效实施.
5基于抽样与数据流方法的应用抽样与数据流方法是高速网络流量测量的重要方法,广泛应用于大流识别、流长分布估计等.
本节主要从大流识别、流长分布估计、异常检测和超点检测应用角度介绍高速网络流量测量方法,并比较不同方法的优劣.
5.
1大流识别在互联网中,少量的大流占据了网络流量的大部分,它们对于网络计费、流量工程等应用非常重要.
在高速网络环境下,存在巨大的网络流,缓存所有流信息需要较大的内存.
由于在路由器等网络设备中SRAM非常昂贵,而DRAM又无法达到线速的要求,因此,抽样与数据流技术应用在高速链路上的大流识别显得尤为重要.
抽样技术已经广泛应用于大流识别.
Duffield等人[41]提出SmartSampling算法,该算法是一种针对流记录的非均匀抽样.
SmartSampling的基本思想是:对象x的抽样概率函数pz(x)=min{1,x/z},流长x大于阈值z的流以概率100%被抽样,而流长x小于阈值z的流以概率x/z被抽样.
小流被抽样的概率与其大小有关,同时通过抽样阈值z控制SmartSampling.
重正化函数rz(x)=max{x,z},其对小流产生偏大的估计z,对于一些应用,可能认为是不利的,如流量计费,过高地估计了用户使用的网络流量.
然而,若计费策略与阈值抽样相结合,则能够提高流量估计的精度.
z越大,被抽样的对象数越少,误差越高;z越小,被抽样的对象数越多,误差越低.
与均匀抽样相比,SmartSampling对大流的估计具有更高的准确性.
Cristian等人[15]提出两种大流识别方法,即MultistageFilters,SampleandHold.
MultistageFilters和SampleandHold具有相似的性能,SampleandHold的优势在于实施简单;而MultistageFilters的优势在于高精度,但却更加复杂.
与SampledNetFlow[7]相比,在相同大小的SRAM下,MultistageFilters和SampleandHold的相对误差与SRAM的大小成反比,而SampledNetFlow的相对误差与SRAM大小的平方根成反比,因此,MultistageFilters和SampleandHold具有更高的精度,SampledNetflow具有更少的访问内存的次数.
它们的不足之处在于:被识别大流的数量受到SRAM存储大小的限制.
Mori等人[42]提出一种大流识别方法,该方法由两个阶段组成:首先,利用截断Pareto分布从抽样流推断原始流长分布;然后,通过Bays定理识别大流.
该方法提供一个灵活的架构,在给定的抽样率下,使得误报与漏报达到一个合理的均衡.
与SampleandHold和MultistageFilters相比,该方法不需要处理每个分组,因此适合于部署在高速网络中.
多数大流识别方法的不足表现在:不能准确地估计流长或不能维护所有大流的流记录.
Lall等人[43]提出一种HybridSRAM/DRAM算法,通过SRAM中的SpectralBloomFilter数据结构维护每个流的近似计数,利用该近似值,以更大的概率对中流和大流进行抽样,将抽样的分组存储到DRAM中的流表.
与SampleandHold和MultistageFilter相比,该方法能够精确地识别所有的大流和中流.
在流量测量中,每种流方法缺乏可扩展性.
在高速链路上,网络流数是巨大的,绝大部分网络流量是由少数大流产生的,而少部分网络流量由多数小流产生.
因此,减小小流的抽样率可能是避免误报的一种合理的策略.
SampleandHold的不足在于准确性和存储要求的均衡,为了获得合理的准确性,必须提高抽样率,从而导致小流识别增加了存储开销.
在SampleandHold和MultistageFilters中,需要的缓存依赖于它们阻止进入流缓存的小流数量.
因此,Raspall等人[44]提出S3(shared-statesampling),S3是SampleandHold和MultistateFilters的扩展.
S3的优势在于:适应于现有的存储技术,允许在DRAM中部分实施.
S3的关键问题在于:如何降低小流的检测率,同时不影响大流的检测率.
S3的不准确性来源于抽样的不确定性和冲突的影响.
SHa[45]与S3的不同之处在于:SHa仅更新每个抽样分组的流记录.
该方法有两个显著的特性:其一,不需要处理每个分组,根据抽样率可以调整计算开销,使得该方法具有轻量级的特性及可扩展性和灵活性,从而可以在DRAM中实现;其二,存储大小不受流量变化的影响,使得该方法适合于流量工程.
另外一个优势在于容易配置.
该方法能够有效地识别大流和准确地周爱平等:高速网络流量测量方法145估计其大小.
基于Bays定理,Mori等人[46]提出基于周期分组抽样的大流识别方法,与其他大流识别方法的不同之处在于,它的通用性和不需要处理每个分组,这样可能减少实施费用和操作开销.
在给定的抽样率下,该方法使得误报率和漏报率达到合理的均衡.
该方法的不足之处在于:无法获得原始流长的概率分布.
在高速网络环境下,由于受到计算和存储资源的限制,准确、实时地识别大流对于检测大规模网络安全事件具有重要的意义.
随着骨干网链路带宽的增加和应用类型的多样化,海量的网络流给网络流量的测量与分析带来极大的困难.
抽样技术成为减少存储和时间复杂性的有效方法.
抽样技术在大流识别方面已取得一些研究成果.
为了进一步提高大流识别的精度和实时性,数据流技术在大流识别中也取得了一些研究成果.
Zhang等人[47]提出一种新的加权数据流频繁项挖掘算法,能够提供单数据项最坏处理时间为O(1)的处理速度.
采用一个部分排序的数据结构POSS(partially-ordered-stream-summary),能够在保证处理速度的同时,尽量降低算法的存储开销.
Alon等人[48]的研究结果表明:利用次线性于数据流的不同元素个数的存储空间中,不能准确地得到大流的大小;然而,有限的存储能够近似估计大流的流长[15].
LossyCounting[49]是一种基于计数器的大流识别算法,误差界限对于表中不同元素的流标识是该算法的一个重要参数,重要性在于小误差界限的元素移走的可能性高于大误差界限的元素.
基于该重要性和网络流长的重尾分布特征,Dimitropoulos等人[50]提出ProbabilisticLossyCounting算法,存储开销低于LossyCounting与MultistageFilters,减小了LossyCounting的误报率,尽管估计误差稍微高于LossyCounting,但仍然较低.
Babcock等人[51]从分布式环境角度提出大流识别方法,在不同的位置观察多个数据流,找到全局上排序靠前的大流,同时使得不同位置之间的通信开销最小化.
表1比较了大流识别算法的性能,其中,en表示识别的大流数,ne表示识别的大流中真实流数,Ne表示实际的大流总数.
Table1Comparisonsofperformanceforheavyhitteridentificationalgorithms表1大流识别算法的性能比较ReferencesHeavyhitteridentificationalgorithmsPerformanceevaluationAccuracyMemoryconsumptionRef.
[15]MultistageFilters,SampleandHold,SampledNetFlowMFandS&HhashigheraccuracythanSampledNetFlowMFandS&HreducesmemoryoverheadRef.
[41]SmartSampling,UniformSamplingS&ShashigheraccuracythanUniformSamplingRef.
[44]Shared-StateSampling,SampleandHold,MultistageFilters,StickySampling,LossyCountingLCandS2hashigheraccuracythanS&H,MFandS3MForS3requirestheminimalflowmemoryRef.
[45]SampleandHashS&HidentifiesheavyhitterswithhighprobabilityandaccuratelymeasuringtheirsizeS&HrequiresconstantmemoryRef.
[46]PeriodicSampling1/,1/feefeeRnnRnN+Ref.
[47]WLC,OWLC,SpaceSaving,LossyCountingWLChassimilaraccuracywithotheralgorithmsWLCrequiresmuchlessmemorythanthetheoreticalboundinpracticeRef.
[50]ProbabilisticLossyCounting,LossyCounting,MultistageFiltersPLChassimilaraccuracywithMF;PLChasslightlyworseaccuracythanLCPLCusesfewermemorythanLCandMFRef.
[52]CCBF,MultistageFiltersCCBFhashigheraccuracythanMFunderthesamememory5.
2流长分布估计流长分布对于流量建模和网络管理是非常重要的测度.
流长分布有助于服务提供商推断网络的使用模式;流长分布有助于检测引起全局的网络动力学模式变换的事件;流长分布有助于检测各种互联网安全攻击.
对于流长分布估计,简单的方法是使用一个由每个流的计数器构成的Hash表,跟踪所有的活跃流,通过计数器值估计流长分布.
虽然该方法比较简单,但不适用于高速链路.
另外一种方法是选择少量的分组,然后从抽样的流量推断流长分布[53],该算法能够从抽样数据获得尽可能多的信息,而它的估计精度受到低抽样率的影响.
基于分组抽样的流长分布估计精度不高,虽然FS(flowsampling)获得大量的统计信息,但需要消耗大量的存储和处理资源.
DualSampling[54]在使用相同的存储处理资源下,能够提供类似于FS的网络流统计信息.
该抽146JournalofSoftware软件学报Vol.
25,No.
1,January2014样方法获得优于其他分组抽样方法的流长分布估计精度,但却不如流抽样算法.
由于通过分组抽样方法获得的所有数据中大部分分组来源于大流,仅有少部分分组来源于小流和中流,小流和中流的信息丢失显著地影响各种网络统计信息估计的精度.
然而,只有储存每个流的信息才能获得每个流的准确大小,在高速链路上所付出的代价是相当高的.
SGS(sketch-guidedsampling)[39]通过牺牲大流的抽样率来提高小流和中流的抽样率,获得了更准确的各种网络统计信息估计.
该方法的不足之处在于:采用简单的Hash表对所有流长作近似估计,导致空间效率低,小流的流长估计误差较大.
虽然利用两级存储结构的统计计数器[26]和MRSCBF[31]能够支持线速更新,却不能支持线速读取.
SGS算法的高空间复杂度导致其实施代价较高,并影响了其部署的灵活性.
多数抽样方法存在小流估计精度不高的问题.
最简单的分组抽样方法StaticSampling(SS)对所有流使用相同的抽样率p对分组进行抽样.
研究结果表明:抽样率p越小,相对误差越大,因此,小流不能够准确地被估计;而抽样率越大,相对误差越小,导致存储空间增加与抽样的目的相矛盾.
根据计数器值调整抽样率,AdaptiveNon-LinearSampling(ANLS)[9]能够解决小流估计精度不高的问题.
该抽样方法显著地提高了流长估计精度(尤其是对于小流而言),节约了存储开销;同时,在相同的估计精度下使用较小的存储空间,流长分布对估计精度没有影响.
Yang等人[55]提出基于分组抽样的流长分布估计算法,该算法有效地克服了抽样带来的有偏性,实现了流长分布与活跃流数估计的分离.
Ribeiro等人[56]利用抽样分组的Fisher信息测度估计流长分布.
网络流长分布具有重尾特性,流长分布依赖于其尾指数,绝大部分算法通过简化假设仅获得近似估计.
Loisean等人[57]利用抽样数据获得准确的流长分布尾指数的极大似然估计,从而有利于流长分布的精确估计.
Kumar等人[37]提出适用于高速链路的数据流算法,该算法由在线流模块和离线处理模块构成,如图5所示.
在线流模块中,使用由一个计数器数组构成的数据结构,具有较低的存储和计算复杂性;在离线处理模块中,利用在线流模块获得的计数器值能够准确地估计流的总数,而因Hash冲突难以准确估计流长分布.
因此,利用Bays统计方法推断流长分布估计.
与基于分组抽样方法相比,该方法获得高于一个数量级的估计精度.
在此基础上,提出了流长分布的多分辨率估计方法,当流的总数远多于计数器数组的大小时,该方法获得的流长分布估计精度稍微下降,从而使得在平均情况下,流长分布估计准确且存储有效;而在最坏情况下,流长分布精度仅稍微有所下降.
Fig.
5Flowchartofflowsizedistributionestimationbasedondatastreaming图5基于数据流的流长分布估计的流程图5.
3异常检测互联网规模的增大、应用类型的多样化以及网络安全事件都会造成网络流量异常.
由于互联网流量每年呈上升趋势,如何对高速骨干网络流量进行实时监测、及时地发现网络流量异常并追踪定位异常源,并做出合理的响应,是保证网络有效运行的重要措施.
异常检测主要分为两类:基于特征的检测和基于统计的检测.
两类检测方法各有优、缺点:基于特征的检测方法的优点是能够准确地检测已知的异常,其缺点是不能检测未知的异常,同时需要预先设定特征库,特征库的规模将影响检测性能;基于统计的检测方法的优点是能够准确地检测已知的和未知的异常,同时不需要预先设定特征库.
因此,基于特征的检测不适用于高速骨干网络[58].
为了满足在高速网络环境下实时处理的要求,抽样与数据流技术已经成为可扩展互联网流量测量与异常检测的重要组成HeaderHeaderHeader.
.
.
OnlinestreamingmoduleOfflineprocessingmoduleUpdateRawstreamingresultFlowdistributionPacketstream周爱平等:高速网络流量测量方法147部分.
分组抽样对网络异常检测的影响已得到广泛研究.
Mai等人[59]评价了分组抽样对3种端口扫描检测算法的影响,表明分组抽样降低了3种算法的检测率,增加了误报率.
Brauckhoff等人[60]评价了分组抽样对异常检测测度的影响,表明通过分组抽样能够获得准确的字节数和分组数估计,而不能够获得准确的流数估计.
然而,特征熵测度受到分组抽样的影响较小,甚至在高抽样率下能够有效检测Blasterworm.
由于分组抽样降低异常检测率,Ali等人[61]提出渐进的安全感知分组抽样方法,通过抽样更多的恶意分组,使异常检测器获得更高的检测率.
该算法具有较低的复杂性,没有通信开销.
与随机分组抽样相比,该算法对所有的异常检测算法均有较高的检测率.
程光等人[62]在高速网络环境下建立了基于抽样的实时异常检测模型,实现了在系统资源可控范围内检测异常行为.
在高速链路上,流抽样是非常有吸引力的、可扩展的获取流统计信息的测量方法.
流抽样对网络异常检测的影响已经得到广泛的研究.
研究表明,网络异常产生大量的小流,如networkscans,SYNflooding,worms.
Mai等人[63]分析了流抽样技术对流量异常与端口扫描异常检测算法的影响,表明SmartSampling与SampleandHold能够准确地估计大流,而显著地降低流量异常和端口扫描检测精度.
Androulidakis等人[64]评价与分析了两级抽样技术[55]对网络异常检测的影响.
抽样数据是不全面的、有偏的原始流量的近似.
由此,提出增强的两级选择抽样方法,通过智能的流抽样优先选择小流.
甚至在小攻击、小抽样率下,该算法显著地提高了异常检测精度,而在大部分情况下甚至优于未抽样算法.
Androulidakis等人[65]提出的流抽样算法侧重于选择小流,提高了异常检测性能,同时减少了被选择的流数.
Androulidakis等人[66]通过基于熵的异常检测算法,评价机会流抽样对不同网络异常的影响.
因此,观察不同类型异常的网络流量特征、选择合适的抽样方法优先地抽取流量数据,进一步减少了抽样数据,能够有效地提高异常检测性能.
随着网络带宽的快速增长和新攻击、病毒、蠕虫的不断出现,传统入侵检测系统中的异常检测算法无法满足高速网络的要求.
Li等人[67]通过数据流技术设计了一个流级入侵检测系统,与传统入侵检测系统相比,该系统可扩展到高速网络流级检测,能够识别SYN泛洪与各种端口扫描,能够进行基于多点的聚合检测,从检测中分离异常,减少误报.
郑军等人[68]提出一种基于数据流的大规模网络异常发现算法,首次将数据流模型用于大规模网络的异常发现.
罗娜等人[58]提出一种基于概要数据结构的异常检测方法.
基于观测值与预测值之间的差异,sketch采用均值均方差模型建立网络流量变化参考模型.
该方法能够检测DDoS、扫描等攻击行为,并能追溯异常的IP地址,利用少量的计算与存储资源,因此适用于高速骨干网络上的异常检测.
郑黎明等人[69]利用数据流中概要数据结构的思想,提出Filter-ary-Sketch数据结构,在该数据结构上采用基于熵的异常检测算法在骨干网上进行异常检测.
该算法能够检测多种类型的网络攻击,且能有效地进行恶意流量阻断,但缺乏理论上的精度保证.
5.
4超点检测在高速链路上实时、准确地检测网络安全事件,如DDoS攻击、端口扫描、蠕虫传播等,对网络安全和网络管理具有重要意义.
这些安全事件具有类似的行为特征,如:端口扫描和蠕虫传播是由在短时间内源主机与不同目的主机建立大量的连接引起的,而DDoS攻击是由大量的主机泛洪到一个目的主机引起的.
它们的共同特点是:源(目的)主机发送或接收到大量来自于不同目的(源)主机的连接.
超点是指在测量时间内与大量源(目的)主机连接的目的(源)主机,超点检测是指检测在测量时间内发送或接收大量流数的源(目的)主机.
维护流存在的状态信息和地址的状态信息,是超点检测的难点.
抽样与数据流方法已经应用于高速链路上的超点检测.
Venkataraman等人[18]通过存储与处理少量的网络流量,极大地减少了所需的存储空间并降低了计算复杂度,该抽样方法的准确性很大程度上依赖于抽样率.
Kamiyama等人[70]提出基于流抽样的超点检测方法,在给定的内存大小和处理时间要求下,根据流量模式变化,该方法能够自适应地优化BloomFilter和HostTable参数,从而有效地检测超点.
研究发现,基于哈希流抽样算法不能有效地扩展到更高速的网络环境中(2.
5Gbps以上).
针对该问题,王洪波等人[71]提出一种基于BloomFilter流抽样的超点检测算法,在高速网络环境下,能够快速、准确地检测超点.
该算法的不足之处在于:需要专用的硬148JournalofSoftware软件学报Vol.
25,No.
1,January2014件以及高速存储器.
程光等人[72]提出一种具有自适应抽样功能的超点实时检测算法,该算法结合多种网络测量技术,表明在自适应性、资源可控性、测量精度等方面优于Sampled和Bitmap等算法,能够实现高速网络上超点高精度实时检测.
Shi等人[73]提出基于抽样与数据流技术的在线架构,用于检测TopSpreaders与TopScanners.
该算法提高了检测精度,同时减少了内存使用和CUP处理时间.
Zhao等人[74]提出两种基于抽样与数据流方法的超点检测方法:第1种超点检测算法是在基于Hash的流抽样算法的基础上提出来的,通过数据流模块进一步过滤抽样流量,允许更高的抽样率,获得更高的检测精度;第2种超点检测算法结合了数据流在高效保存、估计与已知源/目的相关的扇出/扇入的能力和抽样在产生候选源/目的的列表的能力,虽然该算法更加复杂,但却获得了更好的检测精度.
Wang等人[20]对该数据结构[13]加以改进,提出了一种超点检测的有效保留算法.
虚拟索引方法VCDS(virtualconnectiondegreesketch)[22]应用于超点检测.
由于VCDS需要大量的额外内存来存储节点地址,而新的数据结构RVCDS(reversiblevirtualconnectiondegreeskecth)识别超点地址,不需要额外的内存空间,只是估计误差略微有所增加.
此外,将VCDS、RVCDS与均匀流抽样技术相结合,能够有效地减少内存复杂度.
6高速网络流量测量技术的研究成果本节概述了目前国内外高速网络流量测量技术的主要研究成果,并从评价指标方面比较了各种网络流量测量技术的测量精度和实施性.
研究表明,绝大多数网络流量测量技术获得了较高的测量精度,具有可实施性.
随着带宽的快速增长和数据流的急剧增加,高速网络流量测量技术成为必然的发展趋势,已经引起许多研究机构和学者的广泛关注.
抽样和数据流方法是高速网络流量测量技术的重要组成部分,广泛应用于网络管理、网络安全等应用.
虽然分组抽样方法降低了存储和处理开销,但同时也给网络流量测量带来了许多不确定性,如降低异常检测的检测率、不准确的流的大小估计.
由于构成网络流量的分组并不是孤立的,它们是为了完成应用功能而产生的,它们之间存在着一定的关联.
因此,流抽样方法广泛应用于大流识别、流长分布、异常检测以及超点检测之中,均获得了较好的性能.
尽管抽样方法产生了一个原始数据的代表子集,每个被抽样对象都确实存在于原始数据中,但是,从这些数据推断出的关于原始对象的结论却并不一定准确.
如果能够从原始数据产生一些概要信息,这些信息能够支持一些常规的查询,而且其结果具有相同或者更好的准确性,同时,这种方法需要更小的存储或计算需求、具有更小的响应时间.
于是,数据流方法应运而生.
数据流方法具有执行一趟计算,而且只需要使用有限的计算和内存资源的特性,广泛应用于流长分布估计、熵估计、连接度估计等.
实际上,每种网络流量测量方法是针对具体的应用而提出的,具有一定的局限性,因而,多种网络流量测量方法的有效结合,有助于提高算法的测量精度.
两种分组抽样方法的结合[54]、分组抽样和流抽样方法的结合[75]、抽样方法与数据流方法的结合[73,74,76],均有利于提高算法的性能.
抽样方法和数据流方法相结合,已经应用于网络测量与网络安全之中.
研究发现,抽样方法和数据流方法适用于捕获信息谱中不同和互补的区域,抽样方法和数据流方法的结合,能够恢复完整的信息.
在此基础上,Zhao等人[74]提出基于抽样与数据流方法的超点检测方法.
许多研究主要集中在总体流的流长分布估计[37,53]上,而估计子总体流的流长分布是更具挑战性.
子总体流的流长分布估计主要有两个方面的困难:其一,不能事先知道子总体流;其二,子总体流的数量是巨大的.
Kumar等人[76]提出任意子总体流的流长分布估计算法,该算法由两个并行的数据采集模块和一个统计估计模块构成.
抽样模块类似于NetFlow的分组抽样,数据流模块由一个计数器数组构成.
利用抽样模块和数据流模块采集的数据,通过统计估计模块获得准确的子总体流的流长分布估计.
7讨论7.
1主要问题虽然网络流量测量的研究取得了显著的进展,但大部分属于理论分析,与实际应用还存在一定的差距.
目前,我们认为网络流量测量还存在以下几方面的问题:(1)抽样方法对数据进行有效压缩,同时又能保留流量的原始特征信息,有效地缓解了网络测量的处理和存储困难,然而估计却存在较大误差;(2)存储技术的发展滞后周爱平等:高速网络流量测量方法149于高速链路速率的增长,导致无法满足一些网络应用的实时性要求;(3)网络流量测量的可扩展性问题,现有的许多网络测量方法往往是针对具体的应用需求,不能够扩展到高速网络环境,造成了许多资源的低效利用;(4)网络流量测量方法评价指标量化的问题,评价指标的合理量化值得深入研究;(5)小流的识别问题,在实际的网络环境中,许多攻击是由小流组成的,高速链路上网络流量中大部分是小流,无法实时地监测每个小流;(6)高速网络环境下并发连接度检测问题;(7)分布式网络测量问题;(8)高速链路上数据流入侵检测系统的构建问题.
7.
2发展趋势和未来的研究方向综合上述讨论,我们认为,高速网络流量测量技术的发展趋势和未来的研究方向包括:(1)可重构硬件成为网络设备未来的发展趋势,可重构技术使得网络流量测量与分析功能以组件的形式集成到网络设备中成为可能,目前,Cisco的NetFlow、InMon的sFlow以软件组件的形式提供给用户,软件组件的缺陷是性能较差,而可重构硬件组件能够满足高性能的需求;(2)无线网络的流量测量方法研究,现有的有线网络测量方法在无线网络测量中的适用性、可扩展性以及针对无线网络特性的新测量方法研究;(3)随着移动通信网络和Web技术的发展,以微博为代表的在线社交网络已成为人们信息共享和舆论传播的重要媒介,利用网络测量方法了解其网络拓扑特征与用户行为特征等基本属性,已成为网络流量测量研究与发展的趋势之一;(4)利用云计算平台强大的数据处理能力来处理海量网络流量,提高网络流量测量的效率,已成为网络流量测量研究与发展趋势之一;(5)网络流量测量方法应具有可扩展性的能力,以满足多种网络应用需求;(6)针对高速网络中节点连接度检测问题,在深入分析高速链路上数据流特性的基础上,设计出更高效的数据结构来组织数量庞大的并发连接记录,以支持更快的查询等操作;(7)针对现有的大部分抽样方法对小流估计存在的较大误差,自适应的抽样方法动态地调整抽样率,有利于提高估计精度;(8)抽样方法和数据流方法通常适合于获取信息谱中不同的和互补的信息域,抽样方法与数据流方法相结合,能够有助于恢复完全的信息;(9)针对小流的检测问题,可以通过流抽样和数据流方法减少处理和存储开销;(10)分布式网络测量实施;(11)构建适用于高速链路上的数据流入侵检测系统.
8总结近年来,随着链路速率的提高和网络应用的多样化,巨大的数据流给网络流量测量与分析带来挑战,高速网络流量测量方法逐渐成为研究的热点之一.
高速网络流量测量方法大致经历了一个"报文抽样-流抽样-数据流"的发展历程.
高速网络流量测量方法的主要目标是:在保证一定准确性的前提下降低所需要的处理和存储开销.
本文将高速网络流量测量方法分为抽样方法和数据流方法,在此基础上,介绍了抽样方法和数据流及其应用,利用统计学方法对获得的流量信息进行推断,分析了它们的各种网络统计信息量的精度、计算和存储复杂度,指出了它们的不足之处.
提出了高速网络流量测量方法存在的主要问题、发展趋势以及未来的研究方向.
References:[1]ChengG,GongJ.
InternetFlowMeasurement.
Nanjing:SoutheastUniversityPress,2008(inChinese).
[2]http://www.
edu.
cn[3]ChengG,TangYN.
Estimationalgorithmsoftheflownumberfromsampledpacketsonapproximateapproaches.
RuanJianXueBao/JournalofSoftware,2013,24(2):255265(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/4316.
htm[doi:10.
3724/SP.
J.
1001.
2013.
04316][4]MuthukrishnanS.
Datastreams:Algorithmsandapplications.
FoundationsandTrendsinTheoreticalComputerScience,2005,1(2):117236.
[doi:10.
1561/0400000002][5]HeGH,HouJC.
Onsamplingself-similarInternettraffic.
ComputerNetworks,2006,50(16):29192936.
[doi:10.
1016/j.
comnet.
2005.
11.
009][6]RaspallF.
Efficientpacketsamplingforaccuratetrafficmeasurements.
ComputerNetworks,2012,56(6):16671684.
[doi:10.
1016/j.
comnet.
2011.
11.
017]150JournalofSoftware软件学报Vol.
25,No.
1,January2014[7]EstanC,KeysK,MooreD,VargheseG.
Buildingabetternetflow.
ACMSIGCOMMComputerCommunicationReview,2004,34(4):245256.
[doi:10.
1145/1030194.
1015495][8]Sanjuàs-CuxartJ,Barlet-RosP,DuffieldN,KompellaR.
Cuckoosampling:Robustcollectionofflowaggregatesunderafixedmemorybudget.
In:Proc.
ofthe31stAnnualIEEEInt'lConf.
onComputerCommunications(Mini-Conf.
).
Orlando:IEEE,2012.
27512755.
[doi:10.
1109/INFCOM.
2012.
6195693][9]HuCC,LiuB,WangS,TianJ,ChengY,ChenY.
ANLS:Adaptivenon-linearsamplingmethodforaccurateflowsizemeasurement.
IEEETrans.
onCommunications,2012,60(3):789798.
[doi:10.
1109/TCOMM.
2011.
112311.
100622][10]MaXY,HuCC,JiangJC,WangJ.
S3:Smartselectionofsamplingfunctionforpassivenetworkmeasurement.
In:Proc.
ofthe36thAnnualIEEEConf.
onLocalComputerNetworks.
Bonn:IEEE,2011.
416423.
[doi:10.
1109/LCN.
2011.
6115368][11]Carela-EspanolV,Barlet-RosP,Cabellos-AparicioA,Sol-ParetaJ.
Analysisoftheimpactofsamplingonnetflowtrafficclassification.
ComputerNetworks,2011,55(5):10831099.
[doi:10.
1016/j.
comnet.
2010.
11.
002][12]ChakrabartiA,DoBaK,MuthukrishnanS.
Estimatingentropyandentropynormondatastreams.
InternetMathematics,2011,3(1):6378.
[doi:10.
1080/15427951.
2006.
10129117][13]AlonN,MatiasY,SzegedyM.
Thespacecomplexityofapproximatingthefrequencymoments.
JournalofComputerandSystemSciences,1999,58(1):137147.
[doi:10.
1006/jcss.
1997.
1545][14]LallA,SekarV,OginaraM,XuJ,ZhangH.
Datastreamingalgorithmsforestimatingentropyofnetworktraffic.
ACMSIGCOMMComputerCommunicationReview,2006,34(1):145156.
[doi:10.
1145/1140103.
1140295][15]EstanC,VargheseG.
Newdirectionsintrafficmeasurementandaccounting.
ACMSIGCOMMComputerCommunicationReview,2002,32(4):323336.
[doi:10.
1145/964725.
633056][16]ZhaoHC,LallA,OgiharaM,SpatscheckO,WangJ,XuJ.
AdatastreamingalgorithmforestimatingentropiesofODflows.
In:Proc.
ofthe7thACMSIGCOMMConf.
onInternetMeasurement.
NewYork:ACMPress,2007.
279290.
[doi:10.
1145/1298306.
1298345][17]ZhaoQ,KumarA,WangJ,XuJ.
Datastreamingalgorithmsforaccurateandefficientmeasurementoftrafficandflowmatrices.
ACMSIGMETRICSPerformanceEvaluationReview,2005,33(1):350361.
[doi:10.
1145/1071690.
1064258][18]VenkataramanS,SongD,GibbonsPB,BlumA.
Newstreamingalgorithmsforfastdetectionofsuperspreaders.
In:Proc.
oftheNetworkandDistributedSystemSecuritySymp.
SanDiego:theInternetSociety,2005.
149166.
http://citeseerx.
ist.
psu.
edu/viewdoc/summarydoi=10.
1.
1.
133.
1592[19]GuanXH,WangPH,QinT.
Anewdatastreamingmethodforlocatinghostswithlargeconnectiondegree.
In:Proc.
oftheIEEEGLOBECOMTelecommunicationsConf.
Honolulu:IEEE,2009.
16.
[doi:10.
1109/GLOCOM.
2009.
5426280][20]WangPH,GuanXH,QinT,HuangQZ.
Adatastreamingmethodformonitoringhostconnectiondegreesofhigh-speedlinks.
IEEETrans.
onInformationForensicsandSecurity,2011,6(3):10861098.
[doi:10.
1109/TIFS.
2011.
2123094][21]YoonMK.
LiT,ChenSG,PeirJK.
Fitaspreadestimatorinsmallmemory.
In:Proc.
ofthe28thConf.
onComputerCommunications.
RiodeJaneiro:IEEE,2009.
504512.
[doi:10.
1109/INFCOM.
2009.
5061956][22]WangPH,GuanXH,TowsleyD,TaoJ.
Virtualindexingbasedmethodsforestimatingnodeconnectiondegrees.
ComputerNetworks,2012,56(12):27732787.
[doi:10.
1016/j.
comnet.
2012.
03.
025][23]EstanC,VargheseG,FiskM.
Bitmapalgorithmsforcountingactiveflowsonhigh-speedlinks.
IEEE/ACMTrans.
onNetworking,2006,14(5):925937.
[doi:10.
1109/TIFS.
2011.
2123094][24]KimHA,O'HallaronDR.
Countingnetworkflowsinrealtime.
In:Proc.
oftheIEEEGlobalTelecommunicationsConf.
2003.
38883893.
[doi:10.
1109/GLOCOM.
2003.
1258959][25]Sanjuàs-CuxartJ,Barlet-RosP,Solé-ParetaJ.
Countingflowsoverslidingwindowsinhighspeednetworks.
In:Proc.
oftheNetworking.
LNCS5550,2009.
7991.
[doi:10.
1007/978-3-642-01399-7_7][26]ShahD,IyerS,PrahhakarB,McKeownN.
Maintainingstatisticscountersinrouterlinecards.
IEEEMicro,2002,22(1):7681.
[doi:10.
1109/40.
988692][27]RamabhadranS,VargheseG.
Efficientimplementationofastatisticscounterarchitecture.
ACMSIGMETRICSPerformanceEvaluationReview,2003,31(1):261271.
[doi:10.
1145/885651.
781060]周爱平等:高速网络流量测量方法151[28]ZhaoQ,XuJ,LiuZ.
Designofanovelstatisticscounterarchitecturewithoptimalspaceandtimeefficiency.
ACMSIGMETRICSPerformanceEvaluationReview,2006,34(1):323334.
[doi:10.
1145/1140103.
1140314][29]CormodeG,MuthukrisnanS.
Animproveddatastreamsummary:Thecount-minsketchanditsapplications.
JournalofAlgorithms,2005,55(1):5875.
[doi:10.
1016/j.
jalgor.
2003.
12.
001][30]TarkomaS,RothenbergCE,LagerspetzE.
Theoryandpracticeofbloomfiltersfordistributedsystems.
IEEECommunicationsSurveys&Tutorials,2012,14(1):131155.
[doi:10.
1109/SURV.
2011.
031611.
00024][31]KumarA,XuJ,LiL,WangJ.
Space-Codebloomfilterforefficienttrafficflowmeasurement.
In:Proc.
ofthe3rdACMSIGCOMMConf.
onInternetMeasurement.
NewYork:ACMPress,2003.
167172.
[doi:10.
1145/948205.
948226][32]BroderA,MitzenmacherM.
Networkapplicationsofbloomfilters:Asurvey.
InternetMathematics,2004,1(4):485509.
[doi:10.
1080/15427951.
2004.
10129096][33]CohenS,MatiasY.
SpectralBloomFilter.
In:Proc.
ofthe2003ACMSIGMODInt'lConf.
onManagementofData.
NewYork:ACMPress,2003.
241252.
[doi:10.
1145/872757.
872787][34]LauferRP,VellosoPB,CunhaDO,MoraesIM,BicudoMDD,MoreiraMDD,DuarteOCMB.
Towardsstatelesssingle-packetIPtraceback.
In:Proc.
ofthe32ndIEEEConf.
onLocalComputerNetworks.
Dublin:IEEE,2007.
548555.
[doi:10.
1109/LCN.
2007.
15][35]MitzenmacherM.
CompressedBloomFilters.
IEEE/ACMTrans.
onNetworking,2002,10(5):604612.
[doi:10.
1109/TNET.
2002.
803864][36]LuL,MontanariA,PrabhakarB,DharmapurikarS,KabbaniA.
Counterbraids:Anovelcounterarchitectureforper-flowmeasurement.
ACMSIGMETRICSPerformanceEvaluationReview,2008,36(1):121132.
[doi:10.
1145/1384529.
1375472][37]KumarA,SungM,XuJ,WangJ.
Datastreamingalgorithmsforefficientandaccurateestimationofflowsizedistribution.
ACMSIGMETRICSPerformanceEvaluationReview,2004,32(1):177188.
[doi:10.
1145/1012888.
1005709][38]StanojevicR.
Smallactivecounters.
In:Proc.
ofthe26thIEEEInt'lConf.
onComputerCommunications.
Anchorage:IEEE,2007.
21532161.
[doi:10.
1109/INFCOM.
2007.
249][39]KumarA,XuJ.
Sketchguidedsampling—Usingon-lineestimatesofflowsizeforadaptivedatacollection.
In:Proc.
ofthe25thIEEEInt'lConf.
onComputerCommunications.
Barcelona:IEEE,2006.
111.
[doi:10.
1109/INFOCOM.
2006.
326][40]HuaN,ZhaoHQ,LinB,XuJ.
Rank-Indexedhashing:AcompactconstructionofBloomFiltersandvariants.
In:Proc.
oftheIEEEInt'lConf.
onNetworkProtocol.
Orlando:IEEE,2008.
7382.
[doi:10.
1109/ICNP.
2008.
4697026][41]DuffieldN,LundC.
PredictingresourceusageandestimationaccuracyinanIPflowmeasurementcollectioninfrastructure.
In:Proc.
ofthe3rdACMSIGCOMMConf.
onInternetMeasurement.
NewYork:ACMPress,2003.
179191.
[doi:10.
1145/948205.
948228][42]MoriT,TakineT,PanJP,KawaharaR,UchidaM,GotoS.
Identifyingheavy-hitterflowsfromsampledflowstatistics.
IEICETrans.
onCommunications,2007,E90-B(11):30613072.
[doi:10.
1093/ietcom/e90-b.
11.
306][43]LallA,OgiharaM,XuJ.
Anefficientalgorithmformeasuringmediumtolarge-sizedflowsinnetworktraffic.
In:Proc.
ofthe28thConf.
onComputerCommunications.
RiodeJaneiro:IEEE,2009.
27112715.
[doi:10.
1109/INFCOM.
2009.
5062217][44]RaspallF,SallentS,YuferaJ.
Shared-Statesampling.
In:Proc.
ofthe6thACMSIGCOMMConf.
onInternetMeasurement.
NewYork:ACMPress,2006.
114.
[doi:10.
1145/1177080.
1177082][45]RaspallF,SallentS.
Adaptiveshared-statesampling.
In:Proc.
ofthe8thACMSIGCOMMConf.
onInternetMeasurement.
NewYork:ACMPress,2008.
271284.
[doi:10.
1145/1452520.
1452552][46]MoriT,UchidaM,KawaharaR,PanJP,GotoS.
Identifyingelephantflowsthroughperiodicallysampledpackets.
In:Proc.
ofthe4thACMSIGCOMMConf.
onInternetMeasurement.
NewYork:ACMPress,2004.
115120.
[doi:10.
1145/1028788.
1028803][47]ZhangY,FangBX,ZhangYZ.
Identifyingheavyhittersinhigh-speednetworkmonitoring.
SCIENTIASINICAInformationis,2010,53(3):659676.
[doi:10.
1007/s11432-010-0053-5][48]AlonN,MatiasT,SzegedyM.
Thespacecomplexityofapproximatingthefrequencymoments.
In:Proc.
ofthe28thAnnualACMSymp.
ontheTheoryofComputing.
NewYork:ACMPress,1996.
2029.
[doi:10.
1145/237814.
237823][49]MankuGS,MotwaniR.
Approximatefrequencycountsoverdatastreams.
In:Proc.
ofthe28thInt'lConf.
onVeryLargeDataBases.
HongKong:ACMPress,2002.
346357.
http://dl.
acm.
org/citation.
cfmid=2367502.
2367508152JournalofSoftware软件学报Vol.
25,No.
1,January2014[50]DimitropoulosX,HurleyP,KindA.
Probabilisticlossycounting:Anefficientalgorithmforfindingheavyhitters.
ACMSIGCOMMComputerCommunicationReview,2008,38(1):516.
[doi:10.
1145/1341431.
1341433][51]BabcockB,OlstonC.
Distributedtop-kmonitoring.
In:Proc.
ofthe2003ACMSIGMODInt'lConf.
onManagementofData.
NewYork:ACMPress,2003.
2839.
[doi:10.
1145/872757.
872764][52]WuH,GongJ,YangW.
Algorithmbasedondoublecounterbloomfilterforlargeflowsidentification.
RuanJianXueBao/JournalofSoftware,2010,21(5):11151126(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/3568.
htm[doi:10.
3724/SP.
J.
1001.
2010.
03568][53]DuffieldN,LundC,ThorupM.
Estimatingflowdistributionsfromsampledflowstatistics.
In:Proc.
oftheACMSIGCOMM.
NewYork:ACMPress,2003.
325336.
[doi:10.
1145/863955.
863992][54]TuneP,VeitchD.
Towardsoptimalsamplingforflowsizeestimation.
In:Proc.
ofthe8thACMSIGCOMMConf.
onInternetMeasurement.
NewYork:ACMPress,2008.
243255.
[doi:10.
1145/1452520.
1452550][55]YangL,MichailidisG.
Sampledbasedestimationofnetworktrafficflowcharacteristics.
In:Proc.
ofthe26thIEEEInt'lConf.
onComputerCommunications.
Anchorage:IEEE,2007.
17751783.
[doi:10.
1109/INFCOM.
2007.
207][56]RibeiroB,TowsleyD,YeT,BolotJ.
Fisherinformationofsampledpackets:Anapplicationtoflowsizeestimation.
In:Proc.
ofthe6thACMSIGCOMMConf.
onInternetMeasurement.
NewYork:ACMPress,2006.
1525.
[doi:10.
1145/1177080.
1177083][57]LoiseauP,GoncalvesP,GirardS,ForbesF,PrimetP.
Maximumlikelihoodestimationoftheflowsizedistributiontailindexfromsampledpacketdata.
In:Proc.
oftheSIGMETRICS.
NewYork:ACMPress,2009.
263273.
[doi:10.
1145/1555349.
1555380][58]LuoN,LiAP,WuQY,LuHB.
Sketch-BasedanomaliesdetectionwithIPaddresstraceability.
RuanJianXueBao/JournalofSoftware,2009,20(10):28992906(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/3995.
htm[doi:10.
3724/SP.
J.
1001.
2011.
03995][59]MaiJN,SridharanA,ChuahCN,ZangH,YeT.
Impactofpacketsamplingonportscandetection.
IEEEJournalonSelectedAreasinCommunication,2006,24(12):22852298.
[doi:10.
1109/JSAC.
2006.
884027][60]BrauckhoffD,TellenbachB,WagnerA,MayM,LakhinaA.
Impactofpacketsamplingonanomalydetectionmetrics.
In:Proc.
ofthe6thACMSIGCOMMConf.
onInternetMeasurement.
NewYork:ACMPress,2006.
159164.
[doi:10.
1145/1177080.
1177101][61]AliS,HIU,RizviS,RasheedN,SarfrazU,KhayamSA,MirzaF.
Onmitigatingsampling-inducedaccuracylossintrafficanomalydetectionsystems.
ACMSIGCOMMComputerCommunicationReview,2010,40(3):416.
[doi:10.
1145/1823844.
1823846][62]ChengG,GongJ,DingW.
Areal-timeanomalydetectionmodelbasedonsamplingmeasurementinahigh-speednetwork.
RuanJianXueBao/JournalofSoftware,2003,14(3):594599(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/20030340.
htm[63]MaiJN,ChuanhCN,SridharanA,YeT,ZangH.
IssampleddatasufficientforanomalydetectionIn:Proc.
ofthe6thACMSIGCOMMConf.
onInternetMeasurement.
NewYork:ACMPress,2006.
165176.
[doi:10.
1145/1177080.
1177102][64]AndroulidakisG,PapavassiliouS.
Two-Stageselectivesamplingforanomalydetection:analysisandevaluation.
SecurityandCommunicationNetworks,2011,4(6):608621.
[doi:10.
1002/sec.
191][65]AndroulidakisG,PapavassiliouS.
Improvingnetworkanomalydetectionviaselectiveflow-basedsampling.
IETCommunicationsJournal,2008,2(3):399409.
[doi:10.
1049/iet-com:20070231][66]AndroulidakisG,ChatzigiannakisV,ParavassiliouS.
Networkanomalydetectionandclassificationviaopportunisticsampling.
IEEENetwork,2009,23(1):612.
[doi:10.
1109/MNET.
2009.
4804318][67]LiZC,GaoY,ChenY.
HiFIND:Ahigh-speedflow-levelintrusiondetectionapproachwithDoSresiliency.
ComputerNetworks,2010,54(8):12821299.
[doi:10.
1016/j.
comnet.
2009.
10.
016][68]ZhengJ,HuMC,YunXC,ZhengZ.
Anomalydetectionoflargescalenetworkbasedondatastreams.
JournalonCommunicaitons,2006,27(2):18(inChinesewithEnglishabstract).
[69]ZhengLM,ZouP,HanWH,LiAP,JiaY.
Anomalydetectioninbackbonenetworksusingfilter-ary-sketch.
JournalonCommunicaitons,2011,32(12):151160(inChinesewithEnglishabstract).
[70]KamiyamaN,MoriT,KawaharaR.
Simpleandadaptiveidentificationofsuperspreadersbyflowsampling.
In:Proc.
ofthe26thIEEEInt'lConf.
onComputerCommunications.
Anchorage:IEEE,2007.
24812485.
[doi:10.
1109/INFCOM.
2007.
305]周爱平等:高速网络流量测量方法153[71]WangHB,ChengSD,LinY.
Onflowsamplingforidentifyingsuper-connectionhostsinhighspeednetworks.
ACTAELECTRONICASINICA,2008,36(4):809818(inChinesewithEnglishabstract).
[72]ChengG,GongJ,DingW,WuH,QiangSQ.
Superpointdetectionbasedonadaptivesampling.
SCIENTIASINICA(E:Informationis),2008,38(10):16791696(inChinesewithEnglishabstract).
[73]ShiXG,ChiuDM,LuiJ.
Anonlineframeworkforcatchingtopspreadersandscanners.
ComputerNetworks,2010,54(9):13751388.
[doi:10.
1016/j.
comnet.
2009.
12.
003][74]ZhaoQ,KumaA,XuJ.
Jointdatastreamingandsamplingtechniquesfordetectionofsupersourcesanddestinations.
In:Proc.
ofthe5thACMSIGCOMMConf.
onInternetMeasurement.
Berkeley:USENIXAssociation,2005.
7790.
http://dl.
acm.
org/citation.
cfmid=1251086.
1251093[75]LiuWJ,GongJ.
Doublesamplingforflowmeasurementonhighspeedlinks.
ComputerNetworks,2008,52(11):22212226.
[doi:10.
1016/j.
comnet.
2008.
04.
003][76]KumarA,SungM,XuJ,ZeguraE.
Adatastreamingalgorithmforestimatingsubpopulationflowsizedistribution.
ACMSIGMETRICSPerformanceEvaluationReview,2005,33(1):6172.
[doi:10.
1145/1071690.
1064221]附中文参考文献:[1]程光,龚俭.
互联网流测量.
南京:东南大学出版社,2008.
[3]程光,唐永宁.
基于近似方法的抽样报文流数估计算法.
软件学报,2013,24(2):255265.
http://www.
jos.
org.
cn/1000-9825/4316.
htm[doi:10.
3724/SP.
J.
1001.
2013.
04316][52]吴桦,龚俭,杨望.
一种基于双重CounterBloomFilter的长流识别算法.
软件学报,2010,21(5):11151126.
http://www.
jos.
org.
cn/1000-9825/3568.
htm[doi:10.
3724/SP.
J.
1001.
2010.
03568][58]罗娜,李爱平,吴泉源,陆华彪.
基于概要数据结构可溯源的异常检测方法.
软件学报,2009,20(10):28992906.
http://www.
jos.
org.
cn/1000-9825/3685.
htm[doi:10.
3724/SP.
J.
1001.
2009.
03685][62]程光,龚俭,丁伟.
基于抽样测量的高速网络实时异常检测模型.
软件学报,2003,14(3):594599.
http://www.
jos.
org.
cn/1000-9825/20030340.
htm[68]郑军,胡铭曾,云晓春,郑仲.
基于数据流方法的大规模网络异常发现.
通信学报,2006,27(2):18.
[69]郑黎明,邹鹏,韩伟红,李爱平,贾焰.
基于Filter-ary-Sketch数据结构的骨干网异常检测研究.
通信学报,2011,32(12):151160.
[71]王洪波,程时端,林宇.
高速网络超连接主机检测中的流抽样算法研究.
电子学报,2008,36(4):809818.
[72]程光,龚俭,丁伟,吴桦,强士卿.
基于自适应抽样的超点检测算法.
中国科学(E辑:信息科学),2008,38(10):16791696.
周爱平(1982-),男,江苏泰州人,博士生,主要研究领域为网络测量,网络安全.
E-mail:apzhou@njnet.
edu.
cn郭晓军(1983-),男,博士生,讲师,主要研究领域为网络测量,网络安全.
E-mail:xjguo@njnet.
edu.
cn程光(1973-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为网络测量,网络安全,网络管理.
E-mail:gcheng@njnet.
edu.
cn