# Fast-Convergence Reinforcement Learning for Routing in LEO Satellite Networks
## 3 Proposed FRL-SR Algorithm
### Reinforcement Learning Model Setting  
In solving the satellite routing problem using multi-agent reinforcement learning, we consider each satellite node as an agent. When the data packet arrives at the satellite node, it observes the current state and forwards the packet based on the present situation. The node adjusts the forwarding strategy according to the current state of the network. Once a link is broken or there is congestion present, the reward of this port is decreased, and packets are forwarded to another path. This is the main advantage of reinforcement learning compared with traditional routing algorithms. The entire packet forwarding process can be viewed as a finite-state Markov decision process (MDP) whose final state occurs when the packets have arrived at the destination node. We use (S, A, P, R) to represent a state of the MDP, where S is the state of the current system, A is the action space, P is the probability of state transition, and R is the reward. Each satellite node only forwards packets to its neighbor nodes, which means that the action space is up to four. Therefore, we chose reinforcement learning rather than deep reinforcement learning to achieve this. When using reinforcement learning to solve problems, it is crucial to design state, action, and reward functions [24]. For different scenarios, we should follow different design principles. In our satellite network routing scenario, the states, actions, and rewards are defined as follows:  
* States: Each state \(s_{t}\in S=\{N_{c},N_{d},q_{1}^{t},q_{2}^{t},\ldots,q_{p}^{t}\}\) indicates the present situation in the satellite network environment, where \(N_{c},N_{d}\) represent current node and destination node for packet, respectively. The parameter \(q_{p}^{t}\) represents the current queue length of the \(p\)-th node for \(p=1\) to \(p=P\). In multi-agent reinforcement learning, each agent observes a different state, and they make independent routing decisions based on the current state;
* Actions: The action \(a_{t}\in A=\{p_{1},p_{2},\ldots,p_{p}\}\) represents the agent choosing a node from its neighborhood nodes for each upcoming packet, where \(p_{p}\) represents the p-th satellite node. In satellite networks, each satellite has up to four neighbor nodes, so the length of A is up to four [25];
* Propagation delay. In satellite networks, the star link often fails and becomes unavailable, which requires frequent inter-satellite reconnections. For convenience, we consider both reconnection time and propagation time as propagation time delay. \(D_{ij}\) represents propagation delay between node \(N_{i}\) and node \(N_{j}\);
- Queue length. Each satellite node maintains the receiving queue \(q_{r}\) and the transmitting queue \(q_{t}\). Queuing delay occurs when the number of packets received by the satellite is larger than the length of the satellite receiving queue. The agent learns to forward data packets to satellite nodes with small queue length to reduce the waiting time;
- Load growth. To avoid packets being forwarded centrally to individual satellite nodes, causing network congestion, we record the receiving queue length in the previous stage as the load growth of the satellite, which is recorded as \(g_{i}\). Therefore, \(g_{i}\) could be seen as the congestion level of nodes \(N_{i}\). This avoids the situation that everyone sends data to \"high-quality\" nodes at the same time. Equation (3) gives the expression of reward function, where \(q_{max}\) represents the maximum queue length, and \(w_{1}\) and \(w_{2}\) represent the growth and delay coefficients, respectively. When the next hop is the destination node, we set the reward to 20\(N\), which ensures that the packets are transmitted to the destination node as soon as possible. \[reward_{j}= \begin{cases}20N&N_{j}\text{ is the destination}\\ q_{max}-(q_{r}+q_{t})-w_{1}*g_{j}-w_{2}*D_{j}&\text{Otherwise}\end{cases}  \tag{3}\]  
As shown in Figure 2, the system framework consists of three parts: Neighbor Node Discovery, Offline Training, and Online Training.