# Trade-offs between Risk and Operational Cost in SDN Failure Recovery Plan
## 2 System Model and Preliminaries  
We model a network as a set of \(N\) nodes, denoted by \(\{v_{i}\}_{i=1}^{N}\), which are connected by the set of edges \(E=\{e_{i,j}\}\) in which \(e_{i,j}\) connects the nodes \(v_{i}\) and \(v_{j}\). The parameter \(c_{i,j}\) denotes the cost of the link \(e_{i,j}\) and is always a positive number. We define the link cost as an additive metric which could be defined in any number of ways based on parameters such as link bandwidth, delay, hop count, etc., without loss of generality, we assume a traffic flow exists between each node pair \(s\) and \(t\), respectively, representing the source and destination of the traffic flow. Let \(R=\{r_{i,j}\}\) denote the path between the source-destination pair that is taken by the flow from \(s\) to \(t\), where:  
\[r_{i,j}=\left\{\begin{array}{rl}1&\text{the path traverses }e_{i,j}\\ &0\text{ otherwise}\end{array}\right. \tag{1}\]  
We assume that all the paths are simple and contain no cycle. Since the link costs \(\{c_{i,j}\}\) are assumed additive, the total cost of the path \(R\) is given by the sum of the costs of individual links along the path, i.e.,  
\[Total\ path\ Cost=\sum_{(i,j)}c_{i,j}\ r_{i,j} \tag{2}\]  
Let \(p_{i,j}\) denote the probability that link \(e_{i,j}\) fails. Thus, \(e_{i,j}\) survives with probability \(1-p_{i,j}\). We refer to the probability that path \(R=\{r_{i,j}\}\) survives as its survivability probability, which is denoted by \(\pi(R)\) or \(\pi(\{r_{i,j}\})\) and is given by  
\[\pi(R)=\pi(\{r_{i,j}\})\ \triangleq\ \prod_{(i,j)}\big{(}1-p_{i,j}\big{)}^{r_{ i,j}} \tag{3}\]  
We refer to the logarithm of the survivability probability of path \(R=\{r_{i,j}\}\) with a negative sign as its risk, which is denoted by \(\beta(R)\) or \(\beta(\{r_{i,j}\})\), and is given by  
\[\beta(R)=\beta(\{r_{i,j}\})\ \triangleq-\sum_{(i,j)}r_{i,j}\ \log(1-\ p_{i,j}) \tag{4}\]  
The risk function \(\beta(R)\) is non-negative, i.e., \(\beta(R)\geq 0\). In addition, the mapping from risk \(\beta(R)\) to the survivability probability \(\pi(R)\) is one-to-one, and the \(\beta(R)\) is a monotone decreasing function of \(\pi(R)\). Therefore, a lower Risk implies a higher survivability probability and vice versa.  
We categorize path \(R\) into one of the following groups:  
1. **High risk:** with \(\beta(R)>\tau\) or \(\pi(R)<e^{-\tau}\);
2. **Low risk:** with \(\beta(R)\leq\ \tau\) or \(\pi(R)\geq\ e^{-\tau}\);
3. **Low risk:** with \(\beta(R)\leq\tau\) or \(\pi(R)\geq\tau\);
4. **Low risk:** with \(\beta(R)\leq\tau\) or \(\pi(R)\geq\tau\);
5. **Low risk:** with \(\beta(R)\leq\tau\) or \(\pi(R)\geq\tau\);
6. **Low risk:** with \(\beta(R)\leq\tau\) or \(\pi  
where \(0\leq\tau\) is the risk threshold. If a flow path is in the high-risk category, then the flow needs to be rerouted to a new path, preferably in the low-risk category. If a low-risk backup path does not exist, the high-risk path may be rerouted to another high-risk path with a lower risk factor, i.e., \(\beta(\{x_{ij}\})<\beta(\{r_{ij}\})\).  
The link failure probabilities \(\{p_{ij}\}\) may change dynamically. This may occur, for example, because of a time-dependent large-scale failure, such as a natural disaster, which may increase the failure probability of some links or ongoing security attacks and similar reasons. In this work, we model link failures as link failure probability changes, i.e., a failed link has a failure probability of 1. As the link failure probabilities change, the path risk changes, and consequently, the previously assigned paths may become subject to a higher risk of failure. For the case of deterministic link failures, interested readers may refer to our previous work [10].