A Safe and Reliable Heterogeneous Controller Deployment Approach in SDN

Peng Yi,Tao Hu,*,Yanze Qu,2,Liang Wang,2,Hailong Ma,Yuxiang Hu,Julong Lan

1 National Digital Switching System Engineering and Technological Research Center,Zhengzhou 450002,Henan,China

2 Information Engineering University,Zhengzhou 450001,Henan,China

Abstract:Software-Defined Networking(SDN)provides flexible and global network management by decoupling control plane from data plane,and multiple controllers are deployed in the network in a logically centralized and physically distributed way.However,the existing approaches generally deploy the controllers with the same type in the network,which easily causes homogeneous controller common-mode fault.To this end,this paper proposes heterogeneous controller deployment in the SDN,considering the different types of controllers and relevant criteria(e.g.,delay,control link interruption rate,and controller fault rate).Then,we introduce a Safe and Reliable Heterogeneous Controller Deployment(SRHCD)approach,consisting of two stages.Stage 1 determines the type and the number of heterogeneous controllers required for the SDN network based on the dynamic programming.Stage 2 divides the SDN network into multiple subnets by k-means algorithm and improves the genetic algorithm to optimize the heterogeneous controller deployment in these SDN subnets to ensure reliable switch-controller communications.Finally,the simulation results show that the proposed approach can effectively reduce the control plane fault rate and increase the attack difficulties.Besides,the switch- controller delay has been lowered by 16.5%averagely.

Keywords:software defined networking; control plane;reliability;safety;controller deployment

I.INTRODUCTION

With the expansion of Software-Defined Networking(SDN),in many large-scale SDN networks,a single controller is usually unable to satisfy the requirements of delay and flow request,which is not enough to control the whole SDN network[1].In addition,the physically centralized controller often encounters a single point of failure,which seriously limits the reliability of the SDN network.Once the controller is damaged or suffers from the performance bottleneck,the advantage of SDN will be lost.Therefore,multiple controllers are usually deployed in a way of logical centralization and physical distribution to manage the entire SDN network.

In recent years,researchers have designed several distributed controller architectures(e.g.,Kandoo[2],Onix[3],DISCO[4])to improve the scalability of the SDN.However,it is inefficient to increase the number of controllers only.Both the number and the locations of controllers will affect the network performance significantly.Recently,researchers have presented various solutions to solve the Controller Placement Problem(CPP).As defined for the first time in[5],the goal of the CPP is to determine the number and location of controllers in a given SDN network,thus achieving expected optimization objectives,such as minimizing average propagation delay and worst-case propagation delay.For example,the Capacity-aware CPP is introduced in[6].In[7],the authors optimize controller deployment with the goal of controller utilization.On this basis,in[8],the authors consider delay,hops,load balancing,thus solving CPP more comprehensively.

Although a lot of research work has been done to solve the CPP,the existing solutions usually consider that all the controllers deployed in the network are homogeneous.Namely,the whole network is managed by the controllers with the same types.The difference is only limited to the number of controllers deployed.As a matter of fact,the SDN network composed of homogeneous controllers has great safety risks.Since all homogeneous controllers have the same designed function,including any possible design vulnerabilities will be reflected on the relevant components of the homogeneous controllers intactly[9].If the attackers have mastered the attack method of a vulnerability on one controller,all homogeneous controllers will be threatened in the same way in the SDN.In this paper,this type of controller fault is called homogeneous controller common-mode fault and defined as follows:in a multi-controller network,the structure,system,or component of homogeneous controllers fail in the same way due to specific defects(e.g.,vulnerabilities,backdoors).

Therefore,even if the existing research work has solved CPP well,the common-mode fault problem of homogeneous controllers is seriously underestimated or even ignored.When the same design defects lead to a common-mode fault,no matter how to optimize the location of controllers and configuration of redundant controllers,it cannot avoid the collapse of the control plane and network crash caused by the homogeneous controller deployment.To solve this problem,this paper introduces a Safe and Reliable Heterogeneous Controller Deployment(SRHCD)to eliminate the homogeneous controller common-mode fault in the SDN network.The main contributions of this paper are as follows:

We formally formulate Heterogeneous Controller Deployment Problem(HCDP),considering the endto-end delay,control link interruption rate,and controller fault rate comprehensively.

We propose the SRHCD approach to solve HCDP,including two stages:stage 1 computes the number of heterogeneous controllers based on dynamic programming;stage 2 divides the SDN network into multiple subnets by k-means algorithm and improves the genetic algorithm to optimize the heterogeneous controller deployment.

We demonstrate the effectiveness of our proposal through simulation experiment in different network topologies.Results show that SRHCD can reduce the control plane fault rate and attack success rate3 The switch-controller delays have been decreased by 16.5%averagely.

The rest of this paper is organized as followings.Section II gives the related work.Section III is the problem analysis and modeling.The corresponding algorithms are designed for SRHCD in Section IV.Section V provides the evaluation and analysis of simulations.Section VI concludes this paper.

II.RELATED WORK

In recent years,to solve the controller deployment problem in the SDN network,researchers have proposed a variety of solutions and achieved fruitful results.Delay is very important for the SDN network,because switches and controllers require frequent message interactions.Existing controller deployment schemes usually focus on propagation delay and controller delay.In[5],the authors firstly proposed the controller deployment problem.They solved the number of controllers needed by specific network topology.In[10],the authors presented to transform the controller deployment problem into a network partition problem and used an improved clustering method to solve it.In[11],the authors introduced a controller deployment scheme based on heuristic and Dijkstra algorithms to minimize switchcontroller and inter-controller delays.In[6],the authors considered the controller processing delay when formulating the controller deployment scheme,and defined a capacity-aware controller deployment problem.The dynamic controller scheduling strategy is adapted to reduce the number of controllers required significantly.In[12],the authors studied the problem of delay optimization in the case of controller fault and designed a simulated annealing algorithm to solve it.This method can be applied to large-scale networks.The network node or link failures may break the connections between switches and contoller,or crash the network.Therefore,choosing reasonable locations to deploy controllers to maximize reliability is another research hotspot.In[13],the authors presented a reliability-aware controller deployment and proved that it is an NP-hard problem.They firstly defined the percentage of control path fault as a metric to evaluate controller deployment.In[14],an enhanced controller deployment strategy is proposed,which explicitly considers the path diversity,capacity,and fail-over mechanism in the controller deployment problem.In[15],the authors designed a reliable and load-aware controller deployment method by balancing node performance and path quality.In[16],the objective is to improve the flexibility of controller deployment,and an optimization model is designed to minimize the reserve capacity of controller under the condition that the total number of deployed controllers in the network remains unchanged.

When solving the controller deployment problem,researchers consider multiple factors and formulate it as a multi-objective hybrid optimization problem.In[17],considering the delay,isolated nodes,and controller loads,the authors designed a Pareto-based controller deployment framework and analyzed all possible deployment scenarios in detail.In[18],the authors studied the problem of controller deployment in the SDWAN scenario[19,20]and analyzed the end-toend delay and controller processing delay based on the queuing theory model.In[8],the authors considered the transmission delay,hops,and link utilization and designed a genetic algorithm based on hybrid AHP to calculate the optimal locations for the controllers in the network.

Although the existing researches on the CPP are plentiful[21,22],almost all solutions have assumed that the controllers are homogeneous and have left out consideration of the common-mode fault caused by this.To this end,we deploy heterogeneous controllers in the network and take the delay,control link interruption rate,and controller fault rate as the optimization objectives.

III.PROBLEM ANALYSIS AND MODELING

3.1 Problem Analysis

To improve the scalability of SDN,researchers have proposed to deploy multiple controllers in the SDN network to avoid the single point of failure[23].Although the deployment of multiple controllers improves the resilience and fault tolerance of the network effectively,the existing researchers usually consider the control plane to be composed of the homogeneous controllers.Once malicious attackers have mastered the vulnerability knowledge of the controller,they can use this vulnerability to implement malicious attacks on the controller,such as message leakage,disconnection from the switch,controller crash[24].Due to the homogeneity of controllers in the control plane,attackers may launch the same type of attack and destroy all corresponding controllers.

For example,there is an SDN network placing three controllers,as shown in Figure.1.All SDN controllers are homogeneous(e.g.,Floodlight),each of which manages the corresponding SDN subnets.When the attackers have probed that the controller is Floodlight as well as mastered one vulnerability in the Floodlight(e.g.,CVE-2014-2304 is an exposed vulnerability in OpenFlow protocol for Floodlight 0.9 version[25]),they can exploit this vulnerability to crash it.No matter how many Floodlight controllers are placed as the backups in the control plane,the attackers can still easily destroy them by exploiting this vulnerability.At last,all Floodlight controllers fail in the same way,and the control plane is damaged by homogeneous controller common-mode fault.

Figure 1.Homogeneous controller common-mode fault.

Nowadays,for the common-mode fault,the typical practice is heterogeneous and redundancy[26].That is to say,using multiple heterogeneous components with equivalent function or performance can effectively reduce the probability of common-mode fault[27].With the development of SDN technology,there are more than 30 types of open-source controllers.They are written in different programming languages,which are sufficient to meet the heterogeneous requirements of SDN controller deployment[28].Each type of SDN controller can complete network control,and they are functionally equivalent.Although they may have design defects like known(or unknown)vulnerability(or backdoor),the different design and environment conditions(for example,NOX[29],Ryu[30],and Floodlight[31]are developed by C++,Python,and Java,respectively)make the trigger mechanism of vulnerability not the same.In theory,the controllers run independently of each other,that is,there is no dependency relationship.It is difficult for attackers to use the same attack means to make all heterogeneous controllers show abnormal behaviors at the same time.

Based on the above cognition,this paper proposes to integrate the heterogeneity into the controller deployment problem to solve the common-mode fault faced by homogeneous controller deployment in the SDN network.

3.2 Problem Modeling

3.2.1 Network environment model Multi-controller deployment is usually adopted in the large-scale SDN network.In this paper,we consider a large-scale backbone network.The SDN network is described based on graph theory and represented as an undirected graphG=(V,E),whereVrepresents the set of nodes andErepresents the set of links in SDN,respectively.Each network nodevicorresponds to a switchsi,and the set of switches isS.The number of nodes in the SDN network isN.h(vi,vj)represents the number of hops between any two nodesviandvj.Binary variableslijshows the connection relationship between nodes,as shown in Eq.(1).is the link bandwidth.In this paper,we assume that the network traffic in the backbone network is relatively stable,that is,the traffic changes in each time period have little difference,and the flow requests insifollow the Poisson distribution with the parameterλi[32].

Different from the traditional controller deployment methods,here we consider heterogeneous controllers,that is,the types of controllers deployed in the network are not the same.The set of controllers isC,and the total number of controllers deployed is M.The binary variableck(u)represents the heterogeneous controller deployment,whereck(u)=1 represents that the controller of type deployed on the nodevkisu,as shown in Eq.(1).Parameteru∈His set according to the set of available heterogeneous controller typesH,for example,u=1 presents NOX andu=2 presents Ryu.The total number of heterogeneous controller types isU=|H|.Since different types of controllers have different flow request processing capabilities,parameterwk(u)represents the capacity of controllers of typeuon nodesvk.In order to be more consistent with the real network scene,this paper sets that each switch only corresponds to one master controller,which is responsible for processing the flow requests[33].Therefore,a binary variablexikis introduced to represent the mapping relationship between the switch and the controller,as shown in Eq.(2).

As discussed in the related work,the CPP solutions are complex,especially for heterogeneous controller.In this paper,we consider the following metrics for heterogeneous controller deployment:

(1)End-to-end delay In the SDN,the end-to-end delayDik(u)between the switchviand the controllerck(u)is defined as the time from the new flow entering the switch to the switch receiving the responded Packet_Out message from the controller.With the development of hardware technology,the performance of switch is generally improved,and the switch processing delay is almost negligible[34].In addition,in a high-speed network,the packet transmission delay is usually very small.Packet propagation delayDPik(u)is defined as the number of hops between switchviand controllerck(u),as shown in Eq.(3),

The interaction between the controller and the switch can be regarded as an independent M/M/1 queuing model.The controller is similar to the server,and the flow requests sent by the switch are similar to the customers[33].Thus,the average waiting time is computed as the reciprocal of the difference between the server processing rate and customer arrival rate.For the switchck(u),the average processing delay of the controller is the reciprocal of the difference between the controller capacity and the switch flow request rate,as shown in Eq.(4),

The end-to-end delayπk(u)of the controller on the nodevkcan be calculated as the sum of the end-to-end delay of the controller and all managed switches,as shown in Eq.(5)and(6),

The average end-to-end delayπof the network is calculated in Eq.(7),

(2)Control link interruption rate For an SDN network,in order to save construction costs,the controller and switches communicate in in-band mode.Namely,data flow and control flow share the same link.Therefore,the control link is defined as the shortest link from the switch to the controller,which is calculated by Dijkstra algorithm.As shown in Figure.2,the heterogeneous controllers are located in node 1 and node 7,respectively,and the control links between the switch on node 4 and the controller on node 1 are 4-2-1.In the actual network environment,affected by the limited link bandwidth,if a link is used very frequently,the traffic on the link may seriously affect the QoS due to congestion and long delay.For example,intuitively,in Figure.2,when the switches on node 2,3,4 communicate with the controller on node 1,all their control traffic will be transmitted on link 2-1,easily resulting in congestion on this link.

Figure 2.SDN network topology.

Therefore,the interruption rate of the control link is related to the control traffic passing through the link.In the case of the same link bandwidth,the more the number of flow requests,the greater the congestion probability,and the greater the interruption rate of the control link.The control link interruption rateCLIRikis shown in Eq.(8),

whereτikis the direction factor of the linklik·τik=1 indicates that the control flow(i.e.flow request rateλi)is transmitted from the switch nodevito the controller nodevk,otherwiseτik=0.Vice versa.CLIRikranges from 0 to 1.Whenlik=0,there isCLIRik=1.

Therefore,we compute the control link interruption rateCLIRof the whole network in Eq.(9),

(3)Controller fault rate Here,we mainly discuss the controller fault caused by exploiting controller vulnerabilities or backdoors.It should be noted that the controller fault caused by physical failures is beyond controller safety category considered in this paper,and we will concentrate on it in future work.In the SDN network,the probability of controller fault is usually related to the design mode and system composition of the controller.In general,the lower the safety of the controller itself,the higher the fault rate.In addition,the fault rate is also related to the attack frequency on the controller.The more frequent the malicious attacks,the more likely the attackers are to find the vulnerability of the controller and then crash the controller.Based on the above analysis,the controller fault ratePCFk(u)is computed in Eq.(10),

whereCF(u)represents the vulnerability coefficient of controller with typeuandMAkrepresents the attack coefficient of taking the controller on nodevkas target.Next,we will analyze them in detail.

Firstly,the value ofCF(u)depends on the number of vulnerabilities of the controller itself and the prior knowledge of the attacker.In general,the more the number of controller vulnerabilities,the higherCF(u),as shown in Eq.(11),

Noted that in the actual production or design,it is hard to achieve full heterogeneity between different types of controllers.After attacking one type of controller,the attackers can use the prior knowledge obtained from this process to guide subsequent attacks.In this paper,we defineζ(u)as the prior knowledge coefficient on the controller with typeu,as shown in Eq.(12),

whereV U(u′)represents the number of vulnerabilities in the controller with typeu,V U(u,u′)represents the number of common vulnerabilities in the controllers with typeuand typeu′,and Ω indicates the set of controllers that have been attacked by attackers.In addition,ζ(u)∈[0,1].

Based on Eq.(11)and(12),we computeCF(u)in Eq.(13),

We consider that attack coefficientMAkis related to the deployment location of the controller.This is because the attackers usually choose the controllers deployed in the key nodes of the network as the attack targets.Referring to the node degree of the complex network,we computeMAkin Eq.(14),

Therefore,based on Eq.(10),Eq.(13),and Eq.(14),we compute the controller fault rate in Eq.(15),

Accordingly,the control plane fault rate is shown in Eq.(16),

3.2.2 HCDP

Based on the above network model,we introduce the heterogeneous controller deployment problem,which is defined as follows.

Definition 1.Heterogeneous Controller Deployment Problem(HCDP):for a given network and a set of heterogeneous SDN controllers,how to reduce the end-to-end delay,control link interruption rate,and control plane fault rate by determining the controller types,deployment locations,and switch-controller mapping relationships.

Therefore,HCDP is a multi-objective optimization problem with multiple constraints,and its formulation is shown in Eq.(17),

Eq.(18)indicates that loads of the controller cannot exceed its capacity.In addition,each controller needs to reserve a certain proportion of capacity to deal with traffic emergencies,which is determined by the traffic burst coefficientβ.For example,in a network with control load changing significantly,βis set to a higher value.Eq.(19)shows that each switch has only one master controller.Eq.(20)ensures that only one type of controller can be deployed in the same location.Eq.(21)presents that there are at least two types of heterogeneous controllers in the network.

IV.SAFE AND RELIABLE HETEROGENEOUS CONTROLLER DEPLOYMENT APPROACH

Based on the above analysis and modeling,this paper focuses on the real network scenario,where the number of controllers is unknown,and different types of heterogeneous controllers have different processing capabilities and safety attributes.Based on formulated objective function,we can find that the key to solving HCDP is to determine the types and the locations of heterogeneous controllers and the switch-controller mapping relationships.To this end,we propose a Safe and Reliable Heterogeneous Controller Deployment(SRHCD)approach,including two stages.In order to maximize the safety of control plane,stage 1 adopts dynamic programming to determine the types and the number of heterogeneous controllers meeting the network traffic demand.Further,in order to ensure the reliability of controller deployment,stage 2 divides the network into multiple subnets by the k-means algorithm and improves the genetic algorithm to optimize the heterogeneous controller deployment in these SDN subnets to ensure reliable switch-controller communications.

4.1 Stage 1

As mentioned above,the homogeneous controller common-mode fault can be alleviated effectively by deploying heterogeneous controllers in the network.In order to reduce the difficulty of heterogeneous controller deployment,this stage first determines the type and the corresponding number of heterogeneous controllers to be deployed to prepare for the next stage of solving HCDP.

From a safety perspective,the more diverse the controller types are,the lower the probability of the whole control plane breakdown due to common-mode fault is.Therefore,to maximize the safety of the control plane,we must take full advantage of all available heterogeneous controllers.Meanwhile,in order to decrease the controller deployment cost,it is necessary to minimize the total number of controllers.Therefore,the problem of determining the number of heterogeneous controllers can be considered as a special kind of complete knapsack problem,in which the heterogeneous controllers are considered as the goods and the total network loads are considered as the knapsack capacity.For clarity,we use a simple example to show this analogy,as shown in Figure.3.There are four types of goods(e.g.,Good1 to Good4)and one knapsack in Figure.3(a).Each good has two properties:weight and value.For example,the weight and value of Good1 arew1 andv1,respectively.The complete knapsack problem is to maximize the total value of the goods in the knapsack as long as the sum of their weights does not exceed the knapsack capacity.By analogy,there are four types of controllers(e.g.,c(1)toc(4))and one SDN network in Figure.3(b).Each controller also has two properties:controller capacity and value.For example,for one controllerc(1),its controller capacity and value areω(1)andV(1),respectively.Our purpose is to minimize the total value of the controllers in the network as long as the sum of their controller capacities is not less than the traffic loads of the network.

Figure 3.Analogical case analysis.

Figure 4.Binary coding of individual.

Motivated by the above case,here,we formally define the problem of determining the number of heterogeneous controllers in the SDN network:givenUtypes of controllers{c(1),c(2),...,c(U)},their capacities{ω(1),ω(2),...,ω(U)},the values of heterogeneous controllersV(1)=...=V(U)=1,the existing traffic loadsand the number of controllers of each type is{NC(1),NC(2),...,NC(N)}.Our optimal goal iswhere the constraints areNC(u)∈{1,2,...,W/w(u)}(NC(u)indicates the number of controllers of typeu),and∑.

Since the complete knapsack problem belongs to the NP-hard problem,it is also NP-hard to determine the number of heterogeneous controllers.In this paper,we solve it based on dynamic programming.Dynamic programming is based on the Bellman optimality principle and widely used to solve NP-hard problems.The principle is to divide the original problem into several subproblems.A subproblem is solved by finding the iterative relationship between the original problem and subproblems,and the original problem can be solved finally[35].Compared with the brute force search,the complexity of dynamic programming is linear,which improves the efficiency of solution.

Here,the subproblemm(u,j)is described as the minimum value that the formerucontrollers can achieve based on traffic loadj,and the state transition equation can be obtained in Eq.(22),

The initial condition of iteration is shown in Eq.(23),

The algorithm pseudocode is shown in Algorithm 1.Lines 1-8 are used to compute the total number of heterogeneous controllers required,and lines 9-16 output the number of heterogeneous controllers of each type.Moreover,the complexity of algorithm 1 isO(U·W).

4.2 Stage 2

Based on Stage 1,the total number of controllers placed(M)and the number of controllers of each typeNC(1),...,NC(U)are obtained.Based on Eq.(17),it can be seen that HCDP is a typical multi-objective optimization problem.The optimization objectives include minimizing network end-to-end delay,control link interruption rate,and control plane fault rate.In addition,HCDP actually belongs to a special type of CPP.Since CPP has been proved to be NP-hard[5,6],HCDP also belongs to an NP-hard problem.Therefore,this paper uses a genetic algorithm to solve HCDP since it has been widely used to solve multiobjective optimization problems.In order to cope with HCDP in a large-scale SDN network,it is necessary to reduce the population size and iteration times of the genetic algorithm.Thus,for solving HCDP efficiently,this paper adopts “divide and conquer” strategy and joints the clustering algorithm and genetic algorithm to place heterogeneous controllers in the network efficiently.Firstly,the network is divided intoMsubnets(Mis the total number of heterogeneous controllers)by the clustering algorithm.Then the HCDP of each subnet is solved based on the genetic algorithm.The following will be described in detail.

(1)SDN network dividing The clustering algorithm divides a set of data into different clusters according to a specific standard.At present,some researchers have proposed to apply the clustering algorithm to the SDN network.In this paper,we use the K-means clustering to divide the SDN network intoMsubnets(Mis the result of algorithm 1),as shown in Algorithm 2.Algorithm 2 computes the hops between nodes by Dijkstra algorithm and clusters the network nodes based on hops.The algorithm detail is described as follows.Lines 1-3 calculate the sum of hops from each node to all other nodes and select the node with the minimum hop sum,which is recorded asc1.Line 4 calculates the node with the maximum hop count toc1,which is recorded asc2.Lines 5-11 take these two nodes as initial centers,and assign related nodes to the two centers.Specifically,for each nodev∈V,h(v,c1)andh(v,c2)to the two initial centers are calculated,respectively.Ifh(v,c1)< h(v,c2),the nodesvandc1are divided into the same cluster.Once a nodevis assigned to a center,the cluster’sc1is recalculated based on the minimum hop sum described in line 3.The process is repeated until the network ofNnodes is divided intoMsubnets.The algorithm complexity isO(M ·N),and the effectiveness of clustering algorithm has been proved in reference[18].

(2)Heterogeneous controller deployment On the basis of network dividing,the improved genetic algorithm is applied to solve the HCDP of each subnet.It should be noted that the improved genetic algorithm is applied to each subnet.For one subnetGk,the controller must manage all switches in this subnet(xik=1,∀vi∈Vk,vk∈Vk),and the locationkand typeuof heterogeneous controller need to be solved.Referring to the implementation of the genetic algorithm in[17],we consider that the core steps include coding,fitness value computation,and genetic operation(e.g.,selection,crossover and mutation).The details are described as follows.

Firstly,we adopt binary coding for the individual of genetic algorithm,where each individual represents one feasible solution for HCDP.Benefiting from binary coding,the encoding and decoding processes of this method are simple,and the corresponding crossover operator and mutation operator are based on bit operation.We take an example to show the coding of an individual in Figure.4,in which the blue part shows the locationkof the heterogeneous controller and the yellow part shows the typeuof the heterogeneous controller.

Algorithm 1.Heterogeneous controller number optimization.Input:Heterogeneous controller types{c(1),c(2),...,c(U)}Heterogeneouscontrollercapacities{w(1),w(2),...,w(U)}Controller values V(1)=V(2)=...=V(U)=1 Network traffic loads W=∑N i=1 λi Output:The total number of controllers M Number of different types of controllers{NC(1),NC(2),...,NC(N)}1: m(0,)←{0},m(,0)←{0}2:for u=1toU do 3:for j=1toW do 4:for NC=1toj/ω(u)do 5:if j ≥ω(u)then 6:m(u,NC) ←min(m(u,NC),m(u −1,j −NC·ω(u))+NC·V(u))7:end if 8:end for 9:end for 10:end for 11:12:return m(U,W)andM u ←U,j ←W 13:while u>0&&j >0 do 14:15:if m(u,j)=m(u,jω(u))+V(u)then 16:Output NC(u)j ←jω(u)17:else 18:u ←u −1 19:end if 20:end while

Secondly,we define the fitness function of the improved genetic algorithm.The fitness function is usually set as the objective function.Since HCDP is a multi-objective optimization problem,we transform it into a single objective problem based on the linear weighted combination method.The fitness function of thekthsubnet is shown in Eq.(24),

Algorithm 2.SDN network dividing.Input:Network topology G=(V,E)Number of subnets M Output:Network partitioning results G=∩M k=1 Gk=∩M k=1(Vk,Ek)1:Compute hops h(vi,vj)between any two nodes,∀vi,vj∈V 2: ∀vi∈V,SUM=∑N h(vi,vj)3: c1=argminSUM,get Cluster1 4: c2=argmaxh(c1,c2),getCluster2 5: v∈V,compute h(v,cj)and h(v,cj)6:if h(v,ci)

whereρ1,ρ2,ρ3are weights for the above three objectives,0≤ρ1,ρ2,ρ3≤1,ρ1+ρ2+ρ3=1.The weights can be set according to the importance of the three objectives in the corresponding network scene.For example,when more attention is paid to the reliability of the control network,ρ2is given to a higher value.Eq.(25)indicates that all nodes and edges belong to the subnetGk.

Based on the above analysis,the heterogeneous controller deployment based on improved genetic algorithm is shown in algorithm 3.Lines 2-14 run the improved genetic algorithm for each subnet,including initialization,fitness value comparison,selection,crossover,mutation and other operations.Finally,the typeuand locationvkof the controller deployed in each subnet are obtained.The complexity of algorithm 3 mainly comes from the genetic process.The maximum number of nodes in each subnet isN,evolution iterations isI.Therefore,the computational complexity of each subnet isO(I˙ logN),while the genetic process needs to poll M(0< M ≤N)subnets,so the computational complexity of algorithm 3 isO(I ·N ·logN).

Algorithm 3.Heterogeneous controller deployment.Input:SDN network G=∩M k=1 Gk=∩Mk=1(Vk,Lk)Number of controllers{NC(1),NC(2),...,NC(U)}Output:Heterogenouscontrollerdeployment ck(u)1:for k=1toM do 2:in Gk,initialize population p fits ←Fk(p)i=0 3:while i¡1 do 4:fitbest=min(fits)p ←Selection/Crossover/Mutation(p)fits ←Fk(p)5:if fitsbest ≤min(fits)then 6:i++7:end if 8:end while 9:encoding p,get controller type u and location vk in Gk N(u)=N(u)−1 10:end for

V.EVALUATION AND ANALYSIS

5.1 Simulation Environment

In this paper,we build a network environment on the physical server(Intel E3-1230,8 Core,2.3GHz,32GB RAM,Ubuntu 16.04).For heterogeneous controllers,we select the current mainstream controllers(e.g,.NOX,Ryu and Floodlight).We program our proposed algorithms and analyze the data by MATLAB tools.The experimental topologies are taken from the common topology data set Internet Topology Zoo[36],which is used to study the SDN controller deployment in many works.We select two different scale network topologies:OS3E(small-scale topology,N <100),RF-II(large-scale topology,N ≥100),as shown in Table 1.

Table 1.Experimental topology.

In order to simulate the real network traffic,we consider that the flow request rate of switch follows Poisson distribution,and parameterλ∈(0,40]kreq/s.Since different types of controllers have different capacities and vulnerability numbers[24,28],the heterogeneity parameters of the controller(controller capacityωkreq/s,vulnerability numberV U,attacker prior coefficientζ)are set to NOX(80,32,0.1),Ryu(130,36,0.1),Floodlight(190,55,0.3)).During the simulation,we try to set different parameters for the proposed algorithms.On the premise of not affecting the experimental results,the population size of the genetic algorithm is 20 times of the number of nodes,the maximum iteration is 100,and the crossover and mutation probabilities are 0.3 and 0.2,respectively.All the experiments were run 100 times to eliminate the experimental error.

5.2 Simulation Results

We evaluate the safety and reliability of the proposed approach from the following three aspects(control plane fault rate,attack success rate,and network delay).

5.2.1 Control plane fault rate

Figure.5 shows how the control plane fault rate varies with the number of probe attacks under different topologies,where the type of heterogeneous controllerU(1≤U ≤3)changes.We suppose that one single controller will fail with probabilityP=1−e−V U(u)·tafter being exploited by an attacker,whereV U(u)is the number of vulnerabilities of controller with typeuandtis the number of probe attacks.The control plane fault rate is calculated based on Eq.(16).Compared with Figure.5(a)and(b),it can be seen that with the expansion of topology size,the control plane fault rate will also increase.Because the increase of network nodes expands the attack surface.However,regardless of the topology size,heterogeneous controller types significantly affect the control plane fault rate.WhenU=1,only a single type of controller(homogeneous controller)was deployed in the network,and the attacker could crash the whole control plane with fewer probe attacks.With the increment ofU(types of heterogeneous controllers),malicious attackers must launch more probe attacks to crash the control plane.This is because heterogeneous controller deployment eliminates common-mode fault,which increases the attack difficulty.Hence,the proposed heterogeneous controller deployment can effectively reduce the control plane fault rate.

Figure 5.Control plane fault rate.

Next,based on OS3E topology,we also observed the control plane fault tolerance rate by changing the types of heterogeneous controllers in the network.The control plane fault tolerance rate is defined as the percentage of available controllers in the total number of controllers when suffering from malicious attacks.When deploying controllers,SRHCD is compared with the controller deployment approach based on theoretical optimality(abbreviated Optimal)and the controller deployment based on random selection(abbreviated Random).The results are shown in Figure.6.WhenU=1,all controllers in the network are homogeneous.The performances of the three schemes are the same.With the increase of the types of heterogeneous controllers,the control plane fault tolerance rate is improved,and the maximum improvement is achieved whenU=3.This is because the heterogeneous controllers can effectively mitigate the common-mode fault among controllers.One controller fault caused by malicious attacks will not affect other types of controllers.Benefiting from the designed three algorithms,SRHCD performs much better than Random approach and is close to Optimal approach.

Figure 6.Control plane fault tolerance rate.

5.2.2 Attack success rate

In this experiment,the attackers randomly send probe packets to scan controller vulnerabilities,and then attack the controller.We assume that the attackers do not know the deployment of the controllers in the network in advance,they randomly select the target controller.The attackers can exploit the vulnerability and attack the corresponding controller only after probing the vulnerability successfully.Figure.7 shows how the attack success rate varies with the number of probe attacks under different topologies.First,from Figure.7(a)and(b),as the topology scale increases,the attack success rate also increases under the same probe attacks.However,whether in OS3E or RF-II topology,the increase of types of heterogeneous controllers(U=1 toU=3)will significantly affect the attack success rate.The more heterogeneous controller types,the lower the attack success rate.

Figure 7.Attack success rate.

5.2.3 Network delay

In this experiment,based on different topologies,we firstly test the switch-controller delay,and record the inter-controller delay.We compare SRHCD with the two latest controller deployment approaches(RCCPP[10]and RDSDN[14]).RCCPP clusters the network nodes based on the propagation delay between nodes and deploys the controllers in the cluster centers; RDSDN selects the nodes with the most intersecting paths to deploy the controllers by considering the link utilization and load balancing metrics.In order to ensure the fairness of the experiment,it is assumed that RCCPP and RDSDN also deploy the same heterogeneous controllers(for example,U=3).

Figure.8 shows the cumulative distribution function(CDF)of switch-controller delay under different topologies.In the small-scale topology OS3E(as shown in Figure.8(a)),the delay difference between RCCPP and SRHCD is small,but they are better than RDSDN.This is because the controllers are deployed in the center of the network by RDSDN,and the boundary nodes will have a long delay with the controller.With the enlargement of topology size,the delay between nodes increases,and RCCPP only considers network delay,which cannot guarantee the optimal controller deployment.In RF-II topology(as shown in Figure.8(b)),the switch-controller delay gap between RCCPP and SRHCD becomes larger.Compared with the RCCPP and RDSDN,SRHCD can reduce switchcontroller delay by 16.5%on average.

Figure 8.Switch-controller delay.

Figure.9 shows the inter-controller delay under different topologies,which considers homogeneous and heterogeneous controller deployments.When deploying homogeneous controllers(U=1),SRHCD is always superior to the other two approaches in OS3E and RF-II topologies.This is because that SRHCD optimizes the end-to-end delay and effectively reduces the delay between controllers.It also shows that SRHCD can reasonably deploy controllers to ensure reliable inter-controller communication in the network.When deploying heterogeneous controllers(U=3),the delay between controllers increases.This is because different types of controllers have different design patterns.When heterogeneous controllers interact with east-west interfaces,they will need time for message synchronization.Even so,the inter-controller delay of SRHCD(U=3)is only about 14.9%higher than that of RDSDN(U=1).

Figure 9.Inter-controller delay.

The above three experiments show that SRHCD can effectively improve the safety and reliability of the control plane.Although the heterogeneous controller deployment inevitably increases the communication delay between controllers,the produced costs can be further reduced by optimizing the state interaction and synchronization between controllers.Therefore,the tradeoff between delay cost and safety is acceptable.

VI.CONCLUSION

This paper proposes a safe and reliable heterogeneous controller deployment(SRHCD)approach to solve the common-mode fault of homogeneous controllers in the existing controller deployment schemes.Firstly,we identify the type and number of heterogeneous controllers required for the network based on dynamic programming.On this basis,we divide the network into multiple subnets by the k-means algorithm and improve the genetic algorithm to optimize the heterogeneous controller deployment in these subnets to ensure reliable switch-controller communications.Experimental results show that SRHCD can decrease the control plane fault rate and improve the reliable communication of the network effectively.Besides,SRHCD can be applied to different topologies.

In future work,we will pay more attention to the consistency synchronization between heterogeneous controllers to further optimize deployment.

ACKNOWLEDGEMENT

This work is supported by National Key Research and Development Project of China(No.2020YFB1804803),National Natural Science Foundation of China(No.61802429,61872382).