Keywords

1 Introduction

Unlike traditional networks, where both control and forwarding planes are highly integrated on the same boxes, the Software Defined Network (SDN) architecture decouples control and forwarding planes. Such separation is realized by moving the network intelligence onto one or more external servers, called controllers, which make up a network-wide logically centralized control plane that oversees a set of dumb, and simply forwarding elements [1].

A particularly important task in SDN architectures is controller placement, i.e., the positioning of a limited number of controllers within a network to meet various requirements [2]. It is called the controller placement problem which is known to be NP-hard. These requirements range from latency constraints to failure tolerance and load balancing. We narrow our focus to latency constraints, because it places fundamental limits on availability and convergence time. Our goal is to find optimal minimum-latency placements, when the number of controllers is given. It has practical implications for software design, affecting whether controllers can respond to events in real-time, or whether they must push forwarding actions to forwarding elements in advance [3].

Previously, the solution only focused on propagation latency between controllers and switches but ignored the latency between controllers, which is a critical factor in real networks. If there is more than a single controller in a network, synchronization is necessary to maintain a consistent global state. Depending on the frequency of the inter-controller synchronization, the latency between the individual controllers plays an important role and thus should be considered during the controller placement [4]. Besides the propagation latency between controllers, the load of controllers is a critical factor in real networks too. Because of the constraints of possessor, memory, access bandwidth and other resources, a commodity server only has the capacity to manage a limited number of routers [6]. Whenever the load of a controller reaches a threshold, the message processing latency on the controller will increase substantially. In summary, we make the following contributions:

  • To our best knowledge, this is the first work that proposes the Particle Swarm Optimization algorithm to solve the controller placement problem which is known to be NP-hard in SDN. By simulations, we show that the algorithm achieves better solutions than close-to-optimal ones obtained by the Integer Linear Program (ILP).

  • We define the Global Latency Control Placement Problem with Capacitated Controllers (CGLCPP) which takes into consideration both the latency from controllers to controllers and the capabilities of controllers for the first time.

The rest of this paper is organized as follows. The related work is reported in Sect. 2. The Mathematical Model is depicted in Sect. 3. Section 4 briefs the particle warm optimization algorithm to solve the CGLCPP. The results of simulations and discussion of the performance are reported in Sect. 5. Finally, we conclude our work in Sect. 6.

2 Related Work

The controller placement problem in SDN was first proposed in [3]. The authors motivate the controller placement problem and present initial analysis of a fundamental design. This paper examines the impacts of placements on average and worst-case propagation latencies on real topologies. But its goal is not to find optimal minimum-latency placements and don’t take into consideration the latency between controllers which is necessary in SDN with multiple controllers. This paper doesn’t propose a useful algorithm to find the solution, and each optimal placement shown in this paper comes from directly measuring the metrics on all possible combinations of controllers. This method ensures accurate results, but at the cost of weeks of CPU time; the complexity is exponential for k, since brute force must enumerate every combination of controllers. The paper [4] discusses several aspects of the controller placement problem from the view of resilience and failure tolerance. The delay between controllers is only a small part of its multi-objective optimization considering and has not been studied in depth.

The paper [5] addresses the problem of placing controllers in SDN, so as to maximize the reliability of control networks. It presents a metric to characterize the reliability of SDN control networks, and further quantify the impact of controller number on the reliability of control networks. It proposes two heuristic algorithms to solve the problem, which are the greedy algorithm and Simulated Annealing algorithm respectively. In this letter [6], it focuses on the load of controllers and defined a capacitated controller placement problem, taking into account the capabilities of controllers. But it hasn’t dealt with the latency between controllers.

The papers [4, 7] address the controller placement problem according to multiple objective functions. They argue a controller placement should also fulfill certain resilience constraints especially for the control plane. The model simultaneously determines the optimal number, location, and type of controller as well as the interconnections between all the network elements. The goal of the model is to minimize the cost of the network while considering different constraints.

3 Mathematical Model of the Global Latency Control Placement Problem

In SDNs, switches communicate with their controller via standard TLS or TCP connections. When multiple controllers are deployed, the latency between the individual controllers plays an important role, because communications between these controllers are also required to achieve global consistency of network state [8]. For example, the Google’s B4 network provides connectivity among a modest number of data centers, e.g., for asynchronous data copies, index pushes for interactive serving systems, and end user data replication [9]. Thousands of internal application traffic runs across this network. And user data is the most latency sensitive, and is of the highest priority.

Besides the propagation latency between controllers, the load of controllers is a critical factor in real networks too. Because of the constraints of possessor, memory, access bandwidth and other resources, a commodity server only has the capacity to manage a limited number of routers [6]. Whenever the load of a controller reaches a threshold, the message processing latency on the controller will increase substantially. Heavy-load controllers always have higher failure probability, because they have little resources to handle various errors and are more likely to be attacked.

The latency between the individual controllers plays an important role, and the load of controllers is a critical factor in real networks too. Thus both them should be considered during the controller placement. We define the Global Latency Control Placement Problem with Capacitated Controllers (CGLCPP), which consists of both the latency from controllers to switches and the latency from controllers to controllers, and takes into consideration the capabilities of controllers.

For a network graph \( \left( {V,E} \right) \), where V is the set of nodes, E the set of links. Let n be the number of nodes. Let k denotes the number of controllers to be placed in the network, and \( n_{c} \) denotes the number of controller-to-controller paths. The edge weights represent propagation latencies, where \( d(v, c) \) is the shortest path from node v to controller c, and \( d(c_{i} , c_{j} ) \) is the shortest path from controller \( c_{i} \) to controller \( c_{j} \). Let \( F(c) \) denote the forwarding switches controlled by the controller c. Each controller c has a capacity \( L(c) \). The load of control attributed to switch v is denoted by \( l(v) \).

In order to be applicable and universal, we compute the average delay. And the global average propagation latency for a placement of controllers \( S^{\prime} \) is:

$$ G(S^{\prime}) = \frac{1}{n}\sum\limits_{v \in V} {\mathop {\hbox{min} }\limits_{{c \in S^{\prime}}} d(v,c)} + \frac{1}{{n_{c} }}\sum\limits_{{c_{i} ,c_{j} \in S^{\prime}}} {d(c_{i} ,c_{j} )} $$
(1)

Definition:

Global Latency Control Placement Problem with Capacitated Controllers

$$ Min\;\;G(S^{\prime}) $$
(2)

Subject to:

$$ \sum\limits_{v \in F(c)} {l(v)} \le L(c)\quad \forall \;c \in S^{\prime} $$
(3)

Given the number k of controllers to be deployed in SDN, our goal is to find the placement \( S^{\prime} \) from the set of all possible controller placements S, such that \( G(S^{\prime}) \) is minimum and \( \left| {S^{\prime}} \right| = k \).

4 Particle Swarm Optimization for GLCPP Algorithm

With the given input k, the number of controllers to place, the global latency control placement problem is an application example of the famous minimum k-median problem [10], which is proved to be NP-hard. To solve this problem, we propose particle swarm optimization algorithm that automate the controller placement decision for the first time, which has good performance in NP-hard problem optimization. Section 4.1 describes the PSO algorithm, and Sect. 4.2 explains PSO-CGLCPP algorithm.

4.1 PSO Algorithm

Particle swarm optimization algorithm (PSO) was proposed in 1995 by Eberhart and Kennedy [11]. It is a population-based stochastic optimization algorithm that originates from nature. PSO searches the optimum within a population called a swarm and benefits from two types of learning: cognitive learning based on an individual’s history and social learning based on a swarm’s history accumulated by sharing information among all particles in the swarm [12]. Successful applications of PSO have demonstrated that it is a promising and efficient optimization method.

The mathematical analysis of PSO is described as the following. There are n particles which represent potential solutions of the problem. The particle is defined as a d-dimensional vector. The current position of the particle in search space is \( X_{i} = [x_{i1 } ,x_{i1 } , \ldots ,x_{id} ] \), \( i = 1,2, \ldots ,n \), and its current velocity vector is \( V_{i} = [v_{i1 } ,v_{i2 } , \ldots ,v_{id} ] \). We use \( P_{\text{i}} \) to stand for individual best position of the particle, \( P_{i} = [p_{i1 } ,p_{i2 } , \ldots ,p_{id} ] \). And \( P_{g} \) is regarded as global best position vector which particle swarm have found, \( P_{g} = [p_{g1 } ,p_{g2 } , \ldots ,p_{gd} ] \). So, the position and velocity vector of the particles should adjust according to the following equations:

$$ V_{id}^{t + 1} = \omega V_{id}^{t} + c_{1} r_{1} (P_{id} - X_{id}^{t} ) + c_{2} r_{2} (P_{gd} - X_{id}^{t} ) $$
(4)
$$ X_{id}^{t + 1} = X_{id}^{t} + V_{id}^{t + 1} $$
(5)

where ω expresses the inertia weight, \( {\text{r}}_{1} \) and \( {\text{r}}_{2} \) are elements from random sequences in the range of (0, 1), which are mutually independent. The parameter \( c_{1} \) controls the influence degree of a cognitive part of an individual, and \( c_{2} \) determines the effect of a social part of the swarm.

The inertia weight \( \omega \) lets the algorithm improve its performance in a series of applications. Paper [13] found that large inertia weight can help the global search, small inertia weight can improve local search ability. Therefore, adaptive adjustment of inertia weight is proposed. The inertia weight is not fixed value, but a function of linear reduction over time. The inertia weight function is shown as the following:

$$ \omega = \omega_{\hbox{max} } - \frac{{\omega_{\hbox{max} } - \omega_{\hbox{min} } }}{{t_{\hbox{max} } }} \times t $$
(6)

\( \omega_{max} \) is set as the initial weight, \( \omega_{min} \) is set as the final weight. Variable \( t_{max} \) represents the maximum number of iteration, t is the number of current iteration. Usually \( \omega_{max} \) is set as 0.9 and \( \omega_{min} \) is set as 0.1.

The individual best position vector of each particle is computed using the following expression:

$$ P_{i} (t + 1) = \left\{ {\begin{array}{*{20}l} {P_{i} (t)} \hfill & {if\;\;f(X_{i} (t + 1)) \ge f(P_{i} (t))} \hfill \\ {X_{i} (t + 1)} \hfill & {if\;\;f(X_{i} (t + 1)) \le f(P_{i} (t))} \hfill \\ \end{array} } \right. $$
(7)

where f represents the fitness function.

Then, the global best position vector is found by

$$ P_{g} (t + 1) = \arg \;\mathop {\hbox{min} }\limits_{{P_{i} (t + 1)}} f(P_{i} (t + 1)). $$
(8)

4.2 PSO-CGLCPP Algorithm

In PSO, the position vector represents a solution to the optimized problem. For the global latency control placement problem, each particle represents one kind of placement for controllers to be deployed. With the given input k, the number of controllers to place, the particle is defined as a k-dimensional vector, and each dimension represents one of the controllers. So the position permutation of a particle i is defined as \( X_{i} = [x_{i1 } ,x_{i1 } , \ldots ,x_{ik} ] \). For we deploy each controller on one of the existing vertexes of the network, each dimension of position is a integer between 1 and n, i.e., \( x_{ik} \in [1,n] \), where n is equal to the number of total vertexes in the network. Velocity works on the position sequence and it is rather crucial. A good velocity gives the particle a guidance and determines whether the particle can reach its destination and by how fast it could [14].

When the position of the particle is established, namely the controllers are in place, we compute the adaptive value of particle according to formula (1). Because the node is assigned to its nearest controller, the delay from node to corresponding controller is generally measured in that link length value. Then we compute load of controller according to formula (3). If it exceeds the load limitation of controller, assign the switch to the next nearest switch controller. And the delay between controllers and controllers is defined as the shortest link between them in the same way.

In this section, we propose Particle Swarm Optimization for CGLCPP Algorithm (PSO-CGLCPP). The basic idea is, by iteration, multiple particles search the optimal solution in parallel, and minimum total delay controller placement is located. And the overall procedure is about: initialize n particles randomly, with each particle representing a kind of placement of k controllers. Then set the particle with the highest fitness to be the current best solution whose latency value is smallest. According to the PSO algorithm, use the PSO velocity formulas (4) and (5) to merge the controller placement and determine the new particle position until this swarm obtains its longest lifetime or it converges. If PSO-CGLCPP converges, then the best solution can be obtained. The PSO-CGLCPP algorithm for global latency controller placement problem is described as follows.

5 Simulation and Results Analysis

In this section, we generate network topologies randomly according to [15], which is almost closed to the real network. Controller’s capability is a complex concept, including bandwidth, memory and computing resources and so on. In order to simplify the problem, we use a digital to denote it. The load of controller attributed to switch is processed in the same way. Our PSO-CGLCPP is written with C++ in VS2010, and runs on the machine equipped with Intel Core i5 4-Core processors and 4 GB RAM. We obtain the average solution by running the algorithm 100 times on every testing topology.

To evaluate the performance of our algorithm, we run the other two algorithms, along with the random placement algorithm (Random) for comparison purpose. The two algorithms are greedy algorithm (GL) proposed in [5] and integer linear programming algorithm (ILP) in [6] respectively. CPLEX is used to solve integer programming. For a NP-hard problem, it will be hard to find the solution based on the enumeration algorithm which ensures accurate results, but at the cost of weeks of CPU time. Linear programming algorithms are always used to solve the problems, and the solution is regarded as the optimal solution for a reference. So we mainly regard the ILP algorithm as a reference and compare with it. Since the random algorithm returns different results based on the locations selected, we execute random placements over 100 times, and select the placement that yields the best performance.

We evaluate the algorithms in two aspects, the first is the optimal latency solution, and the second aspect is computing time for algorithm to find the optimal solution. And we further characterize both latency and computing time performance against the size of controllers. The results of the simulation are depicted in the following figures. PSO is abbreviated words of PSO-CGLCPP.

Figure 1 evaluates the optimal latency of four algorithms with increasing network nodes, given the same number of controllers. It shows that PSO and ILP get a better average delay. PSO’s performance is slightly better than the ILP algorithms. Greedy algorithm and Random algorithm perform relatively poor, and the worst is random algorithm. Furthermore the Random and GL increase quickly along with increasing nodes while PSO and ILP provide an optimal solution more reliably. The greedy algorithm picks the next vertex that best minimizes latency, which always produces the best location currently, but local optimum does not represent a global optimum. Because of diversity of particles, PSO can search the entire space and jump out of local optimum through exchanging information with each other. Finally the particle will flight to a better global optimum after several iterations.

Fig. 1.
figure 1

Optimal latency solution of the algorithms

Full size image

Figure 2 analyzes number of the controllers’ impact on average latency under the same network topology. In the experiments, we gradually increase the number of controllers for each placement strategy. With the increase of controllers placed in, the average latency decreases. The average delay gained by PSO algorithm is always relatively stable, less volatile, compared with the greedy algorithm. This is because the particle swarm optimization through mutual learning and iteration between the particles can always find a better controllers’ position to achieve better results. Furthermore, the diminishing returns that level off around 4–8 controllers, suggested by the literature [3], have been verified.

Fig. 2.
figure 2

Controller number’s impact on average latency

Full size image

As can be seen from the Fig. 3, greedy algorithm consumes the shortest time, but the solution is far away from the optimal one, which is unacceptable in most environments. Processing time of both PSO and ILP are much more than GL algorithm, but produce a better solution. The time taken by the PSO and ILP algorithm are in almost close level. When network size is larger, PSO algorithm converges to the optimal solution slightly faster than ILP. PSO convergence must take advantages of the swarm intelligence, and achieve a more satisfactory solution within an acceptable timeframe, which can match with commercially available strategies. Although PSO takes much more time in the procedure of exploring the optimal placement than GL, the time is acceptable in lots real application scenarios in which the task has no real-time demand. Figure 4 evaluates calculation time with increasing controller nodes to be deployed, when the network size is the same. As can be seen, when the number of controllers deployed becomes bigger, the convergence of time becomes larger and larger. And the growth rate of computation time becomes bigger, because faster growth of number of links between controllers.

Fig. 3.
figure 3

Computing time of the algorithms

Full size image
Fig. 4.
figure 4

Controller number’s impact on computation time

Full size image

6 Conclusion

In this paper we investigate the controller placement problem in software defined network, and define the Global Latency Control Placement Problem with Capacitated Controllers (CGLCPP), taking into consideration both the latency between controllers and the capabilities of controllers. We then propose a PSO-CGLCPP algorithm based on particle swarm optimization to solve the problem for the first time. Our method could find an optimized solution for the given controllers while conforming to the constraints of controllers. Experimental results show that the algorithm performs rapidly and effectively.