基于多层哈希CBF的长流识别算法研究

《基于多层哈希CBF的长流识别算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、大连海事大学硕士学位论文基于多层哈希CBF的长流识别算法研究姓名：周康中请学位级别：硕士专业：计算机科学与技术（计算机应用技术）指导教师：刘卫江20100601摘要长流识别对发展有效且高效的流鈕工程有着垂要的作用。很多基于流测量的研究显示，网络中的流表现出强烈的重尾行为，即大多数流只包含少数盘的报文,而很小一部分流却携带着很大数比的报文。长流的一个非常显著的特征就超它们仅占流数量的一小部分却占据了总流量的绝大部分。因此，了解了长流信息就能够很好的掌握此次通信行为，另外，通过统计出长流信息对网络操作和网络管

2、理也有着很大的帮助，长流对网络性能的影响也至关重要。另一方面，近年來随着高速链路的快速发展，使得长流识别成为网络测量中的研究热点，但是同时也使得长流识别变得更加困难。本文对多层哈希CBF(CountingBloomFilter)的计数方式进行了改进，使得改进后该结构的空间开销进一步减少。然后将改进之后的多层哈希CBF应用到了长流识别中，实现了一种长流识别算法，采用多层的结构对报文进行统计，通过第一层CBFV可以过滤掉短流，而长流可以由高层的HBV来承担。本文所选取的哈希函数带有部分原来流标识的信息，这样可

3、以通过哈希短串的重叠位把多个短串进行合并，最后整合出长流信息，而不需要维护96bit的流标识，减少了资源开销。在合并长流过程中，本文使用了一种过滤方法，对合并出来的流信息进行过滤，过滤掉那些误识别岀来的长流，得到更准确的长流信息。通过在Linux下编程实验，结果表明，利用这种方法能够准确的识别出长流信息，漏检率为零，同时又有效的减少了资源开销，还可以根据不同的应用设置不同的层数，该算法又具有很好的灵活性和可扩展性。关键词：网络测量；长流；哈希；CountingBloomFilter；多层结构ABSTRAC

4、TIdentifyingelephantflowsisveryimportantindevelopingeffectiveandefficienttrafficengineeringschemes.Asmanymeasurement-basedstudieshaverevealed,flowstatisticsexhibitstrongheavy-tailbehaviorsinvariousnetworks.Thischaracteristicisoftenreferredtoastheelephanta

5、ndmicephenomenon;i.e.,mostflows(miceflows)onlyhaveasmallnumberofpackets,whileaveryfewflows(elephantflows)havealargenumberofpackets.Anoticeableattributeofelephantflowsisthattheycontributealargeportionofthetotaltrafficvolumedespitebeingrelativelyfewinthenum

6、berofflows.Inaddition,obtainingthestatisticsoftheseflowsisalsoveryusefulfornetworkoperationandmanagement,andtheimpactofelephantflowsonnetworkperformanceisalsosignificant.Ontheotherhand,withtherapidgrowthoflinkspeedinrecentyears,itmakesidentifyingelephantf

7、lowsbecomearesearchhot-spotinnetworkmeasurement.However,italsomakesidentifyingelephantflowsbecomemuchmoredifficult.ItisachallengeforbackboneroutertoaccepttheresourceoverheadwhenmaintainingtheinformationofflowIDinthememory.Inthispaper,weimproveacountingmet

8、hodofmultilayerhashedCountingBloomFilter(ML-HCBF)inordertoreducethespaceoverheadandproposeanovelalgorithmtoidentifyelephantflowsbyimprocedML-HCBF.Wecountpacketswithmultilayerstructure,inwhichthefirstlayercanfilterou