Optimize Replica Server Placement in a Satellite Network

Basic Information

• Paper ID: 2510.13689
• Title: Optimize Replica Server Placement in a Satellite Network
• Authors: Zhiyuan He¹, Yi Xu², Cheng Luo¹, Lili Qiu¹, Yuqing Yang¹ (¹Microsoft Research, ²USTC)
• Category: cs.NI (Computer Networks)
• Publication Date: October 15, 2025 (arXiv submission)
• Paper Link: https://arxiv.org/abs/2510.13689

Abstract

Satellite communications provide internet connectivity to remote areas such as villages, deserts, mountains, and oceans. However, content transmission through satellite networks is significantly more costly than traditional internet. To address this challenge, this paper proposes placing content replica servers within satellite networks and optimizes replica placement for important performance metrics including latency, transmission costs, and storage costs. The approach supports different types of satellite networks, including Low Earth Orbit (LEO), Medium Earth Orbit (MEO), Geostationary Orbit (GEO), and their combinations. A critical challenge in supporting content replicas in such networks is the continuous movement of LEO and MEO satellites. This paper addresses this challenge by explicitly considering orbital trajectories and strategically optimizing client performance and inter-satellite content transmission costs.

Research Background and Motivation

Problem Definition

1. Core Problem: High content transmission costs and significant latency in satellite networks impact user experience
2. Specific Challenges:
   • Satellite network latency is 7.1x higher than terrestrial networks
   • Web download time is 2.7x longer than terrestrial networks
   • LEO/MEO satellites continuously move, causing dynamic network topology changes

Research Significance

1. Commercial Value: Starlink already operates 2,600+ LEO satellites; Amazon plans to launch 3,000+
2. Technical Feasibility: Modern servers occupy only 6% of Starlink satellite weight and consume only 15% of solar power collection
3. Application Demand: Satellite networks need to support real-time applications and improve user experience

Limitations of Existing Approaches

1. Traditional CDN: Designed for static networks, cannot handle dynamic satellite topology
2. Existing Satellite CDN Methods:
   • StarFront: Does not allow replica changes, resulting in high storage costs
   • PCH: Periodic replica switching causes unnecessary replication traffic

Core Contributions

1. First Comprehensive Satellite CDN Optimization Framework: Unified optimization method supporting LEO, MEO, GEO, and their combinations
2. Dynamic Replica Placement Algorithm: Proposes MTLS and MTOLS algorithms that explicitly consider satellite orbits and movement trajectories
3. Multi-objective Cost Optimization: Simultaneously optimizes query cost, replication cost, and storage cost
4. Practical System Validation: Validates method effectiveness through simulation and prototype systems, achieving cost reduction of 16.91%-53.26%

Methodology Details

Task Definition

Input:

• Time-dependent graph $G_t = <V, E_t>$ including user nodes $V_{user}$, replica candidate nodes $V_{replica}$, origin server nodes $V_{origin}$
• Content set $C$, user demand $demand_{v,c,t}$

Output: Replica set $S_{c,t}$ for each time slot $t$

Objective: Minimize total cost = query cost + replication cost + storage cost

Cost Function Design

1. Query Cost: $\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)$
2. Replication Cost: $\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})$
3. Storage Cost: $\sum_c \sum_t \sum_{v \in S_{c,t}} size_c \times cost^{storage}(v)$

Core Algorithms

MTLS (Multi-time Local Search)

• Local search algorithm based on dynamic programming
• Time complexity: $O(MTk^2N^2)$, where $M$ is maximum iterations, $k$ is number of neighbors
• Supports add, delete, and replace operations to generate neighboring solutions

MTOLS (Multi-time Orbit-based Local Search)

• Hierarchical optimization algorithm leveraging satellite orbital information
• Time complexity: $O(MT(P^2 + Q^2))$, where $P$ is number of orbits, $Q$ is satellites per orbit
• Achieves hundreds of times speedup compared to MTLS, suitable for large-scale satellite constellations

Algorithm Core Ideas:

1. Orbit selection: First select optimal orbit sequence
2. Satellite selection: Select optimal satellites within selected orbits
3. DP optimization: Use dynamic programming to avoid exhaustive search

Experimental Setup

Datasets

1. Satellite Constellations:
   • LEO: Starlink Phase I (1,584 satellites, 72 orbits, 550km altitude)
   • MEO: O3b (20 satellites, 8,062km altitude)
   • GEO: ViaSat (4 geostationary satellites)
2. Traffic Data:
   • MAWI: Packet traces from monitoring links in Japan
   • Wikipedia: Multimedia content requests from US West Coast
   • CAIDA: Packet traces from US monitoring links
3. Network Measurements: Real latency measurements from Starlink ground station in Texas

Evaluation Metrics

• Hop Count: Each satellite-user, satellite-gateway, and inter-satellite link counts as 1 hop
• Ideal Latency: Calculated based on physical distance and transmission speed
• Real Latency: Random sampling from Starlink network measurements

Comparison Methods

1. UFL Algorithm: Naive greedy, 1.61x greedy, local search
2. Satellite-specific Algorithms: StarFront, PCH (Periodic Cache Handoff)

Implementation Details

• Replication cost ratio: $\alpha = 50$ (replication cost is 50x query cost)
• Storage cost ratio: Gateway $\beta = 1$, Satellite $\gamma = 10$
• Neighbor limit: $k = 4$

Experimental Results

Main Results

The proposed method achieves best performance across three datasets and three metrics:

Cost Decomposition Analysis:

• UFL algorithm: Low replication and storage costs, but high query cost
• Satellite-specific algorithms: PCH has excessive replication cost, StarFront has excessive storage cost
• Proposed method: Balanced optimization across all three cost types

Ablation Studies

1. Prediction vs. Real Demand: Using historical average prediction, performance gap narrows but still outperforms baseline methods
2. Computation Time: MTOLS is 200x faster than MTLS
   • MTLS: 98,576.3 seconds
   • MTOLS: 495.3 seconds
3. Different Satellite Type Combinations:
   • With same storage cost: GEO suitable for hop count optimization, LEO suitable for latency optimization
   • LEO covers small areas, MEO more effective for large area coverage

System Validation

Web Browsing Experiment:

• MTLS average download time: 96.5ms (optimal)
• Uses 37.5 replicas, DNS query accounts for 13.2%

Video Streaming Experiment:

• MTLS total cost: 2,281.0 (lowest)
• Average QoE: 9.15 (highest)

Related Work

CDN Optimization Research

• Traditional problem modeling: Facility location, K-median, K-center
• Existing algorithms: Greedy, heuristic methods suitable for static networks
• Satellite CDN: Limitations of StarFront and PCH

Satellite Network Research

• LEO network simulation: StarPerf, Starlink latency analysis
• Network enhancement: Multi-link, real-time traffic relay
• This paper is the first comprehensive CDN optimization considering multiple satellite types

Conclusions and Discussion

Main Conclusions

1. Significant Performance Improvement: Cost reduction of 16.91%-53.26% compared to strongest baseline methods
2. Algorithm Scalability: MTOLS algorithm suitable for large-scale satellite constellations
3. Multi-scenario Applicability: Supports different applications including web browsing and video streaming
4. Practical Deployment Feasibility: Prototype system validates practical utility of the method

Limitations

1. Prediction Dependency: Actual deployment requires accurate demand prediction
2. Simplified Assumptions: Does not consider content update costs
3. Storage Constraints: Does not explicitly model satellite storage capacity limits
4. Network Dynamics: Actual satellite networks may have more complex connection patterns

Future Directions

1. Advanced Prediction Models: Integrate machine learning-based demand prediction
2. Storage Capacity Constraints: Explicitly model satellite storage limits
3. Multi-content Coordination: Consider coordinated optimization across different content
4. Practical Deployment: Validate method in real satellite networks

In-depth Evaluation

Strengths

1. Problem Importance: Addresses practical needs of satellite network CDN with significant commercial value
2. Method Innovation:
   • First comprehensive CDN optimization framework considering satellite mobility
   • MTOLS algorithm cleverly leverages orbital structure for algorithm acceleration
   • Multi-objective optimization balances performance and cost
3. Experimental Comprehensiveness:
   • Comprehensive evaluation across multiple satellite types, datasets, and metrics
   • Real Starlink network measurement data enhances credibility
   • Prototype system validates practical feasibility
4. Technical Rigor: Clear mathematical modeling and complete algorithm complexity analysis

Weaknesses

1. Insufficient Theoretical Analysis: Lacks theoretical guarantees on approximation ratio or convergence
2. Parameter Sensitivity: Insufficient sensitivity analysis for key parameters (α, β, γ)
3. Simplified Practical Constraints:
   • Does not consider inter-satellite link capacity limits
   • Ignores satellite failures and maintenance impacts
4. Scalability Verification: While theoretical complexity is analyzed, lacks practical verification on ultra-large constellations

Impact

1. Academic Contribution: Provides new theoretical framework and practical algorithms for satellite CDN research
2. Industrial Value: Direct application value for commercial satellite networks like Starlink and OneWeb
3. Technology Promotion: Method extensible to other mobile network environments (e.g., UAV networks)

Applicable Scenarios

1. Large-scale LEO Constellations: Particularly suitable for Starlink-type large-scale LEO satellite networks
2. Hybrid Satellite Networks: Can optimize combined LEO/MEO/GEO deployment
3. Content Distribution Services: Applicable to various scenarios including video streaming and web content
4. Remote Area Services: Provides high-quality content services to areas with insufficient terrestrial network coverage

References

This paper cites 48 relevant references covering multiple domains including CDN optimization, satellite communications, and facility location, providing solid theoretical foundation for the research.

Overall Assessment: This is a high-quality network systems research paper that addresses the important and practical problem of satellite network CDN optimization. The method demonstrates strong innovation, comprehensive experimental validation, and significant value for both academia and industry. While there is room for improvement in theoretical analysis and certain practical constraints, the overall contribution is substantial and expected to have important impact on related fields.