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

doi:10.1109/TMC.2025.3623456

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

2025-10-20

0

PRE

AI

DOI：10.1109/TMC.2025.3623456

Original

Original request for help

Save

Abstract

En 中文

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 flow 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 Flexible Function-Time Expanded Graph (F$^{2}$2-TEG) 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$^{2}$-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$^{2}$-TEG through a linear programming (LP) solver, since F$^{2}$-TEG supports effective pruning. For larger networks, we further propose an efficient graph algorithm over F$^{2}$-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$^{2}$-TEG-based LP scheme is $3.5\times$ faster than other graph-model-based LP schemes. For larger networks, our graph-based algorithm can be more than $130\times$ faster than LP-based schemes, while still improving the maximum flow by 46% compared to SOTA work.

Keywords:

Satellite networks

service function chain

max flow

flexible function-time expanded graph

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

Abstract

Journal

Organization