# A Disruption Tolerant Distributed Routing Algorithm in LEO Satellite Networks
## 3 Disruption Tolerant Distributed Routing Algorithm
### Failure Area Routing Calculation
#### 3.5.2 Detour Path Direction Calculation  
Since the link failure information is flooded to the satellite nodes within \(n\) hops, each satellite can obtain the real-time status of all links within \(n+1\) hops. For a specific failed link, we adopt an early detour strategy to balance the network load. Figure 4 shows the strategy. First determine whether the main path to the destination node passes through a failed link. For the node whose main path passes through the failed link, its detour path direction is the same as the alternate path direction mentioned in Section 3.3. Since our main path calculation algorithm has a small overhead, we can calculate the first \(n+1\) hops of the main path of any node at any time to determine whether it passes through a failed link without storing the main path for each destination node. Whenever new link failure information or link recovery information comes, the router must recalculate the routing table. When calculating the routing table, it needs to consider all failed links in the area. As long as there are failed links, the local satellite records the failure area state as 1. The steps to calculate the routing table are as follows and the calculation algorithm is described in Algorithm 2:  
Figure 4: Early detour strategy for failed links.  
Initialization.  
Record the forwarding interfaces for all destination nodes in the detour routing table as \(-1\) and record the failure area state as 0.  
Traverse all links within \(n+1\) hops.  
During the traversal process, if a failed link is found, the starting satellite node1 and the ending satellite node2 of the failed link are obtained, and step (3) is entered. At the same time, the failure area state is recorded as 1.  
Calculate the forwarding table for a specific failed link.  
For a specific failed link, the starting satellite node1 and the ending satellite node2 are known. For each destination satellite node, we first determine whether its main path passes through the failed link. If it is determined to pass, then the forwarding interface for this node is recorded the same as in the alternate path routing table. If it is determined that it does not pass, then the forwarding interface of the destination node is recorded as \(-1\).  
Update the routing table for a failed link.  
According to the forwarding table calculated in (3), for each destination satellite node, if the forwarding interface in the routing table is \(-1\), use the forwarding interface in the current forwarding table to update the forwarding interface in the routing table, and go back to step (2).  
```
1:A node receives link failure information
2:fornode\(\in\)all nodesdo
3:rt2[node]\(\Leftarrow-1\)
4:endfor
5:\(FAS\Leftarrow 0\)
6:forlink\(\in\)links within \(n+1\) hopsdo
7:if\(link.failure=1\)then
8:\(FAS\Leftarrow 1\)
9:fornode\(\in\)all nodesdo
10:ifnode.mainpath passes link.node1 and link.node2 then
11:\(ft[node]\Leftarrow rt1[node]\)
12:else
13:\(ft[node]\Leftarrow-1\)
14:endif
15:endfor
16:fornode\(\in\)all nodesdo
17:if\(rt2[node]=-1\)then
18:\(rt2[node]\Leftarrow ft[node]\)
19:endif
20:endif
21:endif
22:endfor
```  
**Algorithm 2** Failure area routing calculation.