概述
在巨大的网络流量下，网络测量对于资源的利用有着严格的限制。近似测量的方法可以节省一定的资源，需要人工对其进行合适的配置。详细来说，典型方法通过严控参数，在合理的测量误差下提供足够的资源。我们设计了SketchLearn，这是一个sketch-based的测量框架，可以通过学习统计特性解决资源冲突从而消除了网络流量上的冲突。
介绍
由于网络资源的限制，许多的网络测量方法都需要在资源利用与测量准确度之间进行权衡。基本思路就是将次线性的数据结构压缩，并在有限的资源下理论保证恢复。尽管这具有理论可行性但是现有方法都不方便使用，因为巨大的网络流总是在竞争有限的资源，并由资源冲突引发一定的错误，为了消除这些错误，还需要分出一些资源来实现准确度。综上，资源配置与准确度之间还有紧密的联系，这些联系导致了一部分限制：
- 管理员需要将错误容忍级别当做一个参数引入到资源配置算法中。
- 每一种资源配置都对应一个阈值参数。
- 理论分析只给出了基于实际负载的最坏结果。
- 每一种配置都被特定的流所限制。
- 管理员不能容忍较大的测量误差。
由于以上限制的存在，如何在理论方法与实际应用之间架起桥梁对我们来说是一个挑战。
为了解决这个问题，我们使用的sketch-based方法可以完全记录所有观测到的数据包的统计数据，他们都有固定的数据结构。SketchLearn的基本思想是将固有的资源矛盾的统计特征描绘出来，而非追求一个消除所有资源冲突的配置参数。详细的说，SketchLearn建立了一个多层的sketch来追踪网络流记录的频数。这个多级结构引出了一个计数器的多bit-level的高斯分布。SketchLearn利用高斯分布来确定其限制。它反复从多级sketch中推算并提取出大数据流，直到剩余的多级sketch满足高斯分布。通过分离大小数据流，SketchLearn消除了资源冲突并且提高其测量准确性。
研究动机
在一个时间间隙里每条网络数据流的频数被称为epochs。每条流都用一个flowkey作为标志，例如5元组或者源/目的地址对。通过每条流的频数，我们都可以得到较复杂的数据流统计量，如heavy hitters, heavy changers, superspreaders 以及 DDoS，cardinality(势),流大小分布和熵。
设计要求
- 较小的内存使用
- 较快的包处理速度
- 实时响应
- 通用性
现有方法的一些限制
- 很难说明预期误差
- 很难处理不同的阈值（针对那些阈值作为一项输入的方法来说）
- 很难根据理论依据来调整参数配置
- 很难重新定义flowkeys
- 很难去检查其准确性
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可以部署到全网的测量节点上。