Page 66 - ITUJournal Future and evolving technologies Volume 2 (2021), Issue 1

ITU Journal on Future and Evolving Technologies, Volume 2 (2021), Issue 1

Algorithm 1 Silhouette Analysis
Require: ( , , ), , ,
1: ← ( , , ). ()
2: ← 2
3: for ← 2 do
4: ← . ( ( , , ), , , )
5: for ∈ ( , , ) do
6: ← . ( )/
7: ← . ( . )
8: ← . ( )
9: ← . ( )/
10: end for
11: ℎ ← ( − )/ ( , )
12: end for

described in Section 4.3.2 [33]. The Harvesine distance range of [‑1,1]. Therefore a value closer to +1 is preferred
approach was used to compute the great circle distances as it indicates better cluster con iguration.
between pairs of switches [34]. The great circle distance
is the shortest distance between two locations on a 4.2.2 Gap statistics
sphere, measured along the surface of the sphere (as
opposed to the ordinary Euclidean distance)[35] [36] . Similar to Silhouette Analysis, Gap Statistics is a partition
An alternative method to compute geographic distances algorithm typically used in neural networks, to measure
is the Law of Cosines, which is optimal for shorter the quality of clustering measure based on average
distances and is not as accurate for longer distances intra‑cluster variation [38] [30]. We adopt and enhance
[37]. To compute the great circle distance, Eq. (2) which this algorithm to verify the results from our Silhouette
de ines the Harvesine approach is used, where and 2 Analysis. Therefore our goal is to determine the optimal
1
are the latitudes of points 1 and 2 respectively, and number of SDN controllers to deploy given a network
1
is the longitudes of point 1 and 2 respectively and topology, and compare the outcome of the simulation
2
denotes the radius of the earth, a constant equal to 6371 with the results from the Silhouette Analysis.
km.
The Gap Statistics algorithm constitutes the following
steps (enumerated by instructions from 1 to 12 in
= 2( ) 2 2 − 1 + ( 1 ) ( 2 ) 2 2 − 1 (2)
2 2 Algorithm 2): First the network topology is partitioned
(using the PAM algorithm), by varying the number of
controllers (which corresponds to the number of
The procedure to compute the optimal number of
controllers using Silhouette (with steps/instructions clusters) from 2 to the maximum user‑de ined value
enumerated from 1 to 12 in Algorithm 1) is as follows: (Instruction 3).
First, a cluster model is created from input network Algorithm 2 Gap Statistics
data using PAM and Harvesine approach (Instruction Require: ( , , ), , ,
4). Next, the average propagation latency from each ,
switch to its cluster centroid is calculated (Instruction 1: ← [ ] {Intialize empty array}
6), to ind the intra‑cluster propagation latency 2: ← 2
variation (intraClustVar). To this end, a model from 3: for ← 2 do
the centroids is created (Instruction 7). Next, the average 4: ← ( ( , , ),
propagation latency between each centroid to the global , )
centre (Instruction 8‑9) is calculated. In this way we 5: for ∈ do
obtain the inter‑cluster propagation latency variation 6: ← ( ( , , )
(interClustVar). The last step is to calculate the silhouette 7: ← ( , )
coef icient (Instruction 11). This procedure is repeated
as speci ied by the maxNumControllers input parameter 8: ← ( −
in order to calculate the silhouette coef icient for each )
number of controllers. Moreover, for each number of
9: end for
controllers (Instruction 3), the number of iterations was
10: ← ( , , )

set to 20 to maximize accuracy of the results.
11: return ← . {Take maximum gap
value}
The optimal number of controllers is one that yields the
maximum silhouette coef icient. This coef icient has a 12: end for

50 © International Telecommunication Union, 2021