Online Network Slicing for Real Time Applications in Large-scale Satellite Networks
Binquan Guo, Hongyan Li, Zhou Zhang, Yan Ye
Abstract
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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}(\vert \mathcal{L}^{\tau}\vert \cdot(3\vert \mathcal{V}^{\tau}\vert+\vert \mathcal{L}^{\tau}\vert )^{\vert \mathcal{L}^{\tau}\vert })$</tex> time complexity, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\vert \mathcal{V}^{\tau}\vert$</tex> is the number of nodes, and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\vert \mathcal{L}^{\tau}\vert$</tex> is the number of links during time interval <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tau$</tex> . By adopting a k-shortest path-based algorithm, the theoretical worst case complexity becomes <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\vert \mathcal{V}^{\tau}\vert !\vert \mathcal{V}^{\tau}\vert ^{3})$</tex> . 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{O}(3\vert \mathcal{L}^{\tau}\vert +(2\log\vert \mathcal{V}^{\tau}\vert +1)\vert \mathcal{V}^{T}\vert )$</tex> . Simulations conducted on starlink constellation with thousands of satellites corroborate the effectiveness of the proposed algorithm.