# An Accelerated Maximum Flow Algorithm with Prediction Enhancement in Dynamic LEO Networks
## 5 Evaluations  
To evaluate the performance of the predictive acceleration algorithm for maximum flow in e-TEG networks, we utilized the system tool kit (STK) [39] to model SpaceX's Starlink [1] satellite constellation. This constellation comprises satellites orbiting at an altitude of 550 km with a 53-degree inclination, distributed across five orbital planes. Given the computational complexity of simulating the full Starlink constellation, we adopt a scalable evaluation framework using 10, 15, 20, and 25 satellites. While these configurations represent a fraction of the full network, they preserve key topological properties of large-scale LEO constellations, including dynamic connectivity and constrained onboard resources. Prior work in temporal graph analysis and network optimization demonstrates that reduced-scale networks effectively capture algorithmic behavior while enabling controlled, repeatable experimentation [11, 40]. To establish a representative baseline for constellation construction, we first identified a canonical Starlink satellite (550 km altitude, 53\({}^{\circ}\) inclination) from operational TLE data as the orbital seed. Using this seed as the template, Walker Delta [41] constellations were programmatically generated in STK by replicating its characteristics thereby preserving Starlink-like topological properties. The architecture was implemented with precise orbital parameters, including phase offsets optimized for collision avoidance and uniform coverage. Satellite trajectories were propagated using the SGP4 model [42]. To capture realistic network dynamics, we established a 1 h evaluation window starting at 0400 UTC on 14 October 2024, divided into twelve 5 min intervals corresponding to characteristic LEO network state changes. Link configurations were rigorously modeled with fixed 1 Gbps data rates for both ISLs and ground-to-satellite links (GSLs), incorporating practical constraints. Onboard storage capacities were parameterized across three configurations (500 GB, 600 GB, 700 GB) to systematically evaluate resource-constrained adaptation capabilities. We compared the proposed predictive acceleration algorithm against existing maximum flow methods for e-TEG networks, including the standard [PERSON]'s algorithm [8], MPTPT-based routing [43], and the e-TEG algorithm [11]. In [PERSON]'s algorithm, augmenting paths are found using BFS to construct a layered network, and the depth-first search is employed to send flow along these layers. MPTPT-based routing iteratively selects the most promising path based on current conditions, optimizing flow based on the immediate network state. The e-TEG algorithm extends the traditional time-expanded graph framework by incorporating energy constraints, effectively modeling satellite networks with time-varying topologies and dynamic link capacities. To evaluate the computational efficiency of the proposed algorithm and other existing algorithms, we use running time as the main metric, defined as the time taken to compute the maximum flow. In addition to running time, we also introduce the acceleration percent age to quantify the reduction in computational effort relative to the e-TEG algorithm. This metric compares the performance of the evaluated algorithm with the e-TEG algorithm as the baseline. The acceleration percentage is defined as follows:  
\[Acceleration\text{\emph{Percentage}}=\frac{t_{e-TEG}-t_{compared}}{t_{e-TEG}} \tag{28}\]  
where \(t_{e-TEG}\) represents the running time of the e-TEG algorithm, and \(t_{compared}\) is the running time of the algorithm being evaluated. We first analyzed the running time of the warm-starting Ford-Fulkerson algorithm (labeled as \"warm-starting FF\" in the figures) and the predictive LEO maximum flow algorithm alongside three existing methods in Figure 6 and Figure 7, respectively. For this analysis, we used a satellite network consisting of 25 satellites, each with a limited storage capacity of 600 GB. The running times of the four algorithms were evaluated as the number of time slots varied from 25 to 60.