空间高效的数据包公平抽样算法

ISSN1000-9825,CODENRUXUEWE-mail:[e-mail],Vol.21,No.10,October2010,pp.2642−2655:[phone]©byInstituteofSoftware,theChineseAcademyofSciences.Allrightsreserved.空间高效的数据包公平抽样算法∗张进1+,邬江兴2,钮晓娜21(解放军理工大学通信工程学院,江苏南京210016)2(国家数字交换系统工程技术研究中心,河南郑州450002)Space-EfficientFairPacketSamplingAlgorithmZHANGJin1+,WUJiang-Xing2,NIUXiao-Na21(InstituteofCommunicationEngineering,PLAUniversityofScienceandTechnology,Nanjing210016,China)2(NationalDigitalSwitchingSystemEngineeringandTechnologyResearchCenter,Zhengzhou450002,China)+Correspondingauthor:E-mail:[e-mail],WuJX,NiuXN.Space-Efficientfairpacketsamplingalgorithm.JournalofSoftware,2010,21(10):2642−2655.:Fairpacketsamplingcanobtainahigherpacketsamplingratioofshortflowsbysacrificingthepacketsamplingoflongones;thus,ensuringbetterfairnessamongallflowsthanuniformrandomsamplingdoes.However,thepreviouslyproposedfairsamplingalgorithmofSketchGuidedSampling(SGS)hasthedrawbacksofpoorspaceefficiencyandlargeestimationerrorforshortflows.Inthispaper,aspace-efficientfairpacketsampling(SEFS)algorithmisproposed.ThekeyinnovationofSEFSisamulti-resolutiond-lefthashingschemaforflowtrafficestimation.TheperformanceofSEFSiscomparedtothatofSGSincontextsofbothflowtrafficmeasurementsandalongflowidentificationprocessthatusesreal-worldtraffictracescollectedfromOC-48andOC-192backbonenetwork.TheexperimentalresultsshowthattheproposedSEFSismoreaccuratethanSGSinbothapplicationcontexts,whileareductionof65percentinspacecomplexitycanbeachieved.TheimprovementofestimationaccuracyofSEFSisremarkable,especiallyforshortflows,whichcompriseaspastofalargepercentageofwholenetworktrafficflows.Keywords:networktrafficmonitoring;packetsampling;d-lefthashing摘要:数据包公平抽样通过牺牲长流的包抽样率以换取更高的短流包抽样率,因而比均匀随机包抽样更能保证数据流之间的公平性.现有的公平抽样算法SGS(sketchguidedsampling)存在空间效率低、短流估计误差大的问题.提出了一种空间高效的数据包公平抽样算法SEFS(space-efficientfairsampling).SEFS算法的新颖之处在于采用多解析度抽样统计器对数据流流量作近似估计,各个统计器由d-left哈希表实现.采用在OC-48和OC-192骨干网采集的真实流量数据,在数据流流量测量以及长流检测的应用背景下,对SEFS算法和SGS算法的性能进行了比较.实验结果表明,与SGS算法相比,SEFS算法在空间复杂度降低65%的前提下,仍具有更高的估计精度.特别是对于占网络数据流绝大多数的短流而言,SEFS算法估计精度高的优势更为明显.∗SupportedbytheNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2008AA01A323(国家高技术研究发展计划(863))Received2008-06-18;Revised2009-03-30;Accepted2009-06-01张进等:空间高效的数据包公平抽样算法2643关键词:网络流量监测;数据包抽样;d-left哈希中图法分类号:TP393文献标识码:A对网络流量的测量与分析是流量计费、流量工程、网络安全监测与异常检测等网络运营管理工作的前提.随着网络数据率的不断提高,当前在高速骨干网链路上,流量测量与分析对于计算和存储资源的需求极高.例如,在OC-768链路上,设平均包长为1000bits,则为了实现线速处理,所能允许的平均包处理时间为25ns,这就要求采用专门的硬件,如TCAM,ASIC等实现流量测量与分析设备,代价极其高昂.为了降低骨干网流量测量与分析的实现代价,必须进行有效的数据约减.数据包抽样是一种有效的数据约减的方法[1].与分析完整的链路流量相比,分析包样本通常可以在所能获取的信息量和所需付出的处理代价之间获得更好的折衷.基于上述原因,数据包抽样在高速骨干网链路数据流的流量测量[2−5]、流量异常检测[6−8]等领域被广泛采用.当前,应用昀广泛的抽样方法是均匀随机抽样和固定周期抽样.均匀随机抽样[1]以概率p对任意数据包进行抽样.固定周期抽样的性能和均匀随机抽样的性能相当[1],但更易于硬件实现,因此,Cisco路由器中采用固定周期抽样代替均匀随机抽样[2].然而,由于网络数据流流量分布的不均匀性,均匀随机抽样虽然能够很好地保留数据包级流量信息,但却无法较完整地保留数据流级的流量信息,如并发流数目、流长分布、各条数据流的流量,等等[9−11].对于网络安全监测、网络异常检测以及业务流分类等需要较完整的数据流级信息的应用而言,均匀随机抽样引起的估计误差较大[6,7].文献[12]提出了一种草图指导的抽样算法(sketchguidedsampling,简称SGS),其核心思想是设置包抽样比为该数据包所属数据流的当前流量的单调递减函数.SGS抽样算法通过牺牲长流的包抽样率以换取更高的短流包抽样率,与均匀随机抽样相比,在相同的包抽样比下,SGS抽样算法能够更好地保证数据流之间的公平性,更完整地保留数据流级的流量信息.然而,SGS抽样算法需要实时获知每条数据流的流量.文献[12]采用简单的哈希表对各条数据流的流量作近似估计,该方法的主要缺点是空间效率低,且由于哈希冲突导致对短流流量的估计误差较大.尽管文献[12]认识到此问题,并且提出通过采用两级存储结构的统计计数器[13−15]或者文献[16]提出的MRSCBF(multi-resolutionspace-codeBloomfilter)算法来测量各数据流的流量,以减小对于大容量高速存储器的需求.然而,文献[12]提出的方案并不可行,因为采用两级存储结构的统计计数器和MRSCBF虽然能够支持线速更新,却不能支持线速读取.SGS算法的高空间复杂度导致其实现代价高,并影响了其部署灵活性.此外,考虑到短流占据着网络流量的绝大多数[3],因此SGS算法对于短流的估计误差较大也严重影响了其应用效果.本文提出了一种空间高效的数据包公平抽样算法SEFS(space-efficientfairpacketsampling).SEFS采用多解析度抽样统计器近似的估计各条数据流的流量.多解析度抽样统计器由n层独立的抽样统计器构成,第i层抽样统计器以概率pi=Pi(P为抽样常数且有0P1)独立地对链路数据包进行抽样,并统计所抽取的包样本中各条数据流的流量大小.各层抽样统计器有一定的统计范围,多个抽样统计器的统计范围的并集覆盖整个流量区间.各个抽样统计器采用d-left哈希表[17]实现,在有效地降低哈希冲突概率的同时,仍具有较高的空间效率.采用真实的骨干网流量数据进行仿真实验的结果表明,SEFS算法在空间复杂度比SGS算法降低了65%的前提下,仍具有更小的估计误差.特别是对于短流而言,SEFS算法估计误差小的优势更为明显.本文第1节总结相关工作,并对照说明本文工作的创新之处.第2节首先描述数据包公平抽样算法,然后给出公平抽样的包抽样比和流抽样比的解析结果.第3节给出流量的多解析度抽样估计算法,并分析多解析度抽样估计算法的估计误差、空间复杂度以及时间复杂度.第4节通过仿真实验,在流量测量和长流检测的应用背景下,对SEFS算法和SGS算法的估计误差进行比较.第5节给出算法实现的结果.第6节是结论.1相关工作根据网络流量特性和测量可用的资源状况进行自适应抽样的思想,在文献[18−20]中均有所体现.文献[12]首次考虑到抽样对于数据流之间的公平性的影响,并提出了SGS公平抽样算法.本文的工作和文献[12]基于同一个出发点,即保证数据流之间的抽样公平性.公平抽样需要实时获知各条数据流的流量.文献[12]提出采用简2644JournalofSoftware软件学报Vol.21,No.10,October2010单哈希表估测数据流流量的方法存在空间效率低以及对于短流的估计误差较大的缺陷.本文提出了一种新颖的多解析度抽样统计器以估计链路中各条数据流的流量.与文献[12]提出的采用简单哈希函数进行流量估计的方法相比,本文提出的多解析度抽样统计器在空间效率和估计准确度,特别是对于短流的估计准确度方面有明显的提升.此外,文献[12]没有分析公平抽样的包抽样比和流抽样比,本文给出了当估计误差一定时,公平抽样的包抽样比和流抽样比的解析结果.这一结果对于实际应用公平抽样算法进行网络流量分析时,在估计精度和处理代价之间进行合理权衡提供了理论准则.公平抽样的前提是需要实时获知各条数据流的流量.在高速骨干网链路中,由于包到达间隔短且并发流数量巨大[2−5],因此直接进行流量测量的代价极高.文献[16]采用多解析度的空码布鲁姆过滤器MRSCBF估计各条数据流的流量.虽然MRSCBF更新操作的时间复杂度低,但其查询操作的时间复杂度较高,因而难以实现高速流量条件下的线速查询,从而无法支持公平抽样.此外,文献[16]并没有对MRSCBF的估计误差进行理论分析.本文提出的基于d-left哈希表的多解析度抽样统计器可以实现线速查询,且空间复杂度明显低于MRSCBF算法.此外,本文还对多解析度抽样统计器的估计误差进行了理论分析,并通过仿真实验对所得出的理论结果进行验证.文献[21]提出了采用Time-OutBloomFilter进行包抽样,以期在一定的抽样比下能够比均匀随机抽样抽取到更多的数据流.文献[21]的核心思想