JUDICIOUS REPLICA PLACEMENT AND REQUEST ASSIGNMENT ON LEO SATELLITES AND CLOUDS¶

We propose a series of heuristic algorithms to solve the content distribution problem efficiently. The key idea behind our algorithms is to judiciously make proper cache server assignments that satisfy the application-level latency requirement, while incurring minimal bandwidth and storage cost.

A. Offline Replica Placement and Request Assignment¶

OffPA 通过离线优化方式，逐步构建一个高效的内容分发网络，适用于已知用户请求到达时间的场景。它为在线算法（如 OnPA）提供了理论基础。

B. Online Replica Placement and Request Assignment¶

这段内容的核心是介绍在线副本放置与请求分配算法（OnPA）的逻辑和计算方法，重点在于如何高效地将用户请求分配到缓存服务器，同时满足延迟要求并最小化成本。

逻辑流程

用户请求到达：
- 用户请求从地理分布的区域陆续到达
- 算法会根据延迟要求筛选出可用的缓存服务器集合\(Candidate_{req_q}\)
若有可用缓存服务器：
- 如果\(Candidate_{req_q} \neq \emptyset\)，即存在至少一个满足延迟要求的已开启缓存服务器：
  - 从中选择分配成本最低的服务器
  - 成本计算公式为：\(CT^{opened}_{assign}(req_q, j) = cost_{traffic}(req_q, j) \cdot sz(req_q)\) (其中，\(cost_{traffic}\)是带宽成本，\(sz(req_q)\)是请求大小)
若无可用缓存服务器：
- 如果没有满足延迟要求的缓存服务器，算法需要开启一个新的缓存服务器，并将内容复制到该服务器：
- 成本包括三部分：
  1. 从最近的现有缓存复制内容到新服务器的带宽成本
  2. 在新服务器上存储内容的成本
  3. 从新服务器向用户提供内容的带宽成本成本计算公式为：\(CT^{new}_{assign}(req_q, j) = cost_{traffic}(req_q, j) \cdot sz(req_q) + cost_{cache}(j, sz(req_q)) + \min(cost_{traffic}(i, j) \cdot sz(req_q))\) (其中，\(i\)表示现有缓存服务器集合)
更新系统状态：
- 请求分配完成后，算法会更新系统状态（变量\(x\)和\(\lambda\)）

核心目标

在满足用户延迟需求的前提下，通过优化选择已有或新建缓存服务器，最小化分配成本

C. Exploiting Replica Pre-Allocation to Optimize Online Replica Placement and Region Assignment¶

这部分内容的核心是通过预分配副本（Replica Pre-Allocation）和在线分配（Online Assignment）来优化内容分发网络（CDN）的副本放置和区域分配，从而减少用户请求的访问延迟。以下是逻辑的简要梳理：

主要目标

降低用户请求的访问延迟：通过预分配和在线分配机制，尽量减少由于缓存未命中导致的高延迟
优化副本放置与区域分配：基于历史请求数据和实时需求动态调整资源

算法3（PAOA）的两阶段流程

阶段1：预分配阶段（Pre-Allocation Stage）

输入：历史请求数据、连接图、延迟阈值
目标：为每个区域选择满足延迟要求的缓存服务器，并预先分配副本
步骤：
1. 遍历每个区域 \(r\)，根据延迟要求筛选可用的缓存服务器集合
2. 对于每个时间槽 \(t\)，从候选服务器中选择一个最小化分配成本的服务器进行副本预分配
3. 将区域 \(r\) 与选定的服务器建立初步绑定关系

阶段2：在线分配阶段（Online Assignment Stage）

输入：实时用户请求
目标：根据实时需求，将用户请求指派到合适的缓存服务器
步骤：
1. 检查用户请求是否可以被预分配的缓存服务器处理。如果可以，直接指派
2. 如果没有预分配的缓存满足条件，则在候选服务器中选择一个满足延迟要求且分配成本最低的服务器
3. 若所有候选服务器都不满足延迟要求，则选择延迟最小的服务器处理请求

核心优化点

利用历史数据进行预分配：提前为可能出现高需求的区域准备副本，减少实时计算压力
动态调整以应对实际情况：在实际运行中根据实时需求灵活调整资源分配，确保服务质量
成本与延迟平衡：综合考虑延迟和分配成本，选择最优方案

关键公式

分配成本 \(CT_{assign}\)：

如果缓存已开启：\(CT_{assign} = CT^{opened}_{assign}\)
如果缓存未开启：\(CT_{assign} = CT^{new}_{assign}\)

特殊情况处理

当所有候选服务器都无法满足延迟要求时（例如由于链路条件差或卫星信号中断），算法会选择延迟最小的服务器来保证服务可用性。

总结来说，PAOA算法通过结合历史信息和实时决策，在优化用户体验和控制资源成本之间取得了平衡。