# Rapid Restoration Techniques for Software-Defined Networks
## 5 Experimental Evaluation
### Performance Evaluation  
We considered the performance of recovery algorithms when link failures occurred on a range of different path lengths. In order to be able to draw conclusions from results for network topologies which had different sizes we normalised the path lengths. The length of the longest shortest path is identified for each experimental topology in Table 1 in the column entitled diameter. Each admissible path in \(\mathcal{P}_{r_{1},r_{d}}\) was classified based on its normalized length, for example, its length-percentage. Paths were categorised as having a length which varied from 20 to 100 percent of the longest shortest path length in the topology. This approach allowed us examine different categories of paths for different networks sizes. Having established a way to compare results across different networks we now outline the process of our evaluation in Procedure 1. Lines 2-4 of the below evaluation procedure describe how link failures are caused and resolved. Line 4 describes how path recovery is achieved using different approaches. Lines 5-7 describe how metrics are computed in order to evaluate each of the recovery approaches. **Procedure 1** Process of Evaluation  
1: Select paths with different lengths \(\triangleright\) ranging from 20-100% of the LS length  
2: For each selected path, choose a random link  
3: Remove the randomly chosen link  
4: Find the alternative path  
5: Measure the new path length cost  
6: Measure the new path operation cost  
7: Measure the new path latency cost  
14:15  
**Procedure 1** Process of Evaluation  
1: Select paths with different lengths \(\triangleright\) ranging from 20-100% of the LS length  
2: For each selected path, choose a random link  
3: Remove the randomly chosen link  
4: Find the alternative path  
5: Measure the new path length cost  
6: Measure the new path operation cost  
7: Measure the new path latency cost  
14:15  
**Procedure 1** and 15: 15: 15: 15: 15: 15: 15: 15:  
the relative increase in the cost was not significant, and never exceeded 11.2%. Algorithm 2 provided approximately the same performance as Algorithms 3 and 4. On average, the relative increase in the path cost never exceeded 11.2% in all of the experimental topologies except for Brite2. In Brite2 topology, the relative increase in the path cost was 50% in some cases. Further investigation was warranted to better understand the behaviour of Algorithm 2. To this end, an additional calculation was conducted in which the completion rate and modularity of each topology was measured. The completion rate is a binary score that measures the success and failure rates of path recovery algorithms. Modularity is defined as an indicator to measure the strength of partitioning the network graph into a number of communities. The modularity score measures the quality of graph partitions after the application of the community detection algorithm. The higher the modularity value the better the decomposition of network. The modularity of each network was measured using the approach in Reference [43]. To measure the completion rates, the success rate was defined as the percentage of successful events compared to the total number of paths in \(\mathcal{P}_{r_{1},r_{d}}\) whose length fell within the predefined range (i.e., 20-100). The failure rate was defined as the percentage of fail events compared to the total number of paths in \(\mathcal{P}_{r_{1},r_{d}}\) that satisfied the same range of length condition. The flowchart in Figure 7 illustrates how both successes and failures were calculated. All admissible paths that satisfied the length condition were considered in this evaluation. Starting with the first path, a random link failure was generated. After that, the state of the alternative path was checked by applying the _Algorithm_x_ function, where \(x\in\{2,3,4\}\). Setting \(x=2\) gave rise to Algorithm 2 being used. Every time _Algorithm_x_ succeeded in obtaining a solution, the success variable was incremented, otherwise the failure variable was incremented instead.