## 3 Dynamic Routing Algorithm for Inter-Satellite Network Based on Q-Learning
### Dynamic Routing Algorithm Based on Q-Learning
Then, the agent repeats the above operation for the state \(s_{t+1}\), and so on until the optimal action value \(Q^{*}(s_{t},a_{t})\) is reached, the agent selects the optimal strategy \(\pi_{Q^{*}}\) according to the rewards of each strategy in \(Q^{*}(s_{t},a_{t})\), and the optimal strategy can be expressed as Formula (2h);  
\[Q^{*}(s_{t},a_{t})=E\Big{[}R(s_{t},a_{t})+\gamma max_{a\in A}Q^{*}(s_{t+1},a_{ t+1})\Big{]} \tag{2h}\]  
Long-term rewards indicate the total reward an agent can expect to accumulate over time for each system state. The key to planning a path for a service flow is to select an appropriate path for packet forwarding according to the service requirements and the real-time status of each link in the network. The key to flexible selection of the best transmission path is that there are multiple optional paths in the network, and the states of links are different. In order to avoid data traffic congestion during inter-satellite network communication, data packets re-plan another optional path. This optional path may not be the shortest, but its link utilization rate is low, while for delay-sensitive services, the impact of link delay cannot be ignored, so the reward function is set as an index of comprehensive link states as shown in Formula (2i), in which \(\alpha_{1},\alpha_{2},\alpha_{3}\) are the adjustment factors of link bandwidth, delay and packet loss rate respectively. In this chapter, we divide the link bandwidth into three levels, the link load above 80% is regarded as excessive use, the link between 30% and 80% is regarded as moderate load, and the rest is less than 30% as the link load is light. In this way, the state set is roughly classified, but considering that there are differences in link utilization at each level, for example, it is obviously unreasonable to directly regard 40% and 70% link bandwidth utilization as the same level, so when designing the bandwidth part of the reward function R of Q-learning, the link load of the moderate level ([30-80%]) is divided more finely to reflect the difference. According to the above analysis, the bandwidth part of the reward function is set based on the sigmoid function, as shown in Figure 6. The abscissa represents the remaining link bandwidth ratio (inversely proportional to the link load), while the ordinate represents the immediate reward of the link bandwidth part \(delay_{ij}\). It is characterized in that when the link utilization rate is overloaded, the reward value of the bandwidth part tends to almost 0, and the mid-term transition is smooth, but the gradient value is getting higher and higher, until the link is idle (occupancy rate is lower than 30%), its reward value approaches 100. \(delay_{ij}\) and \(loss_{ij}\) represent the ratio of the delay and packet loss rate of link \((i,j)\) to the maximum delay and packet loss in the global link, respectively, thus, the values are all between (0,100]. Finally, the reward function is shown in formula (2i). Specifically, if the selected link is in a better state, the reward value will be greater after the agent acts. \[R_{i\to j}=\mathrm{R}\Big{(}\left.i,j\right|_{s_{t},\mu_{t}}\Big{)}=-\cos t +\alpha_{1}BW_{ij}-\alpha_{2}delay_{ij}-\alpha_{3}loss_{ij} \tag{2i}\]  
In this chapter, the routing system based on Q-learning is composed of SDN controller and satellite nodes. The SDN controller acts as an agent to interact with the environment and obtain three signals: state, action and reward. Among them, the state space is represented by the traffic matrix of the nodes and the links between the nodes, which represents the current network link traffic load. The agent takes which node to forward the data packet to as an action space. The reward function is related to the type of business. If a business is delay-sensitive, the reward function will increase the weight of the delay part, so that the agent can change the path of the data flow, and the corresponding flow table will be sent to the corresponding nodes.