# Dynamic SDN Controller Load Balancing
## 5 DCC Two Phase Algorithm
### Optimality Analysis  
In this section, our aim is to prove how close our algorithm is to the optimum. Because the capacity of controllers is identical, the minimal difference between clusters is achieved when the controllers' loads are equally distributed among the clusters, where the clusters' loads are equal to the global average, namely \(\varsigma\left(t\right)=0\). Since in the second phase, i.e., in the replacements, the DCC full algorithm is the one that sets the final partition and therefore determines the optimality, it is enough to provide proof of this.  
As mentioned before, the replacement process is finished when all \(RV^{\prime}s\) are 0, at which time any replacement of any two controllers will not improve the result. Figure 5 shows the situation for each of the two clusters at the end of the algorithm.  
For each two clusters, where the load of one cluster is above the general average and the load of the second cluster is below the general average, the following formula holds:  
\[\vartheta(t)_{a}+\vartheta(t)_{b}=L_{a}-L_{b}\leq l(t)_{i}-l(t)_{j}\forall c _{i}\in a,c_{j}\in b \tag{15}\]  
We begin by considering the most loaded cluster and the most under-loaded cluster. When the cluster size is \(g\), we define \(X_{1}\) to contain the lowest \(g/2\) controllers, and \(X_{2}\) to contain the next lowest \(g/2\) controllers. In the same way, we define \(Y_{1}\) to contain the highest \(g/2\) controllers and \(Y_{2}\) to contain the next highest \(g/2\) controllers.  
In the worst case, the upper cluster has the controllers from the \(Y_{1}\) group and the lower cluster has the controllers from the \(X_{1}\) group. Since the loads of the clusters are balanced, one half of the controllers in the upper cluster are from \(X_{1}\), and the other half of controllers in the lower cluster are controllers from \(Y_{1}\).  
According to Formula (15), we can take the lowest difference between a controller in the upper cluster and a controller in the lower cluster to obtain a bound on the sum of the distance of loads of these two clusters from the overall average. The sum of distances from the overall average of these two clusters is equal to or smaller than the difference between the two controllers, i.e., between the one with the lowest load of the \(g\) most loaded controller and the one with the highest load of the \(g\) lowest controllers.  
\[\vartheta\left(t\right)_{most\_loaded}+\ \vartheta\left(t\right)_{most\_ under\_loaded}\leq l\left(t\right)_{g\_th\_bigger}-l\left(t\right)_{g\_th\_smaller} \tag{16}\]  
The bound derived in (Equation (16)) is for the two most distant clusters. Since a bound for the whole network (i.e., for all the clusters is needed) we just have to multiply this bound by the number of cluster pairs we have in the network. There are k clusters in the networks so \(k/2\) pairs of clusters, therefore the bound in (Equation (16)) is multiplied by \(K/2\) in order to determine a bound. However,  
Figure 5: The loads of each of the two clusters at the end of all replacements.  
to obtain a more stringent bound, we can consider bounds of other cluster pairs, and summarize all bounds as follows:  
\[differenceBound\leq\sum_{i=1}^{\frac{M}{2g}}\left(sortList_{(M-ig)}-sortList_{ig}\right) \tag{17}\]  
The \(sortList\) indicates the load list of the controllers sorted in ascending order, \(M\). In Table 3 we show a summary of the time complexity of each of the algorithms we developed in this paper. Explanation on how each time complexity has been derived can be found in the corresponding sections.