2025-11-23T14:10:16.662935

Optimize Replica Server Placement in a Satellite Network

He, Xu, Luo et al.

Satellite communication offers Internet connectivity to remote locations, such as villages, deserts, mountains, and at sea. However, transmitting content over satellite networks is significantly more expensive than traditional Internet. To address this issue, we propose placing content replica servers within satellite networks and optimizing replica placement for important performance metrics, such as latency, transmission, and storage cost. Our approach can support different types of satellite networks, including Low Earth Orbit (LEO), Medium Earth Orbit (MEO), Geostationary Orbit (GEO), and their combinations. An important challenge for supporting content replicas in such networks is that LEO and MEO satellites are constantly moving. We address this challenge by explicitly considering their moving trajectories and strategically optimizing not only client performance, but also the cost of transferring content from one satellite to another as needed. We demonstrate the effectiveness of our approach using both simulated traffic traces and a prototype system.

academic

Optimize Replica Server Placement in a Satellite Network

基本信息

论文ID: 2510.13689
标题: Optimize Replica Server Placement in a Satellite Network
作者: Zhiyuan He¹, Yi Xu², Cheng Luo¹, Lili Qiu¹, Yuqing Yang¹ (¹Microsoft Research, ²USTC)
分类: cs.NI (计算机网络)
发表时间: 2025年10月15日 (arXiv提交)
论文链接: https://arxiv.org/abs/2510.13689

摘要

卫星通信为偏远地区（如村庄、沙漠、山区和海上）提供互联网连接。然而，通过卫星网络传输内容比传统互联网成本显著更高。为解决这一问题，本文提出在卫星网络内放置内容副本服务器，并针对延迟、传输和存储成本等重要性能指标优化副本放置。该方法支持不同类型的卫星网络，包括低地球轨道(LEO)、中地球轨道(MEO)、地球同步轨道(GEO)及其组合。在此类网络中支持内容副本的重要挑战是LEO和MEO卫星不断移动。本文通过明确考虑其运动轨迹并战略性地优化客户端性能和卫星间内容传输成本来解决这一挑战。

研究背景与动机

问题定义

核心问题: 卫星网络中内容传输成本高昂，延迟显著，影响用户体验
具体挑战:
- 卫星网络延迟是地面网络的7.1倍
- 网页下载时间是地面网络的2.7倍
- LEO/MEO卫星持续移动，网络拓扑动态变化

研究重要性

商业价值: Starlink已有2600+颗LEO卫星，Amazon计划发射3000+颗
技术可行性: 现代服务器仅占Starlink卫星重量的6%，功耗仅占太阳能收集的15%
应用需求: 卫星网络需要支持实时应用和改善用户体验

现有方法局限性

传统CDN: 设计用于静态网络，无法处理动态卫星拓扑
现有卫星CDN方法:
- StarFront: 不允许副本变更，导致高存储成本
- PCH: 周期性副本切换造成不必要的复制流量

核心贡献

首个综合卫星CDN优化框架: 支持LEO、MEO、GEO及其组合的统一优化方法
动态副本放置算法: 提出MTLS和MTOLS算法，显式考虑卫星轨道和移动轨迹
多目标成本优化: 同时优化查询成本、复制成本和存储成本
实际系统验证: 通过仿真和原型系统验证方法有效性，成本降低16.91%-53.26%

方法详解

任务定义

输入:

时间相关图 $G_t = <V, E_t>$ ，包括用户节点 $V_{user}$ 、副本候选节点 $V_{replica}$ 、源服务器节点 $V_{origin}$
内容集合 $C$ ，用户需求 $demand_{v,c,t}$

输出: 每个时间槽 $t$ 的副本集合 $S_{c,t}$

目标: 最小化总成本 = 查询成本 + 复制成本 + 存储成本

成本函数设计

查询成本: $\sum_c \sum_t \sum_{v_{user} \in V_{user}} demand_{v_{user},c,t} \times \min_{v \in S_{c,t}} cost_t^{query}(v_{user}, v)$
复制成本: $\sum_c \sum_t \sum_{v_{new} \in S_{c,t}} \min_{v_{old} \in S_{c,t-1}} cost_t^{replication}(v_{new}, v_{old})$
存储成本: $\sum_c \sum_t \sum_{v \in S_{c,t}} size_c \times cost^{storage}(v)$

核心算法

MTLS (Multi-time Local Search)

基于动态规划的局部搜索算法
时间复杂度: $O(MTk^2N^2)$ ，其中 $M$ 为最大迭代次数， $k$ 为邻居数
支持添加、删除、替换操作生成邻近解

MTOLS (Multi-time Orbit-based Local Search)

利用卫星轨道信息的分层优化算法
时间复杂度: $O(MT(P^2 + Q^2))$ ，其中 $P$ 为轨道数， $Q$ 为每轨道卫星数
相比MTLS有数百倍加速，适用于大规模卫星星座

算法核心思想:

轨道选择: 首先选择最优轨道序列
卫星选择: 在选定轨道内选择最优卫星
DP优化: 使用动态规划避免穷举搜索

实验设置

数据集

卫星星座:
- LEO: Starlink Phase I (1584颗卫星，72轨道，550km高度)
- MEO: O3b (20颗卫星，8062km高度)
- GEO: ViaSat (4颗地球同步卫星)
流量数据:
- MAWI: 日本监控链路的数据包轨迹
- Wikipedia: 美国西海岸多媒体内容请求
- CAIDA: 美国监控链路的数据包轨迹
网络测量: 使用德克萨斯州Starlink地面站的真实延迟测量