Lightweight Maximum-Capacity Path Selection for Delay-Sensitive Applications in Large-Scale LEO Satellite Networks

In this study, we design a lightweight maximum-capacity path selection strategy for delay-sensitive services in satellite networks (SNs). Leveraging inter-satellite links (ISLs), large-scale SNs can offer low latency and high bandwidth for real-time communication (RTC). However, realizing data-intensive RTC over intermittent ISLs necessitates effective path selection algorithms that consider both dynamic link capacities and diverse latency requirements. Utilizing the enhanced time-discretization model, we represent SNs as time-varying graphs and formulate the delay-bounded maximum-capacity path selection as an integer linear programming problem. The branch-and-bound approach has a time complexity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(|\mathcal {L}^{\tau }| \cdot (3 |\mathcal {V}^{\tau }| + |\mathcal {L}^{\tau }| - 1)^{|\mathcal {L}^{\tau }|})$</tex-math></inline-formula>, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$|\mathcal {V}^{\tau }|$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$|\mathcal {L}^{\tau }|$</tex-math></inline-formula> represent the number of available nodes and links during time window <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\tau$</tex-math></inline-formula>. By adopting an alternative path flow-based formulation, it can be addressed using a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-shortest path-based method. However, it incurs a factorial worst-case time complexity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal{O}(|\mathcal {V}^{\tau }|! \cdot |\mathcal {V}^{\tau }|^{3})$</tex-math></inline-formula>, making it impractical for large-scale scenarios. To solve the problem in an efficient manner, we propose a graph-based method that combines bounds estimation, graph filtering operation and bisection method accelerated by two techniques, enabling optimal solutions with a complexity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(\log _{2}(f_{\textit {ub}}^{\tau }-f_{\textit {lb}}^{\tau }) \cdot (|\mathcal {L}_{\tau }| + |\mathcal {V}_{\tau }|\log _{2}(|\mathcal {V}_{\tau }|))$</tex-math></inline-formula>, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f_{\textit {ub}}^{\tau }$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f_{\textit {lb}}^{\tau }$</tex-math></inline-formula> denote the upper and lower bounds of link capacity, respectively. Simulations conducted on Starlink constellation validate the efficacy of our proposed method.