【CEDC】Online Collaborative Data Caching in Edge Computing

#edge-resources #optimization

要解决的问题：collaborative edge data caching (CEDC) problem
在满足边缘计算环境中的约束条件（如服务器容量、性能约束）的前提下，最小化包括数据缓存成本、数据迁移成本和服务质量（QoS）惩罚在内的系统成本

本文的主要贡献：

从应用供应商的角度对 CEDC 问题进行了建模和公式化，并证明了它是NP-complete 问题
我们基于 Lyapunov 优化提出了一个在线算法 CEDC-O，来解决 CEDC 问题，并证明了它具有可证明的近似最优性能。
在一个真实世界的数据集上评估了我们算法的性能

论文结构：将问题代数化 → 提出算法 → 评估算法（理论+实验）

就是单纯的 Lyapunov 优化

边缘计算和传统分布式的区别：

边缘服务器的计算和存储资源是有限的（server capacity constraint）
边缘服务器只能覆盖一定的区域（server coverage constraint）
用户和边缘服务器都可以向附近的其他边缘服务器求援（server adjacency constraint）

System Model

System Architecture

Data Retrieval Latency

System Cost = Data Caching Cost + Data Migration Cost + QoS(quality-of-service) Penalty

Pasted image 20230929124748.png

Data Migration Cost

如果一个用户在覆盖他的边缘中没有找到所需要的数据，可以让边缘服务器在周围的边缘服务器上寻找。Data Migration Cost 会比较从云端拉取数据和从周围的边缘服务器拉取数据所耗费的时间，选择省时间的那个。

公式解释：

(c_{m s} \cdot l_{i, d}^{t} - c_{m c}) y_{i, d}^{t} + c_{m c} = min {c_{m s} \cdot l_{i, d}^{t}, c_{m c}}

，其中

c_{m s} \cdot l_{i, d}^{t}

表示从周围的边缘服务器拉取数据需要的时间，

c_{m c}

表示从云端拉取数据需要的时间

$X_{i, d}^{t}$ 表示在 t 时刻开始时，数据 d 是否没有被缓存在边缘服务器 $v_{i}$ 上

$λ_{i, d}^{t}$ 表示在 t 时刻结束时，数据 d 是否没有被缓存在边缘服务器 $v_{i}$ 上

$l_{i, d}^{t}$ is the lowest latency for edge server $v_{i}$ to obtain data d in time slot t

因此， $λ_{i, d}^{t} X_{i, d}^{t}$ 这一项为 1 表示在 t 这整个时刻内，边缘服务器 i 中没有缓存数据 d 。

因为：

y_{i, d}^{t} = {\begin{matrix} 0 i f c_{m s} \cdot l_{i, d}^{t} > c_{m c} \\ 1 i f c_{m s} \cdot l_{i, d}^{t} \leq c_{m c} \end{matrix}

所以当 $c_{m s} \cdot l_{i, d}^{t} > c_{m c}$ 时，也就是从边缘服务器获取数据 d 不如直接从云端获取数据 d 时， $y_{i, d}^{t} = 0$ ，Data Migration Cost 对应的项为 $c_{m c}$ ，也就是直接从云端获取数据所需要的时间。

当 $c_{m s} \cdot l_{i, d}^{t} \leq c_{m c}$ 时，从边缘服务器获取数据 d 更省时，Data Migration Cost 对应的项为 $c_{m s} \cdot l_{i, d}^{t}$ .

QoS Penalty

大部分情况下等价于从云端获取数据的开销。
$c_{p}$ 为常数， $θ_{m, d}^{t}$ 表示移动设备 m 在 t 时刻是否能及时得到数据 d：

θ_{m, d}^{t} = {\begin{matrix} 1 i f l_{m, d}^{t} > l_{T} \\ 0 i f l_{m, d}^{t} \leq l_{T} \end{matrix}

While pursing this optimization objective, it is also necessary to stabilize the time-averaged system latency perceived by the users in the long term.

在最小化 system loss 的同时，也需要保持按时间平均的系统延时的稳定，也就是需要满足：

lim_{T \to \infty} \frac{1}{T} \sum_{t = 0}^{T - 1} \frac{\sum_{m \in M} \sum_{d \in D} θ_{m, d}^{t} \cdot l_{m, d}^{t}}{\sum_{m \in M} \sum_{d \in D} θ_{m, d}^{t}} \leq L (⋆)

在边缘计算环境中，数据请求具有非常高的随机性。所以，系统的长期表现比短期表现更重要。因此，CEDC 问题可描述为下面的约束优化问题：

\begin{array}{cop} \mathcal P_1:\min \lim\limits_{x \to \infty}  \sum\limits_{t=0}^{T-1} \mathcal C(\lambda {#t} ) \\ s.t.:\lim _{T \rightarrow \infty} \frac{1}{T} \sum_{t=0}^{T-1} \frac{\sum_{m \in M} \sum_{d \in D} \theta_{m, d}^{t} \cdot l_{m, d}^{t}}{\sum_{m \in M} \sum_{d \in D} \theta_{m, d}^{t}} \leq \mathcal{L} \end{array}

Online Algorithm CEDC-O

Pasted image 20231026212316.png

$σ (t)$ 表示累积的延时，那么CEDC问题的约束 $(⋆)$ 就可以转化为：

lim_{T \to \infty} \frac{1}{T} \sum_{t = 0}^{T - 1} E [σ (t)] \leq 0 (⋆ ⋆)

Pasted image 20231026213743.png

得到了 Lyapunov drift 的上限后，定义 drift-plus-penalty 函数 $DP (t)$ ：

DP (t) = Δ (σ (t)) + γ \cdot E [C (λ^{t}) | σ (t)]

其中 $γ$ 为超参数。

显然有：

DP (t) \leq Q + σ (t) E [L_{a v g} (λ^{t}) - L | σ (t) |] + γ \cdot E [C (λ^{t}) | σ (t)]

在每一轮中都需要在保持系统稳定的情况下最小化 cost 函数 $C (λ^{t})$
所以约束优化问题 $P_{1}$ 可以转化为：（ $Q$ 是常数）

P_{2} : min {Q + σ (t) (L_{a v g} (λ^{t}) - L) + γ \cdot C (λ^{t})}

Pasted image 20231026220134.png

CEDC-O 算法只需要当前时刻的 data requests 来优化 $C (λ^{t})$
观察式子 (20)，CEDC-O 利用 Lyapunov 优化在目标函数 $C (λ^{t})$ 的基础上额外增加了 $σ (t) (L_{a v g} (λ^{t}) - L)$ ，当 $L_{a v g}$ 超过 $L$ 时，一个惩罚项就被加到新的目标函数中，促使函数稳定系统，降低 $L_{a v g}$ . 并且 $σ (t)$ 越大，稳定系统的重要度就越大。

Perfomance Analysis

理论证明

定理3：CEDC-O 算法按时间平均的 system cost 是 $O (\frac{1}{γ})$ 级别的——证明没看懂
- 假设最优化问题 $P_{1}$ 的解是 $λ_{o p t} = {λ_{o p t}^{0} \dots λ_{o p t}^{T - 1}}$ ，并且对应的 system cost 是 $C_{o p t} = \frac{1}{T} \sum_{t = 0}^{T - 1} E [C (λ_{o p t}^{t}) | σ (t)]$
- $L (σ (t)) = \frac{1}{2} σ^{2} (t)$ 是 Lyapunov 函数， $L_{a v g} (λ^{t})$ 是 system latency 的平均
- 在这道题中，由于 $σ (t + 1) = max {σ (t) + L_{a v g} (λ^{t}) - L, 0}$ ，所以 $L_{a v g} (λ^{t}) - L$ 等价于原始 Lyapunov 优化中的虚拟队列 $Q_{k} (t)$
- 已经有其他研究证明： $\exists λ^{' t}, E [L_{a v g} (λ^{' t}) - L | σ (t)] \leq θ, θ \to 0^{+} (21)$
- （ $λ^{' t}$ 就是不考虑系统稳定性的情况？） $E [C (λ^{' t}) | σ (t)] \leq E [C (λ_{o p t}^{t}) | σ (t)] (22)$
- 累加 $Δ (σ (t))$ ，得：
定理4：CEDC-O 算法按时间平均的累积延时（accumulated latency）是 $O (γ)$ 级别的

所以， $γ$ 越大，CEDC-O 算法得到的解越优，但是对应的累积延时也越高。

Simulation

Settings

环境设置：（Dataset）

没什么特别的

比较对象：（Algorithm）

Delay-Oriented
Online-Optimal：直接求解约束规划问题 $P_{1}$ ，但是由于原约束涉及到无穷的情形，所以将约束条件替换为：
IPEDC：在最小化 cost 的前提下覆盖临近的用户。但是在我们得情形中有些用户可能不会被覆盖，所以我们修改了原始了 IPEDC 算法，转而在不违反延时限制（即式 32）的前提下覆盖尽可能多的用户。
Maximum Revenue：最大化 $R e v e n u e$ （ $= b e n e f i t s - c o s t s$ ）

参数设置（Parameter）

Pasted image 20231028171002.png

从 set #1 开始，每次改变一个参数（固定其它 6 个）

参数含义

$n$ ：边缘服务器数量

$| D |$ ：要缓存的数据量

$M S$ ：每个边缘服务器上最大的缓存空间

$ω = \frac{c_{p}}{c_{s}}$ ：衡量了应用提供商认为 QoS 重要的程度

$l_{T}$ 延时限制，规定了 local edge server 能否从附近的边缘服务器获取信息。当 $l_{T} = 0$ 时，用户只能从他们的 local edge server 获取信息。

$L$ ：long-term latency（对 $L_{a v g}$ 的限制）

$γ$ ：Lyapunov 优化中的 trade-off parameter，权衡 system cost 和 accumulated latency

评价指标

Pasted image 20231028172033.png

Performance Comparison

对于 System Cost：
单个 time slot 的 cost：CEDC-O 比 OO 高 8.60%，并不是很显著，因为 OO 也求了 CEDC 问题的最优解。
但是在 2/3 的time slots 中，CEDC-O 比 OO 更优，说明 CEDC-O 相比 OO 而言有总体的优势（overall advantage）。

其它几幅图感觉没什么特殊的？

Impact of Edge Server Number & Data Number & ……

感觉很详细地介绍了每一个参数地变化会导致算法地结果会产生什么变化

基本上覆盖了所有情况（共 $参数 \times 评价指标$ 种）

Threats to Validity【效度】

这一部分论证了算法 CEDC-O 的 有效性验证 是否可靠。

Construct Validity

主要威胁结构有效性的是用于比较的四种方法。由于 CEDC 问题在 EC 环境中的新颖性，用于比较的四种方法（DO、OO、IPEDC、MR）可能不足以全面评估 CEDC-O 算法。

为了尽量减少这种威胁，我们：

通过将 (32) 包含到它们的实现中来增强了 IPEDC 和 MR
更改了七个参数，以模拟各种 CEDC 场景 —— 演示参数更改如何影响CEDC-O的性能

External Validity【普适性】

主要的外部有效性威胁是 CEDC-O 是否可以被推广应用于 EC 环境中的其他 CEDC 场景。

为了解决这个威胁，这篇论文：

用通用的方式测量了 CEDC-O 的性能。具体来说，通过数据单元的数量来表示数据大小和缓存空间，并通过跳数来表示数据检索延迟。这样，评估结果可以用任意的具体模型来解释。
采用了被广泛使用的真实世界的数据集
改变了 7 个变量来模拟不同大小、不同复杂度的 CEDC 问题

通过以上方法保证了评估的代表性和综合性（the representativeness and comprehensiveness of the evaluation）。

Motivation：在这篇论文之前的工作中，如果一个用户在覆盖他的 edge server 中没有找到所需要的 data，就只能从 cloud 中找 data.

CEDC-O 采用李雅普诺夫优化

最近有论文用李雅普诺夫优化确定边缘数据完整性

在周五的报告中，可以不详细介绍李亚普优化的具体实现和理论证明，但是最好介绍一下李亚普优化有哪些应用。

一般用于：在稳定 A 的前提下（相对“稳定”，可以有一定牺牲，控制在一定范围），优化 B