ITPub博客

首页 > IT基础架构 > 网络通信/物联网 > MV-Sketch介绍--网络流量异常检测

MV-Sketch介绍--网络流量异常检测

网络通信/物联网 作者:上海地面通 时间:2019-12-10 15:39:43 0 删除 编辑

网络测量是对网络行为进行特征化、对各项指标进行量化并充分理解与正确认识互联网的最基本手段,支持着SDN 的发展,网络管理员可以通过网络测量掌握网络状态,进而优化网络结构、改善网络服务质量,及时诊断网络故障并进行恢复。 Sketch 在较小内存下对重流( heavy flow )和 heavy changer (突变流))的快速检测有助于 SDN 云数据中心的大量部署。

 

既然提到了 Sketch 那么我们就来介绍一下什么是 Sketch Sketch 是一种紧凑的用于流量数据统计亚线性数据结构。 使用Hash 算法将属于映射到 Sketch 中,将大量网络流压缩至小部分的内存空间中,无需存储所有网络流,以达到节约内存的目的,并通过查询操作获得流量统计数据。 使用 Sketch 的原因是其 将具有相同哈希值的流存入相同的桶内,可以在保证准确度的同时大大减少存储空间。

 

接下来为大家介绍的是 MV-SKetch 是一种高效、紧凑、可逆的Sketch 可以 在小内存下实现对重流的快速检测 主要利用MJTRY 算法(主票选算法) 相较于动态分配流存储空间的方式,静态分配的方式有助于降低内存管理开销 且可以 利用SIMD 加速 MV-Sketch

 

MV-Sketch 的数据结构由 r 行 构成,每一行有 w 个桶,每个桶中记录三个元素 Vi,j Ki,j Ci,j Vi,j 表示哈希到这个桶内所有流的总和 Ki,j 表示当前桶内的重流候选, Ci,j 记录当前桶内重流候选的计数值,用于判断是否继续保留此重流候选。 如下图所示:

 

 

当数据包到来时,MV-Sketch 利用 r 个独立的哈希函数,将数据包分别映射到 1 - r 行,所映射列序 j 由哈希值 hi(x) 决定。哈希到某个桶之后,根据 MJRTY 算法来更新重流候选。查询时,根据新流和桶内重流候选是否一致来决定估计值,最后返回所有行中估计值最小值。在一个周期结束时, MV-Sketch 以是否大于设定的阈值为标准来判断重流。

 

MV-SKetch 所使用的 MJRTY 算法用于确定任意数量的候选人中,哪一个获得了多数选票,所拥有票数高于总票数一半者,一定是主要候选人。 举例说明: 假设有三位候选人A B C ,并假设按以下顺序对代表进行了投票: A A A C C B B C C C B C C

记录完第三张选票后,A 3 票领先。在处理接下来的三张选票时,将三张 A 票与三张其他票(两张 C 票,一张 B 票)配对(抵消)。记录所有选票之后, C 成为主要候选人。

 

算法 1 MV-Sketch 更新算法

MV-Sketch 借鉴 MJRTY 算法 , 在执行更新操作时(算法 1[2]) ,先累加 Vi,j = Vi,j + vx (Vi,j 增加新流字节数 ) ,再将新流 x 与当前桶内重流候选 Ki,j 进行比较,若相同,那么计数器 Ci,j 增加新流的字节数,否则相应地减少;若减少至零下(即 Ci,j <0) ,则 x 取代 Ki,j ,且 Ci,j 取绝对值。在实际中,由于少数重流所带流量在桶内所有流量中占主导地位,因而在一个周期结束时, MV-Sketch 可以在桶内保持准确的重流候选。


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/69943410/viewspace-2667752/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2019-08-02

  • 博文量
    34
  • 访问量
    15737