# Trade-offs between Risk and Operational Cost in SDN Failure Recovery Plan
## 4 Suboptimal Algorithms
### Lagrangian Relaxation Method  
The Lagrangian Relaxation (LR) method [33] can be used to solve P4, which is presented in Algorithm 2. The LR method imposes a penalty on a violation of inequality constraints and includes that penalty in the cost function of the optimization. The result is an approximate solution to the original problem. ```
Input: Path \(R\) Initialize \(\tau\), \(\varepsilon\) and \(R_{f}=R\). Let \(R_{c}\) be the lowest-risk path. loop Find path \(R\) with lowest cost with: \(c_{i,j}=f_{i,j}-\frac{\mathcal{Q}\left(R_{c}\right)-\mathcal{Q}\left(R_{c} \right)}{\beta\left(R_{c}\right)-\beta\left(R_{f}\right)}\log\left(1-p_{ij}\right)\) if\(|\theta(R)-\theta(R_{f})|<\epsilon\)then return\(R_{f}\) elseif\(\theta(R)\leq\tau\)then \(R_{f}=R\) else \(R_{c}=R\) endif endloop
```  
**Algorithm 2**Lagrangian relaxation method, suboptimal solution to P4. In the following, we present our simulation results in order to evaluate the performance of the proposed algorithms. To this end, we consider ERnet. We assume that a flow exists between every pair \(v_{i}\), \(v_{j}\), where \(ij\in\{1,\ldots,N\}\), \(i\
eq j\). Figure 8 shows the average operational cost of IRR, LR and Dijkstra's algorithms versus the risk threshold for ERnet. As expected, [PERSON]'s algorithm has the highest average operational cost, as it tries to minimize the risk at the price of increasing the path cost. It could be seen that after using IRR and LR algorithms, at the first section of the curves (\(\tau<0.5\)), the found paths have very low operational cost, and after that, the operational cost of the path increases with the risk bound. This phenomenon may be explained by the fact that no path can be established for all source-destination pairings with a low-risk threshold, and since the detected paths are short, their operational costs are similarly minimal. The algorithms find more and more (longer) pathways as the risk bound rises, increasing the average operational cost of the paths. The average operational cost of the paths will drop with the risk bound once a path can be established for every source-destination combination since the algorithms can find paths with lower operational costs and higher risk limits. Additionally, IRR and LR choose a path with a better probability of survivability while having a lower operational cost, which results in a different (average) operational cost than [PERSON]'s algorithm. IRR and LR both provide fairly similar average operational costs, and the large increase above the average operational cost produced by [PERSON]'s algorithm is never greater than 4. This suggests that switching from [PERSON]'s algorithm to the proposed methods has a minimal impact on operational costs. These findings point to a hybrid approach that employs IRR or LR only when the risk threshold is below a certain level. For example, a general rule in ERnet is to use [PERSON]'s algorithm for flow restoration when the risk threshold is extremely close to zero, which indicates that the network is very high risk. As a result, because [PERSON]'s method has the lowest computational complexity, the average processing time will also drop. Additionally, we see that IRR and LR regularly deliver a solution that is close to ideal and can reduce operational costs by up to 50%. Figure 9 shows the number of restored flows against the risk threshold. The majority of flows occur in low-risk areas when the risk threshold is high because the network is inherently safer. SDN can readily identify pathways with lower operational costs and better survivability probabilities. Thus, the number of restored flows is visible (the option for SDN to reroute high-risk flows). In other words, since all flows are risky, the operating cost is highest near zero, and the number of restored flows is minimal. Therefore, when the network is going to be riskier, it may be optimized with IRR or LR algorithms as the number of restored flows grows by decreasing the operational cost.