# Multi-Topology Routing Algorithms in SDN-Based Space Information Networks
## 4 Multi Topology Routing Algorithm
### TBA Algorithm  
As a complex system, SIN have different spatial tasks running at the same time. Therefore, we need to study the routing algorithms when multitasking is performed simultaneously. First, choose the shortest path. When different priority tasks have a common shortest path, the higher priority task flow takes the shortest path first. Low priority task flow depends on the shortest path: (1) When the shortest path has available bandwidth, it should choose the shortest path, otherwise it will take the sub shortest path. (2) The scheduling is performed in real time during the running process to ensure that different tasks meet the QoS requirements. But there are also possible special cases, that is, in the same node or link only one, different users of different tasks at the same time in a link transmission, and the total link bandwidth does not meet all the tasks of the application bandwidth. At this point, the bandwidth allocation strategy needs to be determined according to the priority of different tasks, so that different levels of tasks negotiate the use of bandwidth resources. Therefore, this paper proposes a TBA algorithm [26]. First, we propose a concept of bandwidth resource allocation factor. There are users with different priorities in the SIN, which are divided into ordinary users and special users. At the same time, there are spatial tasks with different priorities. Therefore, in the design of the SIN, it is necessary to consider user priority and task priority to determine the allocation factor of bandwidth resources. User priority is defined as follows. \[\left\{ \begin{array}{l}U=1,\text{ Ordinary user}\\ U=u,\text{ Special user}\end{array} \right. \tag{10}\]  
Figure 4: Schematic diagram of delay forwarding routing. Task priority mainly depends on the importance of the task, maximum delay tolerance and other parameters. \(Task_{i}\)'s priority is defined as follows. \[Task_{i}=\frac{I_{i}}{\lg(D_{i}+1)\times\lg(I_{i}+1)\times\lg(10\times L_{i})} \tag{11}\]  
Here, \(I_{i}\) represents the importance of \(Task_{i}\), \(D_{i}\) represents the maximum end-to-end delay allowed by \(Task_{i}\), \(J_{i}\) represents the maximum time delay jitter of \(Task_{i}\), \(L_{i}\) represents the maximum packet loss rate allowed by \(Task_{i}\). That is, the higher the importance of the task, the smaller the maximum end-to-end delay and delay jitter allowed, and the smaller the maximum allowed packet loss rate, the higher the priority of the task. In summary, the bandwidth resource allocation factor of spatial information tasks can be defined as the product of user priority and task priority, and the expression is as follows:  
\[\varphi_{Task_{i}}=U_{i}\cdot Task_{i} \tag{12}\]  
Suppose there are three spatial tasks on a selected link: \(Task_{1}\), \(Task_{2}\), \(Task_{3}\). Task assignment factor is \(1\geq\varphi_{Task_{1}}>\varphi_{Task_{2}}>\varphi_{Task_{3}}>0\), \(s\) and \(d\) represent the source node and the destination node of a path respectively, the path is represented as path, define \(path=\{b_{1},b_{2}\cdots b_{n}\}\) as the available bandwidth of each hop on the selected path of the routing algorithm, \(b_{r}(1\leq r\leq n)\) is the available bandwidth of hop \(r\) in the path. The path bandwidth \(path^{Task_{1}}(\text{B})\) allocated by the system to \(Task_{1}\) is:  
\[path^{Task_{1}}(\text{B})=\left\{b_{1}{}^{Task_{1}},b_{2}{}^{Task_{1}}\cdots b _{n}{}^{Task_{1}}\right\} \tag{13}\]  
Here, \(br^{task1}\) represents the bandwidth allocated to the \(r\)-hop of the selected path of \(Task_{1}\). Define the bandwidth \(path^{Task_{1}}(\text{B})\) set for \(Task_{1}\) application:  
\[path^{Task_{1}}(\text{B})=\left\{ab_{1}{}^{Task_{1}},ab_{2}{}^{Task_{1}} \cdots ab_{n}{}^{Task_{1}}\right\} \tag{14}\]  
Here, \(ab_{r}{}^{task1}\) indicates the bandwidth requested by the \(Task_{1}\) in the r-hop of the path. Similarly, the allocation bandwidth and application bandwidth of \(Task_{2}\) and \(Task_{3}\) can be obtained.