# Mitigating DDoS Attacks in LEO Satellite Networks Through Bottleneck Minimize Routing
## 5 Simulation and Result
### Complexity Analysis  
In terms of time complexity, K-SP's is finding the shortest k paths between sources by using the [PERSON]'s algorithm. In the worst case, however, every newly discovered path of length up to \(V\) may require enumerating all of its spur nodes, which incurs a base cost of \(O(kV(E+VlogV))\). But once it is found that the actual length of a candidate path exceeds _fiber_len_, further spur enumeration of the path is stopped immediately. Let the average number of spur nodes for each path in the actual graph is \(N\). Since \(N\ll V\), the number of shortest path searches required during actual runtime is much less than the theoretical worst case. Then, it needs to repeat by k times to find paths. Hence, the end-to-end time complexity for K-SP routing is as follows:  
\[O(kN(E+VlogV)) \tag{6}\]  
The K-DG strategy iteratively invokes a single-source Dijkstra search to extract one shortest path per iteration and uses a _fiber_len_ cutoff to prune in advance, costing \(O(E+VlogV)\) each time. Once a path is accepted, its constituent ISLs, uplinks, or down-links are pruned from the graph. If at any point the path contains no ISL segments, the algorithm terminates early. This iterative process continues until k paths have been found or no further paths exist, yielding the following total routing complexity:  
\[O(k(E+VlogV)) \tag{7}\]  
The core of the K-Bottleneck Minimize algorithm is its repeated invocation of single-source Dijkstra search under weighted risk metrics. A single Dijkstra run on a graph with \(V\) vertices and \(E\) edges require \(O(E+VlogV)\) time when implemented with a binary-heap priority queue. Since we extract up to k edge-disjoint paths and allow a bounded number  
Figure 7: Attack MaxUp of different strategy. (**a**) Average attack MaxUp for each strategy; (**b**) Median attack MaxUp for each strategy.  
of retries, we perform \(O(k)\) for such Dijkstra computations. As with the previous two strategies, we enforce the _fiber_len_ bound. However, rather than simply discarding any path whose total length exceeds bound, we iteratively identify and remove its longest edge and re-run Dijkstra to obtain the next candidate. In each iteration, we also traverse the selected path of \(N\) edges in \(O(N)\) time to check the cumulative length and to disable any individual edge that would push the path over the bound. Consequently, the overall time complexity of the routing procedure is as follows:  
\[O(k(E+VlogV+N)) \tag{8}\]  
The computation time cost of the three algorithms is shown in Figure 8.  
We measure the computational cost of different algorithms by actual computation time. Under our experimental conditions, routing computation across the entire Starlink S1 constellation required 3297 s for K-SP, 724 s for K-DG, and 2613 s for K-Bottleneck Minimize. The markedly longer runtime of K-SP arises from its additional overhead: each new path generation invokes a spur-node search, and for every source-destination pair, K-SP exhaustively generates paths until it either finds all k routes or exhausts all feasible options, which leads to the highest total computation cost.  
By contrast, both K-DG and K-Bottleneck Minimize terminate upon discovering the first ground-satellite-ground direct route. In K-DG, each time a path is successfully selected and appended to the result set, only one complete Dijkstra search is required; subsequent edge-pruning operations do not trigger further shortest-path computations, accounting for its reduced total runtime. K-Bottleneck Minimize likewise performs one Dijkstra search, but whenever a candidate path exceeds the length limit and its longest edge must be discarded, each retry entails another full shortest-path run. Its attempt-limit mechanism effectively curtails repeated computation when feasible paths are scarce, and if k valid paths cannot be assembled after multiple attempts, the algorithm terminates early--resulting in a total runtime above that of K-DG.