SketchVisor: Robust Network Measurement for Soware Packet Processing

概要

Sketch是一种紧凑的数据结构,以固定的内存大小来统计网络数据包。传统的sketch-based方法都是消耗大量的CPU资源,例如虚拟机或者容器环境下,同样位置的多个应用都会抢占资源。传统的sketch-based算法过于简洁,因此在将其应用到实际环境当中,就需要加入额外的扩展功能从而导致运算量的增加。虽然在数据中心的链路速度并不总是高要求的,但是这依然是重要的指标。

本文提出的SketchVisor是一种针对软件数据包处理的鲁棒性网络测量框架。即使在很高的网络流量当中,SV都会有很好的性能以及很高的准确性。SV 引入了独立的数据通路(fast path)以提供快速但是低准确度的测量,以解决那些不能被及时处理的数据包。之后,通过sketch-based以及fast path准确恢复整个网络范围内的测量结果。

简介

特别的,SV部署在一个分布式的数据平面上,网络管理员将对不同的数据平面上分配任务,如果这些任务过载或者不能被及时处理,那么就会将任务重定向到fast-path上。本文针对fast-path提出了一个top-k算法以跟踪大数据流。Top-k可以实现较低的偿还过程以及缩紧评价指标。还维持了一个全局的计数器用来追踪进入fast-path的网络流,从而来捕获所有较小的网络数据流的特征。

除此之外,SV还部署了个中心化的控制平面来合并本地的测量结果(sketch-based以及fast path的结果),fast path不可避免的会出现准确性的损失,本文形式化了一个矩阵插入问题,使得在控制平面可以恢复这些丢失的数据。


背景

网络测量

本文着重考虑一下的几个网络数据统计量:

  • Heavy hitter:在一个时期中流字节大小超过一定阈值的网络流。

  • Heavy changer:在两个连续的时期中发生改变的字节大小超过一定的阈值的网络流。

  • DDos:一个目标host在一定时期中接到的网络数据包超过了阈值。

  • Superspreader:在一个时期内,源host向多于阈值个目标host发送数据。

  • Cardinality:势。在一个时期内不同网络流的数量。

  • Flow size distribution:一个时期内不同字节数范围内的分数大小。

  • Entropy:一个时期内流大小的熵。


概览

设计目标:

  • 性能
  • 资源效率
  • 精确性
  • 通用性
  • 简洁性

数据层:

在每一个host上都部署了一个测量模块,每一个模块都处理连续不断的数据流并且统计分析该数据。为了防止多次测量,我们可以只测量出或者入的数据,再或者利用哈希来选择监控不连续的数据包。测量模块被分为两个部分,normal path和fast path。Normal path部署一个或者多个sketch-based方法, fast path作为一种补充,通过部署快速但是低准确度的测量方法。正常情况下,在normal path里采用FIFO buffer。 当数据流负载过重时,buffer满了,SV将重定向这部分数据包到fast path,然后收集这部分流量的数据。由网络管理来决定采用哪一种sketch-based方法。

fast path 所面临的挑战是:

  • 足够快一致于可以吸收所有重定向的网络数据流
  • 虽然比normal path的准确度低但是也要保持一定的准确度
  • 对于不同的网络统计来讲具有一定的通用性。

控制层:

从多个host收集本地测量结果并且合并,提供网络范围内的测量结果。目标是当所有流量都走normal path时,在网络范围内提供准确的测量结果。

控制层面临的挑战:

  • 排除fast path 所导致的测量错误,也就是说所有的错误都是由sketch本身所产生的。这样一来,对于fast path 设计带来了巨大挑战,要保证所有的测量任务的兼容。

Fast path

Fast path 主要保证了系统的鲁棒性,如果没有这个设计,normal path必定要丢弃那些过载的数据流,从而在准确度上作出妥协。

设计fast path要尽可能多地去追踪网络数据信息,在大多数情况下网络都是被几个较大规模的数据流所占有,这个假设就会引起很多sketch 设计(要求该设计识别大规模数据流),在我们的设计中就着重关注最大规模的数据流,或者前k个数据流(k取决于内存空间)。

如果只关注大规模的数据流,那么必定会忽视小数据流的信息,这些对于基于连通的网络统计量来说也很重要,但同时对于所有的小数据流都进行追踪是不现实的。幸运的是,sketch-based解决方法会估计不同流的统计信息。观察发现小流的影响微不足道,因此我们用一个全局变量计数(此处应该是指统计大数据流),并在控制层来推断具体的sketch统计数据。


方案概览

fast path 算法是基于Misra-Gries‘s算法的top-k算法,但是原算法有两点对于高性能和准确性的限制。首先,改进算法剔除一个小数据流然后加入一个潜在的大数据流,它表现出\(O(k)\)的复杂度去更新k个计数器,当有很多个小的数据流时,节省下来的开销就很可观了。其次,改进算法对于估计top-k条数据流的界限要求比较宽松。我们结合了PLC算法,可以提高偏差数据的准确率。最后,每条数据流都用三个计数器来追踪确保每条流都有严格的上界和下界。

主要思路就是保证top-k条流一直在哈希表H中,当H满了就适当移除一条不满足条件的数据流。当接收到一条大小为v的数据流\(f\)时,先更新统计计数器\(V=V+v\),如果\(f\)在哈希\(H\)中,那么就更新\(r_f=r_f+v\),如果\(H\)未满,那么就直接加入\(f\)并初始化为\((E,v,0)\),如果\(H\)已满,那么就要计算一个减小值\(e\),并对\(H\)中的所有流的\(r\)参数减小\(e\)\(d\)参数增加\(e\)。倘若有\(r\)小于0那么将被剔除,并加入合适的流。


网络范围内的恢复

基本思想

控制层通过周期性的收集本地数据提供全网范围内的测量数据,它可以通过矩阵加将所有的sketch合并到一个sketch上(合并后的结果用N来表示),将多个哈希表合并成一个,并且将计数器的结果合并成一个,注意到之前算法有不确定性,因此它只维护top-k个数据流并且没有跟踪到具体的某一个小的数据流上。这部分的研究目标就是精确恢复。

我们分解网络流数据成两个向量,\(x\)表示哈希表\(H\)中的流实际的字节数,\(y\)表示其他流实际的字节数。如果一个流不存在,那么所有的数据就都是0了。\(x+y\)就表示了fast-path中的每一个数据流。

为了恢复出所有的网络流T,我们可以将fast path中的所有流都注入到normal path中,本质就是用sketch方法来处理\(x+y\),表示为\(sk(x+y)\)

\[ T=N+sk(x+y) \]

由于fast path 并不是追踪到每条数据流,因此\(x\)\(y\)实际上是未知的,但是我们可以通过统计量来明确其值的限制条件。\(x\)\(y\)\(l_1\)范数之和可以如下表示:

\[ \lVert x\rVert_1 + \lVert y\rVert_1 = V \]

除此之外,合并后的哈希表H也给出了每条流的上/下确界:

\[ rf+df \leq xf \leq rf+df+ef \]

前两个等式表述的是网络流的聚集合并特性,第三个式子表示的是每条流的错误区间。但是上述信息还不够完整全面,有很多工作都针对其做矩阵插入的解决方案,本文则着力于找到最佳的估计矩阵T,以实现最好的恢复效果。

压缩感知

首先明确出\(T,x,y\)的特性

\(T\)接近是一个低秩矩阵。网络中大多数都是较大流量的数据流,又因为大数据流会引起更多的重视,因此,计数器的统计量大多近似。

\(x\)\(sk(x)\)是稀疏的。因为\(x\)只包含top-k条流在哈希表中,且整张表的规模是非常大的,因此我们可以将\(x\)视作一个稀疏向量,又因为\(x\)在sketch算法中由计数器限定了一定的数量,所以\(sk(x)\)也是稀疏的。

\(y\)\(sk(y)\)是低噪的。由y所记录的所有数据流都是规模小且区分度低。因此我们可以将y视作一个低噪的向量。

我们使用奇异值分解方法,对几个sketch矩阵产生了低秩近似。

目标函数 我们将上述的特性引入到目标函数当中,然后利用压缩感知框架LENS去恢复T,LENS就是这样一种算法,可以将网络流矩阵分解成低秩、稀疏并且低噪的部分。通过LENS我们将目标函数设定为:

\[ minimize: \alpha\lVert T\rVert_* + \beta\lVert x\rVert_1 + \frac{1}{2\gamma}\lVert y\rVert^2_F \]

\(\lVert T\rVert_*\) : T的核范数,可以约束低秩矩阵。 \(\lVert x\rVert_1\) : x的l1范数,约束x的稀疏性。 \(\lVert y\rVert^2_F\) :Frobenius 范数,约束y里面的大元素。