Joint Dataflow and In-Network Computing Resource Optimization for Dynamic LEO Satellite Systems

Abstract

Low Earth Orbit (LEO) satellite constellations are emerging as an important platform for distributed dataflow execution in space-terrestrial integrated networks. Existing studies largely treat routing and processing separately, while next-generation LEO systems are expected to process and transform data in transit by leveraging on-board computing and software-defined infrastructures. However, jointly optimizing routing and in-network processing in dynamic LEO satellite networks remains challenging because of time-varying connectivity, limited on-board resources, and bandwidth constraints. In this paper, we formulate the Dynamic LEO In-network Processing Dataflow Optimization (DLIDO) problem, which aims to maximize the throughput of processed dataflows by jointly optimizing routing paths and processing-resource allocation over a dynamic flow network. We present an approximation algorithm with a proven $(1-\epsilon)$ approximation guarantee for $0\lt \epsilon \leq 0.5$ , providing near-optimal throughput under dynamic processing and communication constraints. To further improve efficiency and practicality, we develop a 2-walk based iterative heuristic algorithm that substantially reduces runtime while maintaining strong empirical performance, and in some regimes provably optimal behavior. Extensive evaluations on realistic LEO network topologies show that both algorithms significantly outperform existing approaches in throughput and adaptability, highlighting a promising direction for dataflow-aware scheduling and optimization in dynamic satellite systems.