# Dynamic SDN Controller Load Balancing
## 5 DCC Two Phase Algorithm
### Phase 1: Initial Clustering
#### 5.1.1 Initial Clustering with the Distance Constraint  
Most of the control messages concerning the cluster load balancing operation are generated due to the communication between the controllers and their MC. Thus, we use the \(K\)-Center problem solution to find the closer MC [27; 30]. In this problem, \(C=\{C_{1},C_{2},...,\ C_{K}\}\) is the center's set and \(P=\{P_{1},P_{2},...,\ P_{M}\}\) contains \(M\) controllers. We define \(P_{C}=\left(d\left(p_{1},C\right),d\left(p_{2},C\right),\ldots,d\left(p_{M},C \right)\right)\), where the \(i\)th coordinate of \(P_{C}\) is the distance of \(p_{i}\) to its closest center in \(C\). The \(k\)-Center inputs are: a set \(P\) of M points and an integer number \(K\), where \(M\in N\), \(K<M\). The goal is to find a set of \(k\) points \(C\subseteq P\) such that the maximum distance between a point in \(P\) and its closest point in \(C\) is minimized. The network is a complete graph, and the distance definition [see Table 2] satisfies the triangle inequality. Thus, we can use an approximate solution to the \(k\)-Center problem to find MCs. Given a set of centers, \(C\), the \(k\)-center clustering price of \(P\) by \(C\) is \(\|P_{C}\|_{\infty}=max_{p\in P}d\left(p,C\right)\). Algorithm 1 is an algorithm similar to the one used in [31]. This algorithm computes a set of \(k\) centers, with a 2-approximation to the optimal \(k\)-center clustering of \(P\), i.e., \(\|P_{K}\|_{\infty}\leq 2 opt_{\infty}\left(P,K\right)\) with \(O(MK)\) time and \(O(M)\) space complexity [31]. In Line 2 the algorithm chooses a random controller as the first master. In Lines 4-6 the algorithm computes the distances of all other controllers from the masters chosen in the previous iteration. In each iteration, in line 9, another master is added to the collection, after calculating the controller located in the farthest radius of all controllers already included in the master group, in line 8. After \((K-1)\) iterations in line 11 the set of masters is ready. ```
0:\(P=\{p_{1},p_{2},...,p_{M}\}\) controllers set, controller-to-controller matrix distances
0:\(C=\{c_{1},c_{2},...,c_{K}\}\) masters set procedure:
1:\(C\leftarrow\emptyset\)
2:\(c_{1}\gets p_{i}\) // an arbitrary point \(p_{i}\) from
3:\(C\gets C\cup c_{1}\)
4:for\(i=1:K\)do
5:for all\(p\in P\)do
6:\(d_{i}[p]\gets min_{c\in C}\;\;d(p,c)\)
7:endfor
8:\(c_{i}\gets max_{p\in P}\;\;d_{i}[p]\)
9:\(C\gets C\cup c_{i}\)
10:endfor
11:return\(C\) // The master set
```  
**Algorithm 1** Find Masters by 2-Approximation Greedy k-Center Solution  
After Algorithm 1 finds \(K\) masters, we partition controllers between the masters by keeping the number of controllers in each group under \(M/K\) as illustrated in Heuristic 1. As depicted in Heuristic 1, lines 1-2 prepare set \(S\) that contains the list of controllers to assign. Lines 3-5 define the initial empty clusters with one master for each one. Lines 7-15 (while loop) are the candidate clusters which have less than \(M/K\) controllers, and each controller is assigned to the nearest master of these candidates. After the controllers are organized into clusters, we check the maximal distance between any two controllers in lines 16-19; this value is used for the \"\(maxDistance\)\" (that was used for Equation (8)). ```
0:\(C=\{c_{1},c_{2},...,c_{M}\}\) Controller list \(M=\{m_{1},m_{2},...,m_{k}\}\) masters list controller-to-controller matrix distances
0:\(CL=\{cl_{1},cl_{2},...,cl_{k}\}\) Clusters list, where \(CL_{i}=\{cl_{1},cl_{2},...,cl_{i(m/k)}\}\)\(maxDistance\)-maximum distance between controllers in a cluster.