基于Sketch的网络流量测量算法研究

发布时间：2021-04-12 04:47

　　随着网络灵活性、可扩展性和可编程性的提高,网络规模和链路带宽的不断增大,网络行为变得更加复杂和多样化,这些均对网络管理和安全防护提出了更高的要求。网络流量测量作为网络领域的研究热点,不仅是实现智能、可靠网络管理的前提,而且在网络性能诊断、异常检测、服务质量保障及安全防护等方面发挥了重要作用。随着对网络流量精细化管理以及智能调度的需要,如何在巨大的网络流量场景下利用有限的内存和计算资源来满足严格的精度、包处理速率以及多任务测量的需求,是当前网络流量测量技术发展所面临的挑战,也是世界各地研究人员的努力方向。本文首先给数据报文引入了序列值的概念,序列值是根据数据报文的出现次序赋予的值,序列值间隔可以用于衡量数据流的出现密度,然后通过对数据流的统计研究,发现了大象流与老鼠流在序列值间隔上的显著区别,并将这个结论加以推广,在此基础上,提出了基于Sketch结构的网络流量测量算法——Seq Sketch,其采用了大象流和老鼠流分离的思想,在普遍应用数据流频率进行区分的基础上,将序列值间隔这一特征用来对大象流进行筛选,从而实现更为精确高效的流量测量。整个算法结构由哈希表和Sketch结构两部分组成,... 

【文章来源】：哈尔滨工业大学黑龙江省 211工程院校 985工程院校

【文章页数】：64 页

【学位级别】：硕士

【部分图文】：

基于计数器结构的示意图

哈尔滨工业大学工程硕士学位论文-9-法没有舍弃任何一个数据项，而是在遇到哈希冲突时将所有信息叠加到一起。显而易见的时，随着测量过程的累积，最终的测量结果往往也会偏离真实值；Sketch方法的另一个误差来源是数组元素的数据共享，由于允许哈希冲突的存在，Sketch中的计数器可以由哈希值相同的多个键值不同的元素共享，因此导致部分数据与真实值相比偏差较大，比如如果大象流和老鼠流哈希映射的位置相同，那么老鼠流也会共享大象流的计数结果。因此对于不同的Sketch测量方法而言，主要区别在于如何控制真实值与测量值的误差。Count-Sketch[16]利用数学期望的方法来减少误差，而Count-MinSketch[17]取K个返回值中的最小值来控制误差，AugmentedSketch[32]和ElasticSketch[19]采用分离大象流和老鼠流的策略，将大象流记录在第一层哈希表中，而将老鼠流记录在下层Sketch结构中，减小了大象流和老鼠流的冲突，提高了测量精确度。图2-2Sketch算法示意图2.2网络流量测量算法举例本节将分别介绍几种典型的基于计数器方法和基于Sketch的算法，并阐述其各自的优缺点并进行比较。2.2.1基于计数器结构的算法（1）频率算法频率算法(frequentalgorithm)[14]，受最大投票算法(majorityvotealgorithm)[20]启发，是一种大象流统计算法，主要用于查询数据流的top-k元素，该算法通过设置长度为k的计数器来找出频率超过N/（k+1）的大象流，其处理每一个数据报文需要的时间复杂度为O（1）。算法思路如下：首先将计数器初始化为空，对于每一个输入项，如果已经存在计数器中，则相应值增加，如果不存在且此时有空计数器，则执行插入操作，如果计数器已被不同的数据项占据，则将所

AugmentedSketch结构


本文编号：3132648