# Trade-offs between Risk and Operational Cost in SDN Failure Recovery Plan
## 3 Design Framework  
We wish to reroute an existing flow from path \(\{r_{i,j}\}\) with low survivability probability, i.e., with \(\pi(\{r_{i,j}\})<e^{-\tau}\), to path \(\{x_{i,j}\}\) with a higher survivability probability conditioned on the incurred operational cost not exceeding \(\eta\geq 0\), i.e., \(\sum_{(i,j)}f_{i,j}\ x_{ij}\leq\eta\). In other words, we wish to solve the following binary integer program:  
\[\text{PI}:\ \max_{k,\{x^{k}_{i,j}\}}\pi\Big{(}\Big{\{}x^{k}_{i,j}\Big{\}} \Big{)} \tag{9}\] \[\text{s.t. }\ \left\{ \begin{array}{c}\sum\limits_{j:(i,j)\in E}x^{k}_{i,j}-\sum\limits_{j:(j,i)\in E}x^{k}_{j,i}=b^{k}_{i}\,\ \forall i,k\\ \sum\limits_{(i,j),k}f^{k}_{i,j}x^{k}_{i,j}\ \leq\ \eta\end{array} \right.\]Problem P1 is equivalent to the following integer linear program:  
\[\text{P2}:\ \min\tau \tag{10}\]  
\[s.t.\ \left\{ \begin{array}{l}\beta\Big{(}\Big{\{}x_{i,j}^{k}\Big{\}}\Big{)}\ \leq\ \tau\,\ \forall k\\ \sum\limits_{j:(i,j)\in\ E}x_{i,j}^{k}-\sum\limits_{j:(j,j)\in\ E}x_{j,i}^{k} =b_{i}^{k}\,\ \forall i,k\\ \sum\limits_{(i,j),k}f_{ij}^{k}x_{i,j}^{k}\ \leq\ \eta\end{array} \right. \tag{11}\]  
Since the risk of a path is a monotone decreasing function of its survivability probability, the solution to P1 solves P2 and vice versa. Solving P1 or P2 for different values of \(\eta\) demonstrates the trade-off between the operational cost, path survivability probability, and path risk. In the following, we study an example to investigate these trade-offs. We use European Reference Network (ERnet), which is shown in Figure 2, with 37 nodes and 57 bidirectional links [10]. We used MATLAB/CPLEX for solving optimization problems. For the following examples, let us start with an initial fixed failure probability of \(\frac{1}{10}\) for each link. Now, suppose that the failure probabilities of the links in ERNET change due to a large-scale failure centered at Strasbouring (i.e., \(v_{12}\) in Figure 2), and as a result of this failure, any link whose end-nodes are within 500 km of this epicenter becomes affected. For this example, we use the exponential failure model of an Earthquake described in [26], where the link failure probability is given by \(\frac{1}{2}\frac{1}{5}^{500}\), in which \(r\) is the distance of the link center to the epicenter of the failure event. The link failure probability of the unaffected links will remain fixed at \(\frac{1}{10}\). In the first example, we assume that there is only one flow between nodes \(v_{10}\) and \(v_{15}\) to reroute. We assume that before the failure, this flow traversed a path with the lowest risk based on a prior link failure probability. To discover such a path, [PERSON]'s algorithm can be employed to find the shortest path between \(v_{10}\) and \(v_{15}\) for which the link costs are re-defined as \(c_{\ ij}=-\log(1-p_{ij})=-\log(1-\frac{1}{10})\). It can be easily verified that the original path in this example is given by \(R_{1}\): 10-12-14-15. After the disaster, \(R_{1}\) is no longer the lowest-risk path between \(v_{10}\) and \(v_{15}\) due to the change in failure probabilities. Given the prior and current failure probabilities, we observe that the survivability probability of \(R_{1}\) drops significantly from 0.9703 (considering the prior values of \(\{p_{ij}\}\)) to 0.5074 (considering the current values of \(\{p_{ij,j}\}\)). Now, we wish to reroute the initial flow \(R_{1}\): 10-12-14-15 to some paths with lower risks. Recall that such flow rerouting requires carrying out some flow operations hence a non-zero operational cost. Depending on the value of \(\eta\) in P1 or P2, different paths can be obtained. In this case, two different paths (denoted by \(R_{1}^{\prime}\) and \(R_{1}^{\prime\prime}\)) can be identified as the solutions to P1 or P2 for individual operational costs \(\eta_{i}\) of 3 and 4. The path survivability probabilities of \(R_{1}\), \(R_{1}^{\prime}\), and \(R_{1}^{\prime\prime}\) are 0.5074, 0.7502, and 0.8585, respectively.