# A Multi-Dimension Spatial Method for Topology Awareness and Multipath Generating
## 4 Multipath Generating
### Exploiting Underlay Diversity  
Links from different autonomous systems are usually independent, so we try to establish multiple paths via various autonomous systems. In Figure 4b, three paths are to be established between origin and destination ARSes from AS1 and AS5. Assuming that AS4 and AS6 are different and have SPs with AS1 and AS5; then, we hope that packets are redirected into AS4 and AS6 earlier and out later, thus packets on two paths might pass less common links. Assuming also that AS2 and AS3 together could bridge AS1 and AS5, we try to find these combined autonomous systems. The multipath generating procedure of a multi-dimensional spatial method is described in Algorithm 2. When MP(i,j) contains candidate multiple paths, we use DA to evaluate the diversity of first hops and filter links with high diversity, i.e., selecting relatively bigger \(DA(lk_{a},lk_{c})\) and \(DA(lk_{b},lk_{d})\), where \(lk_{a},lk_{b}\in P_{1},lk_{c},lk_{d}\in P_{2},P_{1},P_{2}\in MP(i,j)\). When MP(i,j) has less than two paths, then we use above filtering constrains on Origin(i,j) and Dest(i,j) to construct paths. When there still exist no available paths, we just select RSes that satisfy TS and DA filtering constraints.  
\begin{table}
\begin{tabular}{p{142.3 pt} p{142.3 pt}} \hline \hline
**Item** & **Definition and Description** \\ \hline Transmission Direction (TD) & Vector from the coordinate of origin-ARS to that of destination-ARS, TD of 7-9 is TD(7,9) \\ Transmission Surface (TS) & The candidate RSes are restricted within the surface, which is enclosed with constrained criteria, TS of 7-9 is TS(7,9), which includes rectangle surface ABCD, ellipse EF \\ Deviation Angle (DA) & The angle between the link and TD, \(\alpha\) is the deviation angle of 7-2 and 7-9, \(\beta\) the 7-12 and 7-9, Then, the angle of 7-2 and 7-12 is DA(7-2,7-12)=\(|\alpha|+|\beta|\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Geometric items and descriptions referring to Figure 4.  
Figure 4: Sample topologies consist of overlay nodes and different autonomous systems. (**a**) shows a coordinate-based view of Relay Serves and solid circles represent the coordinates of Relay Servers; (**b**) shows the underlay bearing networks consisting of various autonomous systems deployed in different locations (L1–L6).  
```
0:\(RS_{i}\in L_{s},RS_{j}\in L_{t},RS_{i}\in T_{u},RS_{j}\in T_{v}\) \(T_{N}\), N is the number of autonomous systems \(L_{M}\), M is the number of locations (cities) \(NB(M,M),NB_{M}(P,P)\), P is the number of RSes Output:
0:MP(i,j), multiple paths from \(RS_{i}\) to \(RS_{j}\) Origin(i,j), Dest(i,j), candidate RSes near two ARSes
1:while\(L_{k}\in L_{M}\textbf{and}0\leq NB(k,s)\leq 1\)do
2:while\(T_{d}\in T_{N}\textbf{and}L_{k}(u,d)=\textbf{land}L_{k}\in TS(i,j)\)do
3: Add(Origin(i,j), d, k)
4:while\(L_{r}\in L_{set}\textbf{and}0\leq NB(r,t)\leq 1\)do
5:while\(T_{w}\in T_{set}\textbf{and}L_{r}(v,w)=\textbf{land}L_{r}\in TS(i,j)\)do
6: Add(Dest(i,j), w, r)
7:if\(T_{w}=T_{d}\)then
8: Add(MP(i,j), k, r, 1)
9:elseif\(L_{b}(w,d)=\textbf{land}L_{b}\in TS(w,d)\)then
10: Add(MP(i,j), k, b, r, 2)
11:endif
12:endwhile
13:endwhile
14:endwhile
15:endwhile
```  
**Algorithm 2** Generating multiple paths with MDSM