# Hop-by-Hop Multipath Overlay Routing for Optimizing Network Resource Allocation in WANs
## 4 Performance Evaluation
### Overlay Node Placement Algorithm  
Figures 7-10 show the performance of path diversity and underlay link utilization under different numbers of overlay nodes for the topologies of Table 3. The upper and lower bounds of the error bars represent the maximum and minimum values of the results, respectively. In different topologies, MOP outperforms TAO in both link utilization and overall path diversity. In topologies with fewer routers, such as Germany50 (Figure 7a) and ta2 (Figure 8a), the link utilization of these two algorithms differs significantly, whereas in topologies with more routers, like Abovenet (Figure 9a) and Generate Graph (Figure 10a), the gap in link utilization is stable. In terms of diversity, the performance of MOP and TAO is close in fewer overlay nodes. As the number of overlay nodes increases, the performance in diversity is related to the characteristics of the topologies. For ta2 (Figure 8b) and Abovenet (Figure 9b), the diversity of MOP gradually increases and becomes more than twice that of TAO, while the outcome of TAO even shows a decreasing trend with the increase in overlay nodes. For Germany50 (Figure 7b) and the generated graph (Figure 10b), the gap between the two algorithms in terms of diversity does not increase significantly with the number of overlay nodes. Figures 11-14 illustrate the number of paths in the underlay and overlay layers for different numbers of overlay nodes in the topologies of Table 3. The upper and lower bounds of the error bars in the figure represent the maximum and minimum average end-to-end path counts, respectively. The experimental results show that the existing hop-by-hop multipath routing algorithms combined with the proposed node placement algorithm MOP achieve higher numbers of average underlay and overlay paths. In the figures, the trends of the underlay average path number and overlay average path number with respect to the number of overlay nodes are generally similar. The underlay average paths are less than the overlay average paths, due to the overlap of underlay links among overlay paths. In Figure 11, the path number first increases and then decreases. This is mainly due to the limited number of routers. When the number of overlay nodes approaches the number of routers, there is a reduction in the number of neighboring nodes for each router, leading to a decrease in next-hop choices. As shown in Figure 7(a), when the number of nodes exceeds 15, the increase in link utilization slows significantly, indicating that adding more overlay nodes has a diminishing effect on improving link utilization. Correspondingly, in Figure 10(b), it can be observed that the underlay end-to-end path number decreases as the number of overlay nodes exceeds 15. Additionally, from Figure 7(b), when the number of overlay nodes exceeds 25, the growth rate of diversity gradually slows, suggesting that the addition of more overlay nodes does not contribute significantly to diversity. Similarly, in Figure 10(b), when the number of overlay nodes exceeds 25, the overlay average path number begins to decrease instead of continuing to increase. In Figures 11 and 12, the hop-by-hop multipath algorithm corresponding to TAO shows a decrease in path number as the number of overlay nodes increases, while the hop-by-hop multipath algorithm corresponding to MOP maintains an increase in path number with the growth of overlay nodes. This indicates that MOP can effectively leverage node selection to fully exploit the path diversity of the hop-by-hop multipath routing. In Figure 14, the underlay average path number and overlay average path number are the closest in different numbers of overlay nodes, indicating that the overlap of underlay links in overlay paths is relatively low. Figure 10: Link utilization and path diversity vs. overlay nodes in generated graph. Figure 11: Underlay and overlay average path number vs. overlay nodes in Germany50. Figure 12: Underlay and overlay average path number vs. overlay nodes in TA2.