# Rethinking LEO Mega-Constellation Routing to Provide Fast Internet Access Services
## 3 Our Proposed Algorithm
### Satellite Set Matching Strategy  
In the traditional routing algorithm, each satellite needs to calculate the optimal path to the other satellites in the entire satellite network and store the corresponding forwarding table. However, in the routing algorithm proposed in this paper, each satellite only needs to calculate the route to the landing satellite in this satellite set. In this section, we will introduce the satellite matching strategy.  
The purpose of the matching strategy is to assign one or more landing satellites to each satellite, and the landing satellite establishes a connection with the ground station through a feeder link, at the current time. When the satellite receives an internet access request from a ground-based user, it sends the data directly to a matching landing satellite. Users will be connected to the ground core network through the feeder link of the landing satellite. The purpose of this approach is twofold: first, minimize the hop number of satellite network packets to reduce the internet access delay and avoid packet loss caused by unstable ISLs; second, greatly reduce the complexity of the routing algorithm. Each set of satellites includes several non-landing satellites and landing satellites, as shown in Figure 3. Note that, for the sake of brevity, only the satellites in ascending orbit are shown in this figure.  
The following linear programming is used in this paper to match satellites. First, we divide all satellites into the landing satellite set \(\mathbb{D}\), and the non-landing satellite set \(\mathbb{S}\). Then, in order to improve the comprehensive user experience of the whole network, our optimization goal is to minimize the total hops from each satellite to its matching satellite, as shown below:  
\[Min:\sum_{s\in\mathbb{S}}\sum_{d\in\mathbb{D}}W_{s,d}\cdot N_{s,d}. \tag{8}\]  
where, \(W_{s,d}\) are the separate flow ratio of source satellite to destination satellite, defined as the ratio of the traffic transmitted to the destination satellite to the total traffic received by the source satellite. \(N_{s,d}\) are the theoretical minimum hops from the source satellite to the destination satellite, which are obtained in the previous subsection.  
Figure 3: A diagram of satellite sets in a Walker constellation.  
Meanwhile, considering the user's data transmission requirements, and the capacity of the feeder link to establish the connection between the satellite network and the ground, there are the following constraints:  
\[\begin{split} Subject\quad\text{to}\quad:\sum_{d\in\mathbb{D}}W_{s,d}=1 \quad\quad\quad\forall s\in\mathbb{S}\end{split} \tag{9}\]  
\[\begin{split}\sum_{s\in\mathbb{S}}T_{s}\cdot W_{s,d}\leq C_{d} \quad\quad\forall d\in\mathbb{D}.\end{split} \tag{10}\]  
where \(T_{s}\) represents the data traffic received by the source satellite \(s\), and \(C_{d}\) represents the feeder link capacity of satellite \(d\). Formula (9) defines the constraint of user transmission demand, to ensure that all user data can be transmitted to the ground core network. Formula (10) defines the capacity constraint of feeder links, that is, the data rate transmitted on a feeder link cannot exceed its capacity.