基于sketch的网络测量方法介绍

作者简介: 周政演,福州大学数计学院2016级计算机科学与技术(实验班)本科生,目前研究方向为网络测量,邮箱vancasola @gmail.com。

一、背景

网络测量是SDN发展的重要基础。网络状态监测、网络故障分析、网络安全防御,乃至于网络智能化,都依赖于网络测量。作为网络测量前沿研究的主流,基于sketch的高速流量网络测量,是网络领域顶级会议SIGCOMM近两年的研究热点,包括SIGCOMM’17的 SketchVisor[1] 和SIGCOMM’18的SketchLearn[2]、ElasticSketch[3]等。

sketch的网络测量与SDN结合,具有天然特性。一方面,SDN云数据中心的大量部署,需要基于sketch的高速流量网络测量,因为sketch能进行大流和异常流的检测,不占用过多的计算和空间资源。另一方面,SDN 转控分离,控制器具有全局视野,能对网络进行调度、制定策略,实时提供网络信息,有利于sketch的应用实施。

当前的网络流量测量,主要有抽样技术和数据流技术两种方法。抽样技术为每条流维护一个独立的计数器,较高的抽样速率需要消耗大量的性能资源。数据流技术利用散列将庞大信息压缩到较小的空间内,目前被广泛应用的是基于 sketch 的网络测量方法。

sketch 是一种基于散列的数据结构,可以在高速网络环境中,实时地存储流量特征信息,只占用较小的空间资源,并且具备在理论上可证明的估计精度与内存的平衡特性。基于sketch的网络测量,目前主要有ReversibleSketch[4]、OpenSketch[5]、Sketchvisor[1]等相关改进及实现。

二、Sketch 的原理

sketch是基于散列的数据结构,通过设置散列函数,将具有相同散列值的键值数据存入相同的桶内,以减少空间开销。桶内的数据值作为测量结果,是真实值的近似。利用开辟二维地址空间,多重散列等技术减少散列冲突,提高测量结果的准确度。Count-Min[7] 是一种典型的 sketch ,在 2004 年被提出。实际上 Count-Min sketch 用到的是分类的思想:将具有相同哈希值的网络流归为一类,并使用同一个计数器计数。

如何处理包

当高速网络流量到来时,逐个记录所有流量的信息,会带来巨大的计算和空间资源开销。而网络测量往往也无需记录所有的信息。

Count-Min sketch由多个哈希函数(f1……fn)和一张二维表组成。二维表的每个存储空间维护了一个计数器,其中每个哈希函数分别对应表中的每一行。当一个网络流到来时,需要经过每个哈希函数 f1……fn 的处理,根据处理得到的哈希值分别存入每一行对应哈希值的计数器。有几个哈希函数,就要计算几次。算完后,取这m个计数器中的最小值,作为测量的最终值。

图1 Count-Min sketch 结构示意

设计考量

测量值偏大:使用哈希的方法会产生冲突,多个网络流数据哈希到同一个桶内,那么这个桶的计数值就会偏大。

1.为什么允许有误差:在高速网络条件下,若把所有信息都准确地记录下来,要消耗大量计算和空间开销,无法满足实时性;而且在很多情况下,并不需要非常精确的测量数据,在一定程度上可靠的估计值,便足以满足需求。

2.为什么要设置多个哈希函数:如果只设置一个哈希函数,多个流数据存入同一个桶,误差就会很大。通过设计多个哈希函数,减少哈希值的冲突,以减少误差。每个流都要经过所有哈希函数的处理,存入不同的计数器中。计数器的最小值虽然还是大于等于真实值,但最接近真实值。这也是 “ Count-Min ”的由来。

3.哈希函数个数:哈希函数越多,冲突越少,测量值越精确,但计算开销大。需要权衡测量精度和准确度,来设置合适的哈希函数个数。

为了帮助理解sketch的原理,这里从一个例子讲起:

小周是全市的快递中转站的负责人(SDN控制器),他需要合理地分配人员的职责,制定分配的策略(全局调度)。他需要了解每个区的包裹数等信息(测量信息),以便完成人员分配。起初,他把每个包裹的信息都记录下来,并且让百分之八十的人负责统计每个区的包裹数量。

可是这里的包裹有成千上万之多(高速网络环境),统计人员算得满头大汗(计算资源开销大),记了几十页的纸(空间资源开销大),算得晕头转向。而另一头,快递员的数量太少,每个区的包裹,都没有送完。

他意识到,记录所有包裹的所有信息,是没有必要的(精度要求降低)。他的目标,是合理地分配每个区的快递员数量,他只需要了解每个区大致(估计)的包裹量即可(基于sketch的方法)。而且他发现,分类包裹这件事不应成为中转站的负担(减少测量开销),让快递的正常配送无法完成。

于是,他只留下几个人,让其他人负责配送包裹。相同区的包裹记在同一个区(计入同一个桶内),并且只需大致计算每个区的包裹数即可(近似)。这样一来,统计速度明显快了许多,用了一两张纸就把数据记完了。得出数据后,得知 A 区的包裹数最多,而 B 区的最少,小周将 B 区的大部分快递员分配到 A 区,不仅完成了昨天的配送,今天的配送也早早地完成(实时性)。

网络流经过网络结点时,需要制定合理的控制策略完成网络流的高效调度。网络流控制策略的制定,首先需要网络测量提供的流量信息。当流量较小时,如果将每个流的信息都记录下来,消耗计算和空间的资源并不大。

但是,当SDN 控制器进行全局调度时,有高速的流量通过。若将所有信息都一一记录下来,将大大占用网络资源,成为网络的负担。而且很多情况下,得到流量的估计值就足以满足任务的需求,记录所有信息是没有必要的。

此时,基于 sketch 的方法,利用散列技术对网络流进行粗粒度的分类,得出测量的估计值,满足高速环境下实时测量的需求,节约计算和空间的开销。

三、sketch研究热点

sketch 是网络测量研究领域的热点问题,在如 SIGCOMM 等网络领域顶级会议中,提出了一系列关于 Sketch 的解决方案 其中包括 SIGCOMM‘17 的 sketchvisor[1] 和 SIGCOMM’18 的SketchLearn[2] 和 ElasticSketch[3],现简单介绍基于 sketch 的研究热点,主要分为sketch的数据结构和sketch的测量框架。

Sketch的数据结构

  • Count-min sketch[7] 通过设置多个散列函数减少散列冲突,将计数器的最小值作为测量结果,是一种典型的 sketch。
  • 基于 sketch 的方法常常被用来检测大流和异常流,但是无法根据测量信息推出信息来源。而Reversible sketch[4] 可以解决这个问题,推断出信息的来源。
  • SeqHash [8]应用于入侵防御、大流检测,优点是快速精确,资源开销小。
  • top-k[9] 应用于检测数据流中最常见元素,优点是空间开销小,速度快。

基于Sketch的测量框架

  • NSDI’13 的 OpenSketch [5],首次将 sketch 应用在 SDN 中,是此类论文的的开山之作。
  • LD-Sketch [6]将基于计数的方法和基于 sketch 的方法结合,用于检测 heavy hitter 和 heavy changers,保持了一定的准确度和稳定性。

图2 SketchVisor 结构示意

  • SIGCOMM’17 上的 Sketchvisor [1]是基于 sketch 的测量框架,将过载流量导入 Fast Path, 完成高速环境下测量。
  • SIGCOMM’18 的 SketchLearn [2]通过解耦资源配置和精确度的参数,利用自动统计推断提取流量数据。
  • 在多变的环境下,测量的性能会受到到很大的影响, SIGCOMM’18 的 ElasticSketch [3]对此设计了一个可以根据环境动态调整的测量框架,保持测量的稳定性和准确率。

四、总结

  • 高管理能力对网络测量的性能、准确率、资源开销提出了更高的要求。
  • Sketch 是一种基于散列的数据结构,可以在高速网络环境中,实时地存储流量特征信息,只占用较小的空间资源,并且具备在理论上可证明的估计精度与内存的平衡特性。
  • Count-min [7]是一种典型的 sketch ,用到的是分类的思想:将具有相同哈希值的网络流归为一类,并使用同一个计数器计数。
  • 基于 Sketch 的方法是当下主流和热门的网络测量方法,有着广泛的应用和前景。

本文分享自微信公众号 - SDNLAB(SDNLAB)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我是攻城师

理解BitMap算法的原理

位图:一种常用的数据结构,代表了有限域中的稠集(dense set),每一个元素至少出现一次,没有其他的数据和元素相关联。在索引,数据压缩,海量数据处理等方面有...

25430
来自专栏苦逼的码农

一些常用的算法技巧总结

数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些...

22130
来自专栏GreenLeaves

TFS2018环境搭建一硬件要求

TFS可以安装在Windows Server和Windows PC操作系统中,但是TFS2018和2018只支持64位操作系统中,早期的版本没有操作系统的位数限...

41130
来自专栏机器之心

Diss所有深度生成模型,DeepMind说它们真的不知道到底不知道什么

深度学习在应用层面获得了巨大成功,这些实际应用一般都希望利用判别模型构建条件分布 p(y|x),其中 y 是标签、x 是特征。但这些判别模型无法处理从其他分布中...

11710
来自专栏smy

一张图解释负载均衡

首先当大量用户访问时候,先请求到nignx服务器,因为nignx对于高并发支持较好,所以由nignx服务器将访问需求分配给不同的apache服务器,apache...

21330
来自专栏大数据文摘

迷人又诡异的辛普森悖论:同一个数据集是如何证明两个完全相反的观点的?

在辛普森悖论中,餐馆可以同时比竞争对手更好或更差,锻炼可以降低和增加疾病的风险,同样的数据集能够用于证明两个完全相反的论点。

15930
来自专栏chenssy

多线程:为什么在while循环中加入System.out.println,线程可以停止

这个我们都知道,由于 stopReqested 的更新值在主内存中,而线程栈中的值不是最新的,所以会一直循环,线程并不能停止。加上 Volatile 关键字后,...

21640
来自专栏数据结构笔记

python基础类型(一):字符串和列表

注意到最后三个的单双引号是嵌套使用的,但是最后一个的使用方法是错误的,因为当我们混合使用两种引号时必须有一种用来划分字符串的边界,即在两边的引号不能出现在字符串...

14020
来自专栏编程坑太多

『高级篇』docker之Mesos集群架构图(23)

12140
来自专栏Python专栏

200行代码,一行行教你自制微信机器人

1) 用一个windows客户端工具运营公众号,真的很局限。虽然工具的功能很强大,能自动添加好友,自动拉好友入群,关键字回复等等,但是有一个绕不开的点,它是一款...

62520

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励