# Dynamic SDN Controller Load Balancing
## 5 DCC Two Phase Algorithm
### Phase 2: Decreasing Load Differences Using a Replacement Rule  
In the second phase, we apply the coalition game theory [28]. We can define a rule to transfer participants from one coalition to another. The outcome of the initial clustering process is a partition denoted \(\Theta\) defined on a set \(C\) that divides \(C\) into \(K\) clusters with \(M/K\) controllers for each cluster. Each controller is associated with one cluster. Hence, the controllers that are connected to the same cluster can be considered participants in a given coalition. We now leverage the coalition game-theory in order to minimize the load differences between clusters or to improve it if an initial load balancing clustering has been performed such as in Section 5.1.2. A coalition structure is defined by a sequence \(B=\left\{B_{1},B_{2},\ \ldots,\ B_{l}\right\}\) where each \(B_{i}\) is a coalition. In general, a coalition game is defined by the triplet \(\left(N,v,B\right)\), where \(v\) is a characteristic function, \(N\) are the elements to be grouped and \(B\) is a coalition structure that partitions the \(N\) elements [28]. In our problem, the \(M\) controllers are the elements, \(G\) is the coalition structure, where each group of controllers \(G_{i}\) is a coalition. Therefore, in our problem we can define the coalition game by the triplet \(\left(M,v,G\right)\) where \(v=\varsigma\left(t\right)\). The second phase can be considered as a coalition formation game. In a coalition formation game each element can change its coalition providing this can increase its benefit as we will define in the following. For this purpose, we define the Replacement Value \(\left(RV\right)\) as follows:  
\[RV(C_{i},C_{j},a,b,Cnt)=\left\{ \begin{array}{c}0\\ 0\end{array}\begin{array}{c}n(t)_{new}\geq Cnt\\ \text{\emph{belowAverage} is true}\\ \text{\emph{aboveAverage} is true}\end{array} \right\} \tag{14}\]  
where \(sum_{new}=\vartheta(t)_{a^{new}}+\vartheta(t)_{new}\) and \(sum_{old}=\vartheta(t)_{a^{old}}+\vartheta(t)_{b^{old}}\). \(belowAverage\) is true where \((\vartheta(t)_{a^{old}}\leq Avg)\delta(\vartheta(t)_{b^{old}}\leq Avg)\) and \(aboveAverage\) is true where \((\vartheta(t)_{a^{old}}\geq Avg)\delta(\vartheta(t)_{b^{old}}\geq Avg)\). Each replacement involves two controllers \(C_{i}\) and \(C_{j}\) with loads \(Cl\left(t\right)_{i}\) and \(l\left(t\right)_{j}\), respectively, and two clusters \(a\) and \(b\) with loads \(L_{a}\) and \(L_{b}\), respectively. We use the notations \"_old_\" and \"_new_\" to indicate a value before and after the replacement. When \(n\left(t\right)_{new}\geq Cnt\) (see Equations (7) and (8)), the controllers, after the replacement, are organized into clusters such that the maximum distance between controllers within a particular cluster exceeds the distance constraint \(Cnt\). In this case, the value of the \(RV\) is set to zero, because the replacement is not relevant at all. When \((\vartheta(t)_{a^{old}}\leq Avg)\delta(\vartheta(t)_{b^{old}}\leq Avg)\) or \((\vartheta(t)_{a^{old}}\geq Avg)\delta(\vartheta(t)_{b^{old}}\geq Avg)\) (see Equations (4) and (5)), \(\varsigma(t)_{old}=\varsigma(t)_{new}\) (see Equation (6)). When one of the cluster's load moves to another side of the global average then we have \(\varsigma\left(t\right)_{new}\geq\varsigma\left(t\right)_{old}\). With both options, \(\varsigma\left(t\right)_{old}\) do not improve and therefore the \(RV\) is set to zero. Figures 3 and 4 provide an illustration of these two options. The dotted line denotes the average of all clusters. In Figure 3, the sum of the loads' distances from the global average, before the replacement is \(x+y\). After the replacement the  
In Equation (14), if none of the first three conditions are met, \(RV\) is calculated by \(\left(\phi\left(t\right)_{a^{new}}+\phi\left(t\right)_{b^{new}}\right)-\ \left(\phi\left(t \right)_{a^{old}}+\phi\left(t\right)_{b^{old}}\right)\), a value that can be greater than or less than zero. Using the \(RV\), we define the following \"\(ReplacementRule\)\":  
**Definition 1**.