关键场景（这个我放到前面来了）

重新配置以降低成本（同一云区的流量通常比来自不同区域、地区或大陆的虚拟机之间的流量成本低。）

客户通过设计虚拟机的放置来降低成本，同时平衡可用性和与客户的接近程度。

给了三个例子：

属于同一个客户标签L的VM，实际上显示了两种不同的流量特征。一个是将流量或多或少均匀地发送到8个不同区域的虚拟机（图6中的第一个集群），另一个是将80%以上的流量发送到一个单一区域（第二个集群）。客户有可能重新配置后一个集群的虚拟机的位置，以避免区间流量。虽然流量倾斜在所有的虚拟机上都是可见的（所以客户可能已经能够使用虚拟机标签检测到它），但CloudCluster能够识别出需要重新配置的精确的虚拟机集合。

例子二：使用CloudCluster，云提供商可以确定集群内和集群间的流量，并确定其中有多少流量跨越了区域、地区或大陆的边界。利用这一点，它可以估计重新配置虚拟机位置所带来的成本节约。

第一个案例是项目A的集群C，该集群中的虚拟机位于单一云地区的不同区域。 C中几乎90%的流量是区内流量，这在大多数云提供商那里是免费或相对便宜的（[15]、[8]、[11]）。然而，剩余的流量穿越大陆边界，占了向C收取的总成本的很大一部分。如果客户在流量来自的另一个大陆上的区域提供一个小型集群，它可以将归属于这个集群的成本减少41.2%（图7）。

第二种情况是项目A的集群C′，其流量主要是区域间的（区域内流量<0.1%）。将C′中的虚拟机移到R区（有利于出口的安置）可以减少21.1%的成本，而将这些虚拟机移到R区，它们从那里获得最多的流量（有利于入口的安置）可以减少15.1%的成本（图8）。

异常检测器

原理：滑动窗口

检测指标：

each aggregation window
the total volume in bytes
the total flow count
the number of communicating VM pairs between each pair of clusters

检测到的案例

由于对接路由器故障导致的相关流量转移
由于虚拟机迁移导致的结构变化
项目重新配置导致的结构变化

可能的label misconfiguration

silhouette analysis来检测instrinsic performance of clustering

potential mis-configured VMs

CloudCluster可以通过检测集群中的离群机器类型来识别错误配置的虚拟机。

CloudCluster设计

Goals, Approach and Overview

CloudCluster的输入是一个云项目的虚拟机到虚拟机的流量矩阵，包含每个虚拟机之间在一个固定聚合窗口的流量。

在第4节中，我们将讨论聚合窗口的实际值和采样频率。形式上，我们用Y表示这个流量矩阵，尺寸为n×m。其中n是源虚拟机的数量（属于所考虑的这个特定项目），m是目的地虚拟机的数量。（不一定都属于同一个项目，因为一个项目中的虚拟机可以与外部客户或其他项目中的虚拟机进行通信）。

挑战：

noise：引入噪声矩阵
scale：We hypothesize that VMs in a group have similar traffic patterns（这是解决方案吗？有些奇怪）

Feature scaling

我觉得这个点比较弱

Y的每一行都可以被视为一个（高维）特征。然后，在这个特征空间中识别相似性，相当于识别具有相似流量模式的虚拟机。

在实践中，即使在一个项目中，虚拟机之间的流量可以跨越几个数量级。这可能使我们难以区分低流量和中等流量模式。聚类依赖于距离度量，而许多适用的距离度量对较大的数值不成比例地敏感。

对数缩放。特征缩放将每个特征的范围归一化，以使聚类算法对高度变化的交通量具有稳定性。

在现有的特征缩放方法中，标准化和minmax缩放不能处理我们在云项目中看到的流量范围。云项目中的流量可以跨越几个数量级（从0到109），并且具有偏态分布；像Minmax缩放这样的线性变换，或者像标准化这样的假定高斯性的变换，效果都不好。出于这个原因，我们选择了对数缩放，它使用流量的自然对数，而不是原始值；这可以更好地处理量的变化（我们在第4.4节中通过实验证明这一点）。

Estimating M

估计奇异值：Singular value thresholding

估计奇异值的数量：an elbow finding heuristic such as one introduced by [51]

SVD的主要好处。

从大型云项目中获得的流量矩阵可能有几万行和几万列。距离函数（用于计算行-相似性）在特征/列的数量上呈指数级增长。
此外，在高维特征空间和噪声数据中，距离指标是不可靠的[60]（维度的诅咒）。

考虑到这一点，对M的缩减等级估计以及对缩减维度的特征空间的投影使得我们的算法在保留其大部分结构的同时保持了对规模的稳健。

Hiearchical Clustering

已有的一些工作

先前的方法，如[28]，已经在降维和K-Means聚类之间建立了联系。然而，在我们的使用案例中，我们希望使用降维来实现对规模和噪声的稳健性，但同时保持对产生的聚类数量的精细控制。

鉴于我们不知道要产生的聚类数量，围绕K-Means[41]的许多现有工作并不能满足我们的需求。

基于密度的方法，如DBSCAN[32]和OPTICS[22]不需要输入聚类的数量。然而，它们依赖于其他的阈值参数，估计这些参数需要领域知识（例如，关于项目的信息超出了我们现有的抽样交通量），而且在高维数据中可能很难。

MeanShift[29]和Affinity Propagation[33]也不需要集群的数量，但它们的主要缺点是时间复杂性，这取决于收敛前的迭代次数。我们在第4.4节中还表明，MeanShift和Affinity Propagation在虚拟机聚类的情况下表现并不理想。

Agglomerative clustering

聚合式聚类。与基于密度的方法类似，分层聚类并不要求事先确定集群的数量。

CloudCluster使用聚集式聚类[48]，这是一种自下而上的分层聚类方法：每个虚拟机（行）从自己的聚类开始，聚类被递归地合并在一起。它使用Ward linkage[56]来决定哪两个集群应该被合并：在每个迭代中，该技术选择两个集群，使集群内总误差平方的增加最小[44]。在对虚拟机进行聚类的情况下，这样做会产生具有同质流量模式的虚拟机集群，这种方差最小化的特性与K-Means的目标函数相似。聚合聚类的输出是一个虚拟机（行）的树状图；叶子节点是虚拟机（行），非叶子节点是嵌套集群。每个非叶子节点都有一个值（"高度"），它是在该节点合并的两个实体之间的沃德距离[44]。

聚类的阈值切割

在树状图中，每个非叶子节点代表一个潜在的集群（包含其子树中的所有叶子节点）。CloudCluster必须从这个树状图中提取不相交的聚类。

一个简单的方法是选择一个固定的树高。

Cloudcluster的方法是cluster inconsistency（第六页最下面）。实际上就是自己的树高和子树高的一些平均值和方差的简单操作。

当决定是否合并两个子树（或嵌套集群）时，不一致性指标量化了新合并的集群与其中的嵌套集群相比会有多大不同。低值意味着合并后的聚类将与它下面的嵌套聚类相似。相反，高的不一致性意味着合并后的聚类包含的嵌套聚类是相当不同的。因此，当不一致性得分小于阈值μ时，该算法会合并嵌套集群。

估算μ。（选knee，也就是凸点）

我们不需要手动选择阈值μ，我们使用[51]来确定μ。然后，我们根据阈值μ对树状图进行切割，从而得到一组聚类。

cluster merging

最后的合并。

在实践中，我们发现，对于有数千台虚拟机的项目，我们的方法产生了几十或几百个集群，在虚拟机流量模式方面的内部变化很小。然而，它过于激进，我们发现我们可以在一个快速的后处理步骤中合并其中的一些集群。

为此，我们确定由分层聚类产生的每个集群的中心点。每个中心点都可以被看作是候选聚类的一个特征。我们将这些中心点中的每一个都作为一个新的实体，并对这些实体进行聚类。

受MeanShift[29]的启发，我们计算集群中心点的成对余弦距离并递归合并成对的集群，直到没有两个集群的中心点距离小于固定的合并阈值θ。

evaluation

methodology and metrics

数据集

我们使用来自云客户的匿名聚合流量日志（特别是谷歌VPC日志[10]，关于客户数据的道德使用声明，请参见第1页的脚注）来生成我们的评估数据集。该数据集包括具有各种类型工作负载的虚拟机项目（例如，网络服务器、负载均衡器、图像转码器、键值存储等）。它包括谷歌内部的项目和属于外部客户的项目。数据集中的每个流量矩阵都包含统一采样的虚拟机到虚拟机的流量，并在1小时内汇总。我们使用抽样数据；抽样对于测量系统的扩展是必要的，而且，只要抽样机制是统一的，我们期望我们的聚类算法能够像在未抽样数据上一样工作，因为统一抽样应该保留虚拟机之间的流量关系。

implementation

客户流量日志被存储在谷歌的Colossus文件系统中[30]。 CloudCluster将流量日志加载到Dremel[43]中，并使用Dremel的类似SQL的查询方式，对聚合窗口内的数据进行分析，按src-dst VM对进行分组，并按流量进行聚合。 CloudCluster在一个拥有128G内存的单机上运行，将Dremel的汇总结果加载到一个数据框中，提取出虚拟机到虚拟机的流量矩阵，然后运行第3节所述的算法。我们评估的项目的流量矩阵可以很好地适应一个单一的虚拟机。

方法

为了证明CloudCluster产生的集群与按位置和功能分组的虚拟机相一致，我们对数据集中的15个项目的不相干的集合进行了两个实验。

仔细命名的组。有关于每个虚拟机的位置和功能的信息。对于这些项目，客户根据功能仔细地命名了每个虚拟机，可能是为了模拟项目的可管理性。对于这一组的项目，我们表明CloudCluster的集群，当按虚拟机位置（虚拟机的区域，第2节）进一步分组时，与按位置和虚拟机标签（即功能）进行的虚拟机分组非常匹配。
粗略命名的组。我们有每个虚拟机的位置信息，但是虚拟机的命名方案并不总是表明功能，或者粗略地表明功能（我们将在后面精确解释这意味着什么）。对于这组项目，我们表明CloudCluster的分类，当按虚拟机位置进一步分组时，与按位置（区域）和虚拟机标签进行的虚拟机分组并不匹配。

我们强调，云提供商总是知道虚拟机的位置，但不能总是知道虚拟机的功能，因为基于功能的命名不是我们所知的任何云服务API的要求。

衡量标准。我们使用两个标准的聚类好坏度量，同质性和完整性[49]。