# Multi-Topology Routing Algorithms in SDN-Based Space Information Networks
## 4 Multi Topology Routing Algorithm
### TBA Algorithm
When the link bandwidth does not meet the bandwidth requirements of all tasks, you need to allocate bandwidth in different proportions according to the size of different task allocation factors. \[\varphi=\left\{\varphi_{task_{1}},\varphi_{task_{2}},\varphi_{task_{3}} \right\}(\varphi_{task_{1}}>\varphi_{task_{2}}>\varphi_{task_{3}}) \tag{15}\]  
\[\left\{ \begin{array}{l}b_{r}{}^{Task_{1}}=\frac{\varphi_{task_{1}}}{\varphi _{task_{1}}+\varphi_{task_{2}}+\varphi_{task_{3}}}\times b_{r}\\ b_{r}{}^{Task_{2}}=\frac{\varphi_{Task_{2}}}{\varphi_{Task_{1}}+\varphi_{task _{2}}+\varphi_{task_{3}}}\times b_{r}\\ b_{r}{}^{Task_{3}}=\frac{\varphi_{task_{1}}}{\varphi_{task_{1}}+\varphi_{task _{2}}+\varphi_{task_{3}}}\times b_{r}\end{array} \right. \tag{16}\]  
Of course, on the r-hop link, the sum of the allocated bandwidth of the three tasks cannot exceed the total bandwidth of the r-hop, that is:  
\[b_{r}{}^{Task_{1}}+b_{r}{}^{Task_{2}}+b_{r}{}^{Task_{3}}\leq b_{r}(1\leq r \leq n) \tag{17}\]  
In addition, there is a certain minimum bandwidth requirement for delay-sensitive services, throughput-sensitive services and best-effort services. If the minimum bandwidth is not satisfied, the transmission of the task is terminated and the transmission bandwidth of the remaining tasks is reallocated. The link condition is detected in real time. When the link bandwidth meets its minimum requirements, the task is re-transmitted. The minimum path bandwidth \(cpath^{\textit{Task}_{1}}(\text{B})\) required by \(\textit{Task}_{1}\) is:  
\[cpath^{\textit{Task}_{1}}(\text{B})=\left\{cb_{1}^{\textit{Task}_{1}},cb_{2}^{ \textit{Task}_{1}}\cdots cb_{n}^{\textit{Task}_{1}}\right\} \tag{18}\]  
where \(cb_{r}^{\textit{task}1}\) denotes the minimum bandwidth required by \(\textit{Task}_{1}\) in r hop. Similarly, the minimum path bandwidth of \(\textit{Task}_{2}\), \(\textit{Task}_{3}\) can be obtained. Suppose that the order of arrival of the three tasks is \(\textit{Task}_{1}\), \(\textit{Task}_{2}\), \(\textit{Task}_{3}\), when \(\textit{Task}_{3}\) arrives, the \(\textit{Task}_{1}\) and \(\textit{Task}_{2}\) are should be checked first. If the bandwidth applied by \(\textit{Task}_{1}\) and \(\textit{Task}_{2}\) is less than the available bandwidth, it is proved that the link has available bandwidth. Then determine whether the remaining bandwidth meets the request of \(\textit{Task}_{3}\), if it is satisfied, the bandwidth it requests is provided, if it is not satisfied, the allocation bandwidth of all three tasks is verified to be greater than the minimum bandwidth, and then the bandwidth resources are allocated according to the bandwidth resource allocation factor. If the bandwidth requested by \(\textit{Task}_{1}\) and \(\textit{Task}_{2}\) is larger than the available bandwidth, the allocation bandwidth of all three tasks is verified directly to be larger than their minimum bandwidth, and then the bandwidth resources are allocated according to the bandwidth allocation factor [27]. The basic flow of TBA Algorithm is shown in Algorithm 1:  
```
Input: The path has been selected; Output: Bandwidth resource allocation strategy in the SIN;
1: The bandwidth resource allocation factor of \(\textit{Task}_{1}\), \(\textit{Task}_{2}\), \(\textit{Task}_{3}\) are obtained;
2:forNew \(\textit{Task}_{3}\) arrives
3:if\(ab_{r}^{\textit{Task}_{1}}+ab_{r}^{\textit{Task}_{2}}<b_{r}\)
4:\(b_{r}^{\textit{Task}_{1}}=ab_{r}^{\textit{Task}_{1}}\), \(b_{r}^{\textit{Task}_{2}}=ab_{r}^{\textit{Task}_{2}}\);
5:if\(ab_{r}^{\textit{Task}_{3}}\leq b_{r}-ab_{r}^{\textit{Task}_{1}}-ab_{r}^{ \textit{Task}_{2}}\)
6:\(b_{r}^{\textit{Task}_{3}}=ab_{r}^{\textit{Task}_{3}}\);
7:elseif\(ab_{r}^{\textit{Task}_{1}}=b_{r}-ab_{r}^{\textit{Task}_{1}}-ab_{r}^{ \textit{Task}_{2}}\)
8: Calculate \(b_{r}^{\textit{Task}_{1}}\), \(b_{r}^{\textit{Task}_{2}}\), \(b_{r}^{\textit{Task}_{3}}\) according to Formulas (15) and (16).