基于双阶段Sketch的长流检测算法研究

作     者：李潮晨 

作者单位：大连海事大学 

学位级别：硕士

导师姓名：刘卫江

授予年度：2022年

学科分类：08[工学] 0839[工学-网络空间安全] 

主      题：长流 Sketch 概率估计 双阶段 

摘      要：长流检测对于负载均衡,流量工程和入侵检测等方面具有重要意义。网络流量呈现重尾分布,即大多数流包含较少数量的报文,而很小一部分流包含大量报文。从网络流量中检测出长流可以更好的了解网络行为,对网络管理有重要帮助。为了匹配高速网络中的数据传输效率,在读写速度快的SRAM进行长流检测是很有必要的。Sketch是一种概率性的数据结构,可以使用较小的内存来存储和查询给定的多项集中任何一个项的频率,可以很好地用于长流检测,但是现存的Sketch通常使用许多具有相同大小的计数器来记录流中的报文的数量,因此这些计数器必须足够大,以容纳最大流,由于网络中大多数流都是非长流,只有很少一部分是长流,因此许多计数器中记录了很小的值,这样会造成一部分的空间浪费。本文提出了一种基于双阶段Sketch的长流检测算法(Algorithm for Detecting Elephant Flows through Two-Stage Sketch,TSS)。TSS算法的结构由两部分组成:一部分为light part,另一部分为heavy part。TSS算法的核心思想是将长流和非长流进行动态存储,使得非长流存储在light part中,而长流由light part与heavy part共同存储,从而优化内存效率。为了评价TSS算法在长流检测方面的性能,首先针对算法的误差范围进行理论分析,然后使用三个在不同网络环境下收集的真实Trace进行了大量实验,并且与其他三种算法进行了比较。从理论分析以及实验结果表明,TSS在长流检测方面具有更好的性能。