# Hop-by-Hop Multipath Overlay Routing for Optimizing Network Resource Allocation in WANs
## 3 System Design
### Overlay Node Placement
Therefore, if \(\sum_{n=0}^{m}d_{n}\) does not reach its maximum, the end-to-end path diversity cannot be maximized, leading to a contradiction. Hence, if \(\sum_{n=0}^{m}d_{n}\) reaches its maximum, the end-to-end path diversity of all overlay transmissions must also reach its maximum. In addition to the path diversity between overlay nodes, user access should also be considered. Clustering of overlay nodes leads to inefficiency in serving a large number of underlay users. This study measures the scale of the overlay multipath service by the number of utilized underlay links, with fewer links indicating a higher concentration of overlay nodes. Let \(\mathcal{N}\) be the set of selected overlay nodes. The multipath overlay node placement (MOP) problem is formulated as follows:  
\[\underset{\mathcal{N}}{argmax}\sum_{n\in\mathcal{N}}(d_{n}+\alpha\|U_{n}\|)\]  
\[\text{s.t.}\quad\|\mathcal{N}\|=m \tag{4}\]  
In the above optimization problem, the first term maximizes the overall path diversity in the overlay network. The second term introduces the number of underlying links to promote sparsity in the selected nodes. \(\alpha\) is the coefficient of \(\|U_{n}\|\), which determines the weight of link utilization and path diversity in the objective function. The constraint (4) limits the number of overlay nodes. In practice, the locations of some service-providing nodes, such as data centers, are predetermined. In such cases, the positions of the rest nodes are calculated based on fixed location of predetermined nodes in the optimization problem. The problem can be reduced to the Maximum Coverage Problem [29], which has been proven to be NP-hard. To obtain a near-optimal solution in a reasonable time frame, this study adopts a genetic algorithm [30] to solve the above problem. In each generation, the next population is obtained through crossover and mutation, ultimately resulting in an optimal combination of overlay nodes. The complexity of this algorithm primarily depends on the population size \(P\), the overlay node number \(L\), and the number of generations \(G\). The overall time complexity is \(O(G\cdot P\cdot L)\) and the space complexity is \(O(P\cdot L)\). The overlay node placement problem discussed above aims to maximize overall benefit with a fixed number of nodes. In practice, however, there are scenarios in which the number of overlay nodes is chosen based on the average benefits of the overlay nodes or other specific optimization objective [9]. In the context of this study, the objective is to maximize the path diversity of overlay hop-by-hop multipath routing. Define the objective function  
\[F(\|\mathcal{N}\|)=\sum_{n\in\mathcal{N}}(d_{n}+\alpha\|U_{n}\|) \tag{5}\]  
In the MOP problem described above, once the number of overlay nodes \(m\) exceeds a certain threshold, additional nodes contribute only marginal improvements to multipath transmission performance. For both underlay link utilization and overall hop-by-hop path diversity, the marginal gains diminish as \(m\) increases, suggesting that the first derivatives of these metrics with respect to the number of overlay nodes exhibit convexity. However, when underlay link utilization and hop-by-hop path diversity are combined into a single objective function \(F(\|\mathcal{N}\|)\), differences in their respective growth behaviors may lead to the presence of local optima. To assess the effectiveness of increasing the number of overlay nodes, we define the optimal number as the smallest value of \(m\) for which the marginal improvement falls below a predefined threshold \(\epsilon\), i.e.,  
\[\frac{dF(m)}{dm}>\epsilon. \tag{6}\]Given that the selection of \(\mathcal{N}\) is topology-dependent and cannot be expressed analytically, the optimal number of overlay nodes is determined via a search-based method. Let \(i\) denote the step size for incrementing the number of overlay nodes.