# GPU-Accelerated Eclipse-Aware Routing for SpaceWire-Based OBC in Low-Earth-Orbit Satellite Networks
## 2 Problem Description  
### Routing Problem in the LEO Network  
As mentioned earlier, LEO satellite networks operate in a dynamic topology environment, where inter-satellite connections continuously change over time. Specifically, previously established links may be disconnected, while new links are formed as time progresses. Due to this characteristic, conventional routing techniques used in static networks cannot be directly applied. Instead, a routing approach that can dynamically reflect the real-time connectivity status between satellites is required. In this paper, routing is performed based on the KSP algorithm. Unlike traditional shortest path algorithms that identify only a single shortest route, the KSP algorithm generates a set of K shortest path candidates and selects the optimal route from them. This approach is particularly advantageous in LEO satellite networks, where inter-satellite connections are highly dynamic and may suddenly become unavailable. By precomputing multiple alternative paths, network stability can be ensured [17; 18]. There are various methods for implementing the K-Shortest Path (KSP) algorithm, with [PERSON]'s algorithm and [PERSON]'s algorithm being among the most widely used [19; 20]. Beyond these classical approaches, advanced variations have been proposed to improve computational efficiency or enrich path diversity. For example, [PERSON] et al. introduced a technique that accelerates path enumeration by leveraging advanced data structures, significantly reducing the overhead in listing top-k paths [21]. In a different direction, [PERSON] et al. proposed a generalized framework called K-Shortest Paths with Diversity (KSPD), which incorporates similarity constraints between paths to generate more diverse and meaningful alternatives [22]. These approaches highlight the ongoing efforts to optimize KSP computation for different practical needs. A BFS-based KSP algorithm was chosen in this study, primarily for its compatibility with GPU-based parallel processing. While algorithms like [PERSON]'s and [PERSON]'s offer theoretical efficiency, they often involve recursive or heap-intensive structures, which are less amenable to parallel execution on architectures such as CUDA. In contrast, the BFS-based approach allows for flat memory access, minimal branching, and straightforward path expansion, making it particularly suitable for implementation on resource-constrained onboard systems. Future work will explore comparative implementation and benchmarking of these alternative KSP algorithms, including diversity-aware strategies, to better understand the trade-offs between computational complexity, parallelizability, and routing quality in LEO satellite environments. The BFS-based KSP algorithm implemented in this paper operates by first searching for K shortest paths to the target node and then selecting the optimal path based on specific criteria. In this paper, the initial path selection is based on the number of hops, and an additional path selection strategy is applied to consider energy consumption. Additionally, modern onboard networks consist of various elements, each performing different functions while being interconnected through the onboard network communication infrastructure. SpaceWire is one of the widely used technologies in this infrastructure due to its compact structure, efficiency, and ease of understanding and implementation [15]. In particular, SpaceWire-based onboard networks must dynamically reflect changes in network topology in real time through dynamic routing. In this study, a BFS-based KSP algorithm was applied to precompute multiple alternative paths and select the most suitable route for the SpaceWire routing table. By aligning with SpaceWire's routing mechanism, this approach enables the construction of optimal data transmission paths, enhancing both network stability and real-time data transfer performance.