# GPU-Accelerated Eclipse-Aware Routing for SpaceWire-Based OBC in Low-Earth-Orbit Satellite Networks
## 3 Proposed Method  
### BFS-Based K-Shortest Path Algorithm  
To perform efficient path search in a LEO satellite network environment, a BFS-based KSP algorithm was applied. BFS operates by expanding adjacent nodes step by step from the source node, making it suitable for finding K shortest paths. The algorithm implemented in this paper searches for K shortest paths from the source node to the destination node, and Algorithm 2 illustrates the overall computational flow of this process. First, an initial candidate path list is created, including only the source node, while the list of discovered paths reaching the destination is initialized as empty. Then, as long as the candidate path list is not empty and the number of discovered paths reaching the destination remains below K, the algorithm performs BFS-based exploration. During the search, the algorithm expands paths based on the last node of the currently explored  
Figure 2: Profiling results of the conventional Eclipse-Aware Routing algorithm. path, identifying adjacent nodes. To prevent cycles, nodes already included in the path are excluded. If an expanded path reaches the destination, it is added to the discovered path list; otherwise, it is stored in the next candidate path list for further expansion in the subsequent iteration. Once the search concludes, as shown in line 22, the candidate path list is updated with the next candidate paths, and this process repeats until the optimal paths are found. Finally, the paths that reach the destination are stored in the discovered path list. After the search is complete, the paths are sorted based on their costs, and the K paths with the lowest costs are selected and returned. To provide a clearer explanation of the BFS-based KSP search process, Figure 3 is used to analyze the path exploration procedure, representing a portion of the actual graph used in this study's experiments. The gray node represents the starting node where the search begins, assigned as level 0, while the blue nodes indicate adjacent nodes expanded in the first step, corresponding to level 1. The yellow nodes represent nodes further expanded in the second step, forming candidate paths to the destination, with the numbers in the upper right corner of each node denoting the order in which they were explored. In BFS-based search, the exploration expands level by level from the starting node, forming paths while preventing cycles to ensure optimal route selection. Due to the nature of BFS, all possible paths are explored while expansion occurs based on the shortest distance, making it an efficient method for finding the K shortest paths. However, the BFS-based KSP algorithm has inherent limitations due to its sequential processing nature. Since it expands paths step by step, the search time can become significantly longer when executed sequentially. This issue becomes more pronounced in large-scale satellite networks with a high number of nodes and an increased number of paths to explore, leading to a rapid increase in computational time. As the BFS search process requires managing and expanding all candidate paths, the computational complexity grows exponentially, potentially affecting system performance. To address this bottleneck, this paper proposes a GPU-based parallel computing approach to accelerate the BFS-based KSP search. The details of this approach are discussed in the following section. Figure 3: Example graph representing sequential KSP search. ```
**Algorithm 2**BFS-based K-Shortest Path Algorithm in CPU--Pseudo-code

### Graph Representation

To enable efficient graph search in a GPU environment, this study applies the Compressed Sparse Row (CSR) transformation technique. While the traditional adjacency list approach used in CPU-based implementations is intuitive and memory-efficient, it can lead to performance degradation in GPU-based parallel searches due to non-contiguous memory access.