# Load-Balancing Routing for LEO Satellite Network with Distributed Hops-Based Back-Pressure Strategy
## 4 Hops-Based Back-Pressure Routing
### Hops-Based BP Routing  
In the above original BP routing protocols, the backlog of network nodes usually only considers the packets number in cache, rather than the packet delay [38; 39]. This may cause a large delay and affect network performance. According to the above analysis, in the LEO satellite network, hops count between nodes is the key influencing factor of packet delay. In order to improve the delay performance of BP routing, the propagation delay of the packets is approximately estimated by end-to-end hops between the next hop and the destination. The corresponding delay is defined as the destination-hops-delay (DHD). Assume that \(Q_{a}^{c}\) denotes the packet set of flow \(c\) at node \(a\). For \(p\in Q_{a}^{c}\), \(H(p)\) denotes the DHD from \(a\) to destination \(b\).  
In LEO satellite networks, the periodic and predictable orbits make the orbital roots easy to be determined. Therefore, according to the hops estimation method proposed above, intermediate satellites can quickly calculate the end-to-end hops count between the candidate next-hop and destinations. At node \(a\), the cumulative DHD of all packets is recorded as \(\sum H(p)\). In this paper, the cumulative DHD is defined as the backlog metric \(\hat{Q}_{a}^{c}\):  
\[\hat{Q}_{a}^{c}=\sum_{p\in Q_{a}^{c}}H(p)=|Q_{a}^{c}(t)|\times H(p), \tag{10}\]  
where \(|Q_{a}^{c}(t)|\) denotes the packets number in flow \(c\) at node \(a\) at time slot \(t\). On this basis, at time slot \(t\), the backlog difference between \((a,b)\) based on DHD can be defined as:  
\[\hat{\omega}_{ab}^{c}(t)=\max_{c}\big{[}\hat{Q}_{a}^{c}(t)-\hat{Q}_{b}^{c}(t) \big{]}. \tag{11}\]The transmission rate on link \((a,b)\) is determined according to the following strategy:  
\[\text{Maximize}:\sum_{a=1}^{N}\sum_{b=1}^{N}\mu_{ab}(t)\hat{\omega}_{ab}^{c}(t) \tag{12}\]  
\[\text{s.t.}\mu_{ab}(t)\in\Gamma_{s(t)}, \tag{13}\]  
where \(\mu_{ab}(t)\) denotes the transmission rate of flow \(c\) on link \((a,b)\).  
In this paper, the proposed routing strategy is defined as distributed hops-based BP routing (DHBP). An example of cache management and the queue backlog calculation of DHBP is shown in Figure 5. Each node maintains both the packet queue and the virtual DHD queue to determine backlog \(\hat{Q}\) of each packet flow.  
Given the source \(s\) and destination \(d\), packet flow \(c\) is sent from \(s\) to \(d\). The following steps are followed to determine which node is to be selected as the next hop when packet arrives at the node \(A\). The queue length of flow \(c\) at \(A\) is \(Q_{A}^{c}(t)=6\). Accordingly, when it comes to \(B,E,F\), \(Q_{B}^{c}(t)=4,Q_{E}^{c}(t)=4,Q_{E}^{c}(t)=5\). Therefore, the queue backlog difference from \(A\) to \(B,E,F\) is 2,2,1, respectively. In the standard BP routing, node \(A\) to node \(B,E\) have the same queue backlog difference. In the proposed DHBP, the backlog difference to the destination node is calculated according to Equation (10). In the above example, the number of hops between \(B\) and the destination is less than \(E\). Therefore, \(E\) is excluded as the next hop. Assume that \(B\) and \(F\) have the same hops to the destination. In the backlog difference between \(A\) and \(B\), \(F\) is \(Q_{AB}^{c}(t)=2\) and \(Q_{AF}^{c}(t)=1\), respectively. Since \(Q_{AB}^{c}(t)>Q_{AF}^{c}(t)\), in this example, \(B\) will be taken as the next hop.  
Figure 5: Queue management and backlog calculation of DHBP.