Improving Switch-to-Controller Assignment with Load Balancing in Multi-controller Software Defined WAN (SD-WAN)

Abstract

Software defined networking (SDN) gains a lot of interest from network operators due to its ability to offer flexibility, efficiency and fine-grained control over forwarding elements (FE) by decoupling control and data planes. In the control plane, a centralized node, denoted controller, receives requests from ingress switches and makes decisions on path forwarding. Unfortunately, requests processing may lead to controller performance degradation as the number of incoming requests goes up. This paper deals with the controller performance issue in Software Defined WAN (SD-WAN). Mainly, it proposes a new approach to optimize the switch-to-controller assignment problem with load balancing support. The issue is formulated as a Minimum Cost Bipartite Assignment optimization problem which is solved using an improvement of the Hungarian algorithm. The new algorithm is based on the introduction of the load-driven penalty concept which aims to achieve a trade-off between the round trip time and the controller load. Finally, a new protocol denoted Distributed Hungarian-based Assignment Protocol (DHAP) is described as an implementation of the proposed solution in multi-controller environments. As shown in results, the proposed solution outperforms parallel schemes in terms of flow setup time and load balancing.

1 Introduction

Today, software defined networking (SDN) [2] is considered a promising technology towards network evolution and programmability by decoupling data and control planes. Programmable networks are with great opportunities since they support resources sharing, flexibility, adaptability and fine-grained control over the forwarding elements (FE) at less cost compared to traditional networks.

SDN consists of a central controller with a global network visibility that can order updates to any switch directly once required. The communication between the controller and the switch is handled by open and standard protocols such as OpenFlow [3].

In OpenFlow-based networks, the controller-to-switch communication takes place as follows: As the first packet of a flow reaches the ingress switch, a PacketIn message is sent to the controller. Upon receiving a PacketIn message, the controller analyzes the request, computes the forwarding path and updates all nodes in it by adding entries to the corresponding flow-tables. All subsequent packets of the flow are forwarded based on new added entries without any need to contact the controller. Updates are carried into PacketOut or FlowMod messages.

The performance of a controller gains more interest in Wide Area Networks (WAN). Indeed, the amount of received requests (PacketIn messages) goes up as the number of ingress switches increases. As a result, this may lead to controller performance degradation and may disturb core switches.

Obviously, modeling the Openflow-based communication is of paramount importance in order to analyze the performance of a controller. This model may guide us to have answers to several questions such as how long are the flow setup time and the request sojourn time, where are points of bottlenecks and the amount of data that should be injected into the network at a given period. Certainly, answers depend on the switch-to-controller assignment model.

The assignment issue is one of the most hard problems that network operators face. Given two sets S and C of switches and controllers respectively, the assignment problem consists of finding a many-to-one matching between those sets with respect to a cost function $\Psi$. For reliability purpose, this assignment should take into account the current network state. For example, the assignment should consider current loads on both controllers and switches to minimize the flow setup time and to achieve balanced loads among controllers.

This paper deals with the optimization of the switch-to-controller assignment problem. The optimization consists of minimizing the whole setup time experienced by a flow before being served. Obviously, this time depends on current loads of both the switch and the controller as well as the round trip time between them. Hence, we formulate a Multi-objective Combinatorial Optimization problem using a minimum cost bipartite assignment graph which is solved by improving the Hungarian algorithm [4]. The improvement is realized through the introduction of the load-driven penalty which aims to achieve a trade-off between the round trip time and the current load on a controller within a polynomial computation time by updating the matrix costs between controllers and switches and the pool of controllers once required during the assignment process.

The rest of the paper is structured as follows: Sect. 2 describes assets and drawbacks of previous models to solve the assignment problem. Section 3 describes the background of our approach and defines a multi-objective bipartite assignment problem. Section 4 presents a relaxation of the Multi-Objective problem and solves it by an improvement of the Hungarian algorithm to support load balancing. Experimental results are shown in Sect. 5. Section 6 states concluding remarks and forthcoming issues.

2 Related Work

Several researches have focused on improving dynamic switches-to-controllers assignment. They aim providing more resiliency by solving the mapping problem related to connections between control and data planes which influences the overall of the SDN network. The authors in [1] combine the dynamic switch-to-controller association and dynamic control devolution while preserving a reasonable wait time in queues. As a result, a reduced communication cost between data and control planes is achieved and the computational cost spent by the switch to process its requests locally is minimized. For this purpose, they propose a Greedy algorithm based on a stochastic optimization problem which is used to make a scheduling decision that between either directly uploading requests to controllers or waiting at the local queue of the switch. Bari et al. [6] formulated the dynamic controller provisioning in a WAN as an Integer Linear Program in order to minimize the flow setup time and the communication overhead. Mainly, this work is based on reassigning switches to controllers by optimizing three constraints related to switch-to-controller exchange cost, inter-controller synchronization cost and switch reassignment cost, respectively.

Authors in [7] focus on network partitioning as a solution for the controller placement issue. Based on two constraints: the switch-to-controller latency and the path survivability, a multi-objective optimization problem is there defined. In [8], a new architecture of distributed controllers is proposed. Based on current traffic conditions, the pool of controllers is increased or decreased. Moreover, this paper proposes a new approach to migrate switches from an overloaded controller to another less loaded. Authors in [9] solved the switches-to-controllers assignment problem in DataCenter environment using game theory for powerful decision making. It consists of a many-to-one matching phase followed by a coalition game to achieve load balancing among controllers. However, achieving load balancing is considered very costly in terms of network load since switch migration between controllers requires exchanging several messages. To deal with this shortcoming, the solution in [10] is inspired from the last work and consists of exploiting the first phase and abandoning the coalition game. Accordingly, the load balancing is achieved through the definition of the minimum quotas for each controller. A fair algorithm is proposed which considered several constraints associated to the assignment operation, such as load balancing according to the minimum quota and the respect of the processing capacity which must not be exceeded.

Authors in [13] deal with the switch migration problem (SMP). Switch migration plays an important role in maintaining dynamic switch-controller mapping. A local search algorithm is presented that is based on shift and swap moves and incorporates a controlled solution shaking scheme. The shaking scheme consists of evaluating the benefit of a moving to corresponding controllers. The results were conducted in terms of load balancing, robustness and computation time. However, more concern must be focused on the application of this solution in distributed environments in order to take into account several constraints such as connectivity and optimal node placements. Table 1 summarizes main approaches with their contributions.

Table 1 Main approaches and their contributions

In this paper, we present a new approach to associate switches to controllers while maintaining balanced loads among controllers. This approach aims to minimize the whole setup time of incoming flows by achieving a trade-off between the switch-to-controller round trip time (RTT) and the current loads on a controller. The trade-off is achieved with no communication overhead since no updating messages are exchanged.

Mainly, the problem is formulated as a minimum cost bipartite assignment optimization problem that aims to reduce the response time while maintaining balanced loads among all controllers. Then, to solve this problem, an improvement of the Hungarian algorithm is defined. Each controller is associated with a load penalty which is considered in updating the cost matrix and the pool of controllers. The set of controllers is dynamically updated at each iteration to leave out those which the queue utilization has exceeded the maximum threshold.

3 Background Overview

3.1 The Software Defined Networking (SDN) Paradigm

Most current network nodes have control and forward functionalities operating on the same device. The only control available to a network administrator is from the network management plane, which is used to configure each network node separately. The static nature of current network devices makes the control-plane configuration a complex and hard operation. This is exactly where software-defined networking (SDN) [14, 15] comes into the picture.

SDN operates on the idea of centralizing control-plane intelligence, but keeping the data plane separate (Fig. 1). Thus, the network hardware devices keep their switching fabric (data plane), but hand over their intelligence (switching and routing functionalities) to the controller. This enables the administrator to configure the network hardware directly from the controller without need to do it separately. This centralized control of the entire network offers flexibility, programmability and fine-grained governing of switches [16,17,18]. The communication between controllers and switches is handled by open and standard protocols such as OpenFlow [3].

Fig. 1

a Legacy IP networks, b SDN paradigm

3.2 The OpenFlow-Based Communication

In an Openflow-based network, each ingress switch must connect to a controller. In each switch, a packet queue is defined for each ingress port. Upon receiving a packet, the switch checks if a flow entry from the flow table matches the packet header. If yes, the packet will be forwarded based on associated actions. Otherwise, a request is sent to the controller through a PacketIn message. These two operations take different amount of time.

In a controller, it exists a queue for PacketIn messages which are processed with the First In First Out (FIFO) strategy. The controller computes the forwarding path using information carried in the PacketIn message and sends a PacketOut message or a FlowMod message to the switch to forward packet or to install a new flow entry into the flow table, respectively.

The PacketIn processing time depends on the current load of the controller which, usually, depends on the current number of queued requests and the queuing strategy.

3.3 Problem Formulation

An SDN network is defined as a directed graph $G=(C,S,L)$ where S, C and L denote the set of controllers, the set of switches and the set of links, respectively. We denote $\mid .\mid$ the set cardinality.

In Openflow-based networks, an incoming flow f experiences five delays before being served. All delays are provided in Fig. 2. Upon reaching the Ingress switch s, the first packet of a flow f is queued within a local queue $Q_s$. After a waiting time of $T_W^s$, the flow is served for a duration $T_S^s$. If no flow entry matching is found in the local flow table, a PacketIn message is sent to the controller c through a path for a duration of R(s, c).

Upon receiving the PacketIn message, the controller queued the message for a duration of $T_W^c$, before being served within a duration of $T_S^c$. Therefore, the response is sent towards the ingress switch s using a PacketOut message or a FlowMod message through a path within a duration of R(c, s). All subsequent packets of the flow f are forwarded based on the flow entry already installed in the flow table of the switch s.

Fig. 2

Various delays experienced by a flow in OF-based SDN

Let $T_f^{(s,c)}$ be the whole delay experienced by a flow f at the switch s before being served by the controller c. This delay is expressed as follows (Eq. 1):

$$\begin{aligned} T_f^{(s,c)}=T_W^s+T_S^s+R(s,c)+T_W^c+T_S^c+R(c,s) \end{aligned}$$

(1)

Our objective is to minimize the above delay to ensure that a flow is quickly served. Clearly, $T_f^{(s,c)}$ consists of three parameters: (i) The Switch sojourn time $T_{sj}(s)=T_W^s+T_S^s$, (ii) The round trip time between the switch and the controller $T_{RTT}(s,c)=R(s,c)+R(c,s)$ and (iii)The controller sojourn time $T_{sj}(c)=T_W^c+T_S^c$. Hence, the delay $T_f^{(s,c)}$ can be expressed as follows (Eq. 2):

$$\begin{aligned} T_f^{(s,c)}=T_{sj}(s)+T_{RTT}(s,c)+T_{sj}(c) \end{aligned}$$

(2)

4 Linear Minimum Cost Bipartite Assignment Programming

4.1 Analytic Model

Let $S_{c_j}$ be the set of switches managed by the controller $c_j$, where $c_j$$\in$C and $S_{c_j}$$\subseteq$S, the main goal is to find an assignment between switches (S) and controllers (C) that minimizes the cost $T_f^{(s,c)}$. Our problem can be formulated as a switch-to-controller assignment optimization problem [3]:

$$\left\{ \begin{array}{lcr} \min \sum \limits _{c_j \in C}{\sum \limits _{s_i \in S}{T_f^{(s_i,c_j)}}}& &\\ & & \\ {subject}\; {to:} & &\\ & \bigcup \limits _{c_j \in C}{S_{c_j}} = S & \\ \end{array} \right.$$

(3)

The constraint in [3] states that each ingress switch must be assigned to one controller. However, a controller may serve more than one ingress switch. It may also not supporting any ingress switch when it is overloaded. The assignment of switches to controllers should be dynamic and should consider simultaneously the current load on a controller, the load on a switch and the Round Trip Time between them. The set of controllers involved in the assignment process should be dynamically updated to exclude those which are overloaded. The mapping problem between controllers and switches may be resolved using linear programming. One of the most used solutions is Linear Minimum Cost Bipartite Assignment programming [12].

Given two sets S and C and a cost function $T_f^{(s_i,c_j)}$, we formulate the minimum cost bipartite assignment problem as follows (4):

$$\left\{ \begin{gathered} \min \sum\limits_{{c_{j} \in C}} {\sum\limits_{{s_{i} \in S}} {T_{f}^{{(s_{i} ,c_{j} )}} x_{{ij}} } } \hfill \\ subject\;to: \hfill \\ \sum\limits_{{c_{j} \in C}} {x_{{ij}} } = 1\quad \quad \forall s_{i} \in S \hfill \\ x_{{ij}} \ge 0 \hfill \\ \end{gathered} \right.$$

(4)

Where $x_{ij}$ represents the assignment of the switch $s_i$ to the controller $c_j$, taking value 1 if the assignment is done and 0 otherwise.

Lemma 1

Given an assignment problem with cost function $\widehat{c_{ij}}=f(s_i)+c_{ij}+g(c_j)$, where $f(s_i):S \rightarrow {\mathbb {R}}$ and $g(c_j):C \rightarrow {\mathbb {R}}$; $\forall i=1\cdots \mid S \mid$ and $\forall j=1\cdots \mid C \mid$.

The assignment problem with cost function $\widehat{c_{ij}}$ is equivalent to the assignment problem with cost function $c_{ij}$.

Proof

$$\begin{aligned} \sum \limits _{i=1}^{\mid S \mid }{\sum \limits _{j=1}^{\mid C \mid }{\widehat{c_{ij}}x_{ij}}}= & {} \sum \limits _{i=1}^{\mid S \mid }{\sum \limits _{j=1}^{\mid C \mid }{(f(s_i)+c_{ij}+g(c_j))x_{ij}}}\\= & {} \sum \limits _{i=1}^{\mid S \mid }{\sum \limits _{j=1}^{\mid C \mid }{f(s_i)x_{ij}}} + \sum \limits _{i=1}^{\mid S \mid }{\sum \limits _{j=1}^{\mid C \mid }{c_{ij}x_{ij}}}+ \sum \limits _{i=1}^{\mid S \mid }{\sum \limits _{j=1}^{\mid C \mid }{g(c_j)x_{ij}}}\\= & {} \sum \limits _{i=1}^{\mid S \mid }{f(s_i)\sum \limits _{j=1}^{\mid C \mid }{x_{ij}}} + \sum \limits _{i=1}^{\mid S \mid }{\sum \limits _{j=1}^{\mid C \mid }{c_{ij}x_{ij}}}+ \sum \limits _{i=1}^{\mid S \mid }{x_{ij}\sum \limits _{j=1}^{\mid C \mid }{g(c_j)}}\\= & {} \sum \limits _{i=1}^{\mid S \mid }{f(s_i)}+ \sum \limits _{i=1}^{\mid S \mid }{\sum \limits _{j=1}^{\mid C \mid }{c_{ij}x_{ij}}}+ \sum \limits _{j=1}^{\mid C \mid }{g(c_j)} \end{aligned}$$

$\square$

Clearly, $\sum \limits _{i=1}^{\mid S \mid }{f(s_i)}$ does not depend on $x_{ij}$. Hence, it has no impact on assignment result. We can also prove that $\sum \limits _{j=1}^{\mid C \mid }{g(c_j)}$ has no impact on the mapping result.

Let N be the total number of requests that are transmitted to controllers. Let $N_{c_i}^A$ be the number of requests transmitted to the controller $c_i$ according to an assignment A. Let $t_{c_i}$ the time required to server one request at the controller $c_i$. The whole time $T^A(c_i)$ required to serve $N_{c_i}$ requests is: $t_{c_i}N_{c_i}^A$ and the whole time required to serve all requests based on a given assignment A is: $\sum \limits _{i=1}^{\mid C \mid }{T^A(c_i)}=\sum \limits _{i=1}^{\mid C \mid }{t_{c_i}N_{c_i}^A}$.

Given that controllers are high-performance machines, we can assume that $t_{c_i}\backsimeq \theta$; $\forall c_i \in C$. Hence, $\sum \limits _{i=1}^{\mid C \mid }{T^A(c_i)}=\sum \limits _{i=1}^{\mid C \mid }{\theta N_{c_i}^A}=\theta N$. We presume that the whole time required to serve all requests depends only on the total number of requests and the time required to served one request, whatever is the Assignment.

The conclusion is straightforward. The optimization of $\sum \limits _{i=1}^{\mid S \mid }{\sum \limits _{j=1}^{\mid C \mid }{\widehat{c_{ij}}x_{ij}}}$ is equivalent to the optimization of $\sum \limits _{i=1}^{\mid S \mid }{\sum \limits _{j=1}^{\mid C \mid }{c_{ij}x_{ij}}}$, with only difference in values of the optimal solutions.

Using Lemma 1, we define a Relaxed Minimum Cost Assignment problem as follows (5):

$$\left\{ \begin{array}{lcr} \min \sum \limits _{c_j \in C}{\sum \limits _{s_i \in S}{T_{RTT}^{(s_i,c_j)}x_{ij}}}& &\\ & & \\ {subject}\,{to}: & & \\ & & \\ \sum \limits _{c_j \in C}{x_{ij}} = 1 & & \\ x_{ij} \ge 0 & \forall s_i\in S , c_j \in C & \\ \end{array} \right.$$

(5)

4.2 The Standard Hungarian Algorithm

The system [5] can be solved using the Hungarian algorithm [4]. The Hungarian method is a combinatorial optimizing algorithm used to solve linear Assignment problems within balanced graphs $G=(C,S,L)$. It is based on a combinatorial optimization in polynomial computation time of ${\mathcal {O}}(nm+n^2\log n)$, where $n = \mid S \mid =\mid C\mid$ and $m=\mid L\mid$ [11].

The Hungarian algorithm has been recognized as the most fastest algorithm to solve assignment problems [11] with attractive resulting time bounds, even more faster than linear programming. The Hungarian algorithm states that minimizing the total cost of a mapping matrix remains the same as minimizing the total cost of a new mapping matrix after a modification of every element in a row or column is introduced by adding or subtracting a constant. The algorithm stops when it is possible to found a minimum set of zeros that covers all the matrix.

Given a cost matrix $C=[c_{ij}]$, the algorithm consists of 5 steps:

• 1. Step 1(Row Reduction): Let denote $c_{i*}$ the minimum value from the row i. The resulting cost matrix is computed as follows: $c_{ij}=c_{ij}-c_{i*}$.

• 2. Step 2 (Column Reduction): Let denote $c_{*j}$ the minimum value from the column j. The resulting cost matrix is computed as follows: $c_{ij}=c_{ij}-c_{*j}$.

• 3. Step 3: Draw lines through appropriate rows and columns so that all the zero entries of the cost matrix are covered and the minimum number of such lines is used.

• 4. Step 4: Check the size of the zeros cover:

  • a. If the minimum number of covering lines is n, an optimal assignment of zeros is achieved and the algorithm takes end.

  • b. If the minimum number of covering lines is less than n, an optimal assignment of zeros is not yet possible. In that case, proceed to Step 5.

• 5. Step 5: Determine the smallest value not covered by any line. Subtract this value from each uncovered row, and then add it to each covered column. Return to Step 3.

4.3 MoHA: The Modified Hungarian Algorithm

Unfortunately, the Hungarian algorithm (HA) aims at finding a mapping between switches and controllers with only respect to the round trip time. Therefore, a switch will be connected obviously to the nearest controller in terms of travelling time without any consideration of the current load of neither the controller nor the switch. This may lead to unbalanced loads among controllers and may increase significantly the flow setup time.

Fig. 3

Impact of the load-driven penalty on the cost variation between a controller and a switch

To deal with this shortcoming, we introduce the Modified Hungarian Algorithm (MoHA) (Algorithm 1). MoHA considers timely controller loads in the assignment process by adjusting dynamically matrix costs using a load-driven penalty. The load-driven penalty aims to achieve a trade-off between the round trip time and the controller load.

4.3.1 The Load-Driven Penalty

The penalty $\epsilon _{c_i}$ is defined for each controller $c_i \in C$ and is proportional to the current queue utilization so that it goes up as the controller load increases. The penalty must have an impact on relative costs of the controller $c_i$ so that the probability to serve switches is more significant as the controller is less loaded. Figure 3 illustrates the impact of the penalty on costs between a controller C and a switch S. The expected variation of costs depends on the oscillation of the controller load. The penalty must be a negative value when the queue utilization $\rho _{c_i}$ falls below the committed queue utilization $\rho _{c_i}^+$ (CQU). It is expected to be a positive value as the queue utilization exceeds the CQU. To introduce the load-driven penalty, the hyperbolic tangent (tanh) function is used since it can achieve the objective of the penalty (Eq. 6):

$$\begin{aligned} \epsilon _{c_i}=tanh(\rho _{c_i} - \rho _{c_i}^{+})= \frac{e^{2(\rho _{c_i} - \rho _{c_i}^{+}})-1}{e^{2(\rho _{c_i} - \rho _{c_i}^{+})}+1} \forall c_i \in C \end{aligned}$$

(6)

Let $c_j$ and $c_k$ be two controllers with respective queue utilization $\rho _{c_j}$ and $\rho _{c_k}$, where $\rho _{c_j} \le \rho _{c_k}$. Let M(i, j) and M(i, k) be costs of assigning the switch $s_i$ to controllers $c_j$ and $c_k$, respectively. Without loss of generality, let assume that $M(i,j)=M(i,k)$. Costs are adjusted based on respective queue utilization of $c_j$ and $c_k$. Indeed, new costs ${\hat{M}}(i,j)$ and ${\hat{M}}(i,k)$ are computed as follows: ${\hat{M}}(i,j)= M(i,j)+ \epsilon _jM(i,j)$ and ${\hat{M}}(i,k)= M(i,k)+ \epsilon _kM(i,k)$.

Obviously, ${\hat{M}}(i,j) \le {\hat{M}}(i,k)$ since $\epsilon _j \le \epsilon _k$. Therefore, the switch $s_i$ will most probably be assigned to the controller $c_j$ in spite of the controller $c_k$. This remains true in general case. At each step of matrix cost updating, the jth column M(i, j) from the cost matrix is updated as follows (Eq. 7):

$$\begin{aligned} M(i,j)=M(i,j)+\epsilon _{c_j}M(i,j) \forall 1\le i \le \mid S\mid \end{aligned}$$

(7)

4.3.2 Dynamic Update of the Controller Set

The Hungarian algorithm is associated with balanced graphs. Therefore, it requires a square cost matrix of size $L=\max (m,n)$ where $m=|C|$ and $n=|S|$. When m and n are not equal, the set of controllers must be either extended or reduced to meet n. Moreover, a controller $c_i$ must no longer be considered in mapping as its queue utilization goes above an Excess Queue Utilization (EQU) $\rho _{c_i}^{max}$ and it must be immediately replaced by the least loaded one. All controllers are checked beyond each matrix updating phase. A controller which is previously ignored may be reconsidered if it resumes the normal state. Therefore, a set of active controllers $C_{active} \subseteq C$ is defined. An active controller is a controller which queue utilization is still below the EQU. Only the set $C_{active}$ is considered during the assignment process. Figure 4 shows the variation of the probability of assignment regarding the Queue size.

Fig. 4

Probability of assignment vs QU

5 Implementation of the MoHA Algorithm in Multi-controller Environments

This section proposes a distributed variant of the MoHA Algorithm which is applied to multi-controller environments. This solution involves all SDN controllers so that several messages must be exchanged in asynchronous way until an optimal assignment is reached. The proposed solution is implemented as a protocol which is inspired from the Open Shortest Path First (OSPF) protocol and is denoted the Distributed Hungarian-based Assignment Protocol (DHAP).

The diagram Fig. 5 shows the different states through which an SDN controller will go while converging to an optimal assignment. When DHAP is configured, the controller listens to neighbors and gathers all round trip times towards the set of ingress switches then it saves the information in a local database. Using the gathered information, each controller looks for an optimal assignment using the standard Hungarian Algorithm. The protocol DHAP will build three tables to store the following information:

• 1. Neighbor table: contains all discovered neighbors with which cost-state information will be interchanged.

• 2. Cost table/matrix: contains the entire road map of network traveling costs.

• 3. Assignment table: contains the optimal assignment resulting from the application of the HA algorithm.

Fig. 5

Flowchart state of the DHAP protocol

5.1 Basic Concept

In DHAP, each controller establishes neighbor relationship with others through a periodic exchange of Hello messages. Then, it communicates traveling costs of potential ingress switches to neighbors through Cost-State Advertisement (CSA) messages. This information is shared with the entire network of controllers so that a Cost-State DataBase (CSDB) is built in each controller. Finally, all controllers are expected to have the same database which is used to find an optimal switch-to-controller assignment that takes in account the current load of controllers through the application of the HA algorithm.

Each controller must inspect its load. As the load exceeds a threshold, Cost-State Update (CSU) messages are broadcast to all neighbors and hence to the entire network of controllers so that the database is updated. As a result, the HA algorithm is executed another time and the assignment table is adjusted. A controller may request for an update of costs by sending a Cost-State Request message (CSR) once no updates have been received for a long time. Upon receiving an update, a controller must acknowledge the reception by sending a Cost-State Acknowledgement message (CSAck).

5.1.1 Neighbor Discovery

DHAP enables controllers to share information with each other beyond a discovery phase that is achieved through a periodic exchange of HELLO messages. The Neighbor Discovery is illustrated in Fig. 6. A HELLO packet is a special packet (message) that is sent out periodically from a controller to establish and confirm adjacency relationships. On broadcast networks, a HELLO packet can be sent from a controller simultaneously to other controllers to discover neighbors and to elect Designated Controllers (DC) and Backup Designated Controllers (BDC).

Fig. 6

Establishing neighbor tables

5.1.2 DC and BDC Election

Designated controller (DC) and backup designated controller (BDC) are elected based on their IDs. The DC is the controller with the highest controller ID. The BDC is the next highest Controller ID. All remaining controllers are denoted DCOthers. Only Non-DC and non-BDC controllers exchange costs information with the DC and BDC, rather than exchanging updates with every other controllers upon the segment.

Similar to the OSPF protocol, the controller ID is defined as the highest IP address on any of the Loopback Interfaces. If there is no Loopback Interfaces configured, the highest IP address on its active interfaces is selected as the controller ID. All roles are decided during the neighbor discovery process.

5.1.3 Cost-State Database Loading

Upon defining roles in each controller, costs are exchanged between neighbors so that each controller builds a cost-database. The exchanging process is repeated until no modifications are introduced to the last resulting database. Thus, the database building takes end. Costs are shared through Cost-State Advertisement (CSA) messages. The cost-database building is illustrated in Fig. 7.

Fig. 7

Establishing the cost matrix

5.1.4 Cost-State Updating

As a controller observes a change in its load, it updates relative costs using the load-driven penalty. Then, it uses a Cost-State Update (CSU) message to exchange new cost information. Each controller updates its local CSDB and runs the HA algorithm to update the assignment. When a controller does not receive an update from a neighbor for a long time, it can initiate a Cost-State Request (CSR) towards the concerned controller to claim for updated information. Once a CSR is received, a controller replies with a CSU towards the controller which sends the request. The reception of a CSU must be acknowledged by sending a Cost-state Acknowledgement (CSAck). The Cost-State Updating process is shown in Fig. 7.

5.1.5 Leaving and Resuming the Active Set of Controllers

Once a controller load exceeds the Excess Queue Utilization (EQU), the controller must leave the active set of controllers so that it is no longer considered in the assignment process. The controller must enter a promiscuous mode by never responding to Hello messages sent by neighbors. Consequently, the set of neighbors of each controller is immediately updated and the CSDB is reloaded. The assignment table is therefore redefined.

As the controller load drops down, the controller resumes the active set by sending Hello messages to neighbors. Therefore, the process of assignment is restarted.

6 Experimental Results

6.1 Part1: MoHA Evaluation

The performance of the proposed solution (MoHA) is evaluated and compared to the standard Hungarian algorithm (stdHA). The experimental topology is presented in Fig. 8. The cost matrix is chosen randomly. Experimental settings are described in Table 2. All algorithms are implemented using Python3 [25] and simulated through the platform JupyterLab [24].

In order to assess the performance of the MoHA algorithm in terms of flow setup time minimization and load balancing achievement, the proposed solution is compared to the static assignment and the standard Hungarian algorithm (StdHA). The static assignment consists of connecting statically each switch $s_i$ to the controller $C_i$. Hence, $s_1$ is connected to $C_1$, $s_2$ is connected to $C_2$, and so on.

Table 2 Parameter settings for the simulation

All experiments aim to evaluate the total potential cost and the maximum load oscillation among controllers. The total potential cost refers to the total cost of the resulting assignment. The total potential cost Pot is defined as follows: $Pot=\sum \nolimits _{(s_i,c_j) \in S\times C} C(s_i,c_j)$, where $C(s_i,c_j)$ denotes the resulting cost between a switch and a controller after the assignment process takes end. The total potential cost is used to describe the impact of the assignment algorithm on the whole setup time. The maximum load oscillation $\delta$ evaluates the achievement of the load balancing among controllers and is computed as follows: $\delta = \max \nolimits _{c_i,c_j \in C^2}\mid \rho _{c_i} - \rho _{c_j} \mid$, where $\rho _{c_i}$ represents the queue utilisation of the controller $c_i$.

Fig. 8

Experimental topology: a full-meshed network between 10 switches and 10 controllers

The first simulation considers a set of empty controllers and evaluates the behavior of both solutions: stdHA and MoHA. All controllers are associated with a maximum queue size of 50 requests. As illustrated in Fig. 9, the total potential costs achieved by both solutions are equal. However, MoHA is able to ensure better load balancing than the stdHA. The difference between $\delta _{MoHA}$ and $\delta _{stdHA}$ is significant and reaches over 62 ms.

Fig. 9

Load balancing and total potential cost for empty controllers (Queue threshold = 50 requests)

The second simulation focuses on the impact of the maximum queue size on the behavior of the proposed solution. In this simulation, the maximum queue size varies in the range of [10, 30, 60, 90]. The initial queue occupation in number of requests is defined as follows: [65, 2, 15, 32, 10, 18, 68, 18, 55, 10]. Each simulation is run 50 times. Results are illustrated in Fig. 10.

Although the total potential cost in MoHA rises, the load balancing is achieved better than in the StdHA. Due to the introduction of the load-driven penalty, requests are dynamically distributed among controllers basing on the oscillation of the per-controller queue size so that loads on controllers are maintained balanced. The total potential cost is unfortunately moving up since costs are adjusted based on the hyperbolic tangent function. Nevertheless, the proposed solution is able to keep the total potential cost under the cost provided by the static assignment.

Fig. 10

Load balancing and total potential cost for various queue thresholds (#requests): a 10, b 30, c 60, d 90

The third simulation aims to evaluate the computing time of MoHA. MoHA is compared to the standard Hungarian Algorithm. At each step, the size of the cost matrix is changed and the time needed to find the optimal solution is observed. Each step is repeated 10 times. Results are shown in Fig. 11.

Clearly, the MoHA algorithm is able to perform better load balancing than the stdHA within approximately the same computation time. The introduction of the load-driven penalty has no impact on the total computation time since adjusting costs using the load-driven penalty helps to converge quickly towards an optimal mapping despite the computation overhead induced by the calculation of the penalty.

Fig. 11

Computation time(s)

6.2 Part2: DHAP Evaluation

In this section, the protocol DHAP is implemented on the floodlight [19] controller. In this simulation, five controllers and 20 switches are considered. For static assignment, each controller is connected to four switches. At each controller, the maximum queue size is fixed at 8 packets which means that the maximum arrival rate of PacketIn messages is over 11,200 pps (We consider that floodlight is able to handle PacketIn messages at the rate of 12,500 pps as depicted in [23]).

In this section, the arrival rate of each switch is 560 flows per second (fps). All incoming flows are supposed to cross switches for the first time so that, for each flow, no flow entry is found in the local flow table and a PacketIn message is sent to the controller.

In this simulation, the flow arrival rate of controllers varies in the range [0.1, 1] kfps. As adopted in [23], the different arrival rates of PacketIn messages are achieved by adjusting the rate of sending flows at end-hosts using Hping tool [22]. Data plane is simulated using Mininet [20] and all switches adopt OpenVSwitch [21].

In this section, three schemes are compared: (1) the static assignment (StAss), (2) the assignment based on DHAP without load balancing support (DHAP) and (3) the assignment based on DHAP with the load balancing support ($\epsilon$-DHAP). Each switch can connect to any controller. All Travelling costs are chosen randomly in the range of [10, 100] ms.

The variation of the average flow setup time is shown in Fig. 12. Clearly, $\epsilon$-DHAP performs better than parallel schemes. Indeed, taking in account the current load of the controller helps to reduce performance degradation of it. Obviously, less overload controllers are able to serve PacketIn messages rapidly. The difference of flow setup time between schemes increases as the flow arrival rate exceeds 560 fps. The difference reaches 30% between $\epsilon$-DHAP and DHAP, and more than 100% between $\epsilon$-DHAP and stAss.

Fig. 12

Flow setup time

The average oscillation of queue utilization between controllers for various flow arrival rates is illustrated in Fig. 13. The protocol DHAP can not preserve balanced loads among controllers. As the flow arrival rate goes up, the average oscillation becomes significant and reaches over 40 packets. However, the scheme $\epsilon$-DHAP is able to conserve reduced average oscillation of queue utilization among controllers which has not exceeded in worst case 13 packets. Obviously, the introduction of the load-driven penalty helps to adjust dynamically and adaptively the assignment of switches to controllers according to their current loads.

Fig. 13

Average oscillation of the queue utilization

7 Conclusion

This paper deals with the switch-to-controller assignment problem. It proposes an efficient assignment heuristic that achieves a trade-off between the current load of the controller and the Round Trip Time. The assignment issue is formulated as a minimum cost bipartite optimization problem that aims to minimize the flow setup time. The problem is expected to be solved using the Hungarian algorithm. Unfortunately, the Hungarian algorithm uses only static costs and does not take in account dynamic oscillations of the controller load. As a result, this solution leads to unbalanced loads among controllers.

Thus, an improvement of the Hungarian algorithm is proposed by introducing the load-driven penalty concept. It consists of adjusting dynamically values within the cost matrix according to the timely oscillation of the queue utilization in a controller. More a controller is loaded, least it has the chance to be considered in the assignment process. The set of active controllers is updated according to the oscillation of controller’s loads.

Finally, the proposed solution is implemented in multi-controller environments as a Distributed Hungarian-based Assignment Protocol (DHAP). DHAP inspires from the OSPF protocol and involves all SDN controllers. It aims to achieve an optimal switch-to-controller assignment with load balancing support. Performance of the proposed solution is analyzed and compared to the static assignment and the standard Hungarian algorithm. As shown in results, the introduction of the load-driven penalty leads to balanced loads among controllers which helps to serve flows quickly.