SketchLearn: Relieving User Burdens in Approximate Measurement with Automated Statistical Inference

概述

在巨大的网络流量下,网络测量对于资源的利用有着严格的限制。近似测量的方法可以节省一定的资源,需要人工对其进行合适的配置。详细来说,典型方法通过严控参数,在合理的测量误差下提供足够的资源。我们设计了SketchLearn,这是一个sketch-based的测量框架,可以通过学习统计特性解决资源冲突从而消除了网络流量上的冲突。

介绍

由于网络资源的限制,许多的网络测量方法都需要在资源利用与测量准确度之间进行权衡。基本思路就是将次线性的数据结构压缩,并在有限的资源下理论保证恢复。尽管这具有理论可行性但是现有方法都不方便使用,因为巨大的网络流总是在竞争有限的资源,并由资源冲突引发一定的错误,为了消除这些错误,还需要分出一些资源来实现准确度。综上,资源配置与准确度之间还有紧密的联系,这些联系导致了一部分限制:

  1. 管理员需要将错误容忍级别当做一个参数引入到资源配置算法中。
  2. 每一种资源配置都对应一个阈值参数。
  3. 理论分析只给出了基于实际负载的最坏结果。
  4. 每一种配置都被特定的流所限制。
  5. 管理员不能容忍较大的测量误差。

由于以上限制的存在,如何在理论方法与实际应用之间架起桥梁对我们来说是一个挑战。

为了解决这个问题,我们使用的sketch-based方法可以完全记录所有观测到的数据包的统计数据,他们都有固定的数据结构。SketchLearn的基本思想是将固有的资源矛盾的统计特征描绘出来,而非追求一个消除所有资源冲突的配置参数。详细的说,SketchLearn建立了一个多层的sketch来追踪网络流记录的频数。这个多级结构引出了一个计数器的多bit-level的高斯分布。SketchLearn利用高斯分布来确定其限制。它反复从多级sketch中推算并提取出大数据流,直到剩余的多级sketch满足高斯分布。通过分离大小数据流,SketchLearn消除了资源冲突并且提高其测量准确性。

研究动机

在一个时间间隙里每条网络数据流的频数被称为epochs。每条流都用一个flowkey作为标志,例如5元组或者源/目的地址对。通过每条流的频数,我们都可以得到较复杂的数据流统计量,如heavy hitters, heavy changers, superspreaders 以及 DDoS,cardinality(势),流大小分布和熵。

设计要求

  1. 较小的内存使用
  2. 较快的包处理速度
  3. 实时响应
  4. 通用性

现有方法的一些限制

  1. 很难说明预期误差
  2. 很难处理不同的阈值(针对那些阈值作为一项输入的方法来说)
  3. 很难根据理论依据来调整参数配置
  4. 很难重新定义flowkeys
  5. 很难去检查其准确性

SketchLearn 概览

功能设计

对于每位进行追踪的多级sketch SketchLearn维护一个由多个小sketches所组成的多级sketch,每个多级sketch都会对一个给定的flowkey进行特定的网络流数据跟踪。结合统计模型,SketchLearn不仅仅减少了sketch的大小,还加强了对于资源的利用,同时还使得flowkey可以按需随意定制。在多级sketch中,每一个flowkey都有多个域来组成,如5元组。

对大小数据流进行分离 多级sketch提供了一个关键的特性就是如果没有大数据流,他的计数器就跟从高斯分布。这样,SketchLearn从多级sketch中抽取大数据流,并且剩下小数据流的计数器形成高斯分布。这样的分离使得SketchLearn解决哈希冲突。例如SketchLearn只对那些抽取出来的大数据流进行hitter检测。

无参数的模型接口 SketchLearn在不借助任何参数的情况下实现对于大小数据流的区分。它反复学习多级sketch中的统计分布并且利用这种分布来指导大数据流的提取。注意这里的无参数不是说SketchLearn是零配置的,例如对于heavy hitter的检测仍然需要一个阈值,但是SketchLearn已经尽可能减少了配置量。

对于独立数据流的误差测量对于给定数据流统计量SketchLearn都有相应的误差测量。我们不需要识别任何误差,相反的是我们利用这个来识别正确的数据流

全网范围SketchLearn可以部署到全网的测量节点上。

架构设计