Cooperative Service Caching and Workload Scheduling in Mobile Edge Computing

@inproceedings{maCooperativeServiceCaching2020,
  title = {Cooperative {{Service Caching}} and {{Workload Scheduling}} in {{Mobile Edge Computing}}},
  booktitle = {{{IEEE INFOCOM}} 2020 - {{IEEE Conference}} on {{Computer Communications}}},
  author = {Ma, Xiao and Zhou, Ao and Zhang, Shan and Wang, Shangguang},
  year = {2020},
  month = jul,
  pages = {2076--2085},
  publisher = {{IEEE}},
  address = {{Toronto, ON, Canada}},
  doi = {10.1109/INFOCOM41043.2020.9155455},
  isbn = {978-1-72816-412-0},
  language = {en}
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 要解决的问题：边缘服务器之间没有互相合作导致的边缘服务器的资源利用率不足

边缘服务器资源配置的不同造成的利用率不足
- 例如，一个算力不足的边缘服务器和一个存储容量不足的边缘服务器在遇到计算任务或缓存任务时，只能把任务交给云计算中心，而不是互相交换任务
边缘服务器资源配置的不合理造成的资源浪费
- 例如，给一个算力很强的边缘服务器配了一个很小的内存会使得边缘服务器只能一次执行少量计算任务，而不能一次下载多个任务执行

# 研究对象和问题

在一个LAN内网环境下存在多个边缘服务器，每个边缘服务器的算力和存储容量不尽相同
在LAN外有云计算中心
计算能力不足或没有缓存所请求服务的边缘服务器可以将自己的请求处理任务卸载到旁边的未满载边缘服务器或云端
任务的卸载和执行一样需要消耗时间，在处理时需要平衡
两个子问题：服务缓存和任务卸载及它们之间的相互作用
- 任务只有在缓存了对应服务的机器上才能运行
- 因此服务缓存策略决定了任务可以卸载的位置
- 进而任务卸载的结果也可以看出一个服务缓存策略效果如何

# 研究方法

两个子问题建模为一个mixed integer nonlinear programming problem，设计一个two-layer Iterative Caching updatE (ICE) algorithm处理服务缓存和任务卸载的相互作用
用排队模型评估任务卸载和执行的耗时，进而评估系统内任务的平均响应时间，进而可以通过最小化平均响应时间的方法求出任务卸载耗时和任务执行耗时的平衡点
针对边缘服务器算力和存储容量各不相同的问题，利用工作量调度子问题的凸性，并基于注水思想提出了一种具有多项式计算复杂度的启发式工作量调度算法

# 创新点

研究了在边缘端互相合作的情况下的服务缓存和任务调度问题，将问题建模为一个最小化服务响应时间的mixed integer nonlinear programming问题，并且证明了它的非多项式复杂度
证明了任务卸载子问题的凸性，使用排队模型分析了系统各处的延迟
设计了一个two-layer Iterative Caching updatE (ICE) algorithm解决了最小化服务响应时间和外网流量的问题

# 相关研究

多边缘服务器共同优化服务缓存和工作负载调度：在服务缓存成本预算限制范围内最大化边缘处理的请求数量

缺点：

实际情况下很难确定服务缓存成本预算
没有考虑在边缘计算中最为重要的指标——服务响应时间

# 任务卸载

在单跳和多跳边缘服务器间的任务卸载
云-边之间的在线任务调度
分级结构中的任务卸载

缺点：

假定边缘服务器缓存了所有服务，不符合实际

# 服务缓存

基于受欢迎程度的分布式缓存算法
以用户为中心的边缘缓存机制，每个用户都由多个边缘共同提供服务
基于位置的缓存策略，通过预测内容的受欢迎程度最大化缓存命中率
基于预测的缓存放置策略
基于历史的动态边缘缓存

缺点：

计算和服务缓存不应该·割裂来看

# 任务卸载和服务缓存的联合优化

针对数据密集型应用（例如视频）的优化不能直接应用于数据和计算密集型应用（例如AR/VR）中
一些研究只能应用于多基站覆盖用户的情况
一些研究没有考虑边缘端协作
还有一些研究没有把服务响应时间作为性能评价指标因而不能展现边缘计算给用户带来的好处

# 建模

# 边缘缓存和任务规划策略

# 边缘缓存策略

$\bm{C}=(c_{ns}\in\{0,1\}:n\in\mathbb{N},s\in\mathbb{S})$

$\bm{C}$ ：一个矩阵表示边缘缓存策略
$c_{ns}$ ：是否在边缘服务器 $n$ 上缓存服务 $s$
$n$ ：表示一个边缘服务器
$\mathbb{N}$ ：在一个LAN下的所有边缘服务器组成的集合
$s$ ：表示一个服务
$\mathbb{S}$ ：所有要部署的服务的集合

# 边缘服务器存储容量限制

$\sum_{s\in\mathbb{S}}c_{ns}p_s\leq P_n$

$p_s$ ：服务 $s$ 的大小
$P_n$ ：边缘服务器 $n$ 的存储容量

# 任务规划策略

$\bm\Lambda=(\lambda_{ns}\in[0,1]:n\in\mathbb{N}\cup\{\omicron\},s\in\mathbb{S})$

$\bm\Lambda$ ：一个矩阵表示任务规划策略
$\lambda_{ns}$ ：边缘服务器 $n$ 上分担的服务 $s$ 的计算量比率
$\lambda_{\omicron s}$ ：云服务器上分担的服务 $s$ 的计算量比率

# 任务规划限制

# 每个任务都要完成

$\sum_{n\in\mathbb{N}\cup\{\omicron\}}\lambda_{ns}=1$

# 边缘服务器实际计算量不会比分配给它和它周围边缘服务器的计算量还大

$\lambda_{ns}A_s\leq\sum_{i\in\Theta_n\cup\{n\}}A_{is}$

$A_s$ $A_{s}$ ：假定请求的到达过程为泊松过程， $A_s$ $A_{s}$ 是服务 $s$ $s$ 的请求的到达强度
- 单位时间内服务 $s$ 的请求到达次数的期望
$\Theta_n$ ：边缘服务器 $n$ 相连的周围的服务器集合
$A_{ns}$ ：单位时间内到达边缘服务器 $n$ 的服务 $s$ 的请求数量的期望

注：帮助理解到达的请求量 $A_{ns}$ 和实际的请求量 $\lambda_{ns}A_s$

以下以“请求量”指代单位时间内请求到达次数的期望

$\lambda_{ns}A_s$ 表示边缘服务器 $n$ 上实际所处理的服务 $s$ 的请求量
如果 $\lambda_{ns}A_s\leq A_{ns}$ $λ_{n s} A_{s} \leq A_{n s}$ ：
- 说明分配给边缘服务器 $n$ 的服务 $s$ 的请求量 $A_{ns}$ 比它实际运行的服务 $s$ 的请求量 $\lambda_{ns}A_s$ 还大
- 说明有部分服务 $s$ 的请求量被卸载到其他边缘服务器了
- 这时 $A_{ns}-\lambda_{ns}A_s$ 就表示边缘服务器 $n$ 卸载到其他边缘服务器的请求量
反之，如果 $\lambda_{ns}A_s\geq A_{ns}$ $λ_{n s} A_{s} \geq A_{n s}$ ：
- 说明分配给边缘服务器 $n$ 的服务 $s$ 的请求量 $A_{ns}$ 还没有它实际运行的服务 $s$ 的请求量 $\lambda_{ns}A_s$ 大
- 说明有其他边缘服务器的服务 $s$ 的请求量被卸载到了边缘服务器 $n$
- 这时 $\lambda_{ns}A_s-A_{ns}$ 就表示从其他边缘服务器卸载过来的服务 $s$ 的请求量

# 服务延迟

# 边缘服务器上的延迟

$\frac{1}{\mu_{ns}}=\frac{\beta_s}{r_{ns}}$

$\beta_s$ $β_{s}$ ：假定服务 $s$ $s$ 的计算任务在任意CPU时间片内发出“计算请求”的次数服从指数分布，期望值为 $\beta_s$ $β_{s}$
- 即处理服务 $s$ 所需的平均计算量
$r_{ns}$ $r_{n s}$ ：边缘服务器 $n$ $n$ 任意CPU时间片内可以处理的服务 $s$ $s$ 的“计算请求”数量
- 单位时间内可以为处理服务 $s$ 的请求提供的计算量
- 即分配给服务 $s$ 的计算资源量
由于服务请求在任意CPU时间片内的到达次数服从指数分布，而边缘服务器 $n$ 分配给服务 $s$ 的计算资源量固定为 $r_{ns}$ ，因此边缘服务器 $n$ 处理服务 $s$ 的请求所要花费时间也服从指数分布，均值即 $\frac{\beta_s}{r_{ns}}$
$\mu_{ns}$ $μ_{n s}$ ：边缘服务器 $n$ $n$ 单位时间内能处理的服务 $s$ $s$ 的请求数量
- 由于每个服务请求的处理时间服从指数分布，均值为 $\frac{\beta_s}{r_{ns}}$ ，那么单位时间内能处理的服务请求量则为 $\frac{r_{ns}}{\beta_s}$
- （为什么？边缘服务器处理服务请求所花的时间为指数分布，单位时间内能处理的服务请求量是它的倒数，那指数分布的随机变量的倒数的分布是什么分布？）

$D_{ns}=\frac{1}{\mu_{ns}-\lambda_{ns}A_s}$

$D_{ns}$ ：在边缘服务器 $n$ 上的服务 $s$ 的请求处理的延迟
$\mu_{ns}$ ：边缘服务器 $n$ 单位时间内能处理的服务 $s$ 的请求数量
$\lambda_{ns}A_s$ ：单位时间内边缘服务器 $n$ 上处理的服务 $s$ 的请求数量的期望
为什么相减取倒数，似乎需要用到排队论的知识，暂时不懂

# 延迟限制：保持队列的稳定性

$\lambda_{ns}A_s<\mu_{ns}$

似乎需要用到排队论的知识，暂时不懂

# 云服务器上的延迟

假定任务在云服务器上运行时只有传输延迟没有计算延迟

$d_{cloud}=\frac{1}{\frac{B_s}{t_s\beta_s}-\lambda_{\omicron s}A_s}$

$d_{cloud}$ $d_{c l o u d}$ ：在云服务器上运行任务时的传输延迟
- 似乎需要用到排队论的知识，暂时不懂
$t_s$ ：服务 $s$ 每卸载单位的“计算请求”到云服务器所产生的“传输请求”量
$B_s$ ：给服务 $s$ 卸载计算量所分配的带宽
$\frac{B_s}{t_s\beta_s}$ ：单位时间内能完成多少卸载到云端的请求
$\lambda_{\omicron s}A_s$ ：单位时间内卸载到云端的服务 $s$ 请求量的期望值
为什么相减取倒数，似乎需要用到排队论的知识，暂时不懂

# 延迟限制：保持队列的稳定性

$\lambda_{\omicron s}A_s<\frac{B_s}{t_s\beta_s}$

似乎需要用到排队论的知识，暂时不懂

# 优化目标

# 服务响应时间（总传输延迟）

$D_s=\sum_{n\in\mathbb N}\left[\lambda_{ns}D_{ns}+\frac{max(\lambda_{ns}A_s-A_{ns},0)}{A_s}d_n\right]+\lambda_{\omicron s}d_{cloud}$

此式是服务 $s$ 的请求在各个边缘服务器上的响应时间的加权平均值， $\lambda_{ns}$ 和 $\lambda_{os}$ 就是边缘服务器的权重：

$D_s=\frac{\sum_{n\in\mathbb N}\left[\lambda_{ns}A_sD_{ns}+max(\lambda_{ns}A_s-A_{ns},0)d_n\right]+\lambda_{\omicron s}A_sd_{cloud}}{A_s}$

$\lambda_{ns}A_sD_{ns}$ ：在边缘服务器 $n$ 上处理的服务 $s$ 请求所产生的计算延迟
$max(\lambda_{ns}A_s-A_{ns},0)d_n$ ：在边缘服务器 $n$ 上处理的其他边缘服务器卸载而来的请求所产生的传输延迟
$\lambda_{\omicron s}A_sd_{cloud}$ ：卸载到云端处理的服务 $s$ 请求产生的传输延迟

# 外网流量

外网流量就是卸载到云服务器的请求数量 $\lambda_{\omicron s}A_s$

# 汇总

最小化服务响应时间和外网流量，并设置一个表征优化目标重要性的权值 $w_s$ ：

$\begin{aligned} \mathop{min}\limits_{\bm C,\bm\Lambda}&\sum_{s\in\mathbb S}(D_s+w_s\lambda_{\omicron s}A_s)\\ s.t.&\sum_{n\in\mathbb{N}\cup\{\omicron\}}\lambda_{ns}=1\\ subject\ to:&\\ &\sum_{s\in\mathbb{S}}c_{ns}p_s\leq P_n\\ &\lambda_{ns}A_s\leq\sum_{i\in\Theta_n\cup\{n\}}A_{is}\\ &\lambda_{ns}A_s<\mu_{ns}\\ &\lambda_{\omicron s}A_s<\frac{B_s}{t_s\beta_s}\\ &\lambda_{ns}\geq 0\\ &c_{ns}\in\{0,1\}\\ \end{aligned}$

# 求解

# 两种简化方法

假定边缘之间没有合作： $\lambda_{\omicron_ns}=1-\lambda_{ns}$
假定服务只有一种

# two-layer Iterative Caching updatE algorithm (ICE)外层：Gibbs sampling不断逼近服务缓存最优方案

Gibbs sampling不断循环，第 $i$ 轮循环中：

随机选一个边缘服务器 $n$ $n$
- 取它上一轮的服务缓存方案 $\bm c_n^{i-1}$
- 取上一轮的任务调度优化结果 $y^{i-1}$
为边缘服务器 $n$ 随机选一个可行的服务缓存方案 $\bm c_n^*$
计算采用了服务缓存方案 $\bm c_n^*$ 后的任务调度优化结果 $y^*$ （在ICE内层）
根据 $y^*$ 和 $y^{i-1}$ 决定是否采用新的服务缓存方案 $\bm c_n^*$ ：

$\left\{ \begin{aligned} P(\bm c_n^i=\bm c_n^*)&=\rho=\frac{1}{1+e^{(y^*-y^{i-1})/w}}\\ P(\bm c_n^i=\bm c_n^{i-1})&=1-\rho \end{aligned} \right.$

# two-layer Iterative Caching updatE algorithm (ICE)内层：凸优化求解服务延迟最小的任务调度方案

可以证明前文所述的最小化服务响应时间和外网流量的优化问题是一个凸优化问题。

其解法需要用到凸优化的知识，暂时不懂，略。

# 思考

本文所提出的问题非常符合实际且合情合理：
- 不考虑任务卸载的缓存研究最终只能应用于内容分发领域
- 不考虑缓存的任务卸载研究最终会造成边缘设备的高成本（一个边缘就要缓存所以服务）
- 因此，缓存+任务卸载联合优化才是边缘计算中缓存和任务卸载研究的唯一出路
本文所使用的优化方式也很好理解
- 首先确定了给定任意缓存方案时的任务卸载优化方案
- 随机选择一个缓存方案计算最优任务卸载方案
- 每一轮随机改变一个节点的缓存方案，计算最优的任务卸载方案，如果比当前方案更优就采纳，否则不采纳
- 不断循环就能逼近最优方案

貌似可行的深入研究：

边缘之间连接不稳定的情况？
边缘服务器之间不能一跳连接的情况？
本文似乎假定任务少的时候和任务多的时候的任务处理速度符合同样的分布，但是实际情况下，如果任务少了，单位时间内一个任务被分配的CPU时间会增加，任务处理速度因此会加快
- 相关疑惑点：本文是假定边缘服务器一个个运行队伍里的任务还是说所有到达的任务都一起加入CPU轮转处理？
$\beta_s$ 的定义似乎说明本文假定了同一服务的不同请求可能有不同的计算量且这些计算量是连续分布的，实际情况下不同请求的计算量可能集中分布于多个值处（例如分布式神经网络同一步的计算量大致相同，不同步的计算量差别很大）

感觉不太行的深入研究：

边缘怎么知道什么时候要把任务交给其他节点运行？当边缘的资源满了的时候
到达率 $A_s$ $A_{s}$ 不能提前确定的情况？ $A_s$ $A_{s}$ 如何确定？ $A_s$ $A_{s}$ 不断变化的情况？
- 这个two-layer Iterative Caching updatE algorithm (ICE)外层Gibbs sampling调整服务缓存方案的做法是否足够灵活？
- 不同时间段的请求不同服务的 $A_s$ 不断变化的情况怎么搞？比如上班时间街边的编译服务器请求
服务可以被部分缓存的情况（ $c_{ns}\in[0,1]$ ，比如边缘智能缓存部分神经网络层）？一个任务需要多个服务处理的情况？

Yin的笔记本

Choose mode