# Rapid Restoration Techniques for Software-Defined Networks
## 3 Proposed Path Recovery Methods
### Community Detection-Based Approach
#### 3.2.1 CD Model  
The number of communities extracted by a community detection algorithm depends on the network topology structure and the parametrization of the community detection algorithm. We define the set of communities which partition the network graph as \(C\subseteq G\), where \(C=\{c_{i},c_{i+1},\ldots,c_{N}\}\), \(\forall 1\leqslant i\leqslant N\), and where \(N\) is the number of communities. Each individual community \(c_{i}\in C\) consists of a subset of the graph node-set and the graph edge-set:  
\[c_{i}=(V_{i},E_{i})\mid V_{i}\subseteq V\wedge E_{i}\subseteq E \tag{1}\]  
A path, \(P\), between a source and destination, which traverses \(K\) communities, starting at the source router, \(r_{1,c_{i}}\), ending at the destination router, \(r_{d,c_{d}}\), and passing through the intermediate nodes, \(r_{i,c_{j}}\) and \(r_{i+1,c_{j}}\), for \(c_{i},c_{j},c_{d}\in C\) is  
\[P=\{r_{1,c_{i}},\ldots r_{i,c_{j}},r_{i+1,c_{j}},\ldots r_{d,c_{d}}\} \tag{2}\]  
The set of learned communities is mutually exclusive. The intersection of the node-set of community \(c_{i}\) and community \(c_{j}\) is the empty set. The intersection of the edge-sets of these two communities is also the empty set,  
\[\forall c_{i},c_{j}\in C\mid c_{i}=(V_{i},E_{i})\ \wedge\ c_{j}=(V_{j},E_{j})\ \Rightarrow\ (V_{i}\cap V_{j}=\emptyset)\ \wedge\ (E_{i}\cap E_{j}=\emptyset) \tag{3}\]  
Figure 1: Illustration of community detection and graph partitioning process: A good solution (RHS) has a high number of links between members of the same community and a low number of links to other communities.  
A failed link, a 2-router sub-path, \(F_{CD}\), in \(P\) is  
\[F_{CD}=(r_{i,c_{i}},\ r_{i+1,c_{i}})\ |\ \exists c_{i}:c_{i}=(V_{i},E_{i})\wedge F _{CD}\in E_{i} \tag{4}\]  
This definition of \(F_{CD}\) considers only those cases where failed links are always of an intra-community type. In other words, we assume that consecutive routers in a path, for example \(r_{i}\) and \(r_{i+1}\), must be in the same community,  
\[\
exists F_{CD}=(r_{i,c_{1}},r_{i+1,c_{2}}),c_{1}=(V_{1},E_{1}),c_{2}=(V_{2},E_ {2})\ |\ c_{1}\
eq c_{2}\ \Rightarrow\ r_{i,c_{1}}\in V_{1}\ \wedge\ r_{i+1,c_{2}}\in V_{2} \tag{5}\]  
The set of all Dijkstra-based solutions for a given network topology \((V,E)\) is denoted  
\[\mathcal{P}_{Dset}=\{P\ |\ \forall\ r_{1},r_{d}\in V:P=D(\mathcal{P}_{r_{1},r_{ d}})\} \tag{6}\]  
where \(\mathcal{P}_{r_{1},r_{d}}\) represents the set of all possible paths between any two particular nodes, that is, \(r_{1}\) and \(r_{d}\). When we apply [PERSON]'s algorithm to \(G\), we denote the solution \(D_{g}\), and when it is applied to a community \(c\) the solution is denoted \(D_{c}\). The network's _diameter_ quantifies the length of the shortest path between the two most distant nodes. The shortest path between the two most distance nodes is called the longest-shortest path. The function \(L(\mathcal{P})\), takes a set of paths, \(\mathcal{P}\), as its argument, to determine the longest-shortest path.  
\[L(\mathcal{P}_{Dset})=x,\ \text{s.t.}\ x\in\mathcal{P}_{Dset}\wedge\forall y \in\mathcal{P}_{Dset}:len(y)\leqslant len(x) \tag{7}\]  
If there is more than one longest-shortest paths in \(\mathcal{P}_{Dset}\), we pick one randomly. The case of the longest-shortest path is of particular interest. It represents the worst case scenario in terms of the number of rules that need to be updated by the controller as a result of the need for modification.