A Learning Automata Approach for Load Balancing in Software-Defined Networks

الموضوعات : مهندسی هوشمند برق

Mohammad Irandoost ¹ , Mona Salehi ²

1 - Department of Computer Engineering, Hamadan Branch, Islamic Azad University, Hamadan, Iran
2 - Department of Computer Engineering, Hamadan Branch, Islamic Azad University, Hamadan, Iran

تاريخ الإرسال : 30 الجمعة , ربيع الأول, 1443 تاريخ التأكيد : 02 الأربعاء , جمادى الثانية, 1443 تاريخ الإصدار : 02 الأربعاء , ذو القعدة, 1443

الکلمات المفتاحية: Learning Automata, Load balancing, Software-Defined Networks, Switch Migration,

ملخص المقالة :

Since Software-Defined Network is a logically centralized technology, the importance of scalability of the control plane has increased with increasing network scales. Therefore, the use of multiple controllers was proposed instead of a centralized controller. Although multiple controllers have solved scalability in software-based networks, they faced load imbalance on controllers due to the static assignment between the controllers and the switches. As a result, switch migration is proposed as an efficient approach to solving static allocation between the controller and switch. Switch migration allows a dynamic connection between controllers and switches, but which controller or switch is suitable for migration has become a vital problem issue in itself. A learning automaton with a variable structure is proposed to select the target controller in the proposed method. All selection and environment reaction cases are evaluated with learning automata, and choose the best controller for migration costs. The proposed method has been compared with state-of-the-art algorithms. The results showed that the proposed approach could reduce the delays of sending packets in the network by balancing the controllers with the optimal selection of target controllers for switch migration.

نص كامل:



A Learning Automata Approach for Load Balancing in Software-Defined Networks

 

Mona Salehi, Mohammad Amin Irandoost*

Department of Computer Engineering, Hamadan Branch, Islamic Azad University, Hamadan, Iran

* Corresponding author ([e-mail])

[e-mail], [e-mail]

Abstract:

Since Software-Defined Network is a logically centralized technology, the importance of scalability of the control plane has increased with increasing network scales. Therefore, the use of multiple controllers was proposed instead of a centralized controller. Although multiple controllers have solved scalability in software-based networks, they faced load imbalance on controllers due to the static assignment between the controllers and the switches. As a result, switch migration is proposed as an efficient approach to solving static allocation between the controller and switch. Switch migration allows a dynamic connection between controllers and switches, but which controller or switch is suitable for migration has become a vital problem issue in itself. A learning automaton with a variable structure is proposed to select the target controller in the proposed method. All selection and environment reaction cases are evaluated with learning automata, and choose the best controller for migration costs. The proposed method has been compared with state-of-the-art algorithms. The results showed that the proposed approach could reduce the delays of sending packets in the network by balancing the controllers with the optimal selection of target controllers for switch migration.

Keywords: Software-Defined Networks, Load Balancing, Switch Migration, Learning Automata

1. Introduction

Software-Defined Network (SDN) attracts a lot of attention in academia and industry due to its powerful programming capabilities and flexible network management [1]. SDN network is a new network architecture that aims to separate the vertical integration of networks (segregation of data and control planes) and logically centralized management. Logically centralized management does not necessarily require a single and centralized controller. Multiple physical controllers working in a unified manner can also be considered a singular/centralized controller [2, 3]. Technical load balancing distributes workload among a set of resources by optimizing available resources. It increases throughput, reduces response time, and prevents overloading in the network [4]. Compared to traditional networks, the software-defined network provides a global view of the network. It has the ability to directly plan the load balance based on the global view of controllers and switches [5]. In the first phase of designing SDNs, a centralized controller is used to manage the network. SDN has two kinds of connection: a general switch-switch connection, and the other is a controller connection, i.e., switch-controller connection and inter-controller connection [6]. The use of a single controller is appropriate for small and medium-sized networks. But with the development of networks and the increase in the number of switches, using a logically centralized controller could not meet the growing demand of flow processing and causes several problems such as scalability, availability, single point of failure, and reduced reliability in the network. Therefore, the best solution for large-scale software-defined networks is to use multiple controllers or distributed controllers and synchronize them. The use of distributed controllers solves the problems of having a single controller, but it has various challenges, such as load imbalance. The static assignment between the controller and the switch makes it difficult to accordance with the control plane to dynamic traffic changes and leads to imbalanced load distribution between controllers [7].

The unbalanced load distribution could easily lead to a hot-spot (a controller that does not have sufficient control resources to respond to switch requests), or a cold-spot (a controller whose resources have not been used efficiently), which both may cause load imbalance and network instability [8]. Therefore, in software-defined networks, work-flow planning and work-load distribution are of particular importance, which leads to the concept of load balancing. Load balancing is defined as the equal allocation of local work-load (user requests) among controllers, which means no controller with over-load or under-load conditions at different intervals throughout the network. 

Switch migration is one example of dynamic load balancing methods. In this method, the switch is transferred from an over-loaded controller to an under-loaded one, and the workload is balanced as a result of this transfer [9]. Switch migration, which is not commonly used, has challenges such as choosing the switch to migrate and the target controller. Random selection of the switch reduces the efficiency of the migration algorithm. For example, selecting a switch with a few requests increases the number of migrations and the cost of migration [10]. Although the cluster selection of switches reduces the migration costs, it also increases computational time [11]. On the other hand, not checking the residual capacity of the target controller to process new switch requests will lead to load re-imbalance and increased costs. Genetic algorithm (GA) from the evolutionary algorithms family, ant colony algorithm (ACO) from the collective intelligence family, and the Tabu search from meta-heuristics family have been the most appropriate algorithms in terms of load balance, computational time, and the average of response time [12]. However, in the ant colony algorithm, when the number of applications and controllers increases in the SDN network, we decrease diversity in the algorithm, which causes rapid convergence. Also, other algorithms need to be reviewed and restructured due to low speed and local search [13]. Considering the different states of the switch migration costs and the target controller, examining possible situations plays a decisive role. Learning Automata can examine all the possibilities of selecting controllers and the environment responses (switch migration cost and controller status synchronization cost) and provide a learning mechanism to select the target controller to choose the best controller for migration costs. Therefore, using learning automata is very important in reviewing migration candidate controllers. This algorithm is remarkably capable of finding high-quality answers for hybrid optimization problems by searching in answer space. These algorithms provide a good solution for dynamic optimization problems. Therefore, this study aims to provide a new method based on learning automata for load balancing in software-defined networks.

The rest of the paper is organized as follows. Section 2 introduces the related work. Section 3 briefly explains switch migration; in section 4, we introduce the learning automata. In section 5, we discuss the proposed method in detail. In section 6, we present the evaluation criteria and simulation results of the research. Finally, The conclusion and future work is presented in Section 7.

2. Related Work

Load balancing is the process of distributing network traffic across multiple servers. It ensures that no single server bears too much demand. Load-balancing improves application efficiency by spreading the load evenly and also increases the availability of applications and websites for users [14, 15]. The load balances in software-defined networks are divided into centralized architecture and distributed architecture [16]; this structure is presented in figure (1).

 

Load balancing in software-defined networks

 

Distributed Architecture

Centralized Architecture

 

Control plane

Data plane

Data plane

Control plane

 

Load balancing of links

 

Load balancing in flat architecture

Load balancing in hierarchical architecture

Load balancing of server

 

 

Figure 1. Load balance classification in a software-defined network.

2.1. Centralized architecture

The centralized architecture uses a single centralized controller to control the network. Load balancing is performed on a centralized controller at the data plane. It is used to solve the load imbalance in links and servers. Data plane load balancing can be classified as link load balancing, and server load balancing is discussed as follows:

 

2.1.1. Link load balancing

Optimized link load and choose a least loaded link for the new incoming data requests to overcome congestion in the data plane.

2.1.2 Server load balancing

The server load balancing strategy is used to distribute traffic on different servers to overcome network congestion.

In [17] propose a dynamic load balancing method for software-defined network architecture.  In this method, the real-time response time of each server is measured by the controller for load balancing. For balancing the load in the server pool, a genetic algorithm is implemented in [18]. The proposed algorithm can distribute extensive data from clients to servers according to flow table entries such that load is balanced on servers. In [19], several parameters like latency, hop count, bandwidth ratio, packet loss, and packet overhead in real-time are used for selecting a link with the least load. This link is used for the transmission of new incoming data. Authors in [20] proposed a new mixed algorithm based on a genetic and ant-colony for dynamic flow scheduling. The brief of these approaches is demonstrated in table 1.

Table 1. summary of link and server load balancing
Approach		Advantages	Disadvantages
Server load balancing	Try to balance the load on servers based on response time [17]	More cost-effective.  Load balancing is better than round-robin and random.	Energy-saving has not to be evaluated
	A genetic-based algorithm for load balancing in OpenFlow network[18]	Load balancing is better than round-robin and random schemes.	Not evaluated in a real environment preconfigured flow table entries
Link load balancing	An approach for finding the best path with considering Load balancing [19]	Improve latency, packet loss, bandwidth utilization rate	Use only the random method for comparison
	An optimal and dynamic elephant flow scheduling for SDN-based data center networks[20]	Total usage of links is minimized Bandwidth is increased.	There is an overhead of the EF detection method

 

2.2. Distributed architecture

In distributed mode, load balancing can be done at the data plane or control plane. At the control plane, the load balancing is carried out in flat or hierarchical architectures. In flat architecture, the load balance algorithm performs based on two approaches: the controllers' optimization or the switches' migration.

2.2.1. Optimization of controllers

The first category tries to optimize the number and position of controllers to balance load distribution in controllers and guarantee the control plane’s performance. Although this approach easily optimizes controller nodes, it cannot handle immediate traffic changes. Therefore, the researchers [6, 21-23] suggest the second group. 

2.2.2. Switch migration

In the second category, researchers use a dynamic connection between the controller and the switch, known as switch migration, to balance the load between the controllers. Although existing methods dynamically adjust the controller load and improve network flexibility, they focus more on optimizing the use of control resources [24] and less on optimizing the switch migration process. This process can lead to network overload and the complex designing of the algorithm. Also, most of the existing works are based on iterative optimization algorithms to improve the connection between the switch and the controller [25-28], which are very time-consuming and provides little satisfaction in terms of performance [29].

The authors in [30] studied how to place controllers into the network based on the propagation latency, but it only focused on where to place multiple controllers statically. In [31], a dynamic framework for matching the number of controllers and their geographical location is presented to achieve efficiency and scalability in large networks. This work reduced flow start-up time and connection overhead by linear programming but had to reconfigure the control plane by changing the network traffic statistics, resulting in network instability because of the dynamics of the network and a large number of synchronization messages [32].

The performance and scalability of the distributed controllers can be increased effectively by successful switch migration. The Migration process must be carried out with a well-designed mechanism to select which switch must be migrated to which controller. That makes a problem that is called Switch Migration Problem (SMP) [33]. In solving SMP, the static assignment between the control plane and the data plane prevented changing the controller load and network traffic changes. Authors In [9] propose an architecture named ElastiCon to address this problem. Controllers in ElastiCon are selected from a controller pool. This architecture allows the increase or decrease number of controllers under different network situations. Also, ElastiCon designs a protocol for switch migration. In this protocol, switches can be moved between controllers. However, ElastiCon does not determine clearly which switch or controller must be selected for migration.

Previous work has focused mainly on the design of the migration protocol. In [23], the design of the switch migration protocol has been improved by adding the ability to serialize messages and selecting the nearest neighbor controller as the target controller and without considering the load status of the controller. To ensure serialization, they need to buffer the messages in the controller, which increases the delay in processing the packets.

Maximizing resource utilization can be set up as an integer linear program problem that is demanding to solve alternatively. Also, resource allocation is a combinatorial optimization problem, so it can be considered an NP-hard problem that could solve by using distributed algorithms that are more reliable for dynamic networks.

In the researches [34] and [10], the switch migration problem is modeled as the maximization resource utilization problem to process more requests under available control resources, and a distributed hopping algorithm has been designed for switch migration. One of the limitations of these articles is the random selection of controllers and switches. It causes load re-imbalance and reduces the processing capacity by not using all available resources. Selecting a migration switch and target controller is an important issue to improve switch migration. In [32], a distributed decision-making mechanism has been designed based on zero-sum games theory to determine the target controller for switch migration. However, it is not clear what kind of real controller or simulation program is used. When the switches and controllers are connected dynamically, it is easier to manage network traffic changes. In [11], a heuristics approach called BalCon was designed to establish load balancing among controllers using switch migration in dynamic traffic conditions. This approach reduces the number of switch migrations and thus reduces the cost of migration. However, it increases computational time. In [8], a distributed decision-making mechanism has been designed to improve switch migration using a greedy algorithm that allows local and parallel migration. But it cannot sufficiently use the distributed control resources as it uses a centralized algorithm. In [25], the non-cooperative game theory has been used to switch migration and scalability improvement, ultimately improving load balancing, increasing resource utilization, and achieving Pareto optimal. Most existing approaches rely heavily on existing iterative optimization algorithms to manage the dynamic connection between the controller and the switch, which have a lower level of satisfaction in terms of time and performance. Table 2 shows the conclusion of the presented approaches in this sub-section.

Table 2. summary of load balance based on switch migration
Approach	Advantages	Disadvantages
SDN Controller is distributed in an elastic manner[9]	Design a protocol for switch migration.	It did not point to how to select the switch and the target controller.
Design an architecture for increasing or decreasing the number of controllers [23]	Improved switch migration protocol by adding the ability to serialize messages.	It did not check the load of the target controller.
Selects switch or switches for migration in a Distributed manner [10, 34].	Design Distributed Hopping Algorithm for switch migration. Processing more requests under available control resources.	Random selection of controllers and switches. Load re-imbalance.
Dynamically a switch is selected for migration [32].	Using zero-sum games theory to determine the target controller.	It is not clear what kind of real controller or simulation program has been used.
Designing an algorithm for load balancing on controllers by switch migration[11]	Reduces the number of switch migrations and thus reduces the cost of migration.	Increases computational time.
Load balancing can be achieved by switch migration in a distributed manner  [8]	Using a greedy algorithm that allows local and parallel migration.	It cannot sufficiently use the distributed control resources as it uses a centralized algorithm.
Non-cooperative game is used for Dynamic switch migration [25].	Using non-cooperative game theory. Improvement load balancing and resource utilization. Achieves Pareto optimal.	Didn’t investigate the migration efficiency.

 

3. Switch migration

When the control plane and the data plane are connected statically causes load imbalance in the distributed control plane. Therefore, the Open Flow protocol suggested a solution for this problem. In the Open Flow protocol version 1.2, controllers can manage each switch with three different roles: 1. Master 2. Equal 3. Slave. Each switch can have just only one master controller and more than one equal or slave controller. If the master controller has a problem due to over-loading or under-loading, the equal controller or even the slave controller can change to the master role. However, the Open Flow protocol and its features did not offer any explicit mechanism for migrating switches or changing the role of the controller because the writer of Open Flow specification believed that it was the controller's task to select the master controller among them.

Switch migration takes place in three modes:

1- If the aggregated load in the network is more than the capacity of all controllers, we must add a new controller to the network, and a series of switches migrate to the new controller.

2 - To save communication costs and energy and maximize the use of controller resources, the controllers with under-load than a defined threshold go to sleep. Their connected switches must migrate to another controller with enough capacity to process the given switch or switches.

3. When a controller's load exceeds the processing capacity, if we do not change the number of controllers, the migration process should be done by selecting the appropriate switch and target controller.

4. Learning Automata

Learning Automata (LA) is a reinforcement learning approach. LA in interaction with the environment can achieve an optimal policy [35]. Rewards and penalties evaluate the efficiency of these interactions. There is no information about the best action in this approach, and initially, all actions have the same chance. This action is randomly done in the environment based on the probability vector. Given the responses received from the environment, the probability of the actions is updated. Using LA in complex, dynamic, and random environments is effective and helpful, especially when we do not have enough information. We can model the LA environment with  is a limited set that automata actions are selected from, is the environment response to the performed actions, and  is the probability of penalties for each action. LA environments consist of stationary and non-stationary environments. The stationary environment is when the probability of an action’s penalty is fixed in time. If penalty probability alters during the time, we can say that the environment is non-stationary. Although, based on the answers, the environment can be classified into three categories: P, Q, and S. In P mode, the environment response to the action are 0/1. 0 is assigned as the desired action, and 1 is assigned as the undesirable action. The desirable action is rewarded, and an undesirable action is penalized. In Q mode, the environment response is in a separate boundary space in the domain [0, 1]. In S mode, the environment response is persistent in the domain [0, 1]. Learning automata are divided into two major categories based on their structure: fixed structure and variable structure [36]. As shown in figure (3), the structure of the LA model is shown by three variables: inputs, actions, learning algorithm, which has a recursive relation and is used to improve the probability vector action.

The recursive equations (1) and (2) are used to update the probability of actions by learning automata. In these equations,represents the action selected at the moment n, and p(n) is considered the corresponding action of the probability vector. Assume an as the reward parameter and b as the penalty parameter. Then, r denotes the number of the automata’s actions.

 

 

(1)

As shown in figure (2), learning automata select the current actions based on past experiences from the environment. The action probabilities shift is done based on the learning algorithm in LA with the variable structure. In this type of automata, the internal state of the automata is represented by the probabilities of the automata actions.

(2)

Learning automata

Environment

 

 

 

 

Figure 2. Relationship between learning automata and its environment

 

 

5. Proposed Method

Elastic scalability and load balancing are important in useful switch migration and enabling software-defined network controllers to be flexible. However, learning how migration performance may improve is a challenging issue. To deal with this, a decision-making approach based on switch migration has been proposed to detect the load imbalance using the switch migration trigger metric. In this migration, there is a trade-off between load balance rate and migration costs.

The new approach is proposed based on learning automata. In the proposed method, the main goal is to select an effective controller as the master controller to upgrade the load balancing factor and properly select a switch with a low migration cost. These schemes try to solve the following three sub-problems regarding the migration of switches:

1.        Measure the controller’s load imbalance and decide about migrate the switches.

2.        Make a trade-off between the costs of the migration and the rate of the load balance.

3.        Perform a migration program that uses a migration efficiency model to guide possible migration actions.

In the proposed method, the SDN controllers form a set of automata actions, and each controller has the same probability of being selected as the target controller. The cost of data aggregation, switch migration, and synchronization cost of the controller’s status are considered the environment responses. First, one of the controllers is randomly selected. If adding a switch to the controller does not lead to overloading, which means the environment's response is positive, then this automata action is rewarded. So, the probability of selecting the controller will be increased, and the probability of selecting other controllers will be decreased. Among the automata’s actions, the action with the most probability is selected as the automata's output, which is the target controller.

Most existing approaches do not have the power of adaptability and good learning in dealing with different environments. In the proposed method, the adaptive learning rate is used to solve this problem. In this way, when convergence occurs, we reduce the learning rate. In other words, if the difference between the probability of new estimates and the average of previous estimates is large, the learning rate will increase, and if the network structure changes, the learning automaton rate will be decreased. Figure (3) shows the overall structure of the switch migration algorithm based on learning automata.

Selecting migrations switch and target controller based on learning automata

Collecting network data and create a decision field for migration

Switch migration and transfer of controller roles

 

 

 

 

 

No

 

 

 

Yes

 

Figure 3. The overall structure of switch migration algorithm based on learning automata.

 

 

 

 

 

 

 

 

 

 

 

 

5.1 Model and Formulation

A. SDN Network Model

As shown in figure (4), the SDN network can be represented as an undirected graph G= (V, E) where V represents the nodes (switch and controller), and E represents the links (network communication). We represent the controller with the symbol C. If a network has M controllers, then we will have similarly if the SDN network has N switches, we will have . The control domain which each controller manages is represented by.

The network is divided into several sub-domains; distinct controllers manage each domain. In Figure (4), four controllers have been seen in the network. Each controller is connected to some switches to create a sub-domain. If the number of switches connected to the controller C2 is more numerous or the sub-domain 2 has many requests, the controller C2 is in the over-loaded status, and the load distribution of the controllers is uneven in the network.

Each controller manages several switches. However, the static assignment between the controllers and the switches causes load imbalance and inefficient performance amongst the controllers. The structure of the proposed method provides a particular area for the switch migration that includes just one over-loaded controller. This allows parallel migration in large-scale networks and increases the load balancing among controllers in networks. As it can be seen in Figure (5), the network is partitioned into four sub-domains, and controller C2 is the overloaded controller in sub-domain 2, which includes three controllers. But only sub-domain 1 and 3 have been selected to perform the proposed method. Sub-domain 4 has not been selected because it does not have enough capacity to migrate the switch; so  We choose a switch from the set of switches in the overloaded sub-domain in the selected area and select the target controller.

The shortest distance is used for transferring traffic between any two nodes. In addition,  is used for representing the hop distance between node i and node j. As shown in figure (5), the assignment of controllers and switches can be shown according to the network graph using a matrix. , Represents that the switch  is associated with the controller, otherwise.  Table 3 illustrates a summary of notations that are used in this paper.

 

Figure 5. The assignments of controllers and switches.

	….				X
0		0	1	1
1		1	0	0
0		0	0	1
					…
1		0	0	0

Summary of notations in this paper

 

 

B. The migrated switch

The migrated switch is selected from the switches connected to the over-loaded controller. Selecting a switch to migrate is based on a parameter called the probability of switch selection. The probability of switch selection is calculated based on the distance between the switch and the controller and the number of switch requests (the number of packet-in messages sent from the switch to the controller) [37].

Table 3. Continued
Symbel	Description
	controller.
	switch.
	The domain which controller   manage.
	The distance between node i and node j.
	Denotes the connection between switch Si and controller Cj.
	The selection probability of switch
	The number of requests sent from switch  to controller .
	The cost of data aggregation.
	The cost of Switch migration.
	The cost of migration rule installation.
	The cost of communication between switches.
	The cost of Migration request.
	The cost of synchronizing the status of controllers.
	Average of bit rate for traversing one switch.
	The average size of flow-mod packets.
	Data is shared between the two controllers

 the number of switch requests and  is the distance between the switch and the controller.

For each switch, we consider a flag whose initial value is zero. When the switch is selected for migration, the flag's value changes to one, and by counting the number of flags with values of one, we measure the migration number of the switch.

Amongst switches, a switch with the highest selection probability is selected for migration.

A random automaton with a variable structure is used to select the target controller in the proposed method. In this structure, the probabilities of automata actions are updated in each iteration.

Learning algorithms always try to optimize their performance and characteristics by identifying the environmental features to achieve a specific goal. Learning automata is also one of these algorithms that try to change the probability of its states according to the responses it receives from the environment. Each state also performs its own specific function.

First, one of the controllers is randomly selected. The environment response is selected based on the lowest aggregation value of the following parameters.

1.       The cost of data aggregation (Cda)

2.       The cost of switch migration (Csm)

3.       The cost of synchronizing the status of controllers (Csyn)

 

(3)

The fitness function is considered for optimal selection of the target controller to minimize the costs of the data aggregation, switch migration, and synchronize the status of the controllers.,, are the corresponding weights of three costs.

1) The cost of data aggregation () is obtained from the equation (5) [37].

(4)

In this case, dir represents the distance between the switch Si and the controller Cr, is the average of bit rate for transferring one switch, which depends on the link connected to each switch, and xir indicates the relation between the switch Si and the controller Cr.

2) The cost of switch migration (Csm) is considered as a linear sum of the cost of migration rule installation (Crule), the cost of communication between switches (Ccom), and the cost of migration request (Creq), which are presented in equation (6)[37].

(5)

3) The cost of migration rule installation (Crule):

If a switch has been selected to migrate, the controller must set up flow-mod rules on the switch in the area. Equation (7) displays the cost of migration rule installation[37].

(6)

 indicate the average size of flow-mod packets. The dir indicates the distance between the switch Si and the controller Cr and xir indicates the connection between the switch Si and the controller Cr.

4) The cost of communication between switches (Ccom):

The migration requests may pass through various switches to reach the target controller, in which case the cost of communication between the switches is considered and provided as equation (8) [37].

(7)

In this case,  is the average of the connection rate between the switches, xir indicates the connection between the switch Si and the controller Cr, and xjk indicates the connection between switch Sj and the controller Ck. dir is the distance between switch Si and the controller Cr, and djk is the distance between switch Sj and the controller Ck.

5) The cost of migration request (Creq)

When the migration switch sends its request to the target controller, the cost of the migration request is provided in the following equation [37].

(8)

In this equation,  is the minimum distance between the switch and the controller,  is the average connection rate between the switches, and xir indicates the connection switch Si and the controller Cr, and xjk indicate the connection between switch Sj and the controller Ck.

6) The cost of synchronizing the status of controllers (Csyn):

Status synchronizing between controllers occurs after switch migration. Csyn provides the cost of synchronizing the status between the two controllers as an equation (10) [37].

(9)

In this equation, μ is the shared data between the two controllers, which depends on the average connection rate between the switches. Since the controllers do not share information of all sub-domains, therefore μ <ε. and drk is the distance between the controller r and the controller k, if the environment's response is positive, which means that the cost of switch migration and the cost of synchronizing the status of the controllers are low, this automata action is rewarded and the probability of selecting the controller increases and the probability of selecting other controllers decreases. Otherwise, if the environment's response is negative, which means that the cost of selecting the controller is high, this automata action will be penalized. The probability of selecting the controller is reduced, and according to the probability vector, another controller is selected for evaluating the environmental response. Figure (6) shows the flowchart of the proposed algorithm based on learning automata.

 

 

 

 

 

 

 

 

 

 

 

5.2. The proposed method flowchart

 

(10)

Collecting network data and creating a decision field for migration

 

 

Creating Selection Area for switch migration

 

Switch selection (according  to equation (3))

 

 

Select an automata action(a controller) randomly according to the probability vector

Reward the selected action according to equation (1)

 

β=0

Positive response from the environment

 

β=1

Negative response from the environment

 

 

No

 

Penalize the selected action according to equation (2)

 

Yes

 

 

 

Figure 6. The flowchart of the proposed method

6. Findings

 

In this section, the proposed method is compared with [38] and [37]. These algorithms are presented in Table (4).

 

Table 4.The evaluated algorithms
Method	Abbreviation
Greedy	Greedy
Distribution decision making	DDM
Learning automata mechanism	LAM

 

·       Greedy: In [38], a greedy algorithm has provided a model for efficient switch migration. A balance between the cost of migrating switches and the load balance rate is achieved. In this article, unlike LAM and DDM, the switch with the least load and the maximum distance select for migration (because the goal is to reduce the cost of communications overhead and increase the load balance). In the next step, if the total load of the selected controller and switch is less than the total capacity of the controller, the selected controller enters a temporary set of selected controllers. The controller that is the most efficient in terms of the migration cost is chosen as the destination.

 

·       Switch migration based on distributed decision mechanism which was proposed [37]. In this method, before migrating a switch, a temporary area of neighboring controllers is created that has certain conditions, then, among the available controllers in the temporary area, the controller is selected in round-robin which has a lower total cost (switch migration cost, data collection cost, controller status synchronization cost). To select the switch, the switch with the highest number of requests and the maximum distance from the controller is selected to migrate.

 

6.1 Evaluation criteria

 

Different criteria have been used to compare the proposed method with others. These criteria are introduced below.

 

1- Number of Requests

                                                

2- Delay

Delay is the average amount of time for a packet to move from one network point to another.

The number of requests which each controller processes

(11)

3- Jitter

The delay variance is when the packet passes from when it is sent in the network until it reaches its destination.

(12)

 

6.2 Creating topology

Mininet [39] is a network emulator and one of the most well-known simulators presented for software-defined networks. Features of this simulator include being open source, installing on the Linux operating system and running on the Linux-based applications, the ability to use different controllers in the created topology, and the possibility of using real programs such as traffic generating tools. This simulator creates a network with hosts, switches, controllers, and virtual links. Mininet has been used to implement network topology. In Mininet, there is a graphical user interface which is called Miniedit. Figure (7) show an example of creating a topology in Miniedit.

 

 

Figure 7. An example of creating a topology in Miniedit

The D-ITG¹ [40] tool has been used in this research. D-ITG, as a traffic generator on the Internet, is a platform that can generate IPv4 and IPv6 traffic by objectively replicating the workload of current internet applications. Random seed plays an essential role in the packet generation model since it is not the same in different models. Therefore the generated packets are not perfectly matched. If the probability distribution function is equal, the generated packets are approximately had the same tendency. In our experiments, for 30 seconds, we generate UDP packets under an exponential distribution function. The average size of packets is 1250 Bytes. The generated packets are requested under exponential distribution increasing rate to 2500 (p=0.25), 5000 (p=0.5), 7500 (p=0.75), and 10000 (p=1) per second. The link bandwidth is 10 Mbps.

This article uses a Python-based RYU controller[41]. The controller supports various protocols such as Open Flow, Netconf, etc., for managing network devices. RYU also supports different versions of the open flow protocol, such as 1.0, 1.2, 1.3, 1.4, and 1.5. The simulations parameters are presented in table 5.

(13)

Table 5.Simulations Parameters
Parameter	value
OpenFlow Controller	RYU controller
Openflow Version	OpenFlow V1.2
Link bandwidth	10Mbps(10BaseT),100Mbps(100BaseT)
Routing protocol for Legacy router	OSPF
Simulation Time excluding setup(sec)	30
Data Rate (byte/sec)	2500,5000,7500,10000
Distribution for Packet Generation	Exponential

 

6.3 Simulation results

 

The number of requests processed by each controller is recorded to show the load distribution of the controller. Further balance in processing requests by each controller results in better performance of the controller in load balancing.

 

 

Figure 8. the number of the request of each controller before load balancing

 

 

Figure 9. comparison of the number of requests in controllers in the evaluation methods

According to Figures (8) and (9), the proposed method has better performance than the greedy algorithm method. The greedy mechanism has a better speed and performance than its similar methods, but it may not lead to an optimal global response. In the DDM method, the selection of the target controller is done in a greedy mode and based on the cost of the switch migration. However, the decision field forms a temporary area of candidate controllers for migration. So, there is a possibility of optimal local selection. However, all learning states of selection and environment reaction (migration cost) are evaluated using learning automata in the proposed method. A learning mechanism is offered to select the target controller, which allows the best controller to be selected in terms of migration costs.

 

Figure 10. Comparison of delay in controllers in the evaluation methods

According to Figure (10), DDM shows better performance in terms of delay criteria. Learning automata has reduced the delay in sending packets in the network by load balancing in the controllers using the optimal selection of target controllers for switch migration. By running the switch migration algorithm using learning automata, the number of requests changed for controller C1 from 103 to 62, controller C2 from 60 to 76, controller C3 from 23 to 67, and controller C4 68 to 55 requests. The controller C3 initially had a low number of requests, but after executing the load balancing algorithm and switch migration, the requests of other controllers have been transferred to controller C3. When a controller has overloaded, it leads to a delay in requests. Therefore, with the reduction of requests in controllers C1 and C4, we see a significant decrease in the average delay in these controllers. Also, due to the LAM curve, the average delay of all controllers in the learning automata method is almost at the same level, which indicates the load balance in the proposed algorithm.

 

Figure 11. comparison of delay variation in controllers in the evaluation methods

Data packets remain for a period of time in the network to reach their destination. Each data packet contains a header, footer, and a number to connect to the previous and next packets. The length of time each data packet stays on the network to reach its destination is called Latency (Delay). Data packets are not always received at their destination, respectively, but they may be out of turn. In other words, some data packets may reach to destination with a little latency and others with much latency. Therefore, Delay variance is important in the communication delay. The lower the delay, the better the service quality will be.

 

According to Figure (11), the use of the automata learning algorithm compared with the greedy algorithm method and DDM shows better performance in terms of time latency variance. When requests are unevenly distributed among controllers, the time delay variance shows large fluctuations in the controllers. Some packets arrive with a little latency, and others reach with much latency. Therefore, by reducing the requests of controllers such as controller C4, the time latency variance in this controller is significantly decreased, and the LAM curve also shows low variations in time latency in all controllers. In general, it can be said that learning automata have been able to reduce the delay of sending packets in the network with load balancing in controllers by optimal selection of target controller for switch migration.

 

7. Conclusion and Future work

 

Switch migration algorithm is a promising approach for load balancing in SDN networks. Suppose the number of requests to any controller exceeds its processing capacity, the controller overloads and requests for switch migration to reduce the additional load. The selection of the switch is calculated based on the number of requests on the switch and the distance between the switch and the controller. In the next step, the selection of the target controller is done based on minimizing the cost. In this research, a method presents to select the target controller using learning automata. In this method, the controllers of the software-defined network form a set of automata actions. Each controller has the same probability of being selected as the target controller. The costs of data aggregation, the cost of switch migration, and controller status synchronization are considered the environmental response. First, one of the controllers is selected randomly. If adding a switch to the controller does not overload it, meaning that the environment response is positive, this action is rewarded. The probability of selecting the controller increases. Among the automata’s actions, the action with the most probability will be selected as the automata output. The evaluation results showed that LAM has a better performance than the Greedy and DDM algorithms in terms of latency, latency variance, and proper distribution of requests in controllers.

 

The analysis of the results shows that the greedy mechanism generally has a better speed and level of execution than similar methods. Still, depending on the problem, it may not lead to an optimal global solution. In the DDM method, despite the decision field that forms a temporary area of candidate controllers for migration, selecting the target controller is done in the greedy mode and based on the cost of switch migration; therefore, the optimal local selection is probable. But in the proposed method, all selection status and environment responses were examined using the learning automata. A learning mechanism for selecting the target controller is presented, allowing selecting the best controller in terms of migration costs.

 

In our future work, the optimal number of controllers consider in networks with multiple domains. Also, try to reduce the overhead of synchronization between controllers. In addition, this paper does not consider a situation that the number of packet-in sent by switches is much more than controller capacity. In such a situation, switch migration cannot cause load-balanced, and at least one controller must be added to reach it. This item will be considered in our future works.

 

 

References

 

1.        McKeown, N., et al., OpenFlow: enabling innovation in campus networks. 2008. 38(2): p. 69-74.

2.        Levin, D., et al. Logically centralized? State distribution trade-offs in software defined networks. in Proceedings of the first workshop on Hot topics in software defined networks. 2012.

3.        Xie, J., et al., Control plane of software defined networks: A survey. 2015. 67: p. 1-10.

4.        Talukder, A., et al. Dual threshold load balancing in SDN environment using process migration. in 2018 International Conference on Information Networking (ICOIN). 2018. IEEE.

5.        Sun, P., et al., MARVEL: Enabling controller load balancing in software-defined networks with multi-agent reinforcement learning. 2020. 177: p. 107230.

6.        Zhang, B., X. Wang, and M.J.C.C. Huang, Multi-objective optimization controller placement problem in internet-oriented software defined network. 2018. 123: p. 24-35.

7.        Li, Z., et al., Dynamic SDN controller association mechanism based on flow characteristics. 2019. 7: p. 92661-92671.

8.        Hu, T., et al., A distributed decision mechanism for controller load balancing based on switch migration in SDN. 2018. 15(10): p. 129-142.

9.        Dixit, A., et al. Towards an elastic distributed SDN controller. in Proceedings of the second ACM SIGCOMM workshop on Hot topics in software defined networking. 2013.

10.        Cheng, G., et al., Toward a scalable SDN control mechanism via switch migration. 2017. 14(1): p. 111-123.

11.        Cello, M., et al. BalCon: A distributed elastic SDN control via efficient switch migration. in 2017 IEEE International Conference on Cloud Engineering (IC2E). 2017. IEEE.

12.        Jamali, S., et al., On the use of the genetic programming for balanced load distribution in software-defined networks. 2019. 5(4): p. 288-296.

13.        Keskinturk, T., et al., An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times. 2012. 39(6): p. 1225-1235.

14.        Belyaev, M. and S. Gaivoronski. Towards load balancing in SDN-networks during DDoS-attacks. in 2014 International Science and Technology Conference (Modern Networking Technologies)(MoNeTeC). 2014. IEEE.

15.        Komajwar, S., T.J.I.T.o.N. Korkmaz, and S. Management, SPRM: Source Path Routing Model and Link Failure Handling in Software Defined Networks. 2021.

16.        Li, L. and Q. Xu. Load balancing researches in SDN: A survey. in 2017 7th IEEE International Conference on Electronics Information and Emergency Communication (ICEIEC). 2017. IEEE.

17.        Iqbal, M.F., Evaluation of Current Load Balancing Techniques in a Software Defined Network Aimed at Improving Quality of Service. Selected Computing Research Papers, 2019: p. 29.

18.        Chou, L.-D., et al., A genetic-based load balancing algorithm in openflow network, in Advanced technologies, embedded and multimedia for human-centric computing. 2014, Springer. p. 411-417.

19.        Patil, S. Load balancing approach for finding best path in sdn. in 2018 International Conference on Inventive Research in Computing Applications (ICIRCA). 2018. IEEE.

20.        Li, H., H. Lu, and X. Fu, An optimal and dynamic elephant flow scheduling for SDN-based data center networks. Journal of Intelligent & Fuzzy Systems, 2020. 38(1): p. 247-255.

21.        Al-Tam, F. and N.J.C.N. Correia, Fractional switch migration in multi-controller software-defined networking. 2019. 157: p. 1-10.

22.        Hu, T., et al., EASM: Efficiency-aware switch migration for balancing controller loads in software-defined networking. 2019. 12(2): p. 452-464.

23.        Dixit, A., et al. ElastiCon; an elastic distributed SDN controller. in 2014 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS). 2014. IEEE.

24.        Ye, X., G. Cheng, and X.J.C.N. Luo, Maximizing SDN control resource utilization via switch migration. 2017. 126: p. 69-80.

25.        Wu, G., et al., Dynamic switch migration with noncooperative game towards control plane scalability in SDN. 2019. 32(7): p. e3927.

26.        Chen, H., G. Cheng, and Z.J.C.C. Wang, A game-theoretic approach to elastic control in software-defined networking. 2016. 13(5): p. 103-109.

27.        Li, J., X. Hu, and M. Zhang. Research on dynamic switch migration strategy based on FMOPSO. in 2018 IEEE 3rd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC). 2018. IEEE.

28.        Xue, H., K.T. Kim, and H.Y.J.S. Youn, Dynamic load balancing of software-defined networking based on genetic-ant colony optimization. 2019. 19(2): p. 311.

29.        Bourke, T., Server load balancing. 2001: " O'Reilly Media, Inc.".

30.        Heller, B., R. Sherwood, and N.J.A.S.C.C.R. McKeown, The controller placement problem. 2012. 42(4): p. 473-478.

31.        Bari, M.F., et al. Dynamic controller provisioning in software defined networks. in Proceedings of the 9th International Conference on Network and Service Management (CNSM 2013). 2013. IEEE.

32.        Cheng, G., et al., Dynamic switch migration towards a scalable SDN control plane. 2016. 29(9): p. 1482-1499.

33.        Al-Tam, F. and N.J.I.A. Correia, On load balancing via switch migration in software-defined networking. 2019. 7: p. 95998-96010.

34.        Cheng, G., et al. DHA: Distributed decisions on the switch migration toward a scalable SDN control plane. in 2015 IFIP Networking Conference (IFIP Networking). 2015. IEEE.

35.        Narendra, K.S. and M.A. Thathachar, Learning automata: an introduction. 2012: Courier corporation.

36.        Irandoost, M.A., A.M. Rahmani, and S.J.T.J.o.S. Setayeshi, Learning automata-based algorithms for MapReduce data skewness handling. 2019. 75(10): p. 6488-6516.

37.        Hu, T., et al., A distributed decision mechanism for controller load balancing based on switch migration in SDN. China Communications, 2018. 15(10): p. 129-142.

38.        Wang, C.a., et al., A switch migration-based decision-making scheme for balancing load in SDN. IEEE Access, 2017. 5: p. 4537-4544.

39.        Xiang, Z. and P. Seeling, Mininet: an instant virtual network on your computer, in Computing in Communication Networks. 2021, Elsevier. p. 219-230.

40.         ; Available from: https://www.devmanuals.net/install/ubuntu/ubuntu-16-04-LTS-Xenial-Xerus/how-to-install-d-itg.html.

41.        RYU SDN Framework. Available from: https://osrg.github.io/ryu-book/en/Ryubook.pdf.

 

17

 

---

[1]  Distributed Internet Traffic Generator 

---