高速网络流量测量与分析研究及其应用

发布时间：2021-11-14 23:18

　　网络流量测量是网络管理中一项重要任务。然而随着互联网的飞速发展,网络流量呈现爆炸式的增长,使得对高速网络流量的测量面临着很大的挑战。Sketch是一种可以对数据流进行存储和汇总的方法,可以对数据流进行测量和查询,它有几种典型的Sketch算法:Count-Min Sketch、CU Sketch和Count Sketch,可以将它应用到网络测量中来。但是由于网络流量自身的特点,在使用Sketch进行测量时可能会产生大量的空间浪费,造成空间利用率低等问题。此外,由于Sketch是使用散列函数对数据流进行汇总,散列冲突会造成估计值的误差,尤其是对于小流量。因此,本文的工作主要针对于空间利用率低和对小流量的过高估计这两个问题对网络流量测量的算法进行改进。本研究首先引入进位的思想,提出了将多个Sketch与Counting Bloom Filter（CBF）相结合的结构——Self-Adaption Sketch（SA Sketch）。该结构可以根据所需测量的网络流量的大小动态地申请空间、创建Sketch,并使用CBF来存储当前流量使用的Sketch的数量,从而提高空间的利用率。实验结果表明,... 

【文章来源】：南京邮电大学江苏省

【文章页数】：71 页

【学位级别】：硕士

【部分图文】：

Sketch的基本结构

SASketch的结构

南京邮电大学硕士研究生学位论文第四章基于布谷鸟哈希的SASketch优化方法394.2.2优化的数据结构为了解决CBF的查询错误给SASketch的准确性带来的影响，本文基于布谷鸟哈希的哈希表和Sketch的特性，优势互补，将它们结合形成一个新的数据结构——CBSASketch（Cuckoo-BasedSelf-AdaptionSketch）。该结构将原结构中的CBF部分改为布谷鸟哈希部分，并且对原来的布谷鸟哈希进行一定的改进，使得它适用于多层的Sketch结构。图4.3CBSASketch的数据结构CBSASketch的结构如图4.3所示，由Sketch部分和布谷鸟哈希部分组成。Sketch部分包含n+1个Sketch，与SASketch的Sketch部分相同。布谷鸟哈希部分包含一个布谷鸟哈希表，其中包含M个哈希表，T1,T2,…,TM，并且对应M个哈希函数，hc1(.),hc2(.),…,hcM(.)，每个哈希表包含d个桶。为了让布谷鸟哈希表适用于流量测量，将布谷鸟哈希表进行了一定的改进。改进后的布谷鸟哈希表如图4.4所示，每个桶中包含两个部分，一部分存储key，另一部分存储对应的值value。插入的过程如下：（1）对key进行哈希计算，找出对应的桶，（2）若两个桶中均为空，则将<key,value>插入第一个桶；（3）若存在不为空的桶，将key与桶中现存的key进行比较，（a）如果两个key相同，则将该桶中的值加上value，（b）如果两个key不同，并且存在其他空桶，则将该<key,value>插入空桶，（c）如果两个key不同，并且不存在其他空桶，则选择任意一个桶，将现存的内容

【参考文献】：
期刊论文
[1]高速网络流量测量方法[J]. 周爱平,程光,郭晓军.  软件学报. 2014(01)
[2]网络测量方法和关键技术综述[J]. 王海涛,朱震宇.  数字通信世界. 2010(11)
[3]网络测量与分析研究综述[J]. 陈晓霞,任勇毛,李俊,张潇丹.  计算机系统应用. 2010(07)
[4]DRAGON-Lab―Next generation internet technology experiment platform[J]. WANG JiLong1,2,LI ZhongHui2,Lü GuoHan2,JIANG CaiPing2,LI Xing1,2 & ZHANG QianLi2 1 National Laboratory for Information Science and Technology,Tsinghua University,Beijing 100084,China;2 Network Research Center,Tsinghua University,Beijing 100084,China.  Science in China（Series F:Information Sciences）. 2008(11)
[5]一种有效的挖掘数据流近似频繁项算法[J]. 王伟平,李建中,张冬冬,郭龙江.  软件学报. 2007(04)



本文编号：3495553