Elastic Sketch: Adaptive and Fast Network-wide Measurements

概要

当网络面临拥塞、扫描攻击以及DDos攻击等等时,通信特征例如可用带宽、包速率以及流大小都散布非常剧烈,严重影响了测量性能。为了解决这些问题,提出了Elastic sketch。ES对于不同的任务以及平台都有一定的普适性(P4,FPGA,GPU,CPU,多核CPU,OVS)。


简介

背景

现有的网络测量方法都是在准确度、速度以及内存使用量上的一个trade off问题。且现有方法都没有解决的问题是,在网络通信各个特征大幅变化时如何实现网络的准确测量。

第一个网络特征就是可用带宽。数据中心中,管理员相比于一条单独的链路或者节点,更关心整个网络的状态,也就是全网的测量。管理员可以部署多个测量节点,这些节点周期性地向 collector汇报 sketches测量结果,这样的测量过程也需要占用一定的带宽。在数据中心里,网络拥塞也是非常常见的,这样一来,网络测量对于拥塞控制与解除问题来说就至关重要了。一方面,不能等待可用带宽去汇报测量结果,因为这些结果都具有相当的实时性,另一方面,网络测量不应该是网络中的一个负担。一个良好的解决方法是同时兼顾准确性与低带宽的占用。这里用的方法是压缩sketch算法。

第二个网络特征就是包到达速率。这项指标在短时间内可能会大幅变化。有一些路由协议是根据网络性能来调整包的发送速率。但是现有的sketches算法对于包的处理速率都是固定的,因此对于突然提高的包速率处理不好,对此,我们可以加快对于重要信息的处理过程,丢弃不重要的信息。

第三个网络特征是流大小的分配。大多数的网络流都是比较小的。我们应当将大数据流区分出来,并用不同的数据结构来存储他们。然而,流大小十分分散。有的人认为我们可以通过预测实现预先分配内存大小,但是对于小时为单位的预测大数据流是可以的,却没办法精确到秒级。因此我们需要设计一个弹性的数据结构从而动态地给大数据流分配合适的内存空间。

总的来说,为了解决现阶段的问题需要一个弹性的sketch方案:自适应带宽,包速率以及网络流量大小分布。除此之外的要求还有普适性,实时性以及准确性。

解决方案:

Elastic sketch,由heavy part和light part构成。提出了一种Ostracism技术可以保证大数据流导入heavy part 并且小数据流导入light part。

为了实现弹性伸缩,我们可以实现以下内容:

  1. 为了适应带宽,我们提出了压缩与合并sketch的算法。首先是压缩我们原有的sketch到一个合适的大小以适应现在的可用带宽,然后在用服务器来合并sketches并减少带宽使用。
  2. 当包速率提高时,我们改变其处理方法,我们仅仅记录那些大数据流并丢弃小数据流的信息。这样在损失极小的准确度的情况下可以实现更快的数据处理。
  3. 当大数据流的数量发生剧烈变化时,我们设计了一个算法动态增加heavy part的内存大小。

为了实现普适性,我们可以实现以下内容:

  1. 对于测量任务的普适性。我们保留每个数据包最不可或缺的信息,但是要丢弃小数据流的ID信息,因为根据我们观察得知处理ID通常会消耗内存但是实用性较低。
  2. 对于平台的普适性。我们分别提出了一个软件和硬件版本来表示ES,甚至针对P4也做出了适配改进。

背景和相关工作

自适应测量的挑战:

  1. 根据合适的带宽将测量数据以合适的大小发送出去。当可用带宽比较小时,发送较大的sketch将会导致较大的延迟并且影响正常的用户数据。除此之外,所有现有的测量方法都是在开始测量之前选定一个固定大小的内存。问题就是如何将sketch的大小缩小到可用带宽大小以下。设计目标是用低于现有方法一半的内存空间来实现与原方法相近的准确度。
  2. 处理包的速率适应包速率。现有方法大多是固定速率,且需要的内存空间较大(大于数据包10倍的内存空间)。设计目标是如何在包速率较低时用2倍的内存空间,以及包速率较高时用1倍的内存空间,同时保证高准确度。
  3. 在真实的网络环境中,网络流大小的分布式偏斜且变化无常的(skewed and variable)。(Skewed)大多数的网络数据流都是小流,少部分是大数据流。为了实现内存利用效率,可以分离大流与小流,因为大流往往比小流要重要得多,所以给大数据流分配合适的内存大小也是至关重要的。由于在网络中大流和小流都是未知的,因此动态地分配内存是极具挑战的。

测量的通用性方法:

  1. 流大小的估计:对任意一条网络流大小都进行规模估计。ID可以由5元组构成。本文将网络流大小用数据包的数量或者流字节大小来代替。
  2. Heavy hitter检测:将所有大小超过预先定义阈值的网络流报告出来。
  3. Heavy change检测:将所有在相邻两个时隙内流大小变化超过一定阈值的网络流报告出来。
  4. 流大小分布估计
  5. 熵估计:网络流大小的熵
  6. 势估计:网络流数量

弹性Sketches

基本思路

逻辑依据(Rationale): 根据上述提到的,我们需要区分大小数据流。我们将分流问题规约为:已知一个高速的网络流,如果用一个桶(bucket)来选择最大的网络流?因为内存大小有限,不可能实现一个完全准确的答案,因此我们应该致力于提高该算法的准确度。我们的方法与陶片放逐法(Ostracism)的思路类似。详细来讲,每一个桶(bucket)都有三个域:ID,positive votes,negative votes。已知一个ID为\(f_1\)的流传来了一个数据包,如果与bucket 中的ID一致,就增加其positive votes的值,反之增加negative notes的值。如果(\(\frac{negative\ votes}{positive\ votes} \geq \lambda\))其中λ是预先定义好的阈值,我们将原有的数据流从bucket中删除并将\(f_1\)放入到bucket中。

如图所示,数据结构包含两部分,heavy part记录大数据流,light part记录小数据流。\(h(.)\)是一个哈希函数,\(vote^+\)可以记录本数据流的数据包,\(vote^-\)可以记录其他数据流的数据包,flag标志light part里面是否包含本条数据流的positive votes。

light part是一个CM sketch, 一个CM sketch包含\(d\)个数组,每个数组都有一个哈希函数,并组成了\(w\)个计数器。给定一个进来的数据包,CM sketch取出流ID,计算\(d\)个哈希函数去给每一个数组定位一个计数器,并且在该计数器上加1。

插入:给定一个进来的流ID为\(f\)的数据包,我们把它哈希到桶\(\mathcal{H}[h(f)\%B]\)中,\(B\)是heavy part里面bucket的个数。假设bucket保存\((f1,vote+,flag1,vote-)\)。与陶片放逐法Ostracism相同的是,如果\(f\)\(f_1\)匹配,我们增加\(vote^+\),否则增加\(vote^-\)并且决定是否驱逐\(f_1\)。具体来说有以下四种情况:

  1. bucket是空的,插入\((f,1,F,0)\)
  2. \(f=f1\),\(vote^+\)加1
  3. \(f \neq f1\)且在\(vote^-\)加1后,\(\frac{vote^-}{vote^+} < \lambda\),我们将\((f,1)\)插入到CMsketch中,并且将哈希计数器加1。
  4. \(f \neq f1\)且在\(vote^-\)加1后,\(\frac{vote^-}{vote^+}\geq \lambda\), 我们将\(f_1\)剔除bucket并将\(f\)填到桶中,并初始化为\((f,1,T,1)\)\(f_1\)会被放到CM sketch中,增量大小为原\(vote^+\),注意这里的flag置为T,因为在此之前,有可能存在\(f\)流已经被插入到light part的情况。

对于任意不在heavy part的流,light part可以直接反映出其大小。对于任意一个在heavy part的数据流有两种情况:

  1. \(flag=F\),大小就是\(vote^+\)
  2. \(flag=T\),我们需要合并\(vote^+\)以及CM sketch的结果。

Elastic Sketch 的准确性在大多数情况下都是足够高的,得益于以下两点:

  1. heavy part没有任何错误:对于任何flag为F的数据流,\(vote^+\)代表的就是全部的数据流,当flag为T时,\(vote^+\)代表的是一部分的真实数据流。
  2. light part中我们没有记录流ID,仅仅记录那些小数据流的大小,因此可以使用很多小计数器(如8位计数器),相比传统sketch算法中的较大计数器,我们的方法可以更加精确。

对于精确度影响最大的就是大数据流的冲突:当两个或两个以上的大数据流哈希到同一个bucket里,其中一条大数据流就会导入light part中,使得一些小数据流过高估计了。对于该问题的解决方法就是减小哈希冲突,两个经典思路其一是使用子表,另一个就是多个key值匹配。


自适应匹配可用带宽

为了适应可用带宽,我们在发送sketches之前要先对其进行压缩。大多数的网络流都是小数据流,因此,light part的内存使用要远远大于heavy part的。这里我们要研究的内容是如何压缩合并light part,也就是CM sketch的。

压缩的主要思路是先将计数器分组,并将同一组里的计数器合并到一个计数器上。

分组:由上图所示,给定一个大小为\(zw'*d\)的sketch A(宽度\(w=zw'\),深度为\(d\)\(z\)是一个整数代表压缩率),我们的压缩方法遵循以下规定:

  1. 将sketch A划分为相等的部分,每个部分都是\(w'*d\)

  2. 我们设立一个sketch B大小为\(w' * d\)。3)有同样索引的计数器将会被分到同一个组里(\({A_i^k[j]}_{k=1,...,z}\)),因此我们可以设置\(B_i[j]=OP^z_{k=1}{A_i^k[j]}(1<=i<=d,1<=j<=z)\),\(OP\)是一个合并操作符如MAX或Sum,图例中就是取最大值,为了符合sketch B,我们也仅仅需要将哈希函数\(hi(.)\%w\)变为\(hi(.)\%w\%w'\)

合并操作:第一种是加和压缩(SC),将每一组的计数器求和。另一种就是最大值压缩(MC)。关于二者有以下结论: 1. SC不会改变原始的误差范围,MC则会让误差范围更加严格。2. 我们证实使用MC方法,压缩后的CM sketch有over-estimation的错误,但却没有under-estimation的错误,就是说只可能过度估计,不会少估计。 3. 压缩过程是很快的,比原始方法块5~8倍。 4. 不需要解压缩。 5. 压缩也不需要任何额外的数据结构。

合并sketches

如上图所示,可以利用服务器来节省带宽。每一个服务器都从测量节点收到很多个sketches,然后合并sketches并将合并结果发送到collector。为了实现合并,我们需要每一个sketches都使用相同的哈希函数。如果他们都有共同的流ID,我们建议使用求和合并,否则我们建议使用最大值合并。

求和合并(Sum Merging):给定两个相同大小(\(d*w\))的,将相对应的计数器值相加即可,这种方法简单快速但是准确率低。

对于相同大小的sketches进行最大值合并:如下图所示,给定两个sketches A和B(\(w*d\)),建立一个新的sketch \(\mathbb{C}\)\(C_i[j]=max\{Ai_[j],B_i[j]\}(1 \leq i \leq d,1 \leq j \leq w)\)


自适应数据包传输速率

在测量节点上,总是有一个输入队列来缓存数据包。包速率在大多数情况下都是比较低的,但是更糟的情况下,其速度是很高的,输入队列也很快填满了,也就很难记录所有的数据流。上一篇文章SketchVisor使用一个专用组件fast path来容纳高速率的数据包。然而,最差情况下他还要将整个数据结构都进行传输,可能会影响一定的性能。

我们提出了一个方法来应对突发流量。当包数量大于预先设定的阈值时,我们让输入包只到heavy part中,这样保留大数据流,丢弃小数据流。这样一来,只有在以下情况可能发生改变:如果一个bucket里的数据流f由另一个数据流\(f'\)替换,\(f'\)的流大小就被设置成了\(f\)。因此我们需要一个探针,当数据流量速度减小的时候,就回到之前的方法上。

上述方法在损失很小精确度的情况下实现了更高的速度。该策略被激活的时候,我们没有丢弃light part而是阻止其更新。也就是仅仅当数据包速度很快的时候才会发生信息的丢失。


自适应网络流大小分布

对于流大小分布的主要判别依据就是大数据流的数量。我们需要根据数据流的分布来调整heavy part的规模。步骤如下:首先我们向heavy part分配一个小内存空间,随着越来越多的大数据流的加入,heavy part将会满了。我们设定一个阈值T1。当 heavy part满了的时候,我们提出了一下的复制操作:将 heavy part拷贝并与原heavy part合并为一个。哈希函数也从\(h(.)\%w\)变为\(h(.)\%2w\)。这样一来,bucket就节省了一半的空间。

上图所示到达的\(f_2\)数据流哈希到了\(f_3\)的bucket位置上,这样将\(w\)翻倍,由4变到8,\(f_3\)数据流的余数可以变为6,\(f_2\)落到原\(f_3\)的位置上,这样动态实现了网络流大小的分布适应。