  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}(|\mathcal{L}^{\tau}| \cdot (3
|\mathcal{V}^{\tau}| + |\mathcal{L}^{\tau}|)^{|\mathcal{L}^{\tau}|})$ time
complexity, where $|\mathcal{V}^{\tau}|$ is the number of nodes, and
$|\mathcal{L}^{\tau}|$ is the number of links during time interval ${\tau}$. By
adopting a k-shortest path-based algorithm, the theoretical worst case
complexity becomes $O(|\mathcal{V}^{\tau}|! \cdot |\mathcal{V}^{\tau}|^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
$\mathcal{O}(3|\mathcal{L}^{\tau}| + (2\log{|\mathcal{V}^{\tau}|}+1)
|\mathcal{V}^{\tau}|)$. Simulations conducted on starlink constellation with
thousands of satellites corroborate the effectiveness of the proposed
algorithm.
