2.1

Problem description

Currently, there are mainly two solutions for SDN controller network failure in the form of backup and recovery protection, namely active protection as shown in Figure 2, and passive protection in Figure 3¹⁴. Active protection means that all underlying switches maintain a control path with all controllers and each controller sends the same control instructions to all switches, each of which selects one of the controllers as its corresponding authorized controller through a certain strategy. In the event of a controller or switch failure that may cause the control network to fail, the protection strategy can ‘automatically’ ensure that at least one controller of each switch is connected to it.

Figure 2.

Active protection.

Figure 3.

Passive protection.

Accordingly, passive protection means that each switch maintains a control path with only one of the controllers, which can be referred to as an authorized controller. The authorized controller interacts with the switch and synchronously copies the interactive information to the backup controller. At this time, if the main authorized controller fails and causes the control network failure, the switch ‘passively’ switches its authorized controller to the backup controller. Passive protection can also be enhanced by adding an additional shared data server outside the control network. In this case, the information between the main authorized controller and the corresponding switch does not need to be synchronized with the backup controller, but is stored on the shared database server. If the main authorized controller fails, the backup controller receives this information from the server and restores control of the ‘lost’ switch. This method eliminates the need to exchange information between controllers and individual backup controllers, significantly reduces traffic between the controller and its backup, and effectively improves backup efficiency.

In this paper, we consider a passive protection method in which the deployment location of the backup controller is selected according to the number of backup controllers when the failure of the underlying switching network causes a chain reaction of disruption in the control network to ensure that the reliability of the control network is guaranteed and realized to a certain degree. The selection of the number of backup controllers is mainly based on the reliability index and the cost of building links and nodes required for the backup controller. In this paper, we assume that the number of controllers is already fixed.

For the underlying SDN switching network, we first deploy different controllers according to a certain deployment strategy in different application scenarios without considering the controller backup, and divide the whole network into a certain number of control domains. Considering possible multiple failures of the underlying switching network, we then build the reliability model of the backup controller deployment network to evaluate the recovery strategy. Currently, the common recovery model indicators for multiple failures in the network are node degree, betweenness centrality, and adjacency centrality. These indicators suggest the importance of controlling network nodes from the network topology perspective. With this in mind, we examine the protection strategies of each network node for potential failures.

2.2

Average network reliability evaluation model for multiple faults

Based on the definition of network topology proposed¹⁵, we present a strategy for the case when one or more switching nodes fail.

In this regard, the symbol F is used to represent the node failure, and F ⊆ S. In case of failure F, all nodes s in F will be deleted from the original network G, and the edges and control nodes connected to s will also be deleted. Therefore, the network after failure F can be expressed as g(F) = (S(F),E(F)), which is the largest subgraph of G after being divided by fault F, where S(F)=S\F, and E(F)=E ⋂ S (F). Each fault F divides G into several “islands” I. the set formed by all islands is expressed as ℓ(F), for each specific island I, if node s is directly affected by fault F, then I(F,s)=∅, where s is the node in island I and I(F,s) is the island formed by fault F. Based on the above network and the constructed model, we proposed a corresponding model to evaluate the network topology (Figure 4).

Figure 4.

Island and Island collection.

2.2.1

Network Topology Evaluation Model for Multiple Faults.

For fault F, the following model has been defined in this document to evaluate the reliability of the network topology.

Equation (1) represents the number of nodes surviving fault F, equation (2) represents the number of islands caused by fault F, and equation (3) represents the size of the largest island caused by F. These models are used to evaluate the reliability of the network topology exposed to F. Further analysis shows that the above equation (1) can also be described by the average reliability of two-terminal reliability (as equation (4)):

2.2.2

Network Reliability Model for Multiple Faults.

Based on the previous network topology evaluation model, this paper proposes a model to assess the average reliability of a network:

where Coef(F,I) is a binomial coefficient. If there is at least one controller in island I, Coef(F,I)=1, otherwise Coef(F,I)=0. Therefore, NR (F) represents the fraction of switching nodes where at least one controller is connected in the network after error F.

Based on NR (F), the average network reliability model ANR(Γ) for the set Γ consisting of all faults F as elements can be defined as follow:

2.2.3

Controller Reliable Deployment Model for Multiple Faults.

Based on the above model for evaluating average network reliability, another model for controller deployment reliability has been proposed in this paper, which consists of finding an appropriate deployment scheme for the total number of M controllers to maximize the value of equation (6), as shown in equation (7):

3.1

Population guided inversed optimization sparrow search algorithm (PG-OLSSA)

Based on the models presented in the previous sections, we propose a strategy for the reliable deployment of controllers to ensure the continuity of services in case of node failures. For the numerous failures that may occur in the underlying switches, assuming that the SDN controllers have been well deployed and the number of backup controllers is given, we search for the deployment location of the backup controllers to optimize the reliability model of the network. To find the best location for deploying these backup controllers, the Population-Guided Opposite Learning Sparrow Search Algorithm (PG-OLSSA) is used to find a better solution set for the model.

As mentioned earlier, the Sparrow Search Algorithm (SSA) has the advantages of high optimization speed, low complexity, and high comprehensibility when dealing with NP-hard problems¹⁶. Nevertheless, it can easily fall into a local optimum when applied separately. In view of these shortcomings, the mechanism of Opposite Learning in SSA(OLSSA) was introduced¹⁷ to extend the optimization range and prevent the method from falling into the trap of local optimum. In this work, the optimization capability of OLSSA is further improved by using the idea of population guidance¹⁸ after considering the idea of opposite learning in the initialization of the algorithm.

The OLSSA is a revised SSA with the idea of reverse learning in the initialization phase and the population-guided procedure: The traditional sparrow search algorithm usually needs the “leading sparrows” (optimal solution) in the current best position to guide the other sparrows to move to the optimal destination to solve the unreasonable optimal solution problem caused by randomness. Therefore, the leader selection method in the current step is crucial to obtain the global optimal solution. To select the leading solutions for population management, we need to divide the whole population into different levels of Pareto fronts by non-dominant sorting. Then, we can determine the Pareto level by calculating the degree of congestion of each solution according to equation (8), and then sort all these solutions to select the best N solutions for population guidance. The congestion distance refers to the sum of the distances between a Pareto solution and its nearest Pareto solution in each objective function dimension. The larger the congestion distance, the farther it is from the current nearest Pareto solution, i.e., the Pareto solution is sparser; otherwise, it means that the position of the solution is closer to the current nearest Pareto solution and the Pareto solution is denser. By introducing the congestion distance, we can select the population formed by the optimal Pareto solution from the distribution of the Pareto solution and then guide the population find a more uniform solution set at the Pareto front.

m stands for the dimension of the objective function, S[i – 1]_(m) means that after being sorted, the value of the current solution is worse than the value of the ith solution of the objective function, and accordingly S[i+1]_(m) stands for the value of the objective function that is only better than the ith solution. and stand for the maximum and minimum value of the mth dimensional objective function, respectively.

3.2

Deployment strategy process of backup controller for multiple fault recovery

Based on the elements presented in the preceding sections, the backup controller’s multiple failure recovery deployment strategy process consists of a six-step mechanism to solve the target problems in Section 2 as shown in Figure 5, namely:

Figure 5.

PG-OLSSA strategy flow chart.

• Initialize the population by the reverse learning mechanism and calculate the fitness value of the initial population according to equation (6).

• Based on the fitness value, the first 10% of the leader’s optimal solution is used as the guide to update the position of the sparrows, obtaining the updated guide population by the reverse learning mechanism.

• Calculate the new fitness value of the updated population, as well as the Pareto level and the congestion distance.

• If the Pareto level is the same, choose the solution with the larger congestion distance.

• Following the rule above, the top 10% is selected as leaders for the next round, and the followers follow and complete the location updating.

• Continue the above cycle until the algorithm reaches the exit condition.

During this time, the vigilante performs the monitoring task according to the rules¹⁹.

4.1

Experimental environment

Due to the known limitations in simulated environments regarding SDN properties. This study uses a simulated network on the MATLAB platform¹⁵ to verify the functionality and effectiveness of our proposed strategy. The parameters of the network and network flows, such as switching nodes, physical connection, number of unknown flows, rated load, and controller load, have already been described¹⁵. Based on this, the underlying failure of the switching node is assumed to obey the Poisson distribution as a parameter λ=3. For the variable initialization of the algorithm PG-OLSSA, we set the maximum number of iterations MAXINTERATION = 15 and the population size POP_SIZE = 50, the proportion of leaders PL = 0.4, the proportion of followers PF =1- PL =0.6, and the proportion of vigilantes PA =0.1. Among the population as leaders, set the proportion of selected guides as GPL = 20%.

4.2

Simulation results and analysis

Based on the results of the simulated network and controller distribution shown in Figure 6, this paper uses the PG-OLSSA algorithm to deploy the backup controller. The results are shown in Figure 6 below. It can be seen that based on Figure 6b, the black node in Figure 6c is the deployment site of the backup controllers, which is to further improve the reliability and security properties of the control network.

Figure 6.

Deployment result of simulated network and backup controller.

Figure 7 shows the comparison between three algorithms: Standard SSA¹⁹, OLSSA¹⁷ and PG-OLSSA proposed in this paper. It can be seen that the algorithm PG-OLSSA has been optimized to some extent according to the reverse learning and population guided optimization in terms of optimization speed and optimization ability.

Figure 7.

Comparison of optimization curves.

In terms of the reliability index described in equation (6), this paper compares the reliability index obtained from PG-OLSSA and OLSSA, respectively. The results are shown in Figure 8. As you can see, the reliability index obtained by PG-OLSSA is much higher than that of OLSSA, which means that the reliability index proposed in this paper is effective.

Figure 8.

Reliability index comparison.