# Dynamic SDN Controller Load Balancing
## 2 Related Works
DCP-GK and DCP-SA are greedy algorithms for Dynamic Controller Placement (DCP) from [18], which employ for the reassignment phase, Greedy Knapsack (GK) and Simulated Annealing (SA) respectively, dynamically changing the number of controllers and their locations under different conditions, then, reassign switches to controllers. Contrary to the methods in [18; 20], the algorithm suggested by [21], called Switches Matching Transfer (SMT), takes into account the overhead derived from the switch-to-controller and controller-to-switch messages. This method achieves good results as shown in [21]. In the approaches mentioned earlier in this section, all the balancing work is performed in the SC, thus, the load on the super controller can cause a scalability problem. This motivated the architecture defined in [23] called \"Hybrid Flow\", where controllers are grouped into fixed clusters. In order to reduce the load on the SC, the reassignment process is performed by the controllers in each cluster, where the SC is used only to gather load data and send it to/from the controllers. \"Hybrid Flow\" suffers from long run time caused by the dependency that exists between the SC operation and other controllers operations. When the number of controllers or switches increases, the time required for the balancing operation increases as well. Table 1 summarizes the time complexity of the methods mentioned above. The running time of the central element algorithm defines the bound on the time-cycle length. Thus, the bigger the increase of the run time in the central element (i.e., causing a larger time cycle), the lower is the accuracy achieved in the load balancing operation. This is crucial in dynamic networks that need to react to frequent changes in loads [24]. In a previous work [25; 26], a new architecture called Dynamic Cluster Flow (DCF) [25] was presented. DCF facilitates a decrease in the running time of the balance algorithm. The DCF architecture partitions controllers into clusters. The architecture defines two levels of load balancing: A high level called \"_Clustering_\", and an operational level called \"_Reassignment_\". A super controller performs the \"_Clustering_\", by re-clustering the controllers in order to balance their global loads. The \"_Reassignment_\" level is under the responsibility of each cluster that balances the load between its controllers by reassigning switches according to their request rate. For communication between the two levels, each controller has a Cluster Vector (CV), which contains the addresses of all the controllers in its cluster. This CV, which is updated by the SC each time cycle, allows the two levels to run in different independent elements, where the \"_Clustering_\" operation runs at the start time of each unit. In [26] we presented a heuristic for the \"_Clustering_\" operation which balances between clusters according to the loads with a time complexity of \(O(M^{2})\), and suggest to use the method presented in [23] for the \"_Reassignment_\" level. In this initial architecture, the \"_Reassignment_\" level is not sufficiently flexible for various algorithms, which served as a motivation for us to extend it. In this paper, the target is to leverage previous work [25; 26] and achieve load balancing among controllers. This is done by taking into account: network scalability, algorithm flexibility, minor complexity, better optimization and overhead reduction. To achieve the above objectives, we use \begin{table}
\begin{tabular}{c c c c c} \hline
**Approach** & Balance Flow & SMT & DCP-Assignment Phase & Hybrid Flow \\ \hline
**Time Complexity** & \(O(max((N^{2})\cdot log(N^{2}),N^{2}\cdot M))\) & \(O(M\cdot N\cdot logN)\) & \(O(M\cdot N\cdot logN)\) & \(O(N\cdot M^{2})\) \\ \hline \end{tabular}
\end{table} 
Table 1: Time complexity comparison. the DCF architecture, and considered distance and load at the \"_Clustering_\" level that influence the overhead and response time at the \"_Reassignment_\" level, respectively.