Online Network Slicing for Real Time Applications in Large-scale Satellite Networks
Binquan Guo, Hongyan Li, Zhou Zhang, Yan Ye · 2023
In this work, we investigate resource allocation strategy for real time communication (RTC) over satellite networks with virtual network functions. Enhanced by inter-satellite links (ISLs), in-orbit computing and network virtualization technologies, large-scale satellite networks promise global coverage at low-latency and high-bandwidth for RTC applications with diversified functions. However, realizing RTC with specific function requirements using intermittent ISLs, requires efficient routing methods with fast response times. We identify that such a routing problem over time-varying graph can be formulated as an integer linear programming problem. The branch and bound method incurs$\mathcal{O}(\vert \mathcal{L}^{\tau}\vert \cdot(3\vert \mathcal{V}^{\tau}\vert+\vert \mathcal{L}^{\tau}\vert )^{\vert \mathcal{L}^{\tau}\vert })$time complexity, where$\vert \mathcal{V}^{\tau}\vert$is the number of nodes, and$\vert \mathcal{L}^{\tau}\vert$is the number of links during time interval$\tau$. By adopting a k-shortest path-based algorithm, the theoretical worst case complexity becomes$O(\vert \mathcal{V}^{\tau}\vert !\vert \mathcal{V}^{\tau}\vert ^{3})$. Although it runs fast in most cases, its solution can be sub-optimal and may not be found, resulting in compromised acceptance ratio in practice. To overcome this, we further design a graph-based algorithm by exploiting the special structure of the solution space, which can obtain the optimal solution in polynomial time with a computational complexity of$\mathrm{O}(3\vert \mathcal{L}^{\tau}\vert +(2\log\vert \mathcal{V}^{\tau}\vert +1)\vert \mathcal{V}^{T}\vert )$. Simulations conducted on starlink constellation with thousands of satellites corroborate the effectiveness of the proposed algorithm.