# Hop-by-Hop Multipath Overlay Routing for Optimizing Network Resource Allocation in WANs
## 4 Performance Evaluation
### Experiment Settings  
The simulation employs real-world topologies ta2 and germany50 from SNDlib [34], and Abovenet (AS6461) from Rockefuel [35]. Additionally, a large-scale topology (\(|V|=500\)) is randomly generated using the Erdos-Renyi model [36] for further validation. The topology information are demonstrated in Table 1. The cost of edges is calculated from the data set or is randomly generated. We first evaluate the overlay placement algorithm MOP. The purpose of MOP is to improve the performance of all-to-all multipath transmission, rather than focusing on specific demands. Therefore, we choose the node placement algorithm in the topology-aware network (TAO) [8], which also focuses on overall performance, as a comparison scheme. In the classic topology-aware network [8], the node placement algorithm targets the single-hop overlay routing scenario, with the goal of reducing path overlap. For the genetic algorithm that solves MOP, we choose a population size of 50, a genetic generation of 100 and a mutation rate of 0.1. The parameter \(\alpha\) in the optimization problem is chosen to be 0.2. The main performance metrics for comparison include hop-by-hop path diversity, underlay link utilization, and end-to-end path diversity. The evaluation is divided into three main parts. In the first step, we applied both algorithms to the topologies in Table 3 to evaluate the performance of path diversity and underlay link utilization. For different numbers of overlay nodes \(m\), we conducted 10 experiments and computed the average results. In the second step, we verify the relationship between node path diversity and end-to-end path diversity. The next-hop node set for each overlay node is calculated using the existing hop-by-hop multipath routing algorithm MARA and LFI. The average underlay path number and average overlay path number are chosen as the matrix of all-to-all end-to-end path diversity. The number of underlay paths reflects the number of end-to-end disjoint paths, while the number of overlay paths indicates the diversity of next-hop node selections of overlay nodes. Each set of experiments was repeated 10 times, and the results were averaged to obtain the mean value. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Topology** & \(|V|\) & \(|E|\) \\ \hline Germany50 & 50 & 88 \\ \hline TA2 & 65 & 108 \\ \hline Abovenet (AS6461) & 141 & 374 \\ \hline Generate Graph & 500 & 1262 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: The topologies of the experiment. In the third step, we evaluated the overlay node number selection method for the Germany50 and TA2 topologies. In the experiments, the objective function \(F\) was evaluated for varying numbers of overlay nodes using the MOP algorithm. The corresponding values of \(\beta\) for each number of overlay nodes are derived after performing MOP 10 times and averaging the outcomes. In the evaluation of the overlay multipath selection algorithm, we analyze the gains of ONHS under different congestion levels. The performance is evaluated under various numbers of overlay nodes on the topologies Germany50 and TA2 from Table 3. The next-hop sets for each overlay node are generated with existing hop-by-hop multipath routing algorithms MARA-MC. The level of network congestion is simulated by randomly selecting a subset of overlay tunnels. In each set of experiments, \(\gamma=10\%,20\%,30\%,40\%\) of overlay tunnels are randomly selected to simulate congestion. Each experiment is repeated 10 times. ONHS is employed on each congested topology and filters out invalid paths that cause congestion in multipath routing. The experiments validated the performance of the single-hop and multi-hop path selection algorithms by calculating the ratio of paths that were filtered out. The local single-hop algorithm is more direct than the multi-hop algorithm. Therefore, for the single-hop path selection algorithm, the ratio represents the proportion of valid single-hop paths to the total number of paths.