Keywords

1 Introduction

Software-defined networking (SDN) is a new networking paradigm that decouples control plane from data plane [1, 2]. Multiple-controller architectures have been introduced in SDNs and raised a new problem, the controller placement problem, which needs to decide the controllers positions and how to associate switches with the controllers, since random placement is far from optimal [3, 4].

Some research has been conducted on the controller placement problem with the objective of minimizing the node-to-controller latency. The controller placement problem was first proposed by Heller et al. in [3] to minimize the communication latency between the switches and the controllers. A latency metric to minimize the total cost of flow set-up request from switches to controllers was introduced to deal with the mapping between the switches and the controllers under dynamic flow variations, and the metric considered the weight of switches and the delay from the switches to the controllers simultaneously, where the weight of a switch was related to the node degree of the switch and the maximum node degree in the network [5]. A network partition based scheme was designed, where the network was portioned into multiple subnetworks with revised k-means algorithm and a controller was placed in each subnetwork to minimize the maximum latency between the controller and the associated switches in the subnetwork [6]. A framework for deploying multiple controllers within a WAN was proposed to dynamically adjust the number of active controllers and delegate each controller with a subset of switches according to network dynamics [7].

The reliability is also an important performance metric for networks. A metric called expected percentage of control path loss due to failed network component was introduced to characterize the reliability of SDN networks, and a heuristic algorithm l-w-greedy was proposed to analyze the trade-off between reliability and latency; the expected percentage of control path loss was related to the number of control paths going through a component and the failure probability of the component [8, 9]. A controller placement strategy, Survivor, was proposed to explore the path diversity to optimize the survivability of networks with the aim to maximize the number of node-disjoint paths between the switches and the controllers; the strategy enhanced connectivity by explicitly considering path diversity, avoided controller overload by adding capacity-awareness in the controller placement, and improved failover mechanisms by means of a methodology for composing the list of backup paths [10]. The latency-aware reliable controller placement problem was investigated by jointly taking into account both the communication reliability and the communication latency between the controllers and the switches if any link in the network fails [11].

Link failures incur the breakdown of part of the network, during which some flow set-up requests from the switches are unable to reach the corresponding controllers and hence get dropped. To the best of our knowledge, very little attention in literature has ever been paid on the single-link-failure impact on the number of dropped flow set-up requests in SDNs. In this paper, we tackle the multiple-controller placement problem with the aim to improve the reliability in terms of the number of dropped flow set-up requests under single-link-failure.

The main contributions of this paper are as follows. We address the controller placement problem to maximize the reliability of the flow set-up requests under single-link-failure. We define a novel controller placement metric, the average number of dropped flow set-up requests, and propose two efficient algorithms for multiple-controller placements based on the proposed placement metric. We also evaluate the performance of the proposed algorithms through simulations. Experimental results demonstrate the proposed algorithms are very promising.

The rest of the paper is organized as follows. Section 2 presents the problem of this work. Section 3 discusses the proposed two algorithms: Reliability Aware Controller placement (RAC) and Fast-RAC (FRAC). Section 4 discusses our experimental evaluation. Section 5 concludes our work with a summary.

2 Problem Formulation

We model an SDN network topology as graph G = (V, E), where V  is the set of switches (or nodes) and E is the set of links. Each controller is co-located with a switch, and each switch is mapped to one controller. We assume that there is at most one link failure in the network [12]. The notations used in the paper are listed in Table 1.

Table 1 Symbols and notations used in our description
Full size table

When link e on the control path p i,k fails, we calculate the number of dropped flow set-up requests as follows:

$$\displaystyle \begin{aligned} \begin{array}{l} \mathcal{D}(e) = \sum_{s_{i} \in V} \sum_{c_{k} \in C} r_{i,k} \cdot p^{e}_{i,k} \cdot x_{i,k}. \end{array} \end{aligned} $$
(1)

Our objective is to minimize the average number of dropped flow set-up requests by

minimizing

$$\displaystyle \begin{aligned} \begin{array}{l} \bar{\mathcal{D}}=\frac{\sum_{e \in L} \mathcal{D}(e)} {|L|} \end{array}\end{aligned} $$
(2)

subject to

$$\displaystyle \begin{aligned} \sum_{k=1}^{K} x_{i,k} = 1, \quad \forall s_{i}\in V.\end{aligned} $$
(3)
$$\displaystyle \begin{aligned} \sum_{i=1}^{N} y_{i,k} = 1, \quad \forall c_{k} \in C.\end{aligned} $$
(4)
$$\displaystyle \begin{aligned} y_{i,k} \leq x_{i,k}, \quad \forall s_{i} \in V, \forall c_{k} \in C.\end{aligned} $$
(5)
$$\displaystyle \begin{aligned} \sum_{i=1}^{N} x_{i,k} \cdot r_{i,k} \leq u_{k}, \quad \forall c_{k} \in C.\end{aligned} $$
(6)

where |L| denotes the number of links in L, and the average number of dropped flow set-up requests due to single-link-failure in the control paths are defined with Eq. (2). Equation (3) ensures that each switch is mapped to one and only one controller. Equation (4) mandates that each controller is placed onto exactly one switch. Equation (5) dictates that switch s i is mapped to controller c k if controller c k is co-located with switch s i. Equation (6) signifies that the number of requests to the controller cannot exceed the processing capacity of the controller.

3 RAC and FRAC Controller Placement Algorithms

In this section, we propose two controller placement algorithms, flow set-up request Reliability Aware Controller placement (RAC) and Fast-RAC (FRAC).

3.1 Reliability Aware Controller Placement Algorithm

Algorithm 1 RAC

Initially, algorithm RAC assumes that there are N controllers and each controller is co-located with a switch. The algorithm removes the redundant controllers iteratively until the number of controllers is K. For each controller, the algorithm evaluates the cost of removing it (steps 2–10). Assume the set of switches needing to be re-mapped after removing controller c k is S k. For each switch s i ∈ S k, algorithm RAC chooses the controller which incurs the least cost. During the re-mapping, Eq. (6) should be satisfied. After re-mapping all the switches in S k, the algorithm can obtain the cost of removing c k. Algorithm RAC evaluates the removal cost for all the controllers and removes the one which incurs the least cost (steps 11–12).

Time Complexity of Algorithm RAC

The algorithm needs to remove N − K controllers. In the worst case, a controller manages N − K + 1 switches. If the controller is removed, the algorithm performs re-mapping for the O(N − K + 1) switches. The re-mapping for a switch checks at most N − 1 controllers. We can calculate all the shortest paths between all the node pairs in the network within O(N 2 ⋅ N) = O(N 3) time so that we can get the link set on the control path between each node pair before performing algorithm RAC, and hence the calculation of the average number of dropped flow set-up requests when the switch is mapped to the controller runs in time O(N). Therefore, the time complexity of algorithm RAC is O((N − K) ⋅ N ⋅ (N − K + 1) ⋅ (N − 1) ⋅ N) = O(N 3 ⋅ (N − K)2) = O(N 5), since K ≪ N.

3.2 Fast-RAC

We propose algorithm Fast-RAC (FRAC) to reduce the time complexity of algorithm RAC. FRAC maintains a mapping controller priority list PL i for each switch s i, where each item in the list is a controller and the controllers in the list are sorted in the non-ascending order of the path lengths between the switch and the controllers. FRAC uses two arrays Current and Next, each with length N. Current[i] = k denotes that switch s i is currently mapped to controller c k. Initially, each switch is mapped to the co-located controller, that is, Current[i] = i. Next[i] = k ′ indicates that switch s i will be mapped to controller \(c_{k^{\prime }}\) if controller c k is removed, where \(c_{k^{\prime }}\) will cause the least number of dropped flow set-up requests caused by single-link-failure. We initialize arrays Current and Next before placing a controller at each switch (step 1), and update them when a controller is removed (step 11). During the update, if switch s i is re-mapped from c k to \(c_{k^{\prime }}\), Current[i] = k is updated as Current[i] = k ′ and Next[i] should be updated by searching the first controller available in the list PL i.

Time Complexity of Algorithm FRAC

The construction of the mapping controller priority lists for all the switches can be performed in time O(N 3) by calculating the shortest paths between all the node pairs. The initialization and update of the array Current can be performed in time O(N). Array Next can also be constructed in time O(N), while the update of the array Next is conducted in time O(N 2), since FRAC checks at most N − 2 controllers to find the controllers available for each of the N switches. The time consumed to re-map a switch is reduced from O(N) with RAC to O(1) with FRAC. Therefore, the time complexity of algorithm FRAC is O(N 4).

4 Performance Evaluation

In this section, we evaluate the performance of the proposed controller placement algorithm. We also investigate the impact of important parameters on the performance of the proposed algorithms.

4.1 Simulation Set-up

We compare the proposed algorithms RAC, FRAC against the state of the arts: l-w-greedy [9], SVVR [10], and CPP [3]. The two coefficients l and w are set as l = 2 and w = 1 to enable l-w-greedy to achieve the best performance as described in [9]. The network topologies used in the simulation are ATT (ATT North America) and Internet2 (Internet2 OS3E) [13, 14]. All the controllers have the same processing capacity of 1800 kilorequests/s [10]. The requests from the switches are generated with uniform distribution pattern. 30 set of requests are generated for each request distribution pattern randomly, while the average number of flow set-up requests of the switches are 200 kilorequests/s. We use geographical distance as an approximation for latency [3].

4.2 Evaluation Metrics

The performance metrics evaluated are as follows:

  1. 1.

    The average number of dropped flow set-up requests under single-link-failure as calculated via Eq. (2).

  2. 2.

    The average latency of flow set-up requests \(\bar {l}\), defined via Eq. (7), where l i,k denotes the communication latency of control path p i,k.

    $$\displaystyle \begin{aligned} \begin{array}{l} \bar{l} = \frac{\sum_{s_i \in V} \sum_{c_k \in C} r_{i, k} \cdot x_{i, k} \cdot l_{i, k}} {\sum_{s_i \in V} \sum_{c_k \in C} r_{i, k} \cdot x_{i, k}}. \end{array} \end{aligned} $$
    (7)

4.3 Simulation Results

4.3.1 Average Number of Dropped Flow Set-Up Requests

In this section, we evaluate the average number of dropped flow set-up requests of each algorithm by varying the number of controllers from 5 to 10.

Figure 1 shows that both algorithm RAC and algorithm FRAC obtain better performance than the benchmark algorithms because the proposed algorithms minimize the average number of dropped flow set-up requests when placing the controllers in the network. Algorithm RAC performs slightly better than FRAC since RAC removes the controller which incurs the least average number of dropped flow set-up requests, while FRAC finds the controller leading to the least number of dropped flow set-up requests.

Fig. 1
figure 1

The average number of dropped requests under different number of controllers

Full size image

Algorithm CPP achieves the best performance among three benchmark algorithms. Algorithm SVVR aims to maximize the number of disjoint paths between switches and controllers, l-w-greedy tries to minimize the expected percentage of control path loss, and CPP deploys the controllers with the objective of optimizing the average communication latency of switches and controllers. Algorithm CPP potentially aggregates the requests on a subset of the network, which reduces the number of links on the control paths and the total number of requests caused by the single-link-failure.

4.3.2 Average Latency of Flow Set-Up Requests

In this section, we evaluate the average latency of flow set-up requests of each algorithm, assuming the number of controllers varies from 5 to 10.

Figure 2 depicts the average latency of flow set-up requests of RAC, FRAC, SVVR, l-w-greedy, and CPP. Algorithms RAC and FRAC achieve a similar performance. Algorithm l-w-greedy results in the worst performance, because algorithm l-w-greedy aims to optimize the reliability of control path between switches and controllers, which potentially leads to long control paths between the switches and controllers. Algorithms RAC and FRAC place the controllers considering the number of dropped flow set-up requests under single-link-failure, so the two algorithms put the controllers close to the switches which generate a large number of flow set-up requests. Algorithm CPP minimizes the latency between the switches and the controllers without considering the number of flow set-up requests generated by the switches. Therefore, algorithm CPP obtains better performance than the other algorithms, where the distance between the switches and the controllers has an important impact on the controller placement.

Fig. 2
figure 2

The average latency of flow set-up requests under different number of controllers

Full size image

5 Conclusions

Reliability is an important concern during controller placements in SDNs since link failures can cause disconnections between switches and controllers, and even incur cascading failures of other controllers. In this paper, we take the transmission reliability of flow set-up requests into consideration during controller placements. We formulated a novel SDN controller placement problem with the aim to minimize the average number of dropped flow set-up requests due to the single-link-failure. We propose flow set-up request Reliability Aware Controller placement (RAC) algorithm and Fast-RAC (FRAC) algorithm for multiple-controller placements. Experiments are conducted through simulations. Our experimental results demonstrate that the proposed algorithms achieve competitive performance in terms of average number of dropped flow set-up requests under single-link-failure and average latency of flow set-up requests.