1 Introduction

The main property of the SDN architectures is the separation of network controllers and switches. The logically centralized controller is in charge of managing switches by supplying them rules that prescribe their packet handling manner. Indeed, in these networks, the controllers are responsible for the intricacy of creating forwarding rules [1]. Despite the fact that the controller is logically centralized in the network domain, it would be essential to be physically distributed so that some aspects like performance, scalability, resilience, and fault tolerance restrictions are met [2]. To address issues such as scalability and resilience, concepts like HyperFlow permit dividing SDN architecture into multiple domains on such a way that each one is managed by individual controllers [3]. A logically centralized controller which runs the control plane is the main part of a traditional SDN implementation, although in the deployment of a large-scale WAN, this elementary centralized method has various restrictions corresponding to performance and scalability. To cope with the mentioned issues, recent suggestions have pleaded placing multiple controllers which work concertedly to manage a network.

One especially crucial task in SDN networks is controller placement, i.e., locating a restricted number of controllers in a network so that several requirements are satisfied [4]. The controller placement problem is known to be NP-hard [5].

The previous approaches only deal with propagation latency between controllers and switches [2, 5]. However, they disregard either the inter-controller latency, i.e. the latency between each pair of controllers, or the capacities of controllers. Both of these factors are critical in the context of real networks. Although the latency between controllers and switches constitutes a crucial metric in positioning controllers properly, other objectives need to be regarded as well. Therefore, the objectives like latency between each switch and its assigned controller, inter-controller latency, load balancing and failure in nodes, links and controllers should be taken into account. Hence, the controller placement problem can be formulated as a multi-objective combinatorial optimization (MOCO) problem. Since the objectives are supposed to be pairwise conflicting, applying multi-objective approaches allow for a more obvious demonstration of the tradeoffs between possibly competing criteria [6, 7].

It is very important to detect a feasible solution for the controller placement problem. The objective is to determine where to locate a given number of controllers in the network in designing an SDN-based WAN architecture. Notwithstanding, choosing a stochastic placement of a vagarious number of controllers does not result in acceptable performance [5]. Thus, some planning have to be done in order to construct an efficient and reliable SDN, particularly making appropriate decisions for the following questions: how many controllers are required to locate, where should they be deployed, and which nodes are under control of each of them? Rather than applying estimations in this regard, the authors discuss that an exhaustive evaluation of the whole solution space, i.e. evaluating all probable placements of the controllers, is especially possible for real networks. Therefore, finding optimal placements with respect to the metrics is guaranteed. These optima can be utilized to provide guidelines for dimensioning of the control plane.

Hence, obtaining a controller placement which reflects an adequate trade-off between case related goals is critical for an effective operation. Moreover, to tackle with large networks [8], an efficient approach which is computationally fast is essential for solving the aforementioned placement problem. As illustrated in [9], POCO is already capable of doing an exhaustive evaluation of placements within a few seconds for instances with small and medium sizes. Nevertheless, performing exhaustive evaluation for large scale networks needs time budgets in the order of magnitude of tens of minutes and hours, which may not be reasonable. This work investigates heuristic approaches to solve efficiently the multi-objective controller placement problem. In spite of not assuring to obtain optimal solutions, such approaches are capable of achieving results considerably faster than their exhaustive rival. Indeed, despite the fact that performing exhaustive evaluation of all possible placements may take a reasonable time for networks whose sizes are small or medium, it is impractical for large instances which require drastically higher time and memory budget.

Exhaustive search to obtain the optimal placement(s) of the network controllers is not practical for large scale networks. Hence, alternative approaches need to be investigated for large instances. Consequently, this work introduces a heuristic approach called Multi-Start Hybrid NSGA-II (or MHNSGA-II) to solve effectively the multi-objective controller placement problem. In the context of multi-objective optimization, in most cases, a single solution that optimizes all the considered objectives may not exist. Achieving a set of solutions which are non-dominated with respect to each other, called Pareto optimal solutions, constitutes the main target of multi-objective optimization procedures. However, the exact set might not be obtained using heuristic approaches which explore only a small set of the whole search space and have the stochastic behavior within different runs. Our proposed algorithm, like any strong mechanism, is shown to be capable to find a diverse and accurate estimation of the Pareto optimal set. Comparing with the exhaustive search, this method may be less precise, but has the ability to produce results in faster computation times and needs considerably much less memory to execute. In addition, it works efficiently on tackling with both conflict objectives and for large scale networks whose search spaces include numerous number of solutions.

In summary, the following contributions are made:

  • To our best knowledge, this is the first work which proposes an adaptation of NSGA-II algorithm to solve the multi-objective controller placement problem which is known to be NP-hard in SDN.

  • Some new mechanisms which are named below are added to the adapted NSGA-II:

    • Greedy initialization procedure.

    • Fast Pareto finder process.

    • Local search.

    • Dispersion mechanism.

    • Multi- start strategy.

Results show that the algorithm obtains a very good estimation of the Pareto optimal regarding the objectives defined in [4, 7]. Comparing with POCO framework, the proposed algorithm is capable to find near optimal solutions in considerably fewer amounts of time and memory. In particular, dealing with large networks which POCO exceeds the RAM of the used machine, the efficiency of our algorithm in achieving high quality solutions with a good diversity becomes more clear.

The organization of the rest of the paper is as follows. In Section 2, a literature review of the controller placement problem is presented. The definition of this problem is brought in Section 3. In Section 4, the proposed method and its operators in a comprehensive manner are described. Simulations are presented in Section 5. The final section is dedicated to conclusion.

2 Related works

The controller placement problem has been discussed in a couple of papers. This problem is comparable with facility location problem in many aspects. Heller et al. [5] established the first study on this area. The controller placement was then considered with the objective of minimizing the propagation latency in [5, 10]. They utilized the concepts of average-case and worst-case for this type of the latency as the placement metrics discussed. Thus, in the context of location issues, the placement problem was agreeing with the K-center (or K-median) problem. According to their findings, the two mentioned latency, i.e. average and worst ones, cannot be simultaneously optimized in most topologies. Only one controller, in some cases, is sufficient to satisfy usual network requirements regarding to communications delay (apparently excluding fault tolerance). This paper didn’t provide a practical algorithm to obtain the solution, and all the optimal placements presented in the paper derived directly from evaluating all possible combinations of controller placements with respect to the considered metrics.

In most topologies, further controllers result in decreasing returns. Research of Yao et al. based on this matter led to introduce and formulate the capacitated controller placement problem (CCPP) [11]. The problem considered in the CCPP is load capacitated that differs from the famous controller placement problem (CPP). CCPP deals is comparable with the Capacitated K-center Problem. This algorithm for the deployment of the controller which is set or estimate the number of the controller cannot correctly estimate the number of controller based on the requirements.

In the context of locating controllers in SDN, paper [12] argued the problem aiming at maximizing the reliability of control networks. The paper introduced a metric to qualify the SDN control networks’ reliability, and also measure the effect of controller‘s number on the reliability of control networks. It offered greedy and Simulated Annealing algorithms to solve the problem. The work presented in [11] focused on the load of controllers and defined a capacitated controller placement problem, regarding the capacity of controllers. However, the latency among controllers was not considered.

Dynamic controller provisioning issue was presented by [8]. In this context, a Switch Migration Problem (SMP) is defined to a network utilization maximization problem which balances not only one multi-dimensional resource in each controller internally but also multi-controllers in the network. They first give a resource consuming model for SDN to describe the relation between controllers and switches.

In [10], it is supposed that the mapping which exists between a switch and a controller is configured dynamically. Regarding that, although the dynamic assignment can amend the scalability and reliability when the controller is being deployed in LAN, it is not appropriate for Large-scale networks. Lange et al. 2015 [4] has offered an elastic distributed SDN controller.

Various methods for multi-objective facility location have been presented in literature [13, 14]. Nevertheless, the main concentration of most of these studies is optimization methods suitable for particular predetermined sets of objectives instead of presenting generic heuristics. In [6] and [7], the Pareto-Optimal Controller Placement (POCO) framework is proposed to develop Heller et al.’s work [5] with the aim of considering further aspects except network latency. Particularly, some metrics like node to controller latency, controller to controller latency, load balancing (with defining an imbalance concept) among controllers, and resilience have been explored. Considering scenarios containing the failure of at most two vagarious links or nodes, these metrics are utilized in order to evaluate and analyze all the solution space for placements with k controllers. In other words, at the first step, all possible placements including k controllers are created. Then, the trade-offs among the aforementioned metrics are studied. However, this framework could not be implemented for large scale networks.

As a recent work in this context, Lange et al. [4] developed the POCO framework by adding some heuristics to enable it to work for large-scale networks. In their work, POCO does not impose any determined reliability threshold that must be satisfied for paths between nodes and controllers. Alternatively, the authors concentrated on at most two failure scenarios happening in nodes and links. Hence, the operational probability of each switch, link, and controller was not taken into consideration in their formulation. Furthermore, the desired number of controllers (k) which should be deployed in the network was considered as an input parameter in this framework. Meta-heuristics such as the presented Pareto Simulated Annealing (PSA) enable adding vagarious objectives into the evaluation and are not restricted in terms of the number of objectives considered during optimization. They just need a function that maps placements of the search space to their performance considering an especial metric.

Although strategies belonged to evolutionary algorithms’ category [15, 16] have the capability to implement them for multi- objective optimization, these techniques usually suffer from getting trapped in local Pareto optimal solutions. PSA decreases this risk via accepting some worse placements, with respect to the regarded metrics, but it still obtains convergence by utilizing a time dependent acceptance probability. This work motivated us to work on heuristics in order to design stronger algorithm with better search properties.

As the base of our proposed algorithm, Deb et al. [17] proposed a fast and elitist multi-objective algorithm, called NSGA-II. This procedure has some concepts like fast non-dominated sorting, crowding distance, crowded-comparison operator, and elitism mechanism. NSGA-II was very efficient population-based algorithm to solve multi-objective problems. Elitism through non-dominated sorting the population and diversification by using the crowding distance mechanism made the algorithm very powerful to find the Pareto front of multi-objective continuous problems even with non-convex and non-connective Pareto optimal fronts.

Although, regarding our implementation, the adapted NSGA-II for the multi-objective controller placement problem introduced in [4] obtained better results than the PSA on some topologies extracted from Internet Topology Zoo [18], to improve its dispersion and quality of achieved solutions, a Multi- start Hybrid NSGS-II is proposed. This algorithm benefits from fast non-dominated sorting and elitism mechanisms from the original algorithm. In addition, some new aspects like a greedy initialization procedure, a fast Pareto finder process, two powerful strategies including a Reinforcement mechanism as well as a local search for improving the quality of best solutions in the current populations, and a dispersion mechanism based on [19], are cooperated in a multi-start procedure.

Adding the mentioned features made the adapted NSGA-II significantly more powerful to find an approximation of the original Pareto optimal which coincides it in many case studies during different implementations. To sum up, POCO and the algorithm presented in this paper solve the controller placement as a multi-objective combinatorial problem considering the same objectives. Despite the fact that the POCO framework requires drastically growing RAM to run, our proposed algorithm can solve the problem for very large networks consisting of tens of millions possible placements in their search space consuming insignificant memory budget as well as very low CPU times. Furthermore, the obtained solutions shown to have high quality with respect to the considered metrics and to be well distributed during a single run.

3 Problem definition

The controller placement problem deals with location of controllers with respect to the available network topology and the required number of controllers. The user may define various metrics that control the placement of the controller in a network. While minimizing latencies between each node and its assigned controller constitutes a crucial aspect of the controller placement problem, there are numerous other, possibly competing, objectives that require consideration such as node or link failure, controller to controller latency and load balancing.

As discussed in the Section 2, the objectives first introduced in [4] and [7] are considered. These metrics have been used to constitute a multi-objective controller placement problem. The network is represented a graph G = (V E) where V is the set of n nodes, or switches which are connected by the links, or edges, from the set E Furthermore, a distance matrix D contains the shortest path latencies between each pair of nodes where d i j indicates the latency between node i and node j. Latencies in D are normalized with the largest d i j in the matrix, i.e. the graph’s diameter. The desired number of controllers, denoted by k, is supposed to be known before starting to solve the problem. Therefore, the discrete search space contains \(\left (\begin {array}{cc} {n}\\{k} \end {array}\right )\) placements. A placement is a k-element subset of n nodes. For example, given a topology with 34 nodes, when the desired number of controllers to be located in the network is k = 5, the subset P = {2,9,18,23,30} represents a placement with five controllers, i.e. |P| = 5, locating at the sites of 2, 9, 18, 23, and 30. Since changing the position of the elements in the subset does not produce any new combination, the number of all possible placements in such a network is \(\left (\begin {array}{cc}{34}\\{5}\end {array}\right )\). In addition, the set including all subsets with k elements, i.e. the set of all possible placements, is called the search space of the controller placement problem. Therefore, the target of the controller placement problem is to find the Pareto optimal set of the whole search space, consisting of all the placements P of size k, i.e. |P| = k Given a set of objectives, or metrics, {f 1, f 2,…, f m } which are going to be minimized, a placement P is called Pareto optimal if and only if there is no other placement Q in the search space such that f i (P) ≤ f i (Q) for all i ∈ {1,2,…,m} and f i (P) < f i (Q) for at least one index i The set of objective values of all Pareto optimal placements with respect to the metrics is considered as Pareto frontier (PF).

It should be noted that the POCO framework does an exhaustive evolution including the assessment of the whole search space of \(\left (\begin {array}{cc} {n}\\{k} \end {array}\right )\) placements. Therefore, due to extremely high memory and time requirements for large scale networks to implement the POCO, switching to heuristic approaches is preferable. However, switching to this approach may degrade the accuracy of solution. For measuring this quantity, different measures for calculating the difference between the actual and the approximated Pareto frontier have been adopted from [4].

3.1 Objective functions

Several competing objectives are required for evaluating each of the placement P of controllers. The metrics defined in (1) and (2) represent the maximum and average node to controller latency, respectively.

$$\begin{array}{@{}rcl@{}} {\pi}^{L\_max\_N2C}\left( P\right)=\underset{v\epsilon V}{\max}~\underset{p\epsilon P}{\min} ~d_{v,p} \end{array} $$
(1)
$$\begin{array}{@{}rcl@{}} \pi^{L\_avg\_N2C}\left( P\right)=\frac{1}{\left| V \right|}\sum\limits_{v\in V}\underset{p\epsilon P}{\min}~ d_{v,p} \end{array} $$
(2)

Equations (3) and (4) define the metrics for measuring the maximum and average inter-controller, or controller to controller, latency, respectively.

$$\begin{array}{@{}rcl@{}} {\pi}^{L\_{\max} \_C2C}\left( P \right)=\underset{p1,p2\epsilon P}{\max}d_{p1,p2} \end{array} $$
(3)
$$\begin{array}{@{}rcl@{}} {\pi}^{L\_avg\_C2C}\left( P \right)=\frac{1}{\left( {\begin{array}{cc} \left| P \right|\\ 2\\ \end{array}}\right)} \sum\limits_{p_{1}{,p}_{2}{\in p}} d_{p_{1}{,p}_{2}} \end{array} $$
(4)

When the reliability of a network operation is important, besides the metrics corresponding the latency which try to find short communication paths, other metrics like the controller load balance are required to be considered as well. In [4] the imbalance metric is introduced instead of a balance metric and the goal is minimizing the metric’s value. Considering the rule that each node connects to its closest controller, then for each controller placement P and controller p in P,n p denotes the total number of nodes assigned to p. The imbalance metric π imbalance is defined as the difference in n p for the two controllers whose number of assigned nodes are the lowest and highest, respectively, as can be seen in (5).

$$\begin{array}{@{}rcl@{}} {\pi}^{imbalance}\left( P \right)=\underset{p\epsilon P}{\max}~n_{p}- \underset{p\epsilon P}{\min}~n_{p} \end{array} $$
(5)

3.2 Performance metric

In our notation, R denotes the actual Pareto frontier which is used as reference, and M signifies the approximated of the Pareto obtained by the heuristic approach. The inverted generational distance (IGD) [28] is applied to measure the performance of the algorithms in our evaluations. As used in [26, 27], we adapted this metric for our problem as:

$$\begin{array}{@{}rcl@{}} IGD\left( R,M \right) = \frac{{\sum}_{y\in R} {d(y,M)} }{\vert R\vert} \end{array} $$
(6)

Where d(y M) is the minimum Euclidean distance between y and the elements in M. I G D(R,M) is capable to measure both the diversity and convergence of M.

4 Multi-start hybrid non-dominated sorting genetic algorithm-II (MHNSGA-II)

In this section, the fundamentals of our algorithm are described in details.

The input consists of three main parts. Firstly, the problem specific data like the topology graph G and the desired number of controllers k. Secondly, this algorithm uses some parameters which should be initialized first. The probability of crossover, mutation, and local search are represented by pc, pm, and pl, respectively. MaxIt is used for the maximum number of iterations and the parameter imit shows the number of inner repetitions in the replace procedure. The parameter tt is the tabu tenure, the length of the tabu list described later. The final input part is devoted to dispersion parameters.

The parameter ε determines the dispersion’s threshold. An improve is said to be achieved when the difference between the values of IGD for two successive iterations is less than or equal to ε. Two parameters called wic and maxwic are used as without improvements counter and the maximum number of iterations without improvements, respectively. After each maxwic consecutive iterations without improvements, the parameter ri calls the dispersion strategy.

The algorithm is summarized in Fig. 1. First the non-dominated solution set, called M, obtained among all placements from start till the current iteration of the process is defined as an empty set. The initial population is generated by GreedyStart mechanism (see Section 4.1). In each iteration of the algorithm, after finding the first (best) front of the population, or F 1,by ParetoFinder, (see Section 4.2), procedures LocalSearch try to improve the quality of solutions in the first front (see Section 4.3). NonDomSorting (see Section 4.4) and Similarity processes (see Section 4.5) are then performed to rank and calculate the similarity measure of the population, respectively. Mutation is applied to search in vicinity of the solutions to find hopefully better solutions (see Section 4.6). Then M is updated (see Section 4.7).

Fig. 1
figure 1

Flowchart of proposed method

Full size image

In the following, all parts of the algorithm are described comprehensively.

4.1 Construct initialization (Greedy Start)

In this paper, since k controllers are supposed to be placed in the network, a k-vector is used to represent each solution. Many optimization algorithms use completely randomized strategies to generate initial solutions and focus mainly on moving to better solutions in each cycle. However, designing an appropriate initialization procedure can lead to a long movement towards a promising area of the search space. A smart greedy mechanism is designed and implemented here. First, NP number of different node numbers is selected randomly.

For each one, the following mechanism is implemented to construct a complete placement, and hence, NP placements will be generated. After determining a random node number, it is fixed in the first position and creates a partial placement. The other node numbers are placed in the second position one after another. For each one, the created partial placement is assessed by an evaluation function which is defined as the sum of the predefined objective functions. Then the best two-element partial placement is captured. It makes sense because a multi-objective problem is implicitly converted to a single objective and minimized. Hence, the solution is chosen greedily. In each part, the process looks for the best possible partial solution found so far, without considering what is going to happen for this solution in the next steps to complete. Note that a placement with a low value of this sum function is hopefully located near a Pareto solution or at least is better than a totally random generated solution. This process continues to find a promising complete placement.

The mentioned mechanism is repeated NP times to generate the initial population of size NP. Figure 2 illustrates how the greedy start works to produce the initial population. It should be noted that function Search (P, i) returns 1 if node number i exists in a position of placement P and 0 otherwise. In addition, SumFunc represents the sum of the objective functions.

Fig. 2
figure 2

The pseudo code of the greedy start

Full size image

4.2 Pareto finder

A fast scheme is designed and applied to identify the set of non-dominated solutions in the current population, as output of the function ParetoFinder. The indices of these solutions are recorded in the set F1. This function works as follows. Each solution is compared with other solutions in the population with respect to dominancy concept. If the current solution dominates another, the dominated one is recorded in a set called Dominated Set. However, if the current solution is dominated by another one, the current is moved to the set and process of considering this solution is stopped and the procedure shifts to other solutions not located in the set. All the solutions placing in this set will not be visited in the rest of the process. Finally, the solutions which do not belong to this set construct the first front F1. Figure 3 shows this mechanism.

Fig. 3
figure 3

The pseudo code of Pareto Finder procedure

Full size image

4.3 Local search procedure

LocalSearch

implements the mentioned replace procedure in a different manner. First, for each placement in pop (F1), k neighbors are produced by replacing a random number in the k possible of its positions. Next, all the non-dominated neighbors with respect to the placement are stored in a set. Then, all the dominated solutions of this set are removed and the set is returned. Population pl consists of all these non-dominated solutions and is added to the main population. By using this mechanism, indeed, some non-dominated solutions with respect to the current best Pareto front are created. Since these solutions are not dominated by the best placements in this iteration, some new good solutions are produced. Therefore, by passing the algorithm, more and more non-dominated solutions are generated and their qualities are modified by the Reinforcement procedure. In other words, the movement towards the real Pareto optimal is more emphasized. Figure 4 illustrates how this procedure works. As can be seen from the pseudocode, the input consists of a placement P and its objective vector PCost. Output of the procedure involves a population of non-dominated solutions with respect to P and their objective vectors, poploc and poplocCost respectively.

Fig. 4
figure 4

Pseudo-code of LocalSearch procedure

Full size image

4.4 Non-dominated sorting

A fast non- dominated sorting [20] is used to classify the population individuals into different fronts. The solutions which are not dominated by any other solutions in the population are placed in the first front, or F1. The second front F2 includes the non-dominated solutions after removing F1 from the population. By continuing this trend, all the population members are partitioned in different fronts. As mentioned before, the first front F1, therefore, includes the indices of the best front or non-dominated solutions in the population.

4.5 Similarity mechanism

For population-based evolutionary algorithms like genetic algorithms, a key factor that plays important role in their prosperity is how to manage and keep diversity in the population. It is crystal clear that if the diversity strategy does not work well during the run of the algorithm, a premature convergence is likely to happen. In other words, the algorithm is supposed to seek for good solutions in limited portions of the search space. For designing a powerful optimization algorithm, making a balance of the trade-off between exploration and exploitation must be taken into account [21]. In addition, when it comes to multi-objective algorithms, the output population should provide a close approximation of the whole real Pareto front. Hence, the individual must spread enough through the Pareto.

To implement and adapt this with their encoding, Garcia-Najera et al. [22] and Tang Lin et al. [23] used a similarity measure which was designed based on Jaccard’s similarity coefficient that measures the similarity of two sets as the ratio of the cardinalities of the intersection and the union of those sets [19].

This measure is adapted with our algorithm in this way: The similarity measure is a real number in the interval [0,1]. If two placements are identical, the similarity equals to one, the maximum similarity. On the other hand, if they do not have any node number in common, the minimum similarity, i.e. 0, is achieved. For two placements P and Q, the similarity measure is defined as follows:

$$\begin{array}{@{}rcl@{}} S\left( P,Q \right)=\frac{card\left( P\cap Q \right)}{card\left( P\cup Q \right)} \end{array} $$
(7)

It should be noted here that, the denominator of (10) represents the cardinality of distinct node numbers in the union set of the P and Q. For a fixed placement P, the mutual similarity measure (7) should be calculated between P and other placements in the population, except for P. Afterwards, the similarity of placement P to other placements in the population pop is determined as follows:

$$\begin{array}{@{}rcl@{}} Similarity \left( P \right)=\frac{1}{card\left( pop \right)-1}\sum\limits_{Q\in pop\backslash{P} \left\{ P \right\}} {S(P,Q)} , \end{array} $$
(8)

Similarity-Comparison Operator:

The Similarity-comparison operator (≺ r s ) guides the selection mechanism toward a diverse set of solutions. Here, two attributes for each individual, or placement, p in the population is supposed:

  1. 1)

    non-domination rank (p r a n k );

  2. 2)

    similarity measure (p s i m i l a r i t y ).

Now, a partial order ≺ r s is defined as follows:

$$\begin{array}{@{}rcl@{}} &&p{\prec}_{rs} q \Longleftrightarrow \left( p_{rank}< q_{rank} \right) or \left( \left( p_{rank}= q_{rank} \right) and\right.\\ &&\left.\left( p_{similarity}<q_{similarity} \right) \right) \end{array} $$

That is, between two placements with differing non-domination ranks, the solution with the lower (better) rank is preferred. Otherwise, if both placements belong to the same front, i.e. have the same rank, the solution which is more dissimilar to the rest of the solutions wins this competition. For the case that the two attributes are the same for both placements, a random choice is done to select one.

4.6 Mutation:

In this section, the mutation strategy is described. First, the Triple- Tournament -Selection is applied to choose a parent placement. Next, a random number is generated in the interval [1, k/2], where, [k/2] represents the integer part of k/2.This number represents the number of positions, in the parent placement, whose values should be changed.

This modification allows for more diversity in the created children [17]. Next, all the selected positions are replaced with random node numbers and a child is generated.

4.7 Updating M:

After performing the mutation, the non-dominating mechanism is executed and population is ranked and partitioned into different fronts. The first front of the current population is added to M and then M is updated by removing all the dominated solutions. Note that, after adding new solutions, some of them may be dominated by other members existed in M and hence, discarded from M. Some of the new solutions may dominate some existing placements in M and remove them. It is also possible that a particular added solution is non-dominated with respect to all members in M, and therefore, it is maintained.

4.8 Maximum evaluated placements

Although the exact number of distinct placements evaluated by a heuristic approach may not be determined beforehand, by using (9), it is possible to set an upper bound for this quantity for the MHNSGA-II.

$$\begin{array}{@{}rcl@{}} MEP=\!\!\!\!&&\left( ncross\ast \left( k + 2 \right)+nmute\right.\\&&\left.+\left( nlocal\ast imit\ast k \right)+nlocal\ast k \right) \end{array} $$
$$\begin{array}{@{}rcl@{}} \!\ast\! MaxIt\,+\,\left( n\,-\,k\,+\,1 \right)\!\ast\! NP \,+\,\!\left[\!\frac{MaxIt}{maxwic} \!\right]\!\ast\! \left( n\,-\,k\,+\,1 \right)\!\ast \!NP\\ \!\end{array} $$
(9)

Maximum Evaluated Placements (MEP) consists of up to n c r o s s ∗(k + 2) distinct placements created by crossover operator, i.e. ncross is the number of solutions attend the crossover procedure, i.e. k children is generated from path relinking strategy and 2 children from Cross-Controllers process. The number of placements participate in mutation is nmute and in each implementation of this operator, one child is created. The third statement in (9) is an upper bound for the solutions generated during Reinforcement procedure. In each run of this process, a candidate placement with k positions is changed and up to k distinct children are produced. Since this trend is repeated imit times and the whole process of Reinforcement strategy is implemented nlocal times, n l o c a l ∗ i m i t ∗ k represents an upper bound for the number of distinct placements which are evaluated during Reinforcement procedure. The fourth statement in (9) returns to the L o c a l S e a r c h process. In each implementation of this function for a candidate placement, at most k potential distinct solutions are generated. Since this trend is repeated nlocal times, n l o c a l ∗ k shows an upper bound for distinct placements evaluated by the local searchLocalSearch. These processes are repeated MaxIt times during the run of the algorithm. (n − k + 1) ∗ N P or (n − (k − 1)) ∗ N P refers to the number of placements, at most, created in the greedy start or initialization process. Here NP denoted the number of individuals in the population. The final statement represents the number of upper bounds for placements generated by calling the multi-start procedure. In a pessimistic case, when after each maxwic iterations the algorithm is not able to reach a good estimate of the actual Pareto and has to restart the process, \(\left [\frac {MaxIt}{Maxwic} \right ]\) times the greedy start is called and each time at most (n − k + 1) ∗ N P distinct placements are created. Here, [x] denotes the greatest integer number which is lower than x.

5 Experimental study

In this section, different aspects of the algorithm’s performance are investigated. First, some evaluation techniques are described to find parameters of the MHNSGA-II in order to satisfy some accuracy constraints. Next, the resource constraints, i.e. time and search space, are taken into account for comparing the MHNSGA-II with POCO frame work and also analyzing the performance of the MHNSGA-II in solving several problems with various sizes. Finally, focusing on the performance metric IGD, the behavior of this metric within several evaluations is investigated.

5.1 Algorithm setting

All the experiments are run on an Intel Core i7 CPU at 4 GH and 16 GB RAM running Windows 7 and Matlab version 2014a. Now, a strategy to choose the parameters of MHNSGA-II algorithm is described in detail.

With the objective of analyzing the performance of the MHNSGA-II, several evaluation patterns are carried out. More importantly, the main concentrate lies on determining the trade-off between the time that is saved while applying the heuristic approach and the loss with respect to accuracy which is entailed. For reaching this target, firstly, a large number of network topologies from the Internet Topology Zoo [18] are selected and evaluated through the POCO framework in an exhaustive manner. The results are used as reference for measuring how much the accuracy of our proposed method is. By changing the input parameters of the MHNSGA-II algorithm and also by investigating its behavior in terms of various topologies and number of controllers, helpful guidelines are deduced. Recoding these finding allows for expressing the particular requirements for operators of the algorithm with respect to accuracy needs and time restrictions.

The evaluation scheme is as follows. First, the combinations of topology sizes and number of controllers for which the POCO framework can be implemented to run exhaustive evaluation without exceeding the RAM of the applied machine are determined. These scenarios which determine the highest amount of time and memory budget to run the POCO routine indicate the use cases for which the decision makers have to refer to heuristic methods to cope with time and memory constraints.

Then, parameters for the MHNSGA-II algorithm are identified for various target specifications related to accuracy and reliability. Each specification is shown by triples comprising of the reference metric IGD as defined in Section 3, a threshold τ for IGD, and f m i n , and the fraction of instances in which IGD is below τ . With this specification, parameters for the MHNSGA-II process are computed as follows. In this work, an exact parameter tuning to find optimal values for the parameters for a typical specification is not performed, due to large number of parameters and their combinations. If it happened, parameters with fewer values may be obtained and the following results may be achieved significantly better. Hence, only an upper approximation for our algorithm parameters so that the features of the specifications are satisfied is used. Given a guess for the values, MHNSGA-II is applied to the problem instance 30 times. For each of the repetitions, the difference between the obtained Pareto frontier from the heuristic and the original Pareto frontier returned by exhaustive evaluation is calculated with respect to the metricIGD. If the percentage of instances for which IGD is not more than τ is beyond f m i n , the current parameters of the MHNSGA-II algorithm are recorded. If not, the search for new values of the parameters continues with manipulating them until the impose constraints are satisfied. Comparing with [4], our parameters are not at the smallest possible level.

5.2 Relative time and search space

After setting the parameter values, some performance statistics are captured as well. On the one hand, the time usage of the exhaustive evaluation of POCO routine is compared with that of MHNSGA-II. First, the times for running both methods for an instance are recorded as t MHNSGA−II and t POCO Note that, absolute times depend on the used hardware and hence are difficult to interpret. This issue is coped with combining both values into a ratio \(t_{ratio}=\frac {t^{MHNSGA-II}}{t^{POCO}}\) This value indicates the rate achieved by MHNSGA-II relative to the exhaustive method. On the other hand, the fraction of the search space which is explored with MHNSGA-II algorithm is captured to determine possible relationships between this fraction and the resulted performance. Particularly, in the case of selecting parameters for network topologies for which no actual Pareto front as reference values are available, this allows for logical settings for MHNSGA-II. As described in the previous section, (9) determines an upper bound for distinct placements evaluated by MHNSGA-II in a single run. This quantity is denoted as b MHNSGA−II and is considered as budget[4]. Similarly to those for runtime analysis, \(b^{POCO}=\left (\begin {array}{cc} {n}\\{k} \end {array}\right )\) denotes the budget, all the possible placements in the search space, requirement of POCO and \(b_{ratio}=\frac {b^{\mathrm {MHNSGA-II}}}{b^{POCO}}\) indicates the relative budget.

For all regarding scenarios, the parameter k that denotes the desired number of controllers which is to be located is supposed to be known in advance. Therefore, the presented evaluation scheme concentrates mainly on the relationship between the size of the search space and the achieved performance.

All evaluations are implemented with respect to the same set of objectives, called node to controller latency, controller to controller latency, and controller load imbalance. This configuration leads to a total number of five objectives as average and maximum values are optimized for the latency measures.

5.3 Results

According to the evaluation strategy for algorithm setting introduced in Section 5.1, calculations with various specifications are carried out. For better comparing of the two considered approaches, trade-offs between the consumed computational effort and the achieved accuracy are investigated. Furthermore, guidelines considering the selection of algorithms and input parameters for the MHNSGA-II algorithm are resulted from the analysis of real world databases.

When it comes to solving the controller placement problem for a topology consisting of tens of millions placements for which performing the exhaustive evaluation requires a considerable amount of time and memory budget, our proposed heuristic approach is an appropriate choice.

As described before, for such large scale instances, it is only possible to calculate an upper bound for evaluated placements and nothing can be expressed about the obtained accuracy with performing the heuristic algorithm. This is due to not being able to compute the actual Pareto optimal solutions and hence the absence of reference data to compare. An evaluation including 40 graphs from the Internet Topology Zoo is carried out. For each graph, four distinct numbers of controllers are examined ranging from 5 to 15, based on the graph’s size. With graph sizes ranging from 25 to 50 nodes, these scenarios reflect search spaces including between one and 100 million different placements.

5.3.1 Relative search space analysis

Figure 5 demonstrates outcomes of this evaluation. The seven values written in the horizontal axis represent bins’ thresholds. The first bin contains all scenarios for which the search space contains up to 2,000,000 placements, the second bin comprises of all scenarios for which \(2,000,000< \left (\begin {array}{cc} {n}\\{k}\end {array} \right )\le 4,000,000\) and etc.

Fig. 5
figure 5

Size of search space and corresponding relative budget required in order to achieve various performance levels

Full size image

The vertical axis illustrates the relative budget required consumed to obtain the performance targets determined by each of the specifications of the graph, i.e. each triple (I G D,τ,f m i n ) In this evaluation, it is supposed to τ = 0.008 or 0.005 for the precision threshold, and f m i n = 70 or 80 as the fraction of desired instances as described in the previous section. The height and color of each bar demonstrate the mean value of the relative budget in the evaluations of each category and each precision specification, i.e. as represented by each of four triples, respectively. Taking a glimpse to the graph makes clear that the search spaces consisting of less than 2 million placements consume a significantly higher degree of relative budget than six other categories with larger search spaces. This trend is followed when comparing each category with the others located in its right hand side. It can be deduced that for instances whose search spaces are not very large, POCO and MHNSGA-II evaluate closer number of placements. By moving to the right of the graph, the falling rate of the heights is becoming considerably more noticeable. To sum up, the efficiency of our algorithm is more highlighted when it comes to solving extremely large instances. Indeed, for small instances, POCO is a good choice to solve the controller placement problem. However, for very large network topologies, the method should be changed to the heuristic approach which needs reasonable budget. Considering the graph in more detail, another aspect of MHNSGA-II becomes clear. If the bars for each bin are partitioned in two groups, some interesting guidelines will be achieved. For each bin, the bars related to τ = 0.005, as the first group, are standing upper than those counterparts corresponding to τ = 0.008, as the second one. It shows that for achieving results with more precision, higher level of budget should be paid. However, comparing the two bars in each group confirms that improving the accuracy by changing f m i n from 70% to 80% of instances, will not impose a drastic rise in the evaluated placements. It should be noted here that, although two really small values are considered for the threshold τ, the resulting Pareto optimal sets from MHNSGA-II have very good accuracies. Furthermore, this strict decision for our accepting criteria has followed with an estimated of the parameter values of the algorithm. For example, considering τ ∈ {0.01,0.02} and minimal values for our algorithm parameters are calculated, the resulting relative budget bars’ height will certainly decrease. This is again shows efficiency of the MHNSGA-II in providing an estimation of the actual Pareto optimal set with a very high degree of accuracy.

5.3.2 Relative time analysis

In the following, the time required for both exhaustive evaluation of POCO and MHNSGA-II are measured in a relative fashion so that the results are not dependent to the machine used. Again the scenarios which are explained in the first part of this section are used as case studies.

Figure 6 illustrates the outcomes of these evaluations regarding the seven described categories of instances As for the space budget graph, the horizontal axis depicts the search space thresholds in logarithmic scale. The vertical axis shows the values for relative time usage, \(t_{ratio}=\frac {t^{MHNSGA-II}}{t^{POCO}}\) This quantity measures the time required for running the MHNSGA-II as opposed to that for exhaustive evaluation of POCO framework. The height and color of each bar imply for the average value for each corresponding bin and the precision specification respectively similar to the relative budget demonstrated in Fig. 5. By moving toward the right of the graph, i.e. rising the size of the search spaces, the height of the bins fall steadily. Hence, the relative time used for implementing the MHNSGA-II is dropping with extending the size of the network topologies or the number of the controllers or both of them at the same time. Regarding the tiny precision thresholds, the relative time required for the MHNSGA-II reaches under 20% for categories whose sizes are below 14 million for which τ = 0.005 and for those whose sizes are less than 7.7 million in the situation that τ = 0.008, respectively. It can be inferred from the time-precision trade-off induced by the heuristic approach that the MHNSGA-II is capable produce a very good approximation, just with an average deviation of 0.8%, for the original Pareto optimal set more than 20 times faster than the exhaustive evaluation implemented by POCO framework for the scenarios with search spaces include more than 14 million placements.

Fig. 6
figure 6

Size of search space and corresponding relative time required in order to achieve various performance levels

Full size image

5.3.3 Dispersion analysis

For better understanding of how the designed greedy initialization and multi-start mechanism can improve the dispersion of the solution set, the following evaluation has been carried out. Figure 7 illustrates the results in the two dimensional space considered. All comparisons are made based on the IGD performance metric (see Section 3.2).The left half of the figure shows the best results after 30 runs of heuristic approach with replacing the greedy start by random initialization and eliminating multi-start process. Besides, the right half depicts findings from the worst run of the original MHNSGA-II among the 30 runs. Figure 7a and b refers to the solutions obtained after the first iteration of the two scenarios respectively. It is clear that even the worst run of MHNSGA-II provides initial population not only with better distribution, but also much closer to the actual Pareto (see Fig. 8) than the best run the second case. Figure 7c and d show all the solutions evaluated during this procedure for the two considered scenarios respectively. Comparing with Fig 8, one can detect that some parts of the Pareto is not investigated in the while process of randomized algorithm (14(c)). (for example, the right bottom). Indeed, after running a lot and seeing the same results, this motivates us to improve the dispersion mechanism. Hence, in addition to better diversity, they are very close to the optimal set.

Fig. 7
figure 7

Plots of the First and all generations of MHNSGA-II and this algorithm without GreedyStart and Multi-start procedures

Full size image
Fig. 8
figure 8

Pareto optimal solutions of the controller placement of Fig. 7

Full size image

5.3.4 Performance metric analysis

In this section, regarding the IGD parameter which is introduced in 3.2, some simulations for the performance of MHNSGA-II are executed.

Three instances are considered again based on the Internet2 OS3E network topology. Each of the instances 1, 2, and 3 considers the controller placement problem with two metrics which are as follows: controller imbalance (5) opposed to maximum node to controller latency (1) with k = 9 for the first instance, maximum node to controller latency (1) against maximum controller to controller latency (3) with k = 7 for the second one, and maximum controller to controller latency (3) versus controller imbalance (5) with k = 8 for the last instance. PF indicates the original Pareto optimal front

Figure 9 depicts the evolution of the average IGD-metric values of the population with the number of generations in the MHSNGA-II. The values of vertical axis for all plots are in logarithmic scale. Table 1 illustrates the minimum, mean, and standard deviation of the IGD-metric values of the 30 final populations. Figure 10 in the objective space, shows the distribution of the final populations with the lowest IGD-metric values achieved in 10 runs of MHSNGA-II on each test instance. As can be seen from the plots as well as the table, the values of this metric are falling reasonably with the progress of the algorithm. Furthermore, this metric achieves low values in the end of each run resulting that the obtained solution set approximates the original Pareto front with high accuracy and regarding that the solutions are well distributed along the Pareto optimal.

Fig. 9
figure 9

Development of the mean of IGD-metric values against the number of generations for the three instances

Full size image
Fig. 10
figure 10

Plots of the final populations with the lowest IGD-metric values found by MHNSGA-II in 10 runs in the objective space on I1–I3

Full size image
Table 1 IGD-metric values of the nondominated solutions found by MHNSGA-II ON I1–I3
Full size table

5.3.5 Further convergence analysis and comparisons

As discussed in Section 3.2, the I G D(R,M) is able to measure both diversity and convergence of the approximated set of the real Pareto M. Since multi- objective algorithms would be tested on problems whose set of Pareto optimal solutions (R) are known, the computation of metric IGD is possible and shows the extent of convergence to R. In addition to convergence analysis discussed in Section 5.3.4, further evaluation is performed for convergence analysis of the MHNSGA. The smaller the value of this metric, the better convergence to the real Pareto optimal set. Also, this way makes it possible to compare the performance of MHNSGA with some exist algorithms in the literature. For this purpose, 9 topologies are extracted from Internet Topology Zoo to work as our reference data set. The number of nodes (N) and controllers (k) is written below each topology name determining the size of the problem. The same scheme as described in 5.1 is used to parameter setting with threshold τ = 0.08 for IGD and f m i n = 70 for three algorithms. For choosing k, a random process is done. For each topology, the I G D(R,M) is calculated for the output of each algorithm, i.e. M. This process repeats 50 times and the average \(\bar {IGD}\) and the standard deviation σ I G D of this metric is computed. This information is presented in Table 2. This table shows the mean and variance of convergence metric IGD obtained using three algorithms MHNSGA, PSA [4] and PSO-CGLCPP [6]. MHNSGA is able to converge better in all problems than PSA.

Table 2 Mean (First rows) and standrad deviation (second rows) of the convergence metric IGD
Full size table

Moreover, except for one topology Xspedius, where the result is slightly better for PSO-CGLCPP, MHNSGA outperforms for most problems. The figures indicate that the extent of convergence to the real Pareto is good and reasonable for our proposed algorithm.

6 Conclusion

Achieving an appropriate solution for the controller placement in an SDN-based architecture in which some competing metrics need to be considered imposes several challenges to decision makers. It is important to note that the obtained positions of the controllers can impress on many vital performance aspects of the resulting system. This work addressed the controller placement problem considering various crucial metrics in SDN-based networks. These metrics comprise of latency between nodes and its assigned controllers, among controllers themselves, and load balancing. For the reason that several of these objectives conflict with each other, the decision maker needs to explore fair trade-offs among them. The MHNSGA-II was designed which showed to be efficient for obtaining an accurate and diverse estimation set of the Pareto Optimal placements regarding these metrics. This paper showed the advantages of incorporating heuristic approaches in order to analyze problem instances which are too large to evaluate in an exhaustive manner and permits a balance trade-off between time and precision in the presence of time dependent restrictions in the network.