## 3 Methodology  
### Algorithms Used for Optimal Controller Placement  
Determining how many controllers to have and where to place them in the network for optimum performance is one of the primary issues in SDN [28]. K-means++ [29] and OPTICS [30] were implemented to achieve optimal controller placement. K-means++ is an improved version of the K-means algorithm. Despite both solving a clustering problem, K-means++ offers an additional edge by making an informed initialization of initial centroids (making use of the Euclidean distance metric for centroid selection), yielding better clustering results. K-means randomly places k centroids (one for each cluster), so there is a probability of bad initialization, leading to a bad clustering result. K-means++ overcomes this initialization problem [28]. For K-means++, the number of clusters (k) and number of data points are provided as input, and for the output, it returns clusters with minimum loss for the given data points. We have used the Elbow method for the identification of an optimal number of clusters. The details of its implementation are discussed in Section 4.1. Similarly, OPTICS is an improved version of the density-based spatial clustering of applications with noise (DBSCAN) algorithm [31] used to obtain density based clusters [32] in spatial data. A density-based cluster means clustering data points on the basis of a region of high density or low density. Clusters can be arbitrarily shaped in data space [33]. [PERSON] et al. [30] put forth an OPTICS-based cluster analysis technique. Unlike K-means++, for the input field, it does not require an initial number of clusters; instead, it needs a number of data points and two hyper-parameters--namely, \(eps\) = maximum set neighborhood distance and \(minpts\) = minimum number of points to be classified as a dense region--to be provided. Figure 1 summarizes the process of determining the optimal controller placement. First, two GML files representing the topologies, Aarnet and Savvis, were downloaded from the Internet Topology Zoo [34]. From the files, the relevant parameters (Latitude, Longitude for the nodes and LinkLabel for the bandwidth of edges) were extracted. After this, using Haversine distance (Equation (2)) and latency (Equation (1)) metrics, Algorithm 1 was implemented, which tested each topology by two methods, namely, Kmeans++ and OPTICS. The WCSS losses from each method were compared, and the output from the method which yielded a lower WCSS loss was implemented for the implementation of the network containing optimally placed controllers, switches and hosts. ```
1:GraphG(V,E), radius = 6371 km //* Graph without controllers, where G = graph, V = set of vertices and E = set of edges */ //* For calculation of proximity between any two nodes, Equations (1) and (2) are used. */ //* GetNeighbors(v, Graph(vertex,edges)) returns all the vertices connected to v */
2:L1 \(\leftarrow\) 0, L2 \(\leftarrow\) 0 \(\triangleright\) L1 = WCSS loss using OPTICS, L2 = WCSS loss using K-means++
3:G1(V,E), C1(V) \(\leftarrow\) OPTICS(G(V,E), d) \(\triangleright\) G1(V,E) = Graph with controller placement using OPTICS, C1(V) = list of controller vertices from OPTICS
4:G2(V,E), C2(V) \(\leftarrow\) Kmeans++(G(V,E), d) \(\triangleright\) G2(V,E) = Graph with controller placement using K-means++, C2(V) = list of controller vertices from K-means++
5:for each v \(\in\) C1(V) do
6:U \(\leftarrow\) GetNeighbors(v,G1(V,E))
7:foreach u \(\in\) U do
8:L1 \(\leftarrow\) L1+d(u,v)
9:endfor
10:endfor
11:foreach v \(\in\) C2(V) do
12:U \(\leftarrow\) GetNeighbors(v,G2(V,E))
13:foreach u \(\in\) Udo
14:L2 \(\leftarrow\) L2+d(u,v)
15:endfor
16:ifL1+L2 then
17:G(V,E) \(\leftarrow\) G1(V,E)
18:L \(\leftarrow\) L1
19:else
20:G(V,E) \(\leftarrow\) G2(V,E)
21:L \(\leftarrow\) L2 \(\triangleright\) L = Minimum WCSS loss value
22:endif
23:return \(L,G(V,E)\)
```  
**Algorithm 1** Controller Placement Algorithm.