# Safe Approximation--An Efficient Solution for a Hard Routing Problem
## 4 Simulation Experiments  
We have carried out simulation experiments to demonstrate how our approach performs in practice. Below we summarize the experimental results. The calculation of the safety margin \(\rho\) for the edges is based on formula (1). Note that the safety margin is determined by the number of edges and the edge capacities, and the meaning of the safety margin is the fraction of the maximum edge capacity that can be used by our algorithm. This is shown in Table 2, for edge numbers running from 20 through 800,and with edge capacities 1000 and 2000. For example, the second line in the table shows that for 20 edges and capacities of 2000 units the resulting safety margin is 0.926 (92.6%), which allows the usage of 1852 units of capacity, out of 2000 units. The content of Table 2 is represented graphically in Figure 1.  
In our simulation experiments, the number of nodes ranges from \(5\) to 40, while the number of edges ranges from 7 through 62. The actual graph (network topology) is chosen randomly. An example is shown in Figure 2. For each number of edges we ran the simulation with two different edge capacities: \(C=1000\) and \(C=2000\) units. As the safety margin increases with higher capacities, the network can be better utilized, since the safety margin determines what percentage of the maximum capacity is utilized. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**No. of Edges \(m\)** & \begin{tabular}{c} **Capacity of** \\ **Edges** \\ \end{tabular} & \
\begin{tabular}{c} **Safety Margin** \\ **for Edges** \\ \end{tabular} &
\begin{tabular}{c} **Capacity Constraints** \\ \end{tabular} \\ \hline
20 & 1000 & 0.896 & 896 \\
20 & 2000 & 0.926 & 1852 \\
200 & 1000 & 0.867 & 867 \\
200 & 2000 & 0.906 & 1812 \\
400 & 1000 & 0.86 & 860 \\
400 & 2000 & 0.901 & 1802 \\
600 & 1000 & 0.856 & 856 \\
600 & 2000 & 0.898 & 1796 \\
800 & 1000 & 0.853 & 853 \\
800 & 2000 & 0.896 & 1792 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Capacity constraints of edges with different safety margin. Figure 1: Safety margin and capacity constraints for edges. We ran the simulation with two different traffic types (two commodities in the multi-commodity flow); they represent two source-terminal pairs, which were chosen randomly. Furthermore, the number of nodes and edges were varied: the nodes between 5 and 40, the edges between 7 and 62. The results are shown in Table 3. The table contains that for various numbers of nodes and edges, how many iterations were needed to find the optimum, and what was the optimum objective function value in terms of total carried traffic. The same results are represented graphically in Figure 3. The results allowed us to make some observations:  
* As the number of nodes and edges increase, that is, the network becomes larger, the algorithm tends to require more iterations to find the optimum, which, of course, is not surprising. * By setting the repetition parameter to \(r=8\), the algorithm returned an optimal solution in 100% of the cases, which is very encouraging. It shows that one does not need an astronomical number of iterations to guarantee the optimum. * In some cases (actually 25% the of all cases we tried) already the first iteration achieved the optimum. Furthermore, in 75% of cases at most 5 iterations were sufficient to reach the optimum, and we never needed more than 8. Of course, these are relatively small examples, but it reinforces the observation that a limited number of iterations suffice. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**No. of Nodes \(n\)** & **No. of Edges \(m\)** & **Solved in Iteration \(r\)** & **Optimal Objective** \\ \hline
5 & 7 & 2 & \(550\times 10^{3}\) \\
10 & 15 & 1 & \(1.100\times 10^{3}\) \\
15 & 22 & 1 & \(1.650\times 10^{3}\) \\
20 & 30 & 4 & \(2.200\times 10^{3}\) \\
25 & 39 & 5 & \(2.750\times 10^{3}\) \\
30 & 46 & 5 & \(3.300\times 10^{3}\) \\
35 & 54 & 6 & \(3.850\times 10^{3}\) \\
40 & 62 & 8 & \(4.400\times 10^{3}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Simulation results.