An SFC-Constrained Max-Flow Solver for Satellite Networks Using Flexible Function-Time Expanded Graph

Satellite networks will be a critical part of the 6G infrastructure, offering ubiquitous coverage and resilience to natural disasters on Earth. However, the expected increase in the number of services with high communications and compute demands, such as remote sensing and rural Internet of Things (IoT) data analytics, poses challenges to limited resources in satellite networks. Service Function Chain (SFC), an application driven network technology, offers a promising solution by flexibly orchestrating virtualized functions into a service chain to support these demands. Our work studies the SFC-constrained maximum f low problem that aims to find the maximum flow possible between a source and a destination node subject to the SFC constraints, where the data must flow through a predefined sequence of service functions. We propose the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Flexible Function Time Expanded Graph (F²-TEG)</i> to represent the SFC ordering requirements and the time-varying network topology, while uniformly modeling the compute, storage and communication resources. We prove that F<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>-TEG models the entire feasible solution space of the SFC-constrained max-flow problem, in particular, incorporating the full flexibility in the allocation of compute resources. This flexibility is not captured by the state-of the-art (SOTA) work. For smaller networks, the optimal solution can be found effectively using F<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>-TEG through a linear program ming (LP) solver, since F<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>-TEG supports effective pruning. For larger networks, we further propose an efficient graph algorithm over F<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>-TEG that achieves lower computation complexity via local search. Simulation over the real-world Starlink constellation shows that the enlarged solution space compared to SOTA work improves the maximum flow by 50 – 142% and the F<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>-TEG based LP scheme is 3.5× faster than other graph-model-based LP schemes. For larger networks, our graph-based algorithm can be more than 130× faster than LP-based schemes, while still improving the maximum flow by 46% compared to SOTA work.