摘要：
监视和分析从大型ISP网络生成的流量数据在数据收集阶段以及数据分析本身都带来了挑战。
我们以这样的前提为基础——近似是处理海量数据集（如网络数据）的必要方法。我们建议在分布式网络元素和中心构建流量数据的紧凑摘要，称为sketches。这些sketches能够很好地响应那些寻找与众不同的特征的查询，我们称这类功能为heavy hitters。
在本文中，我们描述了sketches并展示了如何使用sketches来回答与聚合和趋势相关的查询，并识别heavy hitters，这可用于对网络运营兴趣进行探索性数据分析。
背景/问题：
为了对网络进行操作控制，服务提供商必须了解其网络与周围其他网络之间的关系，并了解其网络内部和网络之间的动态，故障和流量模式，但是对于大多数大型服务提供商而言，这是一项艰巨的任务。
基于网络数据的IP网络工程和运营面临两个挑战：数据收集和数据分析。
尽管存在这些困难，但是有越来越多的方法来探查网络，设置更多警报和收集更多统计信息。大型服务提供商正在加强其数据收集和分析基础结构，这将是一个漫长的过程，研究团体必须为基于网络数据的工程提供更多原理。
解决方法：
我们将描述一种用于分布式数据收集和分析的新颖方案——sketches。
sketches汇总流过的数据，其空间很小（可能是100K字节），可以很快地计算出数据流，可以在分布式中心收集，并且可以与底层网络基础架构以可交互的方式进行交互以进行网络测量。
利用此基础架构，网络管理员和运营商可以即时动手操作以执行数据分析，尤其是我们提供了一个框架，可以在sketches上进行任意数量的查询，包括简单的集合查询，例如点或范围查询，历史性、趋势相关的查询，分布式查询以及数据的集群或相似性度量。
sketches能够很好地响应发出清晰信号的查询，就是说那些在数据中脱颖而出的，我们称这类特征为“heavy hitters”。但是仅通过sketches，无法在大海捞针中找到那一根针，只能说，如果该答案在数据中不重要，我们可以提供足够好的答案。
传统流量测量：
传统收集流量数据的方法：数据将数据包头信息汇总到IP ow，ow是来自相同端口号和源/目的地对的一组数据包，其中每个连续数据包的间隔不超过特定持续时间。我们可以为每个数据流收集的数据包头统计信息（例如，使用Cisco NetFlow）包括源和目标IP地址，源和目标端口号，传输协议，ToS，TCP ags等，此外还包括每个ow以及ow中的字节和数据包的总数。
数据流数据包头和流收集方法都将信息记录为通过数据包监视器或路由器的流量。
在这两种情况下，都必须构建特殊的软件（有时甚至是硬件），以便以很高的速度高精度地收集此信息。从数据汇总和分析的角度来看，这种类型的数据输入也可能会产生问题。此外，建设数据仓库储存庞大的数据信息也显得有些不合适。
实现细节：
网络工程师和研究人员有三种基本的测量数据的窗口化方法：过滤，聚合和采样。
我们提出了第四种方法：sketches。
sketches基于随机投影。 也就是说，向量a的sketches是a的内积，具有适当的随机向量集合。 随机向量是使用“\ seeds“生成的，可以存储在很小的空间中，根据使用的随机变量不同，sketches的属性也会有所不同。
我们的主要工具是数组概要数据结构，它维护着由N个元素组成的数组的表示，并支持更新数组的值和查询值。 答案极有可能出现失败，并且成功时只能是近似的，但是数据结构的大小比数组的传统数据结构小得多。
我们将特定的数据结构称为数组sketches，数据结构支持以下操作，初始化，更新，合并，规范，cos和查询，如上图所示。
现在，我们详细描述这些操作：
- initialize（）函数返回长度为N的全零数组的sketches
- 如果草图s表示数组a，则update（s，i，v）函数返回通过将v加到ai得到的数组a'的草图
- 如果草图s1表示数组a1，草图s2表示a2，则Combine（c1，s1，c2，s2）返回矢量线性组合
的草图。
- 除此之外，还有许多更复杂的操作。
具体使用:
sketches对于使用未聚合的数据提要和回答有关聚合的查询很有用。
例如，假设有一个数据包监视器，它监视链路上的数据包，并丢弃除源IP地址和字节数之外的所有信息。
我们希望查询有关数组a的信息，ai是从IP地址i发送的字节总数。
- 首先，调用initialize（）以获取零数组的草图s。
- 其次，每当我们看到来自i的b个字节的数据包时，都调用update（s，i，b）。
- 最后，在任何阶段，我们都可以使用query（）或norm（）操作找出a。
所有操作都很快速，因为仅存储较小的s。如果sketches需要通过网络运输，sketches的小尺寸可以节省带宽。
