# Hop-by-Hop Multipath Overlay Routing for Optimizing Network Resource Allocation in WANs
## 3 System Design
### Overlay Node Placement
Obviously, gaining access to a larger number of underlay paths through a small number of overlay nodes can enhance the efficiency and potentially diversify the paths of overlay multipath routing. Figure 3 illustrates an example of underlay link utilization. Figure 3a shows the complete topology, while Figure 3b-d represents the underlay links occupied by overlay nodes B, C, and D to their neighboring overlay nodes, respectively. Figure 3: An example of utilizing underlay links by shortest path trees. (**a**) Shows the example topology. (**b**) Shows the shortest path tree of overlay node B. (**c**) Shows the shortest path tree of overlay node C. (**d**) Shows the shortest path tree of overlay node D.  
Figure 2: An example of overlay node selection. (**a**) Shows the shortest path tree of \(dst\) and the tunnels of overlay node A. (**b**) Shows the underlay paths of the tunnels of overlay node A. (**c**) Shows the underlay paths of the tunnels of overlay node F.  
However, we find that these two metrics are not consistent. To reduce path overlap, nodes with high centrality are more likely to appear in the transmission path, which helps to decrease path overlap (as shown in Figure 2). On the other hand, to increase the diversity of underlay paths, it is preferable to choose nodes where there is a discrepancy between the degree of the shortest path tree and the degree of the graph. (as shown in Figure 3). To describe the ability of overlay nodes to bypass congested or failed paths, we study hop-by-hop path diversity \(d_{n}\) for overlay node \(n\). We define the underlay link utilized by the shortest paths of the overlay tunnel between node \(x\) and \(y\) as  
\[l(x,y)=\{l|l\in\text{shortest underlay paths between $x$ and $y$}\} \tag{1}\]  
Assuming the set of neighboring overlay nodes for node n is denoted as \(S_{n}\), the set of underlay paths occupied by node \(x\) and its neighbors is defined as  
\[U_{n}=\bigcup_{s\in S_{n}}l(s,n) \tag{2}\]  
The overlap of the \(\text{tunnel}(n,m)\) with the tunnel between the node \(n\) and its other neighbor node is defined as  
\[\text{Overlap}(n,m)=\frac{\left\|l(n,s)\cup\bigcup_{s\in S_{n}\setminus\{m \}}l(s,n)\right\|}{\left\|l(n,s)\right\|} \tag{3}\]  
The hop-by-hop path diversity \(d_{n}\) of overlay node \(n\) is defined as the sum of independent paths, which can be calculated by Algorithm 1. The ultimate goal of enhancing \(d_{n}\) of overlay nodes is to increase the end-to-end path diversity for all-to-all multipath transmission. The end-to-end path diversity \(D(x,y)\) is defined as the total number of independent paths obtained from hop-by-hop multipath routing. We believe that the local path diversity of overlay nodes determines the end-to-end transmission path diversity in the network. ```
Input: The neighboring overlay node set of node n is \(S_{n}\). The underlay graph G. Output: Hop-by-hop path diversity \(d_{n}\) of node \(n\). 1 Empty link set \(U=\emptyset\) ;
2\(d_{n}=0\) ;
3 forach\(s\in S_{n}\)do
4 Calculate \(l(n,s)\) from Graph G ;
5\(d_{n}\gets d_{n}+1-\frac{\left\|l(n,s)\cup l\right\|}{\left\|l(n,s)\right\|}\) ;
6\(U\gets U\cup l(n,s)\) ;
```  
**Algorithm 1**Path Diversity Calculation  
**Theorem 1**. : _The number of overlay nodes is \(m\). If \(\sum_{n=0}^{m}d_{n}\) reaches the maximum, then the path diversity of all-to-all end-to-end transmissions also reaches its maximum._  
Proof of Theorem 1.: Assume the contrary, that \(\sum_{n=0}^{m}d_{n}\) does not reach its maximum, implying that the end-to-end path diversity is not maximized. If \(d_{n}\) is not maximized for some node \(n\), it indicates that there are redundant or insufficient independent paths between node \(n\) and its neighbors. Thus, the set of underlay paths \(U_{n}\), occupied by node \(n\) and its neighbors, will also be suboptimal. This results in a decrease in the total path diversity of the network. A reduction in \(d_{n}\) leads to fewer independent paths, which in turn reduces the end-to-end path diversity.