A New Clustering Approach for Efficient Placement of Controllers in SDN using Firefly Algorithm

Subject Areas : International Journal of Smart Electrical Engineering

Azam  Amin ¹ (Department of Computer Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran)
Mohsen  Jahanshahi ² (Department of Computer Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran)
Mohammadreza  Meybodi ³ (Department of Computer Engineering and IT Amirkabir University of Technology, Tehran, Iran)

Received: 2021-08-02 Accepted : 2021-09-30 Published : 2021-09-01

Keywords:

Full-Text:



 

 

 

          

A New Clustering Approach for Efficient Placement of Controllers in SDN using Firefly Algorithm

 

Azam Amin1, Mohsen Jahanshahi1¹, Senior Member, IEEE, Mohammad Reza Meybodi2

1Department of Computer Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran

2Department of Computer Engineering and IT Amirkabir University of Technology, Tehran, Iran

[e-mail] , [e-mail], [e-mail]

       

 

Abstract

 In Software Defined Network (SDN), controller plane is separated from the data plane simplifying management. In these networks, data forwarding cannot be conducted just one controller. Therefore, it is needed to use multiple controllers in control plane. Since, switch-controller propagation delays and inter-controller latencies affect the performance, the problem of determining appropriate number of controllers as well as their suitable locations are two main challenges, which are known as NP-Hard. In this paper, a new clustering method based on K-means, K-Harmonics means and firefly algorithm named CPP-KKF is proposed for controller placement in SDN. Result obtained by CPP- KKF algorithm is benefitted by the advantages of all techniques. The proposed algorithm is evaluated on four topologies of TopologyZoo with different scales, that include Aarnet, Colt, Cognet, and DFN and the conducted simulations demonstrate that the proposed solution outperforms K-means, K-means++, Firefly and GSO algorithms in terms of aforementioned performance issues.

Keywords: Software Defined Network, Controller Placement Problem, K-harmonics Mean, K-Means, Firefly algorithm, Clustering Method

 

 

---

[1] * Corresponding author­­­­­­

 

1.       Introduction

Software Defined Network (SDN) is a new technology in computer network, in which data plane is separated from the control plane. In these networks, data forwarding cannot be conducted just one controller. Therefore, it is needed to use multiple controllers in control plane [1].

 

Switch-controller propagation delays and inter-controller latencies should be considered for a suitable placement of the controllers [2][3][4]. Load balancing problem between the controllers has investigated in some research works (e.g. [5]to [7]). Determining the appropriate number as well as location of controllers will affect network performance. Therefore, the researchers concentrate on how to properly discover place the controllers.

 Controller Placement Problem (CPP) is known to be NP-hard. Network partitioning technique is one of the most popular methods for overcoming this problem with dividing a large network to some sub-networks. Applying this method can lead to less delay between controller and switches. Further, in a formed subnetwork, other performance metrics such as load balancing and reliability are better managed. Utilizing partitioning network reduces complexity of controller placement problem [8].

The K-Means algorithm is one of the most popular data clustering algorithms due to its simplicity and speed of convergence. However, it suffers from two main disadvantages; first, sensitiveness to the initializations of the centroids and second, early convergence leading to local optima solutions. Clearly, for the first concern, if a “far-off” point is initialized as a centroid, the cluster might be formed with any points. Similarly, more than one point might be selected as a centroid in a cluster. To cope with the first issue, K-Means++ has been proposed to improve choosing centroids [9]. K-Harmonic Means (KHM) method has been proposed based on K-means as well. KHM considers harmonic mean distance instead of Euclidean distance [10]. However, both K-Means++ and KHM algorithms are getting stuck in local optima like original K-means. As for the second aforementioned issue, the Firefly algorithm (FA) as another stochastic technique has been presented to escape from local optima [26].

In this paper, we propose a new clustering method for partitioning a given network assigning a dedicated controller for each of which. We have considered switch-controller propagation delays and inter-controller latencies in this research. Clearly, we propose an algorithm based on K-means, KHM, and FA, which makes full use of their competences to determine appropriate placements of the controllers.

The rest of this paper is organized as follows: Sec. 2 reviews the state-of-the-art of controller placement in SDN-based networks. The basic concepts of K-means, KHM, and FA are presented in Sec. 3. Sec 4 dedicated to introduction of the proposed idea. Simulation results and performance analyses of the proposed solution are presented in Sec.5.

 

2.       Related Works

Inappropriate placement of controllers decreases network performance. Suitable number of the controllers is considered as an important issue as well. The aforementioned problems are known to be NP-Hard [11]. Most of the conducted researches just paid attention to delay between controller and switches in controller placement, while inter-controllers’ delay is also an important issue.

        Heuristic algorithms provide some solutions to overcome time complexity of the NP-Hard problem.

In [2], discrete Cuckoo Search Algorithm (CSA) was used to solve the placement problem. The simulation result shows that the proposed algorithm outperforms the methods based on Genetic Algorithm (GA) and Particle Swarm Optimization algorithm (PSO) in terms of delays. In [12], a PSO-based algorithm was proposed for this problem. The algorithm considered the inter-controllers’ latencies in addition to the delay of controller-switches. Two population-based exploration algorithms PSO and FA were used in [13]. The research proposed a  solution for appropriate locations of controllers by adopting a specific set of objective functions. These functions investigate inter-controller latencies in addition to the delay between controllers and switches. In different conditions, the result was demonstrated the FA-based algorithm performs better than PSO-based algorithm. Researches in [14], introduced an algorithm based on Genetic Algorithm named Controller Placement Genetic Algorithm (CPGA). In order to evaluate the performance of this idea, three important criteria namely latency, hop count,  and link utilization. However, in large-scale networks, the propagation delay as one of the key parameters should be taken into account. For example, if there are two paths with the similar number of intermediate node between a controller and its assigned switch, it chooses one of them without paying attention to the link utilization of each path and control traffic on the links . Finally, none of the above criteria is solely sufficient to optimize the CPP. That is why, in this reference, the proposed multi-criteria allocation approach performs better than just link load assignment. In [15], two algorithms based on PSO and Firefly were introduced, which are suitable for large networks. In this research, the delay between the controller and the switch has just been considered. The results demonstrated that the FA performs better than the another one. The genetic algorithm was used in [16] to consider the reduction of latency between controllers, load distribution, and the appropriate number of controllers. Finally, a novel swarm intelligence  based algorithm named GSO has been used for the problem in [29].

In the other hand, clustering is one of the suitable solutions to solve the NP-Hard problem, which many researchers paid attention to the following approaches.

Three clustering algorithms were considered according to spectral graph theory in [17]. Its first clustering algorithm is based on K-median; The controller closest to the switch has the least average propagation delay. This distance between the two nodes is the shortest. As another algorithm, the K-center based idea randomly selects the number of controllers as well as  clusters minimizing latency like the first algorithm. The purpose of this algorithm is to discover the number of controllers that can reduce the maximum latency between controllers and switches. The third proposed algorithm is based on spectral clustering. This method is suitable for weightless and undirected graphs. Finally, the results of this study showed that the spectral load clustering technique yields to balanced load. 

Researchers in [18] focused on two objectives of reducing delay and load balancing at the same time. The algorithm utilizes K-medoids clustering method to solve CPP that considers the capacity constraint. In the first step of the proposed algorithm, it allocates one part to the nodes and the other part to the controllers, and then, according to the distance matrix, connection between node are formed. If a node inside a given cluster reduces the sum of delays, in case of it has no impact on load balancing, then it can be a new center. This algorithm progresses until the best cluster centers and the best number of their associated nodes are specified. The main challenge of these multi-objective models is the lack of analysis for the assignment paths and its effective factors.

In order to improve the reliability and reduce delay in the existing multi-controller deployment scheme, MCEP4 algorithm was proposed in [19].

In this algorithm, first the problem of deploying multiple controllers has investigated based on spectral clustering. Then, the K-medoids algorithm based on Simulated Annealing was used to classify rows of vectors to achieve the flexible deployment of multiple controllers. 

In [20], an algorithm was proposed for CPP based on standard ­­­­for segmentation of the network to determine the cluster center. In this algorithm, distance between nodes is considered according to links in forming topology instead of Euclidean distance. This study assumes the controllers without capacity, and ignores the load balancing and delay between controllers and controllers.

In [21], authors proposed two clustering algorithms K-Center and K-medoids for controller’s placement in a software-based network, which adjust the location of the controller according to the distance of the controllers from each other and the distance between the controller and switches. However, the paper ignores the capacity parameter for controllers. 

Both of the switch-controller propagation delays and inter-controller latencies were also considered in [22] and this problem was solved using K–means and Dijkstra algorithms.

 

3.       Preliminaries: K-means, K-harmonics means and Firefly algorithms

In this section, we demonstrate standard K-means, K-harmonic means and Firefly algorithms with their associated pseudocodes.

3.1.                      K-means

K-means clustering is a partitioning technique for dividing a data set into k groups.  Here, initially, it is needed to determine the number of clusters and select the cluster centers from data set points and then, the algorithm goes on iteratively as follows [23]: It categorizes each point to its closest center and updates the center’s coordinates that is the average of the points categorized. 

K-means standard has two disadvantages, the first one is dependent on initial selected points and the another one is getting stuck in local optima [24].

 

 

Figure 1- pseudocode of K-means

3.2.                      K-harmonic means

In [10], authors proposed a new clustering method based on K-means. The algorithm uses harmonic means instead of the Euclidean distance, and named it K-Harmonic Means (KHM). It is introduced for solving the initialization problem of the KM algorithm.

KHM algorithm has an objective function that calculates the harmonic mean of the distance from each point to all centers. 

 

 

KHM(X,C)=           (1)

 

KHM investigates two functions soft membership and weigh as follows:

 

       (2)

 

 

  ()             (3)

 

 

 

 

 

 

Figure 2- - pseudocode of K-Harmonic means

 

 

The weight function investigates higher weight to data points that are far away from every center. In fact, it defines the impact of each data point on computing new components of cluster center. This algorithm has an input parameter  typically equal or greater than 2, used in KHM, membership, and weight functions [10][25].

 

3.3.                      Firefly Algorithm

Firefly Algorithm (FA) was proposed according to social behavior of fireflies. For simplicity in the algorithm, there are three idealized rules as follows: 1) all fireflies are unisex, so that attractiveness is considered regardless of their sex. 2) Brightness is introduced as an attractiveness parameter, thus between two fireflies, firefly fainter will move toward the brighter one. If a firefly does not find another brighter firefly, it will continuously move randomly. 3) objective function determines brightness parameter in this algorithm [26][27].

The basic steps of the algorithm are demonstrated as the pseudo code presented in fig. 3.

 

 

 

 

 

 

 

 

­­

 

Figure 3- pseudocode of firefly algorithm

             

                

4.       CPP-KKF: the proposed algorithm

The main network elements include controllers, switches and links. Therefore, it can be modeled by an undirected graph G =(V,E), where V is the set of switches and E is the set of links between the switches. Let n be the number of graph nodes or switches and K is the number of controllers in SDN and C={} be the set of controllers. we divide the network to some sub-networks, and we supposed to allocate a controller for any cluster.

The network partition can be defined by SDNi(Vi,Ei), subjects to:

 

 

 

 

 

S()=

 

S()=FALSE,

 

 

 

Eq. (4) demonstrates the network is covered by the total sub-networks. Eq. (5) indicates that one edge or vertex can be allocated to sub-network. Eq. (6) also means that same similarity is between elements of a sub-network. Eq. (7) implies that different similarity is between elements allocated to different sub-network; Eq. (8) demonstrates that all the vertexes in one sub-network are connected by edges. In this research, similarities are supposed to both of switch-controller propagation delays and inter-controller latencies. Total delay is referred to sum of both of delays. The main objectives can be defined as:

       (9)

 

           (10)

 

Total delay=+       (11)

 

In Eqs. 9 and 10, a and b are Integer coefficients, MPc is Minimum shortest path needed exchange control message.

In a clustering method for partitioning network, it is compulsory to compute the distance. Therefore, when there is a large scale network or nodes arranged in a scattered manner it is quite difficult to arrange them in a group and find the center of them. The main problem with mean based algorithm is that mean is highly affected by extreme values. For tackling the problem, we perform both of K-means and KHM. The idea of the new hybrid clustering algorithm is based on applying two techniques to find mean one by one until or unless our goal is met. The accuracy of result is much greater as compared to K-Means & KHM algorithms [28].

Standard K-means can overcome just to the first disadvantage by hybrid method KHM. As mentioned in sec. 3, the second disadvantage is getting stuck in local optima, therefore hybrid of both of K-means and KHM suffer from to get stuck in local trap too.

In CPP- KKF, we apply FA to cope with the local optima problem in which, function m in KHM is used as objective function. Therefore, result obtained by CPP- KKF algorithm is benefitted by the advantages of all techniques. Fig. 4 demonstrates the algorithm.

 

Figure 4-pseudocode of CPP-KKF

5.       Performance Analysis

   This section evaluates the performance of the CPP-KKF, standard K-means, K-means++, Firefly and GSO algorithms on 4 standard topologies with different scales from the Internet topology Zoo as described in Table1.

 

Table 1- The topology feature of the networks

Network Name	Georaphical Area	Network Location	Nodes number	Links Number
Aarnet[30]	state	Australia	19	24
DFN[31]	state	Germany	63	89
Colt[33]	continental	Western Europe	153	191
Cogent[33]	intercontinental	Europe-the USA	197	245

 

Nodes without information are omitted in this evaluation. For example, node 8 in the DFN has no coordinate in DFN dataset, hence it is not considered in this evaluation.

In the simulation initial parameters are defined as Table 2.

Table 2- Initial parameter

parameter	Initial value
a	1
b	1
p	3
Number of firefly movement	20
Number of iteration number	30

 

Where a and b parameters are equal. It means that both of latencies are supposed to same value. Number of controllers in the topology are considered as Table 3.

Table 3- number of controllers in the topology

Topology name	Number of controllers
Aarnet	[4,6,8,10]
DFN	[4,6,8,10]
Colt	[4,6,8,10]
Cogent	[10,15,20,30]

 

Table. 4 demonstrate the attained results from CPP- KKF , standard K-means, K-means++, Firefly and GSO algorithms ran on the Aarnet, Colt, Cognet, and DFN.

 

Table 4- result of CPP-KKF

	Number of controller	4	6	8	10
Aarnet	K-means	52.24	30.79	21.99	17.56
	K-means++	51.04	29.09	19.78	15.92
	Firefly	41.6	27.89	19.75	15.21
	GSO	40.81	27.25	19.3	14.95
	CPP-KKF	40.05	27.07	19.03	14.85
	Number of controller	4	6	8	10
Colt	K-means	43.82	25.26	16.66	12.22
	K-means++	41.04	24.39	15.18	10.98
	Firefly	36.41	18.84	13.55	10.83
	GSO	35.34	18.85	13.83	10.48
	CPP- KKF	34.05	18.77	13.03	10.05
	Number of controller	10	15	20	30
Cognet	K-means	34.49	27.67	21.79	16.78
	K-means++	33.34	26.89	19.95	14.23
	Firefly	18.98	12.61	9.14	6.05
	GSO	21.03	12.99	9.14	6.61
	CPP- KKF	17.87	12.07	9.04	5.97
	Number of controller	4	6	8	10
DFN	K-means	13.65	10.67	6.95	5.09
	K-means++	13.02	9.78	5.76	3.99
	Firefly	11.44	7.56	5.48	4.24
	GSO	9.28	5.72	4.25	3.33
	CPP- KKF	9.07	5.15	4.07	3.07

 

We depict the results in Fig. 5 with Aarnet topology, Fig. 6 with Colt topology, Fig. 7 with Cogent topology and finally Fig.8 with DFN topology.

 

 

Figure 5- compare CPP- KKF with Aarnet topology

 

Figure 6-compare CPP- KKF with Colt topology

 

Figure 7-compare CPP- KKF with Cogent topology

 

 

 

Figure 8- compare CPP- KKF with DFN topology

From Table 4 and the figs. 5 through 8, CPP-KKF algorithm is better than standard K-means, K-means++, Firefly and GSO algorithms in aforementioned topologies.

 

6.       Conclusion

In this paper, we proposed a clustering algorithm based on K-means, KHM and Firefly algorithms for controller placement problem in SDN utilizing their benefits. The proposed algorithm was evaluated on four different network scales and the results demonstrated its efficient performance in all topologies. We have considered the switch-controller propagation delays and inter-controller latencies as well.

 

 

References

[1]       M. F. Tuysuz, Z. K. Ankarali, D. Gözüpek, A survey on energy efficiency in software defined networks, Computer Networks 113 (2017) 188-204.

[2]       F. Li and X. Xu, "A Discrete Cuckoo Search Algorithm for the Controller Placement Problem in Software Defined Networks," in 2018 IEEE 9th Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON), Vancouver, BC, Canada, 2019.

[3]       D. Wu, B. Tang, D. Yuan, H. Hu and J. Ran, "A new model for the controller placement problem in software-defined networks," In Wireless Communication and Sensor Network, 2016.

[4]       G. Ishigaki, R. Gour, A. Yousefpour, N. Shinomiya and J. P. Jue, "Cluster Leader Election Problem for Distributed Controller Placement in SDN," in Global Communications Conference, Singapore, Singapore, 2017.

[5]       Khorramizadeh, Mostafa, and Vahid Ahmadi. "Capacity and load-aware software-defined network controller placement in heterogeneous environments." Computer Communications, vol. 133, pp. 226-247, 2018.

[6]       V. Ahmadi, A. Jalili and M. Khorramizadeh, "Multi-Objective Controller Placement Problem: issues and solution by heuristics," International Journal of Computer Science and Information Security, vol. 14, no. 8, pp. 543-547, 2016.

[7]       B. Zhang, X. Wang, M. Huang, "Multi-objective optimization controller place-ment problem in Internet-oriented software de-fined network," Computer Communications, vol. 123, pp. 24-35, 2018. 

[8]       G. Wang, Y. Zhao, J. Huang, Q. Duan and J. Li, "A K-means-based Network Partition Algorithm for Controller Placement in Software Defined Network," in 2016 IEEE International Conference on Communications, Kuala Lumpur, Malaysia, 2016.

[9]       Arthur, David, and Sergei Vassilvitskii. K-means++: The advantages of careful seeding. Stanford, 2006.‏ 

[10]       Zhang, Bin, Meichun Hsu, and Umeshwar Dayal. "K-harmonic means-a data clustering algorithm." Hewlett-Packard Labs Technical Report HPL-1999-124 55 (1999).

[11]       Heller, Brandon, Rob Sherwood, and Nick McKeown. "The controller placement problem." ACM SIGCOMM Computer Communication Review 42.4 (2012): 473-478.

[12]       C. Gao, H. Wang, F. Zhu, L. Zhai, and S. Yi, "A particle swarm optimization algorithm for controller placement problem in software defined network," in International Conference on Algorithms and Architectures for Parallel Processing., Cham, 2015.

[13]       K.S. Sahoo, A. Sarkar, S.K. Mishra, B. Sahoo, D. Puthal, M.S. Obaidat, and B. Sadoun, "Metaheuristic Solutions for Solving Controller Placement Problem in SDN-based WAN Architecture," in Proceedings of the 14th International Joint Conference on e-Business and Telecommunications, Madrid, Spain , 2017.

[14]       A. Jalili, M. Keshtgari, R. Akbari, and R. Javidan, "Multi criteria analysis of Controller Placement Problem in Software Defined Networks," Computer Communications, vol. 133, pp. 115-128, 2019.

[15]       K. S. Sahoo, A. Sarkar, B. Sahoo and R. Dash, "On the Placement of Controllers for Designing a Wide Area Software Defined Networks," in IEEE Region 10 Conference, Penang, Malaysia, 2017.

[16]       S. Champagne, T. Makanju, C. Yao, N. Zincir-Heywood and M. Heywood, "A genetic algorithm for dynamic controller placement in software defined networking," In Proceedings of the Genetic and Evolutionary Computation Conference Companion, NewYork, USA, 2018.

[17]       K. S. Sahoo, B. Sahoo, R. Dash and M. Tiwary, "Solving Multi-Controller Placement Problem in Software Defined Network," in International Conference on Information Technology, Bhubaneswar, India, 2017.

[18]        S. Lange, S. Gebert, J. Spoerhase, P. Rygielski, T. Zinner, S. Kounev and P. Tran-Gia, "Specialized heuristics for the controller place-ment problem in large scale SDN networks," in 27th International Teletraffic Congress, Ghent, Belgium, 2015.

[19]       J. Lu, Z. Zhen and T. Hu, "Spectral clustering based approach for controller placement problem in software defined networking," Journal of Physics: Conference Series, vol. 1087, no. 4, p. 042073, 2018.

[20]       G. Wang, Y. Zhao, J. Huang, Q. Duan and J. Li, "A K-means-based Network Partition Algorithm for Controller Placement in Software Defined Network," in 2016 IEEE International Conference on Communications, Kuala Lumpur, Malaysia, 2016.

[21]       K.S. Sahoo, S. Sahoo, S. Mishra, S. Mohanty, B. Sahoo, "Analyzing Controller Placement in Software Defined Networks," International Journal of Computer Applications, vol. 975, no. 8887, 2017.

[22]       L. Zhu, R. Chai and Q. Chen, "Control plane delay minimization based SDN controller placement scheme," in 9th International Conference on Wireless Communications and Signal Processing (WCSP), china, 2017.

[23]       Wagstaff, Kiri, et al. "Constrained K-means clustering with background knowledge." Icml. Vol. 1. 2001.‏

[24]       Li, Youguo, and Haiyan Wu. "A clustering method based on K-means algorithm." Physics Procedia 25 (2012): 1104-1109.

[25]       Wu, Xiaohong, et al. "A hybrid fuzzy K-harmonic means clustering algorithm." Applied Mathematical Modelling 39.12 (2015): 3398-3409.

[26]       Yang, Xin-She. "Firefly algorithms for multimodal optimization." International symposium on stochastic algorithms. Springer, Berlin, Heidelberg, 2009.

[27]       Fister, Iztok, et al. "A comprehensive review of firefly algorithms." Swarm and Evolutionary Computation 13 (2013): 34-46

[28]       Jain, Ravindra. "A hybrid clustering algorithm for data mining." arXiv preprint arXiv:1205.5353 (2012).

[29]       Torkamani-Azar, Sahand, and Mohsen Jahanshahi. "A new GSO based method for SDN controller placement." Computer Communications 163 (2020): 91-108.‏

[30]       A. Co, Aarnet is Australia’s National Research and Education Network, or NREN, Aarnet, 2019, [Online]. Available: https://www.aarnet.edu.au/network and-services/the-network. [Accessed 8 May 2019].

[31]       H.M. Adler, P. Eitner, K. Ullmann, H. Waibel, M. Wilhelm, Deutsches forschungsnetz, 2018, [Online]. Available:  https://www.dfn.de/fileadmin/1Dienstleistungen/XWIN/X-WiN-Broschuere_deutsch.pdf  [Accessed 20 Dec 2018]

[32]       The Internet Topology Zoo, Topology Zoo, 2010, [Online]. Available: http://topology-zoo.org/dataset.html. [Accessed 19 Jan 2019].

 

---