FICUS: Fast Incremental Consistent Update in SDN
based on Relation Graph
Qing Li
∗
, Lei Wang
∗
, Yong Jiang
∗
, Guangwu Hu
∗
, Mingwei Xu
†
,Qingmin Liao
∗
∗
Graduate School at Shenzhen, Tsinghua University, Shenzhen, China
†
Tsinghua University, Beijing, China
Abstract—In Software Defined Networking (SDN), the config-
uration inconsistency during updates is one main source of net-
work instability. An efficient updating scheme with configuration
consistency is required. In this paper, we propose the scheme of
Fast Incremental Consistent Update for SDN (FICUS) based on
the relation graph (RG). In our scheme, we analyse the relation
between update operations, construct the relation graph and find
a proper order of these update operations to avoid inconsistency.
To solve the problem, we define two types of relations: the path
dependency relation and the path rejection relation. We evaluate
our scheme and algorithms by comprehensive experiments. The
results show that our scheme needs only 10%-40% of the rules
compared with the two-phase update scheme and speeds up the
update process by 40% in average.
I. INTRODUCTION
As a future network architecture, Software Defined Net-
working (SDN) decouples the forwarding plane and the control
plane, centralizes the intelligence of the network into the
controller [1, 2]. The controller generates rules according to
the routing/forwarding policies and distributes them into the
switches. The switches are only responsible for forwarding
packets according to the rules. SDN can be employed to
simplify the management of the network [3–5]. In all of
these systems, a reliable scheme is required to update the
configuration (rules) fast and exactly.
Although SDN employs the approach of centralized con-
trolling, it is still a distributed system in the respect of
configuration updating. Every switch processes the packets
according to its flow table. Therefore, during the configuration
update, the flow tables of these devices may be inconsistent
[6], which may cause forwarding loop, black hole, service
disruption, etc. Therefore, to avoid these problems, consistency
must be guaranteed during the network update.
Several schemes [7–11] have been proposed to guarantee the
consistency of the configuration during the network transiting
between two configurations. Two phase update (TP) [7] is
proposed to divide the process of configuration update into
two phases. This scheme can guarantee that every packet is
processed by only one configuration (old or new) but never by
the mixed during the network update. It ensures the consistent
properties with no loop and black hole. However, it requires
the network to reinstall the whole configuration (all rules) even
if only a few rules are changed. Dionysus [11] improves the
median update speed through the relations between the update
operation, resource and path. But it only adapts to tunnel-based
forwarding and WCMP forwarding. For data center networks,
zUpdate [10] ensures congestion-free during network updates
under asynchronous switches and traffic matrix changes. The
core of zUpdate is a programming model which enables
lossless transitions when the network changes.
According to the observations, consistency requirements
impose some relations between the update operations. For
example, switch S
n
is the next hop of switch S
m
in the
configuration to be updated; S
m
is the next hop of S
n
in the
old configuration. To avoid the forwarding loop, the update
operation on S
n
must be performed before S
m
. Violating
the updating order may lead to inconsistency and cause the
forwarding loop. In this paper, we propose the scheme of Fast
Incremental Consistent Update for SDN (FICUS), which is
based on the relation graph (RG).
In FICUS, when a configuration update is invoked, we
first analyse the relations between the update operations and
generate a relation graph where the nodes are the update
operations and the directed links are the relations between
these operation. For the packet-level consistency, there are two
types of relations: the path dependency relation and the path
rejection relation. The path dependency is used to ensure the
destination is reachable and the path rejection can guarantee
that the packets are transferred correctly. We then design the
efficient algorithms to find a proper order of these operations
from the RG.
We implement our scheme using POX controller and
Mininet [12] platform. The comprehensive experiment results
show that: 1) FICUS needs only 10%-40% of the rules com-
pared with the traditional update scheme; 2) FICUS installs
the rules 40% faster on average.
The contributions of this paper can be concluded as follows:
• We analyse the relations between the update operations.
For the packet-level consistent update, we define the path
dependency relation and the path rejection relation.
• We propose a new consistent update scheme based on
the relation graph. We construct a relation graph for the
operations. With the help of relation graph, we can find
a proper order to install these update.
• The comprehensive experiment results show that FICUS
makes a significant improvement on reducing the required
rules and the updating time.
The remainder of this paper is organised as follows. In
Section II, we show the network update model. In Section III,
we describe our consistent mechanism based on the relation
graph. In Section IV, we present the preliminary results of