一种新的基于LRU的大流检测算法.pdf

《一种新的基于LRU的大流检测算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、WBN【本文献信息】张毅卜，夏靖波，孙昱，等．一种新的基于LRU的大流检测算法[J]．电视技术，2014，38(15)种新的基于LRU的大流检测算法张毅卜，夏靖波，孙昱，任高明(空军3"-程大学信息与导航学院，陕西西安710077)【摘要l针对LRU(LeastRecentlyUsed)算法大流漏检率过高的问题，提出了一种采用CBF(CountingBloomFilter)和LRU两级结构的大流检测算法。该算法根据大流占用带宽较大、持续时间较长的特点在CBF中引入时间窗口机制来滤出可能的大流，然后将流信息记录在LRU中作进一步筛选。从理论上分

2、析了影响该算法性能的因素，考虑了在存储资源一定的条件下，如何设置参数以发挥该算法最大效能的问题。最后基于实际的互联网数据进行了对比验证。结果表明，与同类算法相比，该算法在有效降低大流漏检率的同时，提高了大流流量的测量精度。【关键词】流量测量；大流；布鲁姆过滤器；时间窗口；最近最少使用【中图分类号】TN919【文献标志码】ANewAlgorithmBasedonLRUforIdentifyandMeasuringLargeFlowsZHANGYibo，XIAJingbo，SUNYu，RENGaoming(InformationandNaviga

3、tionCollege，AirForceEngineeringUnivemi@，舰’an710077，China)【Abstract】AimingattheLRU(LeastRecentlyUsed)algorithm~problemofhighfalsenegativeprobability，atwo—stagestructurealgorithmbasedonCBF(CountingBloomFilter)andLRUispresented．Accordingtothecharacteristicsofthelargebandwidtha

4、ndlongduration，thealgorithmintroducestimewindowmechanismtofiltertheprobablelargeflowandsavestheflowmessageinLRUforfurtherscreening．Analyzingtheefectfactorsofthealgo—rithmintheoryandconsideringthequestionthathowtosetparameterswithlimitedstorageresourcestomakethealgorithmmaxi

5、mumeficiency，Experi—mentsarealsoconductedbasedonrealnetworktraces．Theresultsindicatethatthealgorithmcanreducethefalsenegativeprobability．Meanwhile，theaccuracyoflargeflowmeasuringisimproved．【Keywords】trafficmeasurement；largeflow；Bloomfilter；timewindow；LRU网络流是由相同属性的数据分组组成的集合，

6、由于其据分组所属流记录位于缓存顶部，而最久未到达的数据分在网络运营管理、计费等方面的巨大应用，所以基于流的组所属流的记录位于缓存的最底部。当有新流到达且缓网络测量不断受到重视。IETF(InternetEngineeringTask存已满时，淘汰最久未更新的流来为新流腾出存储空间。Foree)推荐的流测量方法是在测量设备中维护一个流表，由于大流持续时间长且分组到达速率高，所以其总能排在为每个流保存一个流记录，但是当前网络中流的数量十分缓存的上部，从而以较大的概率留在LRU缓存中。该类巨大，而目前的半导体技术并不能提供容量足够大的快速方法处理速

7、度快，识别效率高，硬件实现简单，但当有大量存储器SRAM来记录每个流的信息，因此实现IETF的方小流突发到达时，会造成某些大流被替换出LRU缓存，从法十分困难。已有研究显示，网络中的流大小呈重尾分而引起漏检。布，即少量的大流产生了网络中大部分的流量，而对于网为了进一步优化LRU算法，降低其漏检率，张果等人络运营管理、计费等相关应用而言，只需要获取大流的流提出的基于分层多粒度最近最久未使用的流量统计算量信息就足以满足应用需求⋯。现有的大流检测算法普法，将多级LRU表“串联”在一起来降低原算法漏检率，遍存在准确率不高的问题，不能满足实际应用需求。

8、因该算法的实质是牺牲存储空间来换取测量精度的提高。此，如何更有效率地检测大流成为了网络流量测量中的一考虑到高速缓存资源有限，文献[4]和文献[5]在原有单个热点问题