可编程硬件的广泛异质性以及可用资源和监测所需资源的动态变化使现有的全网监测方法变得不切实际。

我们提出了HeteroSketch，一个由两个主要部分组成的框架。

(1)一个剖析工具，通过预测任意硬件的性能来自动量化它们的sketch算法

(2)一个优化框架，决定测量任务的位置和设备的资源分配，以满足监测目标，同时考虑异质设备的能力。

HeteroSketch使用一种新的聚类方法实现了对大型网络（>40,000个节点）的优化部署，并能对网络拓扑结构、流量、查询和资源动态作出迅速反应。

System Overview

HeteroSketch Workflow

对于任何新设备，HeteroSketch都需要进行离线性能分析，将新的抽象配置文件添加到其设备配置文件库中。设备配置文件库允许HeteroSketch预先判断不同sketch配置的性能-资源权衡。

一旦HeteroSketch获得用户输入（监测要求），HeteroSketch的Optimizer输出草图的配置和对设备的映射（即每个设备的草图清单）以及分配给每个设备的资源（即设备配置）。基于优化器的输出，HeteroSketch将草图部署到网络中，并像其他监控系统一样收集全网统计数据。如果用户输入、网络拓扑结构、流量需求和可用资源发生动态变化，HeteroSketch将进行快速重新优化。

HeteroSketch目前支持基于sketch的流量级遥测查询，即对origin-destination（OD）上定义的流量集进行查询。然后，HeteroSketch将实例化并收集（线性合并）来自多个实例的sketch（例如，Count-Min和UnivMon）的数据，同时确保所有OD对都被监测，资源开销最小。

Challenges and Key Insights

C1: [异质性]：预测不同资源分配的sketch性能。
- insight：我们观察到
  - （1）草图的原始操作（如散列、内存更新）在很大程度上决定了数据包的处理时间
  - （2）基于数据流分析，大多数草图的数据依赖性有限，控制流有限。这意味着有足够多的独立操作要执行（无论是对同一数据包还是跨数据包），性能大致由操作的数量决定，而不是它们的相互依赖关系。
- 因此，我们设计了一个benchmark suite。
C2：[表述和可扩展性] 在异构硬件上的放置的优化形式重新导致了一个NP-Hard问题。
- insight：我们使用求解器的高级功能（双线性约束）来纳入非凸的设备配置文件。为了实现可扩展性，我们将优化问题划分为互不相干的子问题，并同时解决。我们通过将网络划分为群组来定义这些子问题。我们发现，传统的聚类技术，如频谱聚类[51]，要么导致不可行的子问题，要么解决方案远非最佳（见第6节）。我们的关键见解是根据OD-对（流量和监控要求）而不仅仅是网络结构来定义节点之间的聚类亲和力。
C3：[动态调整]
- insight：用快速路径来补充聚类方法。它利用了我们的观察，即只对直接受网络动态影响的设备子集重新计算位置/配置就足够了。

Performance Profiler

具体来说，对于每个设备类型，我们有一个三阶段的方法来确定草图的性能。

第一阶段：测量原始操作的时间。在这个阶段，我们评估了每次草图更新的下列原始操作的时间：哈希计算（计算能力）、内存访问（内存层次的影响）、抛硬币（随机数生成）和包转发。
第二阶段：对不同操作的时间进行组合。第二阶段确定不同的微观基准应如何组成，以获得每个数据包的总时间。目标是通过测试三个关键属性来捕捉设备架构如何组合原始操作的独特属性：（1）内存和计算并发，（2）转发和草图并发，以及（3）草图访问频率。
第三阶段：考虑设备配置的影响。剖析器还必须建立一个模型，说明草图和转发性能如何随设备配置（如CPU内核、微型引擎）的变化而变化。由于性能扩展可能在不同的瓶颈上有所不同，我们研究了三种草图表现：（1）小草图，引发计算瓶颈；（2）单个大草图，引发内存瓶颈；以及（3）无草图，研究转发瓶颈。

Optimizer

优化器的目标是决定哪个草图应该放在哪个设备上，每个设备应该使用哪些资源，同时满足设备约束、监测要求、流量需求，并朝着用户指定的目标进行优化。

我们将放置和资源分配问题制定为混合整数双线性程序（MI- BLP）

Scalability and Dynamics

在Gurobi中解决MI-BLP需要几个小时以上的时间，即使是规模不大的数据中心拓扑结构，有成千上万的设备。为了快速响应网络动态和扩展到更多的设备，我们使用了一个三步法。

第1步：将网络拓扑结构划分为disjoint clusters
第2步：运行优化器，将草图分配给clusters
第3步：对于每个cluster，运行优化器将草图放置到集群内的设备上。

Clustering Approach

我们使用一个特定领域的启发式方法来模仿频谱聚类。

我们的启发式方法是基于这样的观察：许多聚类解决方案为草图放置保留了足够的灵活性，产生了良好的性能

Fast Path

我们从第6.1节得到的关键观察是，子问题应该为草图保留足够的放置选择。基于此，我们发现，在网络变化事件中，只对直接受变化影响的设备A的集合进行重新计算放置就足够了。