International Journal of Engineering & Technology, 7 (3.
4) (2018) 1-5
International Journal of Engineering & Technology
Website: [Link]/[Link]/IJET
Research paper
A Comparison of Algorithms for Controller Replacement in
Software Defined Networking
Anitson T T1*, Smitha Vinod2
1
Department of Computer Science, Christ University, Bengaluru, India
2
Department of Computer Science, Christ University, Bengaluru, India
*Corresponding author E-mail:anitsonttsat@[Link]
Abstract
Software Defined Network (SDN) partitions the control plane and the information plane to decrease the cost and for increasing the
capacity for upgrading, and this will be helpful for the network administrators to manage the network services. It’s the location where
the controller exists. One of the main issue in Software Defined Networking is the location of the controllers as this could affect net-
work execution and cost. In this paper, we have done an analysis on some algorithms that have been used for minimizing the number
of controllers to reduce the latency, delay, etc. while placing a controller with the consideration of communication among the control-
ler and the nodes.
Keywords: Controller Placement, SDN controller, Greedy-SA algorithm, Network Partition, K-Critical algorithm, Latency, Software Defined Net-
working (SDN).
1. Introduction
The principle behind Software Defined Networking is based on
the partitioning of control plane (Control Layer) and the data plane
(Infrastructure Layer) for reducing the cost and to increase the
capacity to enhance [1].
In the figure (Figure 1) given below, three layers such as Control
Layer, Application Layer and Infrastructure Layer are shown.
Application layer contains Business Applications, that can be
directly accessed by the end users and its where the business
logics and improvement process happens. Control Layer is where
all the automated data-driven fulfilment and assurance operations
has been done. And the Infrastructure Layer is where all the data
collection and machine learning analytics should be done.
SDN controller is one of the application used in Software Defined
Networking for enabling the intelligent networking by managing
the flow control. OpenFlow is one of the protocol that is used by
SDN controllers, that enable servers to inform switches where the Fig 1: SDN Architecture
packets are to be transmitted. The controller lies between network
devices and applications and it’s the core of an SDN network. Any In this paper, we are doing a comparative study on some
kind of communication between the application and the device has algorithms which are used for the Controller Replacement
to be done with the help of controller. OpenFlow protocol is used Problems, mainly on Greedy-SA algorithm and K-Critical
by the controller for configuring the network devices and selecting algorithm based on the controller selection.
the optimal network path for the application traffic [2].
The paper is been followed as, in Section 2 discusses the various
works related to controller placement problems. Section 3
discusses the proposed model based on the selected algorithms.
Section 4, followed by comparison of the algorithms according to
the results that has been collected. Section 5 gives the conclusion.
Copyright © 2018 Authors. This is an open access article distributed under the Creative Commons Attribution License, which permits
unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
2 International Journal of Engineering & Technology
2. Related work delay amongst controllers and nodes, and a management architec-
ture will be created with those selected controllers that can im-
prove the underlying network performance. They are concentrat-
In [3], M. Huang et al. have developed an algorithm, Adaptive
ing on the controller selection method and demonstrate the desired
Bacterial Foraging Optimization (ABFO) for the calculation of
management particularities that upgrade the control and manage-
complexity with the actual network state. According to this
ment of the network. The outcomes demonstrate that their man-
proposal the outcomes demonstrate this proposal, the outcomes
agement trees adjust the heap among them and the data loss is
can possibly manage optimization goals proficiently and
been reduced.
successfully.
In [4], Y. Zhao et al. have proposed a K-means algorithm which is 3. Proposed model
optimized for the investigation on the multi-controller placement
issue from the point of view of reducing the latency. The network 3.1 Controller Selection Using K-Critical Algorithm
partition procedure has been introduced to reduce the issue. In
particular, the network partition issue or problem and the The k-Critical algorithm is one of the algorithm that has been used
controller placement issue are figured out initially. Based on the for illuminating the controller placement problem in software
simulations conducted the results show that the proposed defined networking. By using this algorithm we can reduce the
algorithm comparatively works surprisingly better than the number of controllers required to cover the whole network and to
standard K-means in minimizing latency between centroid and select the controllers that authorize to construct robust and homo-
other nodes. geneous management trees.
In [5], N. Jena et al. have proposed and implemented Simulated Controller placement relies upon the requirements and
Annealing algorithm along with the Greedy heuristic to overcome characteristics of the physical network. For choosing the best
the controller replacement problem. A network is given by a set of placement for the controller, the characteristics of the nodes are
switches or routers. The controllers should be able to manage calculated regarding the network topology through the function θ
them. The algorithm finds the number of controller(s) required to which can be used for evaluating the candidate nodes, because of
cover all the network elements within the network in an optimal their location, to fulfil the delay ‘Dreq’ to nodes that are not
way. The primary criteria is the distance between all nodes and handled by a controller before. Along with that, they ensure that
selected controllers is minimized. Controller's capacity is a the resultant tree branches will have the most extreme delay
constraint of the controller, that restricts a controller to manage an amongst nodes and the controller, constrained by Dreq.
unlimited number of data plane devices.
In [6], L. Han et al. have proposed an algorithm which optimizes
minimum-control-latency, based on the Greedy controlling pattern
design. The thoughts and process are illustrated the Internet2 The coefficient γ measures the connectivity of a node and the
OS3Etopology comparison with the average-latency-optimized weight of the path considering the candidate nodes. It is defined
placement and lowest-case-optimized placement. Furthermore, a as,
novel strategy in view of dynamic latency estimation is (1)
additionally displayed to get more exact control inactivity. Broad
analyses have demonstrated that their minimum-controllatency-
optimized can enhance the inequality when dividing software Where And Lh, is the
defined networking spaces and achieving the highest number of greatest path length measured in number of jumps for the
nodes per controller controlled. candidate node, and Lmax, is been defined as the greatest path
length found among the candidate nodes. The connectivity of node
In [7], L. Yao et al. have defined yet another metric to place relates the level of the candidate node to the node partition in its
controller, considering the weight of the node for an individual branches in i hops. The weight of the path relates the most
domain to start with, and after that they proposed a dynamic extreme delay value that the candidate node achieves when it is
switch migration algorithm to adjust the flow of elements and the root, regarding Eq.1.
acknowledge controller load balance in different Software Defined
Networking areas. NB: γ is candidate node’s least value with the smallest width, and
1 for the candidate nodes with the biggest width.
In [8], G. Jourjon et al. proposed, LiDy, an algorithm which
combines dynamic flow management and controller placement, Algorithm for the Controller Selection using K-Critical are as
and the evaluation for the controller utilization and latency on follows:
sparse and dense regions. The analysis shows that, LiDy is able to
achieve a higher utilization than the latest controller replacement
solution, in all settings. Required: Speed Delay Matrix.
[Link]
In [9], Y. Hu et al. by considering the high complexity of the BIP
in huge networks, a genetic heuristic algorithm is been proposed
to locate a successful problematic arrangement. Simulation result
demonstrate that the energy consumption of the heuristic CT = Set of candidate nodes that satisfies the
algorithm is near that of the BIP solution. Close to 4%, extra
connections are utilized by the heuristic algorithm if every one of
If
the connections have a similar energy consumption.
In [10], C. Cervelló-Pastor et al. have proposed an algorithm Then
called k-Critical for solving the controller placement problem in
software defined networking. It will be finding the minimum
number of controllers to fulfill an objective of intercommunication For every node has be converted to a controller
International Journal of Engineering & Technology 3
Go for
Cl Cnij
Evaluating θ
The nodes will be assigned to the nearest controller. In this
End on situation the controller don't have the ability to deal with the node,
the algorithm inquires for the accompanying closest controller and
do a similar operation. This procedure will proceed until the
Selecting the node with the maximum values in θ; controller could find and designate rest of the node to the
count =0. controller. The greedy solution given by the algorithm goes wrong
Else when no controller can suit the required limit, that case is
considered as the more terrible case.
While there are no more nodes associated with the cluster
Go for Greedy Heuristic Algorithm used for the Controller Selection is:
Cnd Finding the outermost node to the cluster For every Binary string S of SA(Simulated Annealing)
Ccnd Finding the set of the candidate nodes for managing Pick N number of one as controllers
the cluster
For all the candidate node Pick M - N number of zero as the nodes
Go for
Select a permutation pi(M N_K) at arbitrary
Evaluation θ
For each terminal pi(Mi)
End for
Selecting the node nd which is having maximum value in θ Go for
Clusterk Finding from the nodes vnd that satisfies Determining Cij = separate from pi(Mi) to the nearest
Controller Cnj
, Where the
Cnj pi(Mi)
End all Cl Cnij
End if Finding F (z) = sum of (C l)
3.2 Controller Selection using Greedy-SA algorithm end on
The Greedy-SA algorithm is a combination of both Greedy 4. Evaluation and Results
algorithm and SA algorithm that has been used for the problems in
case of controller replacement. Basically the SA (Simulated
Annealing) algorithm is used for solving the optimization All K-Critical algorithm have been used to demonstrate the
problems. The SA technique they have used for controller assumption on the controller selection in the controller
selection is by considering N number of nodes which will be performance regarding delay, node management allotment, data
considered as controllers for the network, with the help of a loss among controllers and depth of the tree. To facilitate this,
method in which the number of ones in the string suggests that the three system classification are created, i.e. dense, medium and
quantity of controller has been picked, though a zero infers that sparse networks. Software defined in [11] is used to create these
the relating network component isn't a controller, but instead it networks. At that point they assessed the performance and strength
will be serving as a switch. The SA will be looking exactly for the of the trees built at the controllers chosen and for every single one
N ones among them. The standard SA algorithm won’t be able to of the exhibited answers for every last one of the network levels.
deal with the fixed set of ones among the string, so we have to add
an additional opeartor(oper) to the algorithm. The additional The controllers were found for various delay values in the scope
operator will be acting like as follows: of microseconds. The outcomes displayed were the normal
outcomes got for each system class assessed. MATLAB was used
for calculating the algorithm and their performance.
The calculation of the data loss can be done by,
(2)
The standard SA algorithm is used along with the Greedy
algorithm and while finding an answer using Greedy algorithm, it Where, i ∈ V(Tk).
goes for the best immediate and starts with a permutation of,
By considering data loss ‘di’ for a node, i relies upon the number
pi(M N_K) of the nodes ‘ni’ that are established, and on the probability that
the node i goes down. Along with the consideration of each node
in the tree topology ‘Tk’ has a similar loss probability and ‘N’ will
Along with the Euclidean distance among switch ‘i’ and controller
‘j’ is been calculated with, be the number of nodes in the network while ‘V(Tk ) will be the
nodes in the tree ‘Tk’.
4 International Journal of Engineering & Technology
One of the result says that for the medium and the sparse heuristic approach includes to meet the time and resource demand.
connectivity networks, the controllers chosen by K-Critical have According to the results obtained by using Greedy-Sa algorithm,
preferred the node allotment over alternate solutions. The the number of controllers in the control plane has been known
outcomes acquired for dense networks isn't appeared, on the formerly, however their positions majorly affect numerous
grounds that only one controller deals with the entire network for ongoing issues ([12] [13]).
all cases.
In future work the arrival and execution of real time task as other
The next result says that the depth of the tree is been influenced by important metric for the said problem and implement the cost
the allotment of node for each controller. Those trees made out of function on a real time environment can be considered. Along
controllers found by K-Median is having the most exceedingly with defining how the tree topology is built from the selected
bad node appropriation with lengthy paths is an example. For the controllers taking into account several network performance
dense network, whereas just one controller is needed, K-Critical metrics. This is because selecting the shortest paths between
will be allotting the best node among the branches, therefore the controller-nodes is not the best option for improving the load and
most limited ones are the subsequent trees. the robustness of the control layer.
So the best controller allotment can be done by the K-Critical. References
That best outcomes acquired utilizing K-Critical are because of
the measure to choose the leading controller. That determination [1] Wang, Guodong, Yanxiao Zhao, Jun Huang,Qiang Duan, and Jun
relies upon the bad node in the network in form of delay, the Li. "A K-means-based network partition algorithm for controller
demanding node. Then again, k-Median doesn’t achieve better placement in software defined network", 2016 IEEE International
performance as a result of the foremost criteria to choose the Conference on Communications (ICC), 2016.
controller isn't productive. [2] Afrim Sallahi, Marc St-Hilaire. "Expansion Model for the Control-
ler Placement Problem in Software Defined Networks", IEEE
Communications Letters, 2016.
The computational complexity for every single controller
[3] B. Zhang, X. Wang, L. Ma and M. Huang, "Optimal Controller
placement methods assessed by O(nk). While locating a controller Placement Problem in Internet-Oriented Software Defined Net-
it requires checking the least space in the network among the N work," 2016 International Conference on Cyber-Enabled Distribut-
nodes. So, the computational complexity for locating a controller ed Computing and Knowledge Discovery (CyberC), Chengdu, 2016,
also can be characterized by O(n).That mechanism has to be pp. 481-488.
repeated till the k controllers were found. [4] G. Wang, Y. Zhao, J. Huang, Q. Duan and J. Li, "A K-means-based
network partition algorithm for controller placement in software de-
fined network," 2016 IEEE International Conference on Communi-
By using Greedy-SA algorithm, the result says that the average cations (ICC), Kuala Lumpur, 2016,pp. 1-6.
delay got by Greedy – SA algorithm is consistently stable. In the [5] K. S. Sahoo, B. Sahoo, R. Dash and N. Jena, "Optimal controller
same way the results on average latency says that, while the selection in Software Defined Network using a greedy-SA algo-
quantity of the controllers are continuously expanding under a rithm," 2016 3rd International Conference on Computing for Sus-
similar topology in every technique [12]. tainable Global Development (INDIACom),New Delhi, 2016, pp.
2342-2346.
[6] L. Han, Z. Li, W. Liu, K. Dai and W. Qu, "Minimum Control La-
while evaluating the computational time with expanding
tency of SDN Controller Placement," 2016 IEEE Trust-
controllers in a given topology while the size of the network is the com/BigDataSE/ISPA, Tianjin, 2016, pp. 2175-2180.
same. It has seen that, by extending more number of controllers, [7] L. Yao, P. Hong, W. Zhang, J. Li and D. Ni, "Controller placement
the confluence of time is bigger. At the point when the number of and flow based dynamic management problem towards SDN," 2015
controllers expands the growth rate of calculation also raise. IEEE International Conference on Communication Workshop
(ICCW), London, 2015, pp. 363-368.
[8] M. T. I. ul Huque, G. Jourjon and V. Gramoli, "Revisiting the con-
5. Conclusion troller placement problem," 2015 IEEE 40th Conference on Local
Computer Networks (LCN),Clearwater Beach, FL, 2015, pp. 450-
In this paper the algorithms that has been discussed are mainly 453.
used for the controller selection process along with the assessment [9] Y. Hu, T. Luo, N. C. Beaulieu and C. Deng, "The Energy-Aware
Controller Placement Problem in Software Defined Networks," in
based on the involvement of the controller selection in the
IEEE Communications Letters, vol. 21, no. 4, pp. 741-744, April
succeeding control layer. The demonstration includes the number 2017.
of controllers that’s been selected along with their locations for [10] Y. Jiménez, C. Cervelló-Pastor and A. J. García, "Defining a net-
determining the performance of the network, and the control work management architecture," 2013 21st IEEE International Con-
network robustness controller selection can also be influenced ference on Network Protocols (ICNP), Goettingen, 2013, pp. 1-3.
significantly because of bad selection of controller, as well as the [11] M. Bastian, S. Heymann, and M. Jacomy Gephi: an open source
network operation also. According to the results obtained the best software for exploring and manipulating networks,Proceedings of
count on the controllers are based on the components of physical International AAAI Conference on Weblogs and Social Media
(ICWSM).,pp. 361-362. California, USA, 2009.
network along with the specifications, an excellent selection of
[12] Sahoo, Sampa, et al. "Execution of real time task on cloud envi-
controllers will enable the network while adjusting the weight as ronment." (2015).
well. [13] Kumar, Dilip, and Bibhudatta Sahoo. "Energy efficient heuristic
resource allocation for cloud computing." (2014).
By using k-Critical for choosing the controllers a strong control
layer in suspense of network interruptions is developed. This is
because of the physical components of the network are considered
in the time of selecting appropriate controllers and the finest
location for the controller can also be organized meanwhile a
network has to be enlarged or by replacing the load.
One of the major challenge in the designing of the control plane in
architecture of SDN. Brute force access with this issue is basically
attainable for small and medium size network, so another
mechanism is required for large example of networks. Typically