#
Dynamic Load-Balancing Vertical Control for Large-Scale Software-Defined
Internet of Things

Lianming Zhang, Xiaoxun Zhong, Yehua Wei, and Kun Yang L. Zhang
(zlm@hunnu.edu.cn), X. Zhong and Y. Wei<EMAIL_ADDRESS>are with Key
Laboratory of Internet of Things Technology and Application, College of
Physics and Information Science, Hunan Normal University, Changsha, China. K.
Yang<EMAIL_ADDRESS>is with the School of Computer Sciences and
Electrical Engineering, University of Essex, CO4 3SQ, Colchester, UK.

###### Abstract

As the global Internet of things increasingly is popular with consumers and
business environment, network flow management has become an important topic to
optimize the performance on Internet of Things. The rigid existing Internet of
things (IoT) architecture blocks current traffic management technology to
provide a real differentiated service for large-scale IoT. Software-defined
Internet of Things (SD-IoT) is a new computing paradigm that separates control
plane and data plane, and enables centralized logic control. In this paper, we
first present a general framework for SD-IoT, which consists of two main
components: SD-IoT controllers and SD-IoT switches. The controllers of SD-IoT
uses resource pooling technology, and the pool is responsible for the
centralized control of the entire network. The switches of SD-IoT integrate
with the gateway functions, which is responsible for data access and
forwarding. The SD-IoT controller pool is designed as a vertical control
architecture, which includes the main control layer and the base control
layer. The controller (main controller) of the main control layer interacts
upward with the application layer, interacts with the base control layer
downwards, and the controller (base controller) of the basic control layer
interacts with the data forwarding layer. We propose a dynamic balancing
algorithm of the main controller based on election mechanism and a dynamic
load balancing algorithm of the basic controller based on the balanced delay,
respectively. The experimental results show that the dynamic balancing
algorithm based on the election mechanism can ensure the consistency of the
messages between the main controllers, and the dynamic load balancing
algorithm based on the balanced delay can balance between these different
workloads in the basic controllers.

###### Index Terms:

SD-IoT, Large-Scale IoT, Traffic Management, Vertical Control, Load Balancing

##  I Introduction

IoT is a kind of the Internet which is connected to the things. IoT contains a
large number of interconnected devices, including household appliance, public
facilities, wearable equipments, residential office buildings, industrial
processes, medical equipments, law enforcement equipments, military
installations, unmanned aerial vehicles, interconnected cars and other network
applications that may be almost impossible to imagine at present [1]. IoT
provides a huge market opportunity for equipment manufacturers, Internet
service suppliers and application development engineers. At present, the
global application of IoT is increasingly favored by consumers and business
environment. Machine to machine (M2M) has become the fastest growing mobile
connection category in IoT application. According to Cisco VNI forecast [2],
global M2M connections will grow from 780 million in 2016 to 3.3 billion by
2021, going to grow at a compound annual growth rate of 34 percent, and there
will be a fourfold growth from 2016 to 2021. The traffic generated by global
M2M connections reached 0.14 billion gigabytes per month at the end of 2016,
accounting for 2$\%$ of global mobile data traffic. At the end of 2021, M2M
traffic will reach 2.45 billion gigabytes per month, making up 5$\%$ of global
mobile data traffic.

Traffic management is an important theme to optimize the performance in
Internet of Things [3, 4]. Through the dynamic analysis, forecasting and
adjustment of transmission data, the traffic management technology to optimize
the performance has been widely used. Existing traffic management technologies
rely on closed, rigid existing network architecture designs. The control plane
and data plane of this network architecture are tightly coupled, integrated,
which hinders current traffic management techniques to provide true
differentiated services for large-scale IoT to accommodate fast, growing,
uneven, high-speed variable flow mode.

SD-IoT is a new paradigm [5, 6], which introduces the software defined
framework into the IoT architecture. Under the software defined framework,
users can get a dynamic, automated network, which is a bit different than in
the past and provides full-virtualization for application requirements. The
architecture of the SD-IoT separates the control plane from data plane, which
has the following obvious characteristics: visibility, programmability,
openness, virtualization, and new flow patterns and characteristics. More
importantly, SD-IoT provides a unified global network view that paves the way
for inherently flexible, adaptive, customizable traffic control and management
technologies of large-scale IoT.

The architecture of SD-IoT consists of two main components: SD-IoT controllers
and SD-IoT switches. When an SD-IoT switch receives a new flow, the first
packet of the flow is forwarded to a corresponding SD-IoT controller. The SD-
IoT controller to compute a forward path for the flow. All SD-IoT switches
located on this path install a new forwarding rule. The SD-IoT switch sends
the first packet of the new flow to the SD-IoT controller that can cause
transmission delays, and the SD-IoT controller calculates the forward path of
the flow to generate a processing delay. Even more frightening is that it
takes a lot of time to install new forwarding rules on the forward-path
switches and is prone to delay peaks. When a large number of new flows are
injected into the SD-IoT switch, the control plane and data plane of the SD-
IoT architecture all generate significant computing and communication costs.
Beacon [7], which is the most advanced multi-threaded controller, has a
maximum throughput of 12.8 million flow requests per second (Mfrps). The
global M2M traffic reached 32407.4 billion bytes per second at the end of 2016
[2]. Obviously, a single SD-IoT controller has been unable to meet the needs
of big data flow for large-scale networks. In order to solve the above-
mentioned problems of large-scale IoT, our preliminary work [8, 9] studied the
problem of load balancing of data plane in large-scale software-defined
networks. In this paper, we will further study the dynamic load balancing in
the control plane of the large-scale SD-IoT. The main contributions of this
paper are as follows.

  * •

A general framework for the large-scale SD-IoT is presented, and it includes
two main components: SD-IoT controllers and SD-IoT switches. The SD-IoT
controllers use resource pooling technology, which are responsible for the
centralized control of network resources. The SD-IoT switches integrate IoT
gateway function, and are responsible for data access and forwarding.

  * •

A vertical control structure for the control plane of SD-IoT is proposed, and
it includes the controllers (main controllers) of the main control layer and
the controllers (basic controllers) of the basic control layer. The main
controllers are responsible for resource management and coordination of the
basic control layer, and also provide a northbound interface for the upper
application. The basic controllers are responsible for the interaction between
the control layer and data forwarding layer.

  * •

A dynamic load balancing algorithm for the main controllers based on the
electoral mechanism is proposed, which selects a main controller called a
_Leader_ from the main controllers to coordinate the message consistency
between the main controllers to ensure that the main controllers can get the
same, real-time global network view.

  * •

A dynamic load balancing model based on balanced delay is deduced, and then a
dynamic load balancing algorithm of the basic controller is proposed to reduce
the network delay and avoid the traffic load imbalance.

The remainder of this paper is organized as follows. Section II summarizes the
relevant work and current research trend of the load balancing schemes of the
software-defined networking. Section III presents the general framework of the
SD-IoT and the vertical control structure of the control plane. Section IV
proposes dynamic load balancing algorithms for main controllers and basic
controllers. Section V presents the experiment settings and evaluates the
performance. Finally, a conclusion is given in Section VI.

##  II Related work

When an SD-IoT switch receives a new flow, it forwards the first packet of the
flow to the corresponding SD-IoT controller. The SD-IoT controller calculates
and determines the path to forward the flow. The forwarding rules are
installed in all SD-IoT switches on the flow path. Obviously, when a large
number of new flows are injected into the IoT, the SD-IoT controller will
frequently receive and forward the new flow request information and calculate
the flow path. At the same time, the installation of the forwarding rule
process in the SD-IoT switch will produces a delay peak, easy to cause the
Internet traffic load imbalance. Thus, a single centralized controller is easy
to become a performance bottleneck. At present, the feasible solutions of the
performance bottlenecks can be divided into two categories [3, 4]: controller
load balancing and switch load balancing.

###  II-A Controller Load Balancing

Controller load balancing refers to the ability to enhance network data
processing by using multiple controllers. It can be divided into two levels:
horizontal controller load balancing and vertical controller load balancing.
Horizontal controllers adopt flat structure. All controllers have the same
responsibilities and functions, and the controllers can communicate with each
other directly. Vertical controllers adopt hierarchical structure. Controllers
in each layer have different responsibility and duty, and upper controllers
are responsible for the communication and coordination between lower
controllers.

Typical controllers with level structure are HyperFlow [10], DIFANE [11], Onix
[12],and BalanceFlow [13]. HyperFlow uses a publishing and subscribing method
based on a distributed file system, but it adds additional overhead for
subscription management and maintenance. DIFANE uses a core switch instead of
a controller, but the core switch increases resource consumption. Both
HyperFlow and DIFANE have a logical centralized, physically distributed
control plane, and all controllers (or core switches) share a global network
view. Onix uses a publishing and subscribing method based on the data
structure of the NIB (network information base). Each local controller has an
NIB data structure, and the controllers share a copy of the network state with
each other, but the controller adds additional subscription management and
maintenance overhead. BalanceFlow uses a dedicated controller for load
balancing of all controllers and periodic reporting of flow request
information. Each controller maintains its own flow request information, but
it increases the overhead of the control plane. Onix and BalanceFlow divide a
large-scale network into many small networks, and each small network is
managed by a local controller.

Typical vertical control structures are Kandoo [14], Orion [15], SOX and DSOX
[16], HybridFlow [17]. Kandoo uses the root controller to control all local
controllers, and each local controller manages one or more switches and has a
global network view. Orion is similar to Kandoo. SOX, DSOX, and HybridFlow all
use logical centralized control plane but physically distributed controller
cluster architecture, and each controller cluster shares NIB.

Controller load balancing improves the latency between the switch and the
controller in a single controller environment. The level controller
architecture provides better recovery capability, but is difficult to manage.
The vertical control structure is easier to manage through the upper
controller, but there are single points of failure and complete consistency.

However, the load balancing strategy of the control plane has not been
exploited to some extent. It needs to solve a series of fundamental problems,
which are aimed at finding the optimal number of controllers, deployment
location, workload distribution, forwarding path of control messages, and
coordinates an optimal balance between the delay performance of control
messages and the control costs, and has the statistical characters of network
traffic and the diversity of network topology.

Heller _et a_ l. [18] first studied the static deployment of controllers, by
calculating the minimum propagation delay to determine the number and location
of controllers. Dixit _et al_. [19] proposed a distributed controller pool
architecture that dynamically adjusts the work status of controllers and to
balances the real-time workloads of the controllers based on traffic
conditions. Bari _et al_. [20] studied the dynamic supply of controllers in a
large-scale local area network, and dynamically changed the controller
deployment through the number of real-time flows in the network. Yao _et al_.
[21] studied load balancing based on the capacitated K-center problem,
minimizing the maximum delay between the switch and the controller. Jimenez
_et al_. [22] uses the k-critical algorithm to find the minimum number of
controllers and the location of the deployment so that the selected
controllers are workload balanced. Guo _et al_. [23] proposed a controller
state synchronization strategy based on changes in the load to improve the
load balancing performance of multi-controller and multi-domain SDNs. Liao _et
al_. [24] proposed a density-based controller deployment method that divides
the network into multiple subnets and configures a controller in each subnet.
Huque _et al_. [25] studied the deployment of dynamic controllers by adjusting
the controller deployment location to limit the communication latency and
adjusting the number of controllers to support dynamic loads. Hu _et al_. [13]
studied the problem of controller deployment and workload distribution. Schmid
and Suomela [26] proposed a local protocol development algorithm and a
localized model of distributed computing. Jim _et al_. [27] designed the
K-Critical algorithm to handle failure and balance load between controllers by
finding the minimum number of controllers and its location to establish a
controller topology. Ma _et al_. [28] proposed a load balancing mechanism
based on a hierarchical control structure, which meta controllers analyze the
resources and utilization in local control planes and optimize the processing
performance. However, these efforts focus on finding quantitative or even
heuristic results, the lack of deep research to the load balancing mechanism
of the control plane in large-scale SD-IoT.

###  II-B Switch Load Balancing

ECMP [29] is a load balancing strategy that uses a flow-based hashing method
to optimal flow allocation, but two or more long flows are prone to conflict
on their hash and share the same output port, resulting in network
bottlenecks. Hedera [30] is an extensible dynamic flow scheduling system that
collects statistics information of flows on edge switches. If the flows
increases beyond a given threshold rate, it will dynamically compute a
suitable path and install the path in the switch. This allows for a balance
between the high utilization and minimal scheduling overhead of networks.
Mahout [31] monitors and detects large flows on the terminal host through a
mezzanine of the operating system. When the mezzanine detects that the
socket’s buffer exceeds a given threshold, it will mark the subsequent packet
of the flow. The switch forwards these marked packets to the Mahout
controller. The Mahout controller calculates the best path for the large flow
and installs a specific flow entity in the switch. MicroTE [32] is similar to
Mahout. The above three methods use the central controller to calculate the
appropriate flow path, and ECMP routing is used in the switch for a small
flow. However, Hedera increases the processing overhead of controllers and
switches and the bandwidth overhead of switches. Mahout and MicroTE increase
the processing overhead of switches and hosts and the bandwidth overhead of
the host.

In order to reduce the number of interactions between controllers and
switches, the traffic management of SDNs implements the wildcard rule in
OpenFlows witches. Switches can handle the local route of microflows.
Controllers only process directional macroflows, especially the quality of
service of macroflows is more and more important, such as DevoFlow [33].
Another approach is using a core switch to complete all the packet processing,
such as DIFANE [11]. However, this approach don’t require the controller to
participate in the process at all, and reduces the load on the control plane,
but increases the burden on the core switch.

However, load balancing policies based on hash ECMP and wildcard rules are
static and difficult to adapt to flow dynamics. In [34], a decision strategy
based on switch migration is proposed, which senses load imbalance through
switch migration triggering metrics, establishes a corresponding migration
efficiency model, and weighs between migration costs and load balancing rates.
Paper [35] proposed an alternative to the Beacon controller, which collects
statistical information of OpenFlow devices in real time. The Beacon
controller reroutes the flows according to the queues in the switch to ensure
queue balancing in the switch. A load balancing algorithm in SDNs is proposed
by collecting the traffic statistics of the switch subset in [36]. Obviously,
the traffic management in SD-IoT needs a dynamic load balancing mechanism,
which can dynamically adapt to time-varying network status and fine-grained
traffic characteristics, such as traffic burst and arrival time interval.

Recently, paper [37] proposed a dynamic load balancing method for SDN-based
cloud centers, which offers improved flexibility to the task scheduling using
of the SDN technology, and completes the real-time monitoring of service node
flows and load conditions based on the OpenFlow protocol. The controller can
deploy global network resources once imbalance occurs. A constrained
optimization particle swarm algorithm based on SDN is proposed, which can
effectively reduce the network delay and improve the quality of service of
cloud and fog networks in [38].

To sum up, in order to avoid the bottleneck of a single centralized
controller, traffic management should consider the network traffic load
balancing solution. For optimizing the number of SD-IoT controllers, the
location of the deployment, the workload distribution, and the control message
forwarding path, the traffic equalization solution must facilitate the
efficient and accurate acquisition of the traffic statistics of SD-IoT. In
order to take full advantage of the flexible control of SD-IoT and the global
view of the characteristics of the SD-IoT, traffic management needs a dynamic
load balancing mechanism, which can adapt to time-varying network status, and
fine-grained characteristics of flows based on traffic burst and arrival
interval can be adjusted. The above studies have shown that the effective
dynamic load balancing strategy of vertical controllers in SD-IoT is
especially important for large-scale IoT.

##  III Vertical Control Structure for SD-IoT

###  III-A SD-IoT Framework

In this subsection, we describe a generic framework for SD-IoT, as shown in
Fig. 1. The generic framework for SD-IoT can be divided into three layers:
application layer, control layer and infrastructure layer. The application
layer consists of IoT servers, which connect to SD-IoT controllers through the
Internet and provide a variety of applications and services through APIs. The
control layer is composed of SD-IoT controllers, which run the distributed
operating system, and provides a logical centralized control and view for the
network data forwarding in the distributed IoT. SD-IoT controllers use the
resource pooling technology, and the use of controller resources in the
controller pool can be dynamically adjusted based on the real-time conditions
of IoT switch resources. The infrastructure layer is composed of SD-IoT
switches, which integrate the functions of IoT gateways and SDN switches, and
access different actuating and sensing devices of IoT, such as cameras,
digital cameras, smart phones and personal computers by controlling the
interface of data plane in SD-IoT.

Figure 1: A generic framework for SD-IoT.

###  III-B Vertical Control Structure

In the above proposed framework of SD-IoT, the controller pool is designed as
a vertical control structure, as shown in Fig. 2. The vertical control
structure includes the main control layer and basic control layer. The main
control layer interacts with the application layer upwards, and interacts with
the basic control layer downwards. The basic control layer interacts with the
data forwarding layer downwards.

Figure 2: Vertical control structure of the controller pool.

The controllers of the main control layer are called the main controllers.
Each of the main controllers manages the base controllers in the base control
layer, while the other basic controllers are used as resources in reserve. The
main controllers are responsible for resource management and coordination of
the base control layer, and also provide a northbound interface for the upper
application. In the main controllers, a _Leader_ is generated by the election
mechanism. The _Leader_ can obtain the global network topology information,
control the main controller, and coordinate the basic controllers.

The basic controllers are responsible for device resource management in a
region of IoT, as shown in Fig.1. The IoT devices in the same region can
communicate through the basic controller of the region. Each switch will be
one of the base controllers as a _Master_ controller, and others as _Slave_
controllers. The IoT devices in different areas communicate with each other
through a main controller. The basic controller communicates with the switch
of the data forwarding layer, regularly sends Packet_out messages to the
switch, and obtains the information of the switch through feedback Packet_in
messages. The basic controller submits its own control information by
interacting with the main controller so that the main controller can obtain
the entire network global view. Network load balance is achieved through the
coordination of messages between main controllers and the dynamic load
balancing strategy in the base controller layer.

Compared with the horizontal controller structure, the vertical control
structure is easy to manage, but also solves a series of problems caused by
single point failure of the existing vertical control structure. The problems
include the incongruity of underlying controllers, non-global topology, load
imbalance, the inconsistencies of main controllers.

##  IV Dynamic load balancing algorithm for vertical control

In this section, a dynamic load balancing strategy of vertical controllers is
proposed using the proposed SD-IoT framework. It consists of two parts: a
dynamic load balancing algorithm of the main control layer and a dynamic load
balancing algorithm of the basic control layer. The former is responsible for
the single point of failure of the main controller and the consistency of all
controller messages. The latter is responsible for the load balancing of the
basic controllers.

###  IV-A Dynamic load balancing algorithm for the main control layer

Existing vertical control structures are generally used with a controller or
super controller [14, 17]. However, they are easy to prone to a single point
of failure. Multiple super controllers can solve the problem of single point
of failure [16], but there is the inconsistency of messages between the main
controllers. In order to solve this problem, it is necessary to construct a
set of effective message consistency mechanism in the multi-controller
structure. PAXOS [39] is a consistency algorithm based on the information
transfer model, which is considered to be the most effective of similar
algorithms. In this section, we proposed a dynamic load balancing algorithm
for the main control layer based on PAXOS algorithm.

####  IV-A1 Algorithm ideas

A dynamic load balancing algorithm for the main control layer proposed in this
section is to use a set of ideas to select a main controller as a _Leader_
from multiple main controllers to ensure that multiple main controllers
interact with each other, and the _Leader_ manages execution and replacement
information is passed to other main controllers so that all network views held
by all the main controllers are quickly consistent, and the single point of
failure is also optimized. Similar to the PAXOS algorithm, the proposed
algorithm consists of three roles: a _Proposer_ , an _Acceptor_ and a
_Learner_. The _Proposer_ is responsible for proposing proposals. The
_Acceptor_ votes on the nomination proposal. The _Learner_ collects the
proposal accepted by each _Acceptor_. All the main controllers can be any of
three roles.

####  IV-A2 Algorithm design

Assume _n_ controllers in a main control layer are sent to their respective
_Proposer_ a message and claim to be a _Leader_ , the _Proposer_ sends a
proposal with their own $<$_K_ , _V_ $>$ message to all _Acceptors_. According
to _K_ , all _Acceptors_ will complete the update of _K_ and promise to ensure
that the proposal is rejected less than the updated _K_ value, at the same
time pass the proposal $<$_K_ , _V_ $>$. When no more than half of the
feedback was received by the _Proposer_ , it will update itself of _K_ , and
continue to give proposal messages from all _Acceptors_. Finally, $<$$K_{N}$,
$Controller_{N}$$>$ is the proposal to pass the resolution, and $K_{N}$ is the
largest number and $Controller_{N}$ is the largest numbered controller. At
this point, the _Learner_ perceives the adoption of the $<$$K_{N}$,
$Controller_{N}$$>$ proposal and learns the proposal. At the end of the
process, $Controller_{N}$ is elected as a _Leader_. Once the Leader fails, it
will return to zero to launch a new election.

####  IV-A3 Algorithm implementation

The dynamic load balancing algorithm proposed in this section is deployed in
the main controllers, so that when multiple main controllers interact with
each other, the Leader manages the execution and replacement information to
pass to other main controllers. The main implementation process of the dynamic
load balancing algorithm in the main control layer is as follows in Algorithm
1.

Algorithm 1 : A dynamic load balancing algorithm for the main control layer.

0: The number $N$ of controllers.

0: The _Leader_ and election time.

1: for $all$ $controllers$ do

2:  _All controllers send a message to the Proposer to elect the leader and
generate the value of K based on the time stamp._

3: for $<$$K$,$V$$>$ $of$ $all$ $Proposers$ $\rightarrow$ $Pcceptors$ do

4: if $new(K)>old(K)$ then

5: $Update(new(K),controller_{N})$

6: end if

7: if  _any of Proposers receives the number Acceptors returned more than
half_ then

8:  _this Proposer will update its own K_

9:  _the new K is used to send election massages to other Acceptor_

10: end if

11: end for

12:  _Gain the Leader_

13: end for

14:  _Gain the election time_

The dynamic load balancing algorithm proposed in this section mainly uses the
idea of the set, and solves the problem of single point failure of the
existing vertical control structure, and ensure that the global views of the
network in the main controllers are consistent with each other.

###  IV-B Dynamic load balancing algorithm for basic control layer

In the vertical control structure of the SD-IoT, the request messages sent by
the switch on the basic control layer to controllers are too large, and it can
make huge burden on the corresponding controller and result in network delay.
In a worse case scenario, it will lead to the base controller failures and
network collapse. Other base controllers may be in an idle state. In order to
optimize the above problems in the basic control layer, we propose a dynamic
load balancing algorithm based on balanced delay for the basic controllers in
this section. When a base controller fails or the single base controller is
overloaded and the other base controllers are in the idle state, the algorithm
is used to make the switches managed by the base controller of the faulty or
the overload manage the other switches migrate to other base controllers, and
achieves the load balancing of the basic control layer.

####  IV-B1 Load balancing model

In a vertical control architecture, each switch is connected to one or more
controllers, and one controller controls multiple switches. Assume that the
number of SD-IoT base controllers in the control plane is _n_ , we have
$C=\\{C_{i}\\}_{i=1,2,...,n}$, where $C$ indicates a set of controllers and
$C_{i}$ is the _i_ th controller. Assume that the number of the SD-IoT
switches in the data plane is _m_ , we have $S=\\{S_{j}\\}_{j=1,2,...,m}$,
where $S$ indicates a set of switches and $S_{j}$ is the _j_ th switch.
Obviously, the control relationship between _n_ base controllers and _m_
switches can be represented by a matrix $Q_{nm}$ of _n_ rows and _m_ columns,
as shown in Equ.(1).

$Q_{nm}=\left[\begin{array}[]{cccc}q_{11}&q_{12}&...&q_{1m}\\\
q_{21}&q_{22}&...&q_{2m}\\\ ...&...&...&...\\\ q_{n1}&q_{n2}&...&q_{nm}\\\
\end{array}\right]$ (1)

where $q_{ij}=0$ indicates that the _j_ th switch $S_{j}$ is not controlled by
the _i_ th base controller $C_{i}$; $q_{ij}=1$ indicates that the _j_ th
switch $S_{j}$ is controlled by the _i_ th base controller $C_{i}$.

Assume that the number of the Packet_in packets sent by the _j_ th switch
$S_{j}$ to the _i_ th base controller $C_{i}$ at time _t_ is $p_{ij}$, we have

$p_{ij}=q_{ij}f_{ij}(t)$ (2)

where $f_{ij}(t)$ is the rate at which the _j_ th switch $S_{j}$ sends the
packet.

Obviously, during the interval [0, $T$], the total amount of Packet_in packets
sent by the _j_ th switch $S_{j}$ to the _i_ th base controller $C_{i}$ is
$P_{ij}$, and we have

$\displaystyle P_{ij}$ $\displaystyle=\int_{0}^{T}p_{ij}dt$ (3)
$\displaystyle=\int_{0}^{T}q_{ij}f_{ij}dt$

So, the total number of Packet_in packets processed by the _i_ th base
controller $C_{ij}$ from _m_ switches: $S_{1},S_{2},...,S_{m}$ at time $t$ is
expressed by

$p_{i}=\sum_{j=1}^{m}(q_{ij}f_{ij}(t))$ (4)

During the interval [0, $T$], the total number of Packet_in packets processed
by the _i_ th base controller $C_{ij}$ from _m_ switches:
$S_{1},S_{2},...,S_{m}$ is expressed by

$P_{i}=\int_{0}^{T}\sum_{j=1}^{m}(q_{ij}f_{ij}(t))dt$ (5)

Thus, the total number of Packet_in packets processed by the _n_ base
controllers in the basic control layer from the _m_ switches in the data plane
layer can be expressed by

$\displaystyle P$ $\displaystyle=\sum_{i=1}^{n}P{i}$ (6)
$\displaystyle=\sum_{i=1}^{n}(\int_{0}^{T}\sum_{j=1}^{m}(q_{ij}f_{ij}(t))dt)$
$\displaystyle=\int_{0}^{T}\sum_{i=1}^{n}(\sum_{j=1}^{m}(q_{ij}f_{ij}(t)))dt$

In vertical control structure of the large-scale SD-IoT, once the edge switch
receives a new flow, the edge switch will forward the first packet of the flow
to the corresponding base controller. The base controller calculates and
determines the path to forward the flow. All switches on the flow path will
install forwarding rules. Obviously, when a large number of new flows into the
IoT, the basic controller will frequently receive and forward the new flow
request information and calculate the flow path. The switches on the path will
frequently install forwarding rules. It will produce a peak of the network
delay, and cause the load imbalance of the IoT.

Network delay is mainly composed of processing delay, queuing delay,
transmission delay and sending delay. In general, the processing delay and
sending delay of the controller and switch can be considered constant.
Therefore, the network delay depends mainly on the queuing delay and
transmission delay. From the queuing model M/M/1, it can be concluded that the
queuing delay $T_{j,w}$ of a Packet_in packet sent by the _j_ th switch
$S_{j}$ in the _i_ th base controller $C_{i}$ can be expressed as

$T_{i,w}=\frac{\lambda_{i}}{\mu_{i}(\mu_{i}-\lambda_{i})}$ (7)

where $\lambda_{i}=\frac{P_{i}}{T}$ is the arrival rate of packets, that is,
the average value of Packet_in packets arriving at the _i_ th base controller
$C_{i}$ in unit time; $\mu_{i}=\frac{P_{i}}{T_{d}}$ is the service rate of
controllers, that is, the average rate of the _i_ th base controller $C_{i}$
precessing Packet_in packets.

Assuming that the transmission delay of packets transmitted by the _j_ th
switch $S_{j}$ of the data forwarding layer to the _i_ th base controller
$C_{i}$ of the control layer is $T_{i,c}$, which can be obtained by
calculating the maximum delay of all effective shortest paths between the
switch $S_{j}$ and the base controller $C_{i}$ [42], we have

$T_{i,c}=\max_{S_{j}\in S}\min_{C_{i}\in C}d(S_{j},C_{i})$ (8)

As a result, the total time $L_{i}$ of the _j_ th switch receiving a new flow,
the _i_ th controller calculating the path and the switches on the path
installing forwarding rules is expressed by

$L_{i}=T_{s}+T_{d}+T_{i,w}+T_{i,c}$ (9)

where $T_{s}$ is the processing delay and $T_{d}$ is the transmission delay.

Thus, the sum of the delay between the base control layer and the data
forwarding layer is

$\displaystyle L$ $\displaystyle=\Sigma_{i=1}^{n}L_{i}$ (10)
$\displaystyle=\Sigma_{i=1}^{n}(T_{s}+T_{d}+T_{i,w}+T_{i,c})$
$\displaystyle=\Sigma_{i=1}^{n}(T_{s}+T_{d}+\frac{\lambda_{i}}{\mu_{i}(\mu_{i}-\lambda_{i})}+\max_{S_{j}\in
S}\min_{C_{i}\in C}d(S_{j},C_{i}))$

In the SD-IoT vertical control structure, the workload from basic controllers
can be approximated as the amount of Packet_in packet requests [41].
Therefore, the load balancing model of basic controllers can be expressed as

$B=\\{Q_{nm},L,P\\}$ (11)

where $Q_{nm}$, $L$ and $P$ are given by Equ.(1), (6) and (10), respectively.

In fact, if you can reduce the network delay, it is easy to achieve load
balancing. That is, the load balancing model can be converted to the lowest
delay model, this is

$B=\\{Q_{nm},L\\}$ (12)

When the switch’s requests for the base controller are too large or the base
controller fails, the switch is mapped to a different base controller for
balancing delay [41]. It can be seen from Equ.(10) and Equ.(12) that the
network congestion caused by the excessive load of basic controllers can be
alleviated by reducing the queuing delay and transmission delay.

####  IV-B2 Dynamic load balancing algorithm for basic controllers

In this section, we present a dynamic load balancing algorithm for basic
controllers based on balanced delay. The proposed algorithm obtains the
network topology $G(S,C)$ of switches in the data forwarding layer through
basic controllers. Assuming that the threshold for the Packet_in packet
processed by a base controller in unit time is $P_{th}$, which can also be
referred to as the load peak of base controllers. When the total number of the
Packet_in packets which the _i_ th base controller $C_{i}$ processes from the
_m_ switches is greater than or equal to the load peak $P_{th}$ of the _i_ th
base controller $C_{i}$, and the request amount of Packet_in packets which the
$j$th switch $S_{j}$ sends to the _i_ th base controller $C_{i}$ is $p_{i}$,
and $p_{i}>\frac{P_{th}}{m}$. At the same time, the total value of the queuing
delay and transmission delay exceeding the initial value is greater than the
total value of the transmission delay and processing delay used to retransmit
the Packet_in packet to the unoccupied basic controllers at the shortest
distance, and the corresponding basic controller changes Slave into Master,
that is, $q=1$. While the portion of the Packet_in packets beyond the original
base controller is handed over to the idle base controller which has an
minimum distance. Otherwise, the packets continue to wait for the base
controller to handle until the iteration is complete. When the base controller
fails, that is, $q=0$, the switch through the $G(S,C)$ will make the idle
Slave with a shortest distance as the Master, that is, $q=1$, and it repeats
the above steps. The specific implementation code of the proposed algorithm is
as shown in Algorithm 2.

Algorithm 2 : Dynamic load balancing algorithm for the base control layer.

0: The initial value of $Q_{nm}$, the rate $p_{ij}$ of Packet_in packets.

0: The value of $Q_{nm}$.

1: for $S_{j}\in C_{i}$ do

2: if $C_{i}$ $goes$ $down$ then

3: $q_{ij}=0$

4: $S_{j}\rightarrow C_{\min d(s,c)}$

5: $q_{\min d(s,c)j}=1$

6: end if

7: if $p_{ij}>\frac{P_{th}}{m}$ and
$T_{s}+T_{w}(p_{ij}-\frac{P_{th}}{m})>T_{c}(p_{ij}-\frac{P_{th}}{m})+T_{d}$
then

8:  _Add and control the controller with the smallest distance in the topology
for the switch_.

9: $q_{\min d(s,c)j}=1$

10:  _The packet-in message exceeding the threshold set by the controller is
processed to the new controller_.

11: end if

12: end for

13:  _Get the value of the newly controlled condition_.

The dynamic load balancing algorithm proposed in this section transforms the
load balancing problem into a network latency problem, which avoids load
imbalance by reducing the queuing delay and transmission delay.

##  V Performance Evaluation

###  V-A Experimental environment

In order to evaluate the effectiveness of the proposed SD-IoT framework and
the performance of the proposed dynamic load balancing algorithms for vertical
control structure of the SD-IoT, we set up the following experimental
platform. The hardware environment of the platform includes: Intel core
i7-5960X, DDR4 213316G, SSD 250G + 1T HDD 7200 and Intel PRO/1000 MT. The
software environment includes: Ubuntu14.04LTS, OpenDaylight, Mininet2.2,
VMware Workstation 12 pro and RabbitMQ 3.6.3. The main controllers and base
controllers of the control layer in SD-IoT all use OpenDaylight as controllers
based on the OSGi architecture. The switches of the data forwarding layer
adopt a simulation platform: Mininet. The communication between the main
controllers and base controllers is implemented using JGroups in OpenDaylight.
The communication between the base controllers and switches is implemented
using the OpenFlow protocol and OF-CONFIG protocol. Fig.3 shows a scenario of
the SD-IoT. There are nine controllers, including three main controllers and
six basic controllers. Each of main controllers connect to six basic
controllers, and each of base controllers manages five switches in the local
region and connects with other regional switches. We deploy Algorithm 1
presented in this paper in the main controllers, and deploy Algorithm 2
presented in this paper in the base controllers.

Figure 3: A scenario of the SD-IoT.

###  V-B Performance analysis

####  V-B1 Performance evaluation indicators

For the dynamic load balancing algorithm of main controllers, we use the time
electing a _Leader_ as an evaluation index. In order to evaluate the
performance of the dynamic load balancing algorithm of base controllers, we
use a terminal in Mininet to send packets to another address in the basic
control layer. The the packet passes a switch in Mininet. If no match is found
in the flow table, the switch sends a Packet_in packet to the controller in
such a way that the switch generates a Packet_in packet in unit time to
provide the load pressure to the controller of the base control layer.

Assuming that the average delay of the switch sending requests to the base
controller responding to requests is $\overline{T}$, the standard deviation is

$\sigma=\sqrt{\frac{\sum_{i=1}^{n}(T_{i}-\overline{T})^{2}}{n}}$ (13)

Therefore, in the basic control layer, the response time of the controllers,
the standard deviation of the response time of the controllers and the CPU
utilization rate of the controllers will be used as the evaluation index of
the dynamic load balancing algorithm of basic controllers.

####  V-B2 Results analysis

In order to evaluate the performance of the dynamic load balancing algorithm
proposed in this paper. We deploy the dynamic load balancing algorithm of the
main controllers in a variety of different scenarios. The results are obtained
by duplicating the experiment multiple times.

The impact of test number on the time spent on electing a _Leader_ from three
main controllers is given in Fig.5. As can be seen from Fig.5, the average
value of the election time of our algorithm is significantly less than that of
the PAXOS algorithm. The average time spent on electing a _Leader_ from three
main controllers based on our algorithm is is about 125 ms, and the time based
on the PAXOS algorithm is about 144 ms, and it is reduced by 13 percent. Our
algorithm adopts the idea of set, which reduces the time of two stages in
PAXOS. The impact of test number on the time spent on electing a _Leader_ from
five controllers is given in Fig.5. We have the same results. The average time
spent on electing a _Leader_ based on our algorithm is about 145 ms, and the
average time using the PAXOS algorithm is about 155ms.

2.65in  Figure 4: Election time with three controllers. Figure 5: Election
time with five controllers.

In order to evaluate the performance of the dynamic load balancing algorithm
for basic controllers proposed in this paper. We deploy Algorithm 1 in three
main controllers, and deploy Algorithm 2 in six base controllers.

The impact of average request response time of base controllers on the rate at
which a switch sends Packet_in packets. As can be seen from Fig.7, the greater
the rate at which the switch sends Packet_in packets, the more data packets
received by the base controllers, and the average response time of the base
controllers is gradually increased. The performance of the dynamic load
balancing algorithm for basic controllers proposed in this paper is far
superior to that of the original data without deploying load balancing
algorithm. With the increase of Packet_in packet rate, the advantages of the
proposed algorithm are becoming more and more obvious. The impact of standard
deviation of average request response time of base controllers on the rate at
which a switch sends Packet_in packets. It can be seen from Fig.7 that the
standard deviation of the controller response time increases rapidly as the
Packet_in packet rate increases without the deployment of the load balancing
algorithm. In the case of deploying the load balancing algorithm for basic
controllers, the standard deviation of the controller response time is almost
unaffected by the Packet_in packet rate of the switches. The dynamic load
balancing algorithm for basic controllers balances the request response time
for the switches to send Packet_in packets to base controllers.

2.65in  Figure 6: Average response time vs. average rate. Figure 7: Standard
deviation of average response time vs. average rate.

It can be seen that the standard deviation of the controller’s response time
depends only on the delay of switches and controllers, regardless of the
Packet_in packet rate of switches. In the absence of the deployment of the
load balancing algorithm, due to the fact that the load of each controller is
different, the response time is different and the average response time of the
entire controller is relatively large. Obviously, the proposed algorithm is
very suitable for load balancing of large-scale IoT.

The impact of CPU utilization for configuring six base controllers without
deploying the dynamic load balancing algorithm presented in this paper (case
1) is given in Fig.9. As can be seen from Fig.9, in the case of the CPU
utilization of basic controllers changes dramatically over time fluctuations.
The impact of CPU utilization for configuring six base controllers with
deploying the dynamic load balancing algorithm presented in this paper (case
2) is given in Fig.9. As can be seen from Fig.9, the CPU utilization of basic
controllers fluctuates with slighter rate.

2.65in  Figure 8: CPU utilization under the load balancing algorithm (case 1).
Figure 9: CPU utilization without dynamic load balancing algorithm (case 2).

The average (blue bar) and standard deviation (red bar) of the CPU utilization
of basic controllers in both cases are given in Fig.10. In both cases, the
average of the CPU utilization of the six base controllers is close. In case
1, the average CPU utilization of the six base controllers is 55.15$\%$. In
case 2, the average CPU utilization of the six base controllers is 54.18$\%$.
However, the standard deviation of the CPU utilization of the base controllers
in case 2 is much less than that in case 2. The average standard deviation of
the CPU utilization of the six basic controllers is about 15.44$\%$ in case 1,
but it is about 1.55$\%$ in case 2. Obviously, the CPU utilization in case 1
has better stability than that in case 2, that is, the load is more balanced.
The load balancing algorithm of basic controllers is based on the balance
delay to select a controller, and achieves the purpose of load balancing.

Figure 10: Average and standard deviation of the CPU utilization of basic
controllers.

To sum up, we can see that the dynamic load balancing algorithm for main
controllers proposed in this paper can make main controllers to quickly
synchronize the information of the global network view. The load balancing
algorithm for basic controllers proposed in this paper can ensure that basic
controller resources are distributed evenly to achieve the effect of load
balancing.

##  VI Conclusions

This paper describes a general framework for SD-IoT. The control plane of the
framework uses a vertical control architecture, which is divided into the main
control layer and the basic control layer. The main controllers in the main
control layer coordinate and manage the basic control layer, and the basic
controllers in the basic controller layer manage and control the data
forwarding layer of switches. In the main control layer, we design an
algorithm for electing a controller as a _Leader_ , which is used to
coordinate and manage the main controllers, in order to achieve the dynamic
load balancing of main controllers. In the basic control layer, we design a
dynamic load balancing algorithm based on balanced delay, which is used to
process Packet_in packets of witches in the data forwarding layer to ensure
the dynamic load balancing of the base control layer. The experimental results
show that the proposed SD-IoT framework and dynamic load balancing algorithms
in the vertical plane are effective. The work would assist and support traffic
control and management of large-scale IoT.

##  VII Acknowledgements

This work was supported in part by Natural Science Foundation of China (Grant
No. 61572191 and 61402170) and the Research Foundation of Education Bureau of
Hunan Province of China (Grant No.17A130).

## References

  * [1] U. Lindqvist and P. Neumann, “The future of the Internet of Things,” Communications of the ACM, vol. 60, no.2, pp.26–30, 2017.
  * [2] Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update, 2016–2021 White Paper. [Online]. Available: https://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/mobile-white-paper-c11-520862.html#MeasuringMobileIoT
  * [3] I. F. Akyildiz, A. Lee, W. Pu, and L. Min, “Research challenges for traffic engineering in software defined networks,” IEEE Network, vol.30, no.3, pp.52–58, 2016.
  * [4] I. F. Akyildiz, A. Lee, W. Pu, L. Min, and C. Wu, “A roadmap for traffic engineering in SDN-OpenFlow networks,” Computer Networks, vol.71, no.3, pp.1–30, 2014.
  * [5] J. Liu, Y. Li, M. Chen, and W. Dong, “Software-defined internet of things for smart urban sensing,” IEEE Communications Magazine, vol.53, no.9, pp.55–63, 2015.
  * [6] L. Kuang, L. T. Yang, and K. Qiu, “Tensor-based software-defined internet of things,” IEEE Wireless Communications, vol.23, no.5, pp.84–89, 2016.
  * [7] D. Erickson, “The Beacon Openflow controller,” in Proc. ACM SIGCOMM Workshop on Hot Topics in software defined networking, 2013, pp.13–18.
  * [8] Y. Chen, W. Chen, Y. Hu, L. Zhang, and Y. Wei, “Dynamic load balancing for software-defined data center networks,” in Proc. EAI International Conference on Collaborative Computing: Networking, Applications and Worksharing, 2016.
  * [9] L. Zhang, Q. Deng, Y. Su, and Y. Hu, “A box-covering-based routing algorithm for large-scale SDNs,” IEEE Access, vol.5, no.1, pp.4048–4056, 2017.
  * [10] A. Tootoonchian and Y. Ganjali, “Hyperflow: a distributed control planefor openflow,” in Proc. Internet Network Management Conference on Research on Enterprise Networking, 2010, p. 3.
  * [11] M. Yu, J. Rexford, M. J. Freedman, and J. Wang, “Scalable flow-based networking with difane,” ACM SIGCOMM Computer Communication Review, vol.40, no.4, pp.351–362, 2010.
  * [12] T. Koponen, M. Casado, N. Gude, J. Stribling, L. Poutievski, M. Zhu, R.Ramanathan, Y. Iwata, H. Inoue, T. Hama, and S. Shenker, “Onix: a distributedcontrol platform for large-scale production networks,” in Proc. USENIX Conference on Operating Systems Design and Implementation, 2010, pp. 1–6.
  * [13] Y. Hu, W. Wang, X. Gong, X. Que, S. Cheng, “Balanceflow: controllerload balancing for openflow networks,” in Proc. IEEE 2nd International Conference on Cloud Computing and Intelligent Systems, 2012, pp.780–785.
  * [14] S. H. Yeganeh and Y. Ganjali, “Kandoo: a framework for efficient andscalable offloading of control applications,” in Proc. the First Workshop on Hot Topics in Software Defined Networks, 2012, pp. 19–24.
  * [15] Y. Fu, J. Bi, Z. Chen, K. Gao, and B. Zhang, “A hybrid hierarchical control plane forflow-based large-scale software-defined networks,” IEEE Transactions on Network and Service Management, vol.12, no.2, pp.117–131, 2017.
  * [16] M. Luo, Y. Tian, Q. Li, J. Wang, and W. Chou, “Sox – a generalized andextensible smart network openflow controller(x),” in Proc. the First SDN World Congress, 2012.
  * [17] C. Qiu, C. Zhao, F. Xu, and T. Yang, “Sleeping mode of multi-controller in green software-defined networking,” EURASIP Journal on Wireless Communications and Networking, vol.2016, no.1, pp.282, 2016.
  * [18] B. Heller, R. Sherwood, and N. Mckeown, “The controller placement problem,” ACM SIGCOMM Computer Communication Review, vol.42, no.4, pp.473–478, 2012.
  * [19] A. Dixit, H. Fang, S. Mukherjee, T. V. Lakshman, and R. Kompella, “Towards an elastic distributed SDN controller,” ACM SIGCOMM Computer Communication Review, vol.43, no.4, pp.7–12, 2013.
  * [20] M. F. Bari, A. R. Roy, S. R. Chowdhury, Q. Zhang, M. F. Zhani,R. Ahmed, and R. Boutaba, “Dynamic controller provisioning in software defined networks,” in Proc. International Conference on Network and Services Management, 2013.
  * [21] G. Yao, J. Bi, Y. Li, and L. Guo, “On the capacitated controller placement problem in software defined networks,” IEEE Communications Letters, 2014, 18(8): 1339–1342.
  * [22] Y. Jimenez, C. Cervello-Pastor, and A. Garcia, “On the controller placement for designing a distributed SDN control layer,” in Proc. IFIP Networking, 2014, pp. 1–9.
  * [23] Z. Guo, M. Su, Y. Xu, Z. Duan, L. Wang, S. Hui, and H. Jonathan, “Improving the performance of load balancing in software-defined networks through load variance-based synchronization,” Computer Networks, vol.68, no.11, pp.95–109, 2014.
  * [24] J. Liao, H. Sun, J. Wang, Q. Qi, and K. Li, “Density cluster based approach for controller placement problem in large-scale software defined networking,” Computer Networks, vol.112, pp.24–35, 2017.
  * [25] M. T. I. U. Huque, W. Si, G. Jourjon, and V. Gramoli, “Large-scale dynamic controller placement,” IEEE Transactions on Network and Service Management, vol.14, no.1, pp.63–76, 2017.
  * [26] S. Schmid and J. Suomela, “Exploiting locality in distributed SDN control,” in Proc. ACM SIGCOMM workshop on Hot topics in software defined networking, 2013, pp.121–126.
  * [27] Y. Jiménez, C. Cervelló-Pastor, and A. J. Garcia, “On the controller placement for designing a distributed SDN control layer,” in Proc. IFIP Networking Conference, 2014, pp.1–9.
  * [28] Y. W. Ma, J. L. Chen, Y. H. Tsai, K. H. Cheng, and W. C. Hung, “Load-balancing multiple controllers mechanism for software-defined networking,” Wireless Personal Communications, vol.94, pp.3549–3574, 2017.
  * [29] C. E. Hopps, “Analysis of an equal-cost multi-path algorithm,” RFC2992, Tech. Rep., 2000.
  * [30] M. Al-Fares, S. Radhakrishnan, B. Raghavan, N. Huang, and A. Vahdat, “Hedera: dynamic flow scheduling for data center networks,” in Proc. Networked Systems Design and Implementation Symposium, 2010, pp.19.
  * [31] A. R. Curtis, W. Kim, and P. Yalagandula, “Mahout: low-overhead datacenter traffic management using end-host-based elephant detection,” in Proc. IEEE INFOCOM, vol.2, no.3, pp.1629–1637, 2011.
  * [32] T. Benson, A. Anand, A. Akella, and M. Zhang, “Microte: fine grained traffic engineering for data centers,” in Proc. the Seventh Conference on Emerging Networking Experiments and Technologies, 2011, p. 8.
  * [33] A. R. Curtis, J. C. Mogul, J. Tourrilhes, P. Yalagandula, P. Sharma, and S.Banerjee, “Devoflow: scaling flow management for high performance networks,” ACM SIGCOMM Computer Communication Review, vol.41, no.4, pp.254–265, 2011.
  * [34] C. Wang, B. Hu, S. Chen, D. Li, and B. Liu, “A switch migration-based decision-making scheme for balancing load in SDN,” IEEE Access, vol.5, no.99, pp.4537–4544, 2017.
  * [35] L. Boero, M. Cello, C. Garibotto, M. Marchese, and M. Mongelli, “BeaQoS: Load balancing and deadline management of queues in an OpenFlow SDN switch,” Computer Networks, vol.106, pp.161–170, 2016.
  * [36] H. Xu, X. Y. Li, L. Huang, Y. Du, and Z. Liu, “Partial flow statistics collection for load-balanced routing in software defined networks,” Computer Networks, vol.122, pp.43–55, 2017.
  * [37] Y. Wang, X. Tao, H. E. Qian, and Y. Kuang, “A dynamic load balancing method of cloud-center based on SDN,” China Communications, vol.13, no.2, pp.130–137, 2016.
  * [38] X. He, Z. Ren, C. Shi, and J. Fang, “A novel load balancing strategy of software-defined cloud/fog networking in the Internet of vehicles,” China Communications, vol.13, pp.140–149, 2017.
  * [39] L. Lamport, “The part-time parliament,” ACM Transactions on Computer Systems, vol.16, no.2, pp.133–169, 1998.
  * [40] F. Botelho, A. Bessani, F. M. V. Ramos, and P. Ferreira, “On the design of practical fault-tolerant SDN controllers,” in Proc. Third European Workshop on Software Defined Networks, 2014, pp.73–78.
  * [41] F. Cimorelli, F. D. Priscoli, A. Pietrabissa, R. CelsiL, V. Suraci, and L. Zuccaro, “A distributed load balancing algorithm for the control plane in software defined networking,” in Proc. Mediterranean Conference on Control and Automation, 2016: 1033–1040.
  * [42] M. Vochin, E. Borcoci, and T. Ambarus, “On multi-controller placement optimization in software defined networking-based WANs,” in Proc. International Conference on Networks, 2015, pp.273–273.