## 4 Design of Proposed Scheme: FAPR
### Algorithms and Formulation
#### 4.5.4 Formulation of Backup Path Allocation  
As mentioned before, the FAPR scheme strives to assign the most appropriate path for each flow affected by link failures, in order to mitigate the probability of congestion or interruption after failure recovery. The problem of appropriately assigning backup paths can be seen as a backup path assignment problem, which has been detailed in Section 4.3.5. In this subsection, we try to formalize this issue.  
Firstly, we present the definitions of network congestion and flow interruption. If the remaining available bandwidth of the backup path is not sufficient to support the required bandwidth of a flow after failures, congestion will occur. Even in severe cases, the interruption of flows may happen, and the definition of flow interruption for a backup path is shown in Formula (1).  
\[\Gamma\Big{(}f_{ij}^{n}\Big{)}+\Gamma(F_{mn}^{o})+\sum_{n^{\prime}\
eq n}^{N}\Gamma \Big{(}f_{ij}^{n^{\prime}}\Big{)}\dot{n}_{mn}^{n^{\prime}}\leq\Gamma(e_{mn}), \forall e_{mn}\in b_{ij,f}^{n} \tag{1}\]  
Assume that the link \(e_{ij}\) fails, with a total of \(N\) flows being affected. Among all the affected flows, \(f_{ij}^{n}\) is the \(n\)-th flow passing by link \(e_{ij}\), and \(\Gamma\Big{(}f_{ij}^{n}\Big{)}\) represents the size of this flow, i.e., the bandwidth it requires. \(b_{ij,f}^{n}\) represents the backup path for the flow \(f_{ij}^{n}\), and \(e_{mn}\) represents any link of \(b_{ij,f}^{n}\). \(F_{mn}^{o}\) represents the set of flows transmitted normally on link \(e_{mn}\) before link failures, and \(\Gamma(F_{mn})\) represents the sum of the bandwidths required by these flows. \(\Gamma\Big{(}f_{ij}^{n^{\prime}}\Big{)}\) represents the bandwidth required by a single affected flow other than \(f_{ij}^{n}\), and \(i_{mn}\) is a binary quantity indicating whether a flow will pass through link \(e_{mn}\), with 1 indicating yes, and 0 indicating no. Therefore, \(\sum_{n^{\prime}\
eq n}^{N}\Gamma\left(f_{ij}^{n^{\prime}}\right)_{mn}^{n^{ \prime}}\) represents the sum of the bandwidths required by all the affected flows that pass through link \(e_{mn}\), excluding \(f_{ij}^{n}\). On the other hand, \(\Gamma(e_{mn})\) is the total bandwidth of link \(e_{mn}\). Thus, the sum of the three parts on the left-hand side of the inequality is the total bandwidth required by all flows passing through link \(e_{mn}\). When link \(e_{ij}\) fails, any link, \(e_{mn}\), of the backup path \(b_{ij,f}^{n}\) for any flow, \(f_{ij}^{n}\), must satisfy Formula (1). Otherwise, the link may face congestion due to insufficient bandwidth, and the flow \(f_{ij}^{n}\) might experience interruption.  
For each link, \(e_{ij}\), of the topology, we generate a set of backup paths, \(B_{ij}\). When the link \(e_{ij}\) fails and the \(n\)-th flow, \(f_{ij}^{n}\), on this link is affected, a backup path, \(b_{ij,f}^{n}\), is selected from \(B_{ij}\), and the chosen backup path should satisfy the following two objective functions.  
\[\min\left(\frac{\text{size}\Big{(}F_{ij}^{r}\Big{)}}{\text{size}\big{(}F_{ij} \big{)}}\right) \tag{2}\]  
\[\max\sum_{n}^{N}P\Big{(}b_{ij,f}^{n}\Big{)} \tag{3}\]  
In Formula (2), \(F_{ij}^{\prime}\) represents the set of flows that is interrupted after the failure recovery of link \(e_{ij}\). \(F_{ij}\) represents the set of flows on link \(e_{ij}\). The \(size(\ )\) function is used to find the size of the set. The objective of this formula is to minimize the flow interruption rate. In Formula (3), \(P(\ )\) represents the suitability, i.e., a matching degree between a flow and a backup path, with a value ranging from 0 to 1. The higher the extent to which this backup path satisfies the feature indicators of this flow, the higher is its suitability. The objective of this formula is to maximize the total suitability of the backup paths for all flows.