# Optimal Routing for Federated Learning over Dynamic Satellite Networks: Tractable or Not?

arXiv: https://arxiv.org/abs/2604.19399 · HTML: https://mlsanity.com/paper/2604.19399/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 21 Apr 2026.

## Builds on (most cited first, 9 of 9)

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies](https://mlsanity.com/paper/2010.01243/) (2020)
- [Federated Learning over Wireless Networks: Convergence Analysis and Resource Allocation](https://mlsanity.com/paper/1910.13067/) (2019)
- [Client Selection in Federated Learning: Principles, Challenges, and Opportunities](https://mlsanity.com/paper/2211.01549/) (2022)
- [FedSN: A Federated Learning Framework over Heterogeneous LEO Satellite Networks](https://mlsanity.com/paper/2311.01483/) (2023)
- [Federated Learning in Satellite Constellations](https://mlsanity.com/paper/2206.00307/) (2022)
- [Satellite Federated Edge Learning: Architecture Design and Convergence Analysis](https://mlsanity.com/paper/2404.01875/) (2024)
- [FedHC: A Hierarchical Clustered Federated Learning Framework for Satellite Networks](https://mlsanity.com/paper/2502.12783/) (2025)

## Abstract (arXiv)

Federated learning (FL) is a key paradigm for distributed model learning across decentralized data sources. Communication in each FL round typically consists of two phases: (i) distributing the global model from a server to clients, and (ii) collecting updated local models from clients to the server for aggregation. This paper focuses on a type of FL where communication between a client and the server is relay-based over dynamic networks, making routing optimization essential. A typical scenario is in-orbit FL, where satellites act as clients and communicate with a server (which can be a satellite, ground station, or aerial platform) via multi-hop inter-satellite links. This paper presents a comprehensive tractability analysis of routing optimization for in-orbit FL under different settings. For global model distribution, these include the number of models, the objective function, and routing schemes (unicast versus multicast, and splittable versus unsplittable flow). For local model collection, the settings consider the number of models, client selection, and flow splittability. For each case, we rigorously prove whether the global optimum is obtainable in polynomial time or the problem is NP-hard. Together, our analysis draws clear boundaries between tractable and intractable regimes for a broad spectrum of routing problems for in-orbit FL. For tractable cases, the derived efficient algorithms are directly applicable in practice. For intractable cases, we provide fundamental insights into their inherent complexity. These contributions fill a critical yet unexplored research gap, laying a foundation for principled routing design, evaluation, and deployment in satellite-based FL or similar distributed learning systems.