微服务架构的实用服务放置方法

摘要

近年来，随着自发部署的Wi‐Fi热点和家庭网络数量不断增加，社区网络（CNs）发展迅速。这些由志愿者拥有和管理的网络为其成员和公众提供各种服务。为了降低服务部署的复杂度，社区微云最近成为向社区用户提供云服务的一种有前景的推动手段。通过将服务贴近消费者，微云不仅追求更好的服务性能，还致力于降低在社区网络内部署主流互联网服务的准入门槛。然而，服务的提供并不简单。由于社区网络拓扑结构庞大且不规则，软硬件多样性高，因此需要在网络中对微云和服务进行“谨慎”的放置。为此，本文提出利用网络的状态信息来指导服务放置决策，并通过一种快速的启发式算法实现，这对于快速响应变化的条件至关重要。为了评估其性能，我们将所提出的启发式算法与基于随机部署的方法在Guifi.net（全球最大的社区网络）中进行比较。实验结果表明，在带宽增益方面，我们的启发式算法性能持续优于随机部署，提升达211%。我们在一个真实的在线视频流服务中量化了该启发式算法的优势，证明视频块丢失显著减少，丢包率降低了37%。此外，通过使用一种流行的Web 2.0服务，我们表明，采用我们的启发式算法可使客户端响应时间减少高达一个数量级。

索引术语

服务放置；社区网络；微云；

一、引言

自21世纪初以来，社区网络（CN）或“ Do-It-Yourself”网络为应对农村和城市社区日益增长的网络连接需求而迅速发展。社区网络的主要特点是采用“自下而上”的方式构建，混合使用无线和有线链路，由公民群体自行建设、运营和管理网络。这种开放且聚合式的建设过程最终形成了一个高度异构的网络，具备自管理链路和设备。例如，设备通常属于“低技术”类型，完全由现成硬件和开源软件构建，并通过无线链路进行通信。这带来了诸多挑战，例如缺乏服务保障、资源利用效率低下以及安全性缺失等。

这些挑战并未阻碍社区网络（CN）的发展。例如，位于西班牙加泰罗尼亚地区的Guifi.net1,就是这一模式的成功范例。Guifi.net被定义为由其成员构建的开放、免费且中立的社区网络。也就是说，公民和组织共同投入资源并协调努力，以建设和运营本地网络基础设施。Guifi.net始于2004年，至今已发展成为一个拥有超过32,000个运行中节点的网络，使其成为全球最大的社区网络[1]。为了说明情况，图1描绘了近两年来接入互联网的总入站流量（粉色）和出站流量（黄色）的变化趋势。仅从该图即可看出，Guifi.net的流量已增长了两倍。流量峰值对应于新用户的加入以及网络中带宽密集型服务的部署。事实上，包括GuifiTV、图形服务器、邮件和游戏服务在内的大量服务正在Guifi.net内部运行。所有这些服务均由个人、社会团体以及小型非营利或商业服务提供商提供。

Guifi.net的最终目标是创建一个覆盖高度本地化区域的完整数字生态系统。但这一使命并不简单，因为只需粗略查看用户需求的服务类型，就会发现互联网服务（代理和基于隧道的）所占比例超过50%。这证实了Guifi.net用户通常对主流互联网服务感兴趣[2],，这给“薄弱”的骨干链路带来了沉重负担，用户因此经历较高的服务波动性。

除了其他问题外，这一问题还推动了为Guifi.net 用户设计“替代性”服务部署模型的发展。其中一种模型是基于微云的模型。微云本质上只是一个平台，用于向庞大社区网络内的本地公民群体提供服务。服务可以是任何类型，从个人存储到视频流和P2P电视[3]。请注意，该模型不同于雾计算，后者通过在设备和数据中心之间引入一个中间层来扩展云计算。微云则采取相反的路径，将服务置于更靠近消费者的位置，从而在互联网中无需或仅需极少的操作。其理念是利用用户之间更短、更快的连接，以提供更好的服务并减轻骨干链路的过载。

然而，这种方法带来了新的挑战，例如在社区网络内对微云进行最优部署以克服性能次优的问题。Guifi.net 也不例外。显然，一个对底层网络状态不敏感的部署算法可能会导致严重的低效率。尽管从概念上看很简单，但由于社区网络和使用模式的动态特性，要计算出最优决策仍然具有挑战性。

本文试图回答以下两个研究问题： 1) 首先，在具备充足的状态信息的前提下，网络感知部署是否足以向社区网络用户交付令人满意的性能？ 2) 其次，服务的冗余部署能否进一步提升性能？

为回答这些问题，本文提出了一种新的放置启发式方法——BASP（带宽与可用性感知的服务部署），该方法利用底层CN的状态来优化服务部署。具体而言，它考虑了两类信息：i）网络带宽和ii）节点可用性，以做出优化决策。与需要数小时才能完成的穷举搜索相比，BASP运行速度快得多，仅需几秒钟即可完成，同时能够达到同样理想的结果。

我们的结果表明，BASP在端到端带宽方面，相较于Guifi.net中现有的就地部署和自然快速策略——即随机部署，性能持续提升了211%。受这些发现的推动，我们随后在真实CN中运行了BASP，并量化了根据BASP部署实时视频流和Web 2.0服务后所实现的性能提升。我们的实验结果表明，使用BASP后，对等端的视频块丢失最多减少了3个百分点，相当于丢包率降低了37%的减少，这是一个显著的改进。此外，在使用BASP部署Web 2.0服务（即社交网络服务）时，客户端响应时间最多减少了近一个数量级。

本文的其余部分组织如下。在第二节中，我们描述并分析了QMP网络的性能。第三节定义了我们的系统模型，并介绍了我们的BASP启发式方法。第四节讨论了评估结果。第五节展示了视频流和Web 2.0服务的实际部署实验，并进行讨论。第六节描述了相关工作，第七节总结全文并探讨未来的研究方向。

II. 网络表征

我们的服务放置策略考虑了两个方面：节点可用性和网络带宽。作为第一步，至关重要的是

以了解这两个维度在真实CN中的行为。我们通过对一个生产级无线CN（如QMP（快速网状网络项目）网络）进行为期五个月的表征来实现这一目标。我们的目标是确定网络的关键特征（例如带宽分布）及其节点的关键特征（例如可用性模式），这些特征有助于我们设计用于CN中智能服务放置的新启发式方法。

A. QMP网络：简要背景

QMP网络于2009年开始在西班牙巴塞罗那市的一个名为桑茨的区域部署，是快速网状网络项目（QMP）2的一部分。QMP是一个城市网状网络，属于Guifi.net CN的一个子集，有时也称为GuifiSants。截至撰写本文时，QMP拥有约71个节点。网络中分布有两个网关（代理），用于将QMP连接到 Guifi.net其余部分和互联网（见图3）。关于QMP的详细描述可参见[4]。

通常，QMP用户在屋顶上安装带有Wi‐Fi接口的室外路由器（OR），并通过以太网连接到室内AP（接入点）以构成本地网络。QMP中最常见的OR是NanoStation M5，如图2所示，用于在网络中建立链路，集成了扇区天线，并配备带有无线802.11an接口的路由器。一些战略位置部署了多个NanoStations，以提供更大的覆盖范围。此外，部分长达数公里的链路使用抛物面天线（ NanoBridges）建立。QMP中的OR刷写了在QMP项目内部开发的Linux发行版，该发行版是OpenWRT3的一个分支，并采用BMX6作为网状路由协议[5]。

连接到ORs的用户设备包括Minix Neo Z64和 Jetway迷你PC，它们配备了Intel Atom CPU。这些设备运行Cloudy操作系统，可在Docker容器中运行服务。

方法论与数据收集 ：通过SSH连接到每个QMP OR并运行QMP发行版中提供的基本系统命令来获取测量数据。这种方法的优点是无需在节点上安装任何更改或额外软件。在2016年7月至2016年11月的五个月期间，每小时进行一次实时测量，我们的实时监控页面和数据在互联网上公开可用4。我们使用这些数据来分析QMP网络的主要方面。

B. 节点可用性

QMP中所用异构硬件的质量和状态会影响链路的稳定性以及网络性能。QMP节点的可用性被用作新成员对网络连接质量预期的间接衡量指标。

图4显示了在五个月期间收集的节点可用性的经验累积分布函数（ECDF）。我们将节点的可用性定义为该节点在其首次出现后，在每次捕获中出现的时间百分比。捕获是指我们从QMP网络获取的每小时网络快照（总共进行了2718次捕获）。图4显示，25%的节点可用性低于90%，其余节点的可用性介于 90−100%之间。在QMP这样的社区网络中，用户通常不会刻意重启设备，除非需要进行升级，而这种情况并不常见。因此，节点在捕获中出现的次数比例可以较好地反映因随机故障导致的节点可用性。

当我们比较在类似研究和PlanetLab环境中报告的可用性分布时，QMP节点断开连接或无法从网络访问的可能性更高。PlanetLab在其节点上表现出更高的平均可用性（即sysUpTime），这可能是因为它是在更加稳定的计算机和环境中运行的实验平台。此外，QMP成员不仅负责其节点的维护，还需确保与其他网络部分保持最低限度的连接性。

图5展示了在捕获期间的节点和链路数量。该图显示 QMP正在增长。总体上，检测到77个不同节点。其中，71个在整段测量期间处于活动状态。大约有6个节点在大多数捕获中未被发现。这些是来自其他网状网络和用于各种实验的实验设备中的临时工作节点。图5还显示，节点之间使用的链路平均有175条是双向的，34条是单向的。对于双向链路，我们将相反方向的两条链路计为一条链路。

总之，节点可用性对于识别那些能够最小化长期服务中断的节点至关重要。根据测量结果，我们为每个节点分配可用性评分。高可用性节点是部署微云的潜在候选节点。

C. 带宽特征分析

在QMP和Guifi.net网络上运行的大量服务属于网络密集型（带宽和延迟敏感），在网络节点[2]之间传输大量数据。这类服务的性能不仅取决于计算和磁盘资源，还依赖于其部署节点之间的网络带宽。因此，在网络中进行服务放置时，考虑网络带宽至关重要。

首先，我们通过研究QMP网络的带宽来表征其无线链路。图6显示了所有链路的平均带宽分布。该图表明，链路吞吐量的均值可拟合为21.8 Mbps。同时，图6还显示60%的节点的吞吐量为10 Mbps或更低。网络中测得的21.8 Mbps的平均带宽使得许多流行的高带宽需求服务能够运行而不会出现严重中断。这种高性能可归因于网络中使用的802.11an设备。

为了观察带宽的变化性，图7展示了三条最繁忙链路在两个方向上的带宽平均值。上传操作用实线表示，下载操作用虚线表示。三条最繁忙链路的节点在图的顶部被突出显示。我们注意到，两个方向测得的带宽不对称性并不总是由用户流量的不对称性引起的（图中未显示）。例如，在6点左右，当GSgranVia255节点的用户流量最低且两个方向相等时，图7中观察到的链路带宽不对称性仍然存在。因此我们得出结论：尽管带宽偶尔会受到流量的轻微影响，但我们所看到的链路不对称性可能是由于链路特性所致，例如两端存在的干扰程度或不同的发射功率。

为了测量链路的不对称性，图8展示了在每个方向上测得的带宽。右侧还绘制了偏差绝对值相对于均值的箱线图。该图显示，大约25%的链路其偏差高于40%，同时另外25%的链路其偏差小于10%。在对设备的信号功率进行一些测量后，我们发现部分社区成员重新调整了其设备的无线电设备（发射功率、信道及其他参数），试图获得更好的性能，从而改变了链路的特性。因此，我们可以得出结论：链路对称性这一在无线网状网络文献中常被采用的假设，在我们的场景中并不现实，服务部署算法必须加以考虑。

D. 讨论

以下是我们在QMP网络的测量中得出的一些观察结果（特征）：

动态拓扑 ： 由于多种原因，QMP网络具有高度的动态性和多样性，例如其在城市区域中的社区性质；其去中心化的有机增长特性，导致硬件、无线介质、链路协议、信道、路由协议等方面的技术选择极为多样；以及其网络中的网状结构等。当前的网络部署

该模型基于地理奇异性而非服务质量。该网络不是无标度网络。其拓扑结构是有机的，与传统的ISP网络不同。

非均匀分布资源 ： 网络中的资源并非均匀分布。对于服务而言，无线链路具有非对称质量（25%的链路偏差超过40%）。我们观察到高度偏斜的流量模式和高度偏斜的带宽分布（图6）。

QMP 和 Guifi.net 当前普遍采用的有机（随机）放置方案，不足以捕获网络的动态性，因此无法提供令人满意的服务质量（QoS）。随机服务放置所依赖的强假设，即资源均匀分布，在此类环境中并不成立。

此外，所部署的服务具有不同的服务质量（QoS）要求。对于需要密集组件间通信的服务（例如流媒体服务），如果其副本（服务组件）被部署在高容量链路上且彼此靠近，则性能更佳[3]。另一方面，带宽密集型服务（例如分布式存储、视频点播）若将其副本尽可能靠近最终用户部署，则可显著提升性能（例如，服务提供所需的总体带宽减少）[7]。

我们的目标是基于这一洞察，设计一种感知网络的服务放置算法，通过优化社区网络中带宽等稀缺资源的使用，来提升服务质量与网络性能。

III. 上下文与问题

首先，我们描述了网络和服务图的模型。随后，我们在此基础上阐述服务放置问题。所使用的符号列于表I中。

A. 网络图

通过社区网络微云（CNMCs）实现服务在社区网络 （CN）中的部署与共享。CNMC的理念是将云放置在靠近社区终端用户的边缘，使用户能够快速、可靠地访问服务。为了充分发挥其潜力，需要仔细部署CNMC，以充分利用可用的带宽资源。

在社区网络微服务架构（CNMC）中，服务器或低功耗设备（例如家庭网关）直接连接到无线基站(室外路由器) 向位于合理距离内或直接连接到基站的用户提供云服务。

我们将社区网络（CN）称为底层网络，以区别于由服务构建的覆盖层网络。底层网络应是连通的，我们假设每个节点都知道其他节点是否可达（即下一跳已知）。我们可以将底层图建模为：G ←(N,E)，其中N是连接到社区网络中室外路由器（ORs）的节点集合，E是连接这些节点的无线链路集合。节点之间的物理链路由给定的带宽（Bi）表征。此外，每条链路具有带宽容量（Be）。网络中的每个节点都有一个可用性评分（Rn），该评分源自 QMP网络中的实际测量。

B. 服务图

本文所针对的服务位于基础设施即服务（IaaS）层面，即当前专用数据中心中的云服务。因此，这些服务直接部署在网络的核心资源上，并由客户端访问。服务可由 QMP用户或管理员部署。

本文所考虑的服务是分布式服务（即微服务架构5中的独立可部署服务）。这些分布式服务可以是由较简单部分构建而成的复合服务（非单体），例如视频流（由源和对等组件构成）、Web服务（由数据库、memcached和客户端组件构成）等。在实际部署中，一个服务组件对应一个Docker容器。这些服务的部件或组件形成一个覆盖层，并相互交互以提供更复杂的复合服务。两个服务s1和s2之间的带宽需求由 βs1,s2给出。每个服务s最多可部署k个副本。

服务可能与网络中的特定节点相关联，也可能不相关联。每个节点可以托管一种或多种类型的服务。在本研究中，我们假设采用一种离线服务放置方法，即将单个或一组应用程序一次性放置到底层物理网络上。由于服务性能波动（例如天气条件、节点可用性、使用模式变化等），我们可能会随着时间的推移重新安排（迁移）同一服务的放置位置。我们不考虑实时服务迁移。

C. 服务放置问题

服务和网络图的概念使我们能够更精确地表述问题： “给定一个服务和网络图，如何在网络中放置服务以最大化用户QoS和QoE，同时满足每个节点（N）所需的可用性水平，并考虑最多k个服务副本？” 设Bij为从节点i到节点j的路径的外部带宽。我们希望对网状网络中的节点集合进行划分为k个簇（即服务）：C ← C1,C2,C3,…,Ck。簇Ci的集群头i即为该服务将被部署的节点位置。使集群头到簇内其他节点的带宽最大化的划分由以下目标函数给出：

$$
\text{argmax} C \sum {i=1}^{k} \sum_{j \in C_i} B_{ij}
$$

关于以下约束条件：
1) 每条链路使用的总带宽不得超过该链路的链路容量：
$$
\forall e \in E: \sum_{s1,s2 \in S} X_{s1,s2}(e) \times \beta_{s1,s2} \leq B_e
$$
2) 可用性感知：节点可用性应高于预定义阈值 λ：
$$
\forall n \in N: \sum_{n \in N} R_n \geq \lambda
$$
3) 准入控制：每个服务最多可放置k个副本：
$$
|D| = k
$$

D. 提出的算法：BASP

以穷举法求解公式1中任意数量的N和k的问题是NP难且成本极高的。朴素穷举法可通过计算第二类斯特林数[8]来估算，该数值表示将一个包含n个元素的集合划分为k个非空子集的方法数，即 $ \frac{1}{k!}\sum_{j=0}^{k}(-1)^{j-k}\binom{k}{j}j^n \Rightarrow O(n^k k^n) $。因此，由于明显的组合爆炸问题，我们提出了一种低成本且快速的启发式算法，称为BASP。BASP （带宽

符号	描述
N	网络中物理节点的集合
E	网络中边（物理链路）的集合
S	服务集合
D	服务副本集合
k	最大服务副本数量
Be	链路e的带宽容量
βs1,s2	服务s1和s2之间的带宽需求
Rn,λ	节点n的可用性，λ可用性阈值
Xs1,s2	至少有一个服务使用物理链路e 在s1和s2之间放置虚拟链路，若已放置则为1

算法1 BASP

需要：G(节点集合,边集合) 网络图
C′ ← C1,C2,C3, …,Ck k簇的划分
Bi 节点i的带宽
Rn,λ节点n的可用性， λ可用性阈值

1: 过程 执行K均值(G,k)
2: 如果 Rn ≥λ 那么
3: return C
4: 结束如果
5: 结束过程
6: 过程 FINDCLUSTERHEADS(C)
7: 簇头 ←列表()
8: 对于所有 k ∈C 执行
9: 对于所有 i ∈Ck 执行
10: Bi ← 0
11: 对于所有 j ∈setdiff(C,i)执行
12: Bi ←Bi+估计路由带宽(G,i, j)
13: 结束循环
14: 簇头 ← maxBi
15: 结束循环
16: 结束循环
17: return簇头
18: 结束过程
19: 过程 RECOMPUTECLUSTERS(簇头,G)
20: C′←列表()
21: 对于所有 i ∈簇头 执行
22: clusteri ←列表()
23: 对于所有 j ∈setdiff(G,i)执行
24: Bj ←估计路由带宽(G, j, i)
25: 如果 Bj是来自其他节点的最佳选择 i那么
26: clusteri ←j
27: 结束如果
28: C′ ←clusteri
29: 结束循环
30: 结束循环
31: return C′
32: 结束过程

并考虑网络带宽和节点可用性的感知可用性服务放置）在分配服务时，会考虑网络的带宽和节点可用性。

我们的BASP算法（见算法1）分三个阶段运行：
1) 第一阶段：K‐均值 ：最初，我们使用朴素K‐均值划分算法，根据节点的地理位置对其进行分组。其目的是将彼此靠近的节点划分为同一簇。K‐均值算法基于节点之间的欧几里得距离形成簇，而在本例中，距离度量为节点的地理坐标。在传统的K‐均值算法中，首先从n个节点中随机选择k个作为簇头（质心）。其余每个节点根据欧几里得距离选择离自己最近的簇头所属的簇。在网络中所有节点都被分配到k个簇之一后，重新计算每个簇的质心。每个簇包含一个服务的完整副本，即此阶段的算法将网络拓扑划分为k个簇（服务副本的最大允许数量）。基于地理位置的节点分组符合QMP的组织方式。QMP中的节点被组织成一个区域的树形层次结构zones。一个区域可以表示来自邻域或城市的所有节点。每个区域可进一步划分为覆盖更小地理区域的子区域，其中节点彼此靠近。从服务视角来看，我们考虑特定区域内的部署位置。我们使用带有地理坐标的 K‐均值作为算法的初始启发式方法。作为替代方案，可以采用基于网络局部性的聚类方法。在我们的环境中可使用多种图社区检测技术。[9]

2) 第二阶段：聚合带宽最大化 ：该算法的第二阶段基于寻找簇头的概念，以最大化第一阶段形成的簇Ck中簇头与其成员节点之间的带宽。两个节点之间的带宽被估计为最短路径中具有最小带宽的链路的带宽。所计算出的簇头即为服务放置的候选节点。这在图9中表示为朴素K‐均值。

3) 第三阶段：簇重新计算 ：该算法的第三步也是最后一步，包括将节点重新分配给在第一阶段形成的簇中具有最大带宽的已选集群头，因为第一阶段形成的簇中节点的地理位置并不总是与其带宽相关。通过这种方式，簇的形成基于节点的带宽。这在图9中表示为BASP 。

复杂度 ：BASP的复杂度如下：对于BASP，如果K‐均值（即第一阶段）聚类问题中的k和d（维度）是固定的（例如，在我们的情况下n= 71，且d= 2），则该问题可以在时间O(ndk+1 logn)内精确求解，其中n是要聚类的实体数量。第二阶段计算簇头的复杂度为O(n2)，第三阶段重新分配簇的复杂度为 O(n)。因此，BASP的整体复杂度为准对数级O(n2k+1 logn)，远小于暴力搜索方法，因而适用于通用处理器。

第四部分 评估

A. 实验设置

我们从QMP网络的71个物理节点中获取了一个网络快照（捕获），涉及链路6的带宽和节点可用性。所获得的节点和带宽数据已被用于构建QMP的拓扑图。QMP拓扑图仅考虑标记为“运行中”状态且具有指向其他节点的一个或多个链路的运行中节点。此外，我们舍弃了一些孤立簇。链路包括双向和单向链路，因此我们使用有向图。该拓扑图的节点集合

QMP 包含 Intel Atom N2600 CPU、4GB 内存和 120 GB 磁盘空间。我们的实验包含5次运行，所呈现的结果是所有运行的平均值。每次运行包含15次重复。

B. 比较

为了强调算法1中不同阶段的重要性，我们在本节将我们的启发式方法的两个阶段与随机部署（即QMP中的默认部署）进行比较。

随机部署 ：目前，QMP 上的服务部署（类似于网络部署）并非集中规划，而是由 CN 成员各自发起。面向公众、用户和社区的服务分别随机放置在超级节点和用户场所上。服务放置时唯一考虑的参数是设备必须处于“生产状态”。网络本身完全没有被考虑。所有处于生产状态的节点对用户而言都是等同的。

朴素K‐均值放置 ：这对应于算法1的第二阶段。服务被放置在由K‐均值形成的初始簇中具有最大带宽的节点上。我们将簇头的选择限制在使用K‐均值获得的簇集合内部。

BASP放置 ： 它包括算法1的三个阶段。在重新计算簇后，服务被放置在具有最大带宽的节点上。

C. 结果

图9展示了使用随机、朴素K-均值和BASP算法获得的到簇头的平均带宽。该图显示，对于任意数量的服务k，BASP均优于朴素K-均值和随机放置。当k= 2时，到簇头的平均带宽从18.3 Mbps（朴素K-均值）提升至27.7 Mbps（BASP），实现了50%的改进。当k= 7时，最大提升达到67%。当网络中最多有7个服务时，BASP相对于朴素K-均值的平均增益为45%。根据图9的观察结果，随着k的增加，两种算法之间的差距也随之增大。我们观察到，随着网络规模的扩大，k将增加。因此，BASP在较大规模网络中的表现预计会优于其他策略。

关于BASP与Random放置的比较，我们发现Random放置会导致网络资源的低效使用，从而造成性能次优。如图9所示，BASP相较于简单的Random放置平均提升了211%。

与最优解的对比 。请注意，我们的启发式方法能够选择出比任何其他随机或朴素方法提供更高带宽的簇头。但是，如果我们试图在簇内寻找最优带宽（即簇的最优平均带宽），则该问题是NP难的。原因在于，找到最优解需要我们在一个大小为n的集合中对所有大小为k的组合运行我们的算法。这是一个组合问题，即使对于较小的规模也会变得难以处理

大小为k或n（例如，k= 5，n= 71）的情况。例如，如果我们希望找到一个大小为k= 3的集群的最优带宽，则该算法需要对从71个元素中选出的所有可能的（非重复的）大小为3的组合运行，即choose(71,3)=57K种组合。我们成功完成了这一计算，并发现最优平均值为62.7 Mbps。对于k= 2，最优值为49.1 Mbps。对于k= 1，最优值为16.9 Mbps。

缺点是，在普通机器上计算最优解耗时非常长。具体而言，当k= 3时耗时5小时，当k= 2时耗时30分钟。相比之下，BASP在k= 3时仅耗时23秒，在k= 2时仅耗时15秒。表二显示了BASP相对于Random和Naive K-Means的改进。综上所述，BASP能够在极低的计算复杂度下实现良好的带宽性能。

与中心性指标的相关性 。表二展示了每个簇头获得的一些中心性度量和图属性。此外，图10显示了QMP网络的邻域连通性图。节点v的邻域连通性定义为v所有邻居的平均连接性。在图中，邻域连通性值较低的节点用亮色表示，而值较高的节点用暗色表示。值得注意的是，一些具有最高邻域连通性的节点正是BASP选择作为簇头的节点。图中用矩形标出了簇头（对于k= 2和k= 3）。对服务放置与网络拓扑属性之间关系的深入研究超出了本文的范围，将留作我们未来的工作。

第五部分 实验评估

A. CLOUDY：微云的服务枢纽

为了促进社区微云环境的采用和过渡，我们提供了一个社区云发行版，代号为CLOUDY7。该发行版包含社区云系统的平台和服务。CLOUDY是我们的微云核心软件，因为它将云系统的不同工具和服务统一到一个基于 Debian的Linux发行版中。CLOUDY是开源的，可以从公共仓库8下载。

Cloudy的主要组件可被视为一个分层堆栈，其中服务既存在于内核内部，也存在于用户级别。图11报告了在 Docker容器上运行的一些可用服务。Cloudy包含一个基于Serf的工具，供用户在微云中发布和发现服务，Serf是一种用于集群成员管理和编排的去中心化解决方案。在网络协调层，BASP在充分了解底层网络拓扑的基础上，决定服务的放置，然后通过Serf进行宣告，如图11所示。因此，其他用户可以发现该服务。

B. 评估在真实生产社区网络

为了了解我们的网络感知服务放置算法在真实生产社区网络中的收益，我们将该算法部署在连接到位于巴塞罗那市的QMP网络节点的真实硬件上。我们重点对两种最受欢迎的网络密集型应用程序进行基准测试：实时视频流服务和由最流行网站提供的Web 2.0服务。

1) 实时视频流服务：

PeerStreamer9,一种开源的实时P2P视频流服务，已在CLOUDY中被范式化地确立为实时流媒体服务。该服务基于块扩散，对等节点将其拥有的数据块选择性地提供给其邻域中的某些对等节点。一个数据块包含待传输视频的一部分（默认情况下为视频的一帧）。PeerStreamer区分源节点和对等节点。源节点负责将视频流转换为数据块，并发送给网络中的对等节点。在本例中，源节点和对等节点均运行在QMP节点之上的 Docker容器中。

实验设置 ：我们使用20个真实节点，这些节点连接到QMP的无线节点。这些节点位于用户家中（作为家庭网关、机顶盒等）或分布在巴塞罗那市的其他基础设施中。它们运行 Cloudy操作系统。作为控制器节点，我们利用 Community‐Lab10的实验基础设施。Community‐Lab提供一个中央协调实体，能够实时掌握网络拓扑信息。允许研究人员在生产环境的社区网络中部署实验性服务并进行实验。运行实时视频流服务的QMP节点属于 Community‐Lab。在我们的实验中，我们将一个实时流媒体摄像头（最大比特率为512 kbps，每秒30帧）连接到本地的PeerStreamer实例，该实例作为源节点。

因此，源在这种动态网络中的位置至关重要。将源放置在连接性较弱的QMP节点上会负面影响观看者的服务质量（QoS）和体验质量（QoE）。为了确定BASP在选择合适QMP节点以托管源时的准确性，我们测量对等端的平均块丢失百分比，该指标定义为丢失且未及时到达的数据块所占的百分比。这一简单指标将帮助我们理解网络在社区网络（CN）上实时视频流可靠运行中所起的作用。

我们的实验由20次运行组成，每次运行包含10次重复。结果基于所有成功运行的平均值计算得出，其中90%的运行是成功的。在10%的失败运行中，源无法从摄像头流式传输捕获的图像，因此对等方未能接收到数据。该实验持续运行了2周，总共约100小时的实时视频数据以及数兆字节的日志内容。所展示的结果来自PeerStreamer源一小时的连续实时流媒体。

结果 ： 图12显示了随着源数量增加的平均块丢失情况k。数据表明，对于任意数量的源节点k，BASP在QMP网络中的表现均优于当前采用的随机部署。当k= 1时，BASP将平均块丢失从12%降低到10%。该情况对应于单一源节点向QMP网络中的20个对等节点进行流媒体传输的场景。根据图12的观察结果，随着k的增加，两种算法之间的差距逐渐扩大。例如，当k= 3时，块丢失方面获得了3个百分点的改进，丢包率显著降低了37%。

2) Web 2.0服务：

我们实验的第二种服务是Web 2.0服务。Web2.0网站的工作负载与上一代网站的工作负载不同。上一代网站通常提供静态内容，而Web2.0网站提供动态内容。这些内容由其他用户的行为以及来自外部源（例如其他网站的新闻源）动态生成。我们正在实验一种社交网络服务，它是微服务架构的一个示例，因为它由一组可独立部署的服务组件构成（即Web服务器、数据库服务器、memcached服务器和客户端）。在这种类型的服务中，Web服务器（连同数据库服务器）的放置对用户 QoS起着决定性作用。

实验设置 ：在评估中，我们使用了CloudSuite网页服务基准 [10]的容器化版本。Cloudsuite基准测试包含四个层级： Web服务器、数据库服务器、memcached服务器和客户端。每个层级都有其独立的Docker镜像。Web服务器运行Elgg 11，并连接到memcached服务器和数据库服务器。Elgg社交网络引擎是一个用PHP开发的Web2.0应用，功能类似于 Facebook。客户端（通过Faban工作负载生成器实现）向社交网络发送登录请求并执行不同的操作。我们总共使用10 个可用的QMP节点，其中3个作为客户端。其余7个节点是部署Web服务器的候选节点。Web服务器、数据库服务器和 memcached服务器始终共置于同一主机上。在客户端一侧，我们测量执行某些操作（如登录、实时动态更新、消息发送等）时的响应时间。在Cloudsuite中，每种操作都分配有独立的服务质量延迟限制。如果少于95%的操作满足服务质量延迟限制，则认为该基准测试失败（在表III中标记为F）。

结果 ： 图13和图14分别描述了在使用随机和BASP放置Web服务器时，三个客户端执行更新实时动态操作所观察到的响应时间。使用随机方法放置Web服务器时，图13显示，随着每个客户端增加线程数（即并发操作），三个客户端的响应时间急剧上升。当每个客户端的操作数达到120次（即20 个线程）时，所有客户端感受到的响应时间相似（ 300‐350毫秒）。当执行160次操作（即80个线程）时，客户端2和客户端3的响应时间增加超过一个数量级，而客户端1的响应时间增加一个数量级。

图14显示，与图13中所示的随机方法相比，在使用我们的BASP启发式方法时，更高工作负载下的客户端响应时间降低了近一个数量级。当每个客户端执行最多120个操作时，三个客户端感知到的响应时间略优（200‐280毫秒），优于采用随机方法部署Web服务器时的响应时间。

此外，表III展示了在Cloudsuite基准测试中更新和登录操作的成功与失败测试情况。该表表明，使用BASP启发式方法时，满足服务质量延迟限制的成功测试次数高于使用随机方法的情况。同时，它还显示了采用BASP启发式方法相对于随机方法的标准偏差值以及平均客户端响应时间改进。我们可以注意到，随着工作负载强度增加，BASP启发式方法带来的增益更为显著。

操作	10	20	40	80	10	20	40	80
线程	更新实时动态	更新实时动态	更新实时动态	更新实时动态	执行登录	执行登录	执行登录	执行登录
QMP‐随机	T	F	F	F	T	T	F	F
QMP‐BASP	T	T	T	F	T	T	T	F
标准差	0.02秒	0.03秒	0.01	0.01	0.02	0.02	0.01秒	0.03秒
改进	0.1s	0.2s	1.8s	6.7s	0.1s	0.1s	1.2s	4.2s

表III CLOUDSUITE基准测试结果

六. 相关工作

服务放置是云管理系统的一项关键功能。通常，通过监控系统中的所有物理和虚拟资源，服务放置旨在通过任务的分配、迁移和复制来实现负载均衡。

数据中心 : Choreo [11]是一种基于测量的方法，用于在云基础设施中放置应用程序，以最小化应用完成时间等目标函数。Choreo 使用数据包序列及其他方法对云网络进行快速测量，利用机器学习算法分析应用程序的网络需求，并采用贪心启发式方法进行应用程序放置。Volley [12]是一个系统，可在微软地理分布的数据中心之间执行自动数据放置。Volley 使用基于数据访问模式和客户端位置的迭代优化算法分析请求日志，并向云服务返回迁移建议。大量关于数据中心内服务放置的研究工作致力于寻找启发式解决方案 [13]。

数据中心环境中的大多数工作不适用于我们的情况，因为我们的节点和链路具有有限容量，且无线链路存在非对称质量，导致系统具有较强的异构性。网络中链路容量的差异/不对称性使得服务放置问题与大多同质化的云数据中心中的情况大为不同。我们的测量结果表明，25%的链路对称性偏差高于40%。

分布式云 ： 当服务部署算法决定计算实体之间的通信在底层网络中的路由方式时，我们称之为网络感知的服务放置，即与虚拟网络嵌入（VNE）密切相关。文献[14]提出了在分布式云环境中高效部署服务的算法。这些算法需要输入网络状态、计算资源和数据资源的信息，并将其与应用需求相匹配。文献[15]的作者提出了一种选择算法，用于为面向服务的应用程序分配资源，而文献[16]则专注于在分布式的小型数据中心中的资源分配。另一个网络感知方法的例子是Moens在文献[17]中的工作，该工作采用面向服务的架构（SOA），其中应用程序由一组服务构成。他们的方法同时执行节点与链路映射。文献[18]将 Moens的工作扩展到无线场景中，并考虑了物联网（IoT）。Mycocloud [19]是另一项工作，它通过在去中心化云中实现自组织服务放置来提供弹性。Elmroth的工作 [20]在移动云计算网络（MCN）中放置应用程序时考虑了快速用户移动性和资源成本。Tantawi最近的研究[21]使用有偏统计抽样方法进行云工作负载放置。关于通过迁移实现的服务放置，文献[22]和[23]研究了在网络边缘托管基于云服务的移动边缘云中的动态服务迁移问题。他们利用马尔可夫决策过程（MDP）框架将服务迁移建模为一个序贯决策问题，并通过使用旧金山出租车的真实世界移动轨迹进行仿真，展示了其方法的有效性。

在分布式云中的大多数研究考虑的是微数据中心，而我们的情况是，CN微型云由受限/低功耗设备（如家庭网关）组成。此外，在我们的情况下，关于计算设备的信息是部分的，因此他们的方法并不完全适用于我们的环境。

无线环境 ：在[24]中，作者提出了一种针对环境智能环境的最优分配方案，通过任务复制来避免网络性能下降。在无线场景下开展的其他一些研究包括Davide [25]的工作以及我们最近的研究[7]，后者提出了若干部署算法，旨在最小化协调和覆盖成本沿社区网络的开销。本文工作的重点是为CN微型云设计一种低复杂度服务部署启发式方法，以最大化带宽并改善用户QoS和QoE。

第七节. 结论

在本文中，我们阐述了在社区网络（CN）微云基础设施中进行带宽和可用性感知的服务放置的必要性。社区网络为以贡献方式部署和使用社区服务提供了理想的场景。以往在社区网络中的研究主要集中在设计更优的网络结构以避免热点和瓶颈，但并未涉及服务实例的网络感知部署方案。

然而，随着服务变得越来越网络密集型，即使在资源充足的云环境中，它们也可能受到网络瓶颈的限制。对于 CN微型云而言，由于节点和链路的有限容量以及不可预测的网络性能，网络感知变得更加关键。如果没有支持网络感知的服务放置系统，可能会选择网络路径较差的位置，而更快、更可靠的路径位置则未被使用，最终导致用户体验不佳。

我们提出了一种称为BASP的低复杂度服务放置启发式方法，以在部署CN微型云时最大化带宽分配。我们给出了该算法的详细设计，分析了其复杂度，并在真实场景下对其性能进行了仔细评估。实验结果表明，BASP在 Guifi.net当前采用的随机部署方案基础上，性能持续提升了211%。此外，随着服务数量的增加，性能增益也相应提高。进一步地，我们将该服务放置算法部署于QMP网络的一个真实网络段中，QMP是一个实际运行的社区网络 （CN），并对算法的性能和效果进行了量化。本研究以通过Cloudy分发集成的实时视频流服务和Web 2.0服务为例进行分析。真实实验结果显示，在使用BASP算法时，对等端的视频块丢失减少了最多3个百分点，即丢包率降低了37%。在Web 2.0服务中使用BASP时，客户端响应时间最多减少了一个数量级，这是一个显著的改进。

作为未来的工作，我们计划研究服务迁移，即控制器需要在用户移动性和网络中其他动态变化存在的情况下，决定哪个微云应为特定用户执行计算。