Learning Spatiotemporal Failure Dependencies for Resilient Edge Computing Services
阅读笔记

一、 文献信息

标题：Learning Spatiotemporal Failure Dependencies for Resilient Edge Computing Services
作者：Atakan Aral, Ivona Brandic
发表时间：JULY 2021
发表途径：IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS

二、 问题意义

由于移动计算和物联网技术的普及，边缘计算的需求不断增长，网络边缘产生和数据量成倍增加。目前边缘计算在服务上的两大问题是节点和链路故障导致的服务中断，以及网络延迟。因此，如何通过历史数据学习边缘服务器故障之间的时空依赖关系，并将它们与拓扑信息相结合来评估在边缘基础设施上冗余部署的服务系统的故障概率并合理部署备用的边缘服务系统以减小服务中断概率，是非常有价值的问题。

三、 思路方法

本文的贡献可以概括为以下两点：

• 一种基于机器学习的近实时服务中断预测方法
• 一种保证服务弹性的服务部署算法

模型的整体框架如图1所示。使用动态贝叶斯网络（DBN）表示服务器之间的时空依赖关系。根据历史故障数据学习得到网络拓扑，建立故障概率推断模型。然后根据故障概率模型进行，在合适的节点部署边缘服务系统以减小服务中断概率。

3.1 故障概率推断

3.1.1 问题定义

一个边缘计算服务是一系列边缘部署的集合。每一个边缘部署由一个边缘服务器和边缘服务器上维持的边缘服务系统副本组成。边缘服务器部署之间由链路相连。导致服务故障的情况分为两种——节点故障和链路故障。
节点故障是由节点上部署的边缘服务器系统副本无法正常工作导致的。一般所有由于节点之间存在方向性的传递消息，以及一些节点会共享供电系统等原因，边缘设备的故障存在并发性，即节点故障有时空依赖性。
链路故障是节点（边缘服务器）之间的通信中断。本文假设不同链路的故障相互独立。

3.1.2 节点故障概率

若假设节点的故障相互独立，则可以大大简化模型，但与实际严重不符；如果考虑每个结点之间的相互关系，一个节点的概率预测时间复杂度为，在网络中节点数量很多的情况下，复杂度无法接受且受噪声影响大。因此，使用既考虑拓扑结构，又考虑时间关系的动态贝叶斯网络对节点间的依赖关系进行建模。
首先，根据边缘服务的历史数据，使用模拟退火算法学习一个较优的贝叶斯网络拓扑。理想拓扑的具体搜索步骤如下：

1. 新拓扑生成：对拓扑进行局部改动。在随机选择一种改动方法，包括添加新依赖，依赖关系取反，删除已有依赖关系。
2. 环路检查：检查新产生的拓扑是否是无环图（DBN的拓扑是有向无环图），如果是无环图返回步骤1。
3. 拓扑评价：使用BDe度量给新拓扑打分。
4. 接受判决：如果新拓扑的分数更高则接受，否则根据Metropolis准则以一定概率接受。

下一步，根据学习得到的DBN拓扑和当前活跃节点的部署，得到一个只包含活跃节点（边缘服务器及其维持的边缘服务系统）和其父节点的子图以减小图的复杂度。如此每个结点推理的时间复杂度只有，其中|P|是父节点数目。
随后，根据历史数据，使用最大似然估计法计算每一个节点的条件概率表。每一个结点的状态只与其父节点的状态有关。如此即可使用DBN预测服务的故障概率。

3.1.3 链路故障概率

由于假设了链路是否发生故障是相互独立的，链路故障导致服务中断的概率为每一条链路故障的概率的乘积。

3.2 弹性服务部署方案

本文并未给出“弹性”的明确定义。于我理解，弹性表现在两方面，一是可以基于历史数据学习到时空依赖关系，达到近实时的依赖关系建模与预测；二是决策目标具有弹性：可以是最小通信时延，一定边缘部署数量下最小服务中断概率，和一定服务中断概率下最小的部署数量。基于三种不同目标，分别有三种部署算法。

1. 以最小时延为目标

该方案只部署活跃边缘服务系统副本，不部署备用副本，在无差错的情况下达到最小时延。部署过程是根据拓扑结构计算每一个边缘服务器到用户的最短距离并排序，在实验最小的若干服务器上部署边缘服务系统。

1. 以最小服务中断概率为目标

在已有活跃节点的基础上，部署新的边缘服务系统副本。遍历解空间，计算中断概率。遍历搜索和概率推断的总时间复杂度为。

1. 以最小部署数量为目标

在已有活跃节点的基础上，部署数量从1逐个增加并求解中断概率，直到中断概率满足要求或部署数量达到上限。时间复杂度最坏为。我认为采用二分法搜索，可以减小至。

四、 实验结论

4.1 实验方法

本文在三个不同部署策略的的分布式硬件系统的历史状态数据集上验证了方法的有效性。部署越靠近边缘设备，通信时延越短，但计算能力越弱，可靠性越低。在实验配置方面，使用软件banjo学习DBN拓扑，使用一半的历史数据作为训练集，另一半作为测试集。用于对比的baseline模型有RAND（随机部署服务）、PRIOR（基于先验预测服务器状态）、TTR（基于SVR的预测，考虑空间关系）、DAFR（仅基于节点故障概率预测）。用来评估方法性能的指标有网络宕机时间、网络时延、网络开销、违约数量、网络中断数量和成本。

4.2 实验结论

对于所有的方法，宕机时间、违约数量、网络中断数随着预测任务的时间长度增加而增加。这是因为随着预测的时间范围增加，使用的仍然是最初的DBN。实际应用时应该根据最新的历史数据重新训练，得到实时的DBN，从而对时空依赖关系更准确地建模。
对比各种性能度量，该算法在可用性、故障数量、网络延迟和成本方面优于最先进的算法，并且在成本和性能之间能找到一个帕累托最优区间，有非常好的实用价值。
总之，本文提出的基于时空依赖关系感知的算法可以大大减小边缘部署的并发故障，提高整体服务的可靠性，减少了需要的边缘副本的数量，降低了端到端网络的延迟和链路故障的概率，可以使低延迟、多故障的边缘服务器达到与云服务器相近的可靠性。

五、 启发思考

本文对我的思考主要有两点：一是使用动态贝叶斯网络，巧妙地对网络时空依赖关系进行建模，简单有效，并使用模拟退火算法进行优化，让我感受到了概率图模型的实用性。二是完整的研究流程，从问题提出，到问题定义、模型建立、在多个数据集上对比实验，使我对科学研究有了更深入的认识。