IEEE Communications Magazine - June 2017 - page 41

39
IEEE Communications Magazine • June 2017
0163-6804/17/$25.00 © 2017 IEEE
A
bstract
Software defined networking has brought
new interesting challenges by externalizing the
task of controlling the network to some gener-
ic computer software. In particular, the control-
ler software can modify the network routes by
introducing new forwarding rules and deleting
old ones at a distributed set of switches, a chal-
lenge that has received lots of attention in the
last six years. In this article, we survey the dif-
ferent techniques to update rules, sometimes
relying on redundant paths to reroute the traffic
during the update, sometimes activating rules
at distinct switches in a specific order, to avoid
looping packets. This state of the art helps under-
stand another, often overlooked, problem that
consists of determining the appropriate point in
the update where it is safe to
garbage collect
old
rules. To illustrate the difficulty of the problem,
we list the previously proposed assumptions, like
the upper bound on the transmission delay of
every packet through the network. Finally, we
propose a solution that alleviates these assump-
tions and speeds up the original two-phase rule
update by about 80 percent through the use
of dedicated clean-up packets that detect the
absence of in-flight packets.
I
ntroduction
Software defined networking (SDN) eases the
management and configuration of networks,
leading to a more dynamic environment where
forwarding rules can potentially be updated at
a high pace. For example, OpenFlow switches
commonly build upon ternary content address-
able memory (TCAM) to match packets to
some rule in a flow table entry. The rule update
problem consists of two phases: (1) installing
a new forwarding rule version in the switches
and (2) garbage collecting the old forwarding
rule version. While various solutions were pro-
posed to update rules [1, 2], to our knowledge
there is no full-fledged solution for garbage col-
lecting unused forwarding rules. The garbage
collection of the old version of forwarding rules
is a difficult problem. Deleting a rule too early
makes it impossible for a switch to match some
packets to a flow table entry and hence leads to
packet loss or what is often called a
blackhole
[1, 3]. Collecting a rule too late wastes the stor-
age space of TCAM and even increases power
consumption unnecessarily [4] by keeping mul-
tiple rule versions even though no in-flight pack-
et matches the old rule version any longer. The
crux of the problem is thus to decide the earli-
est point in the rule update execution when it
is safe to garbage collect the old rule version.
Time-based tentatives [5, 6] assume
synchro-
nous
communications so that the rule update
protocol knows a maximum period after which
all in-flight packets will reach their destination.
Other tentatives assume that paths between
switches are redundant [2] or that all in-flight
packets can be tracked [4]. Unfortunately, there
is no way to implement these requirements in a
practical way: large-scale networks lack redun-
dant paths between switches, too many pack-
ets can be in transit at the same time, and their
delay varies depending on external parameters
such as switch firmware [7].
In this article, we propose the path clean-up
procedure to garbage collect the old version of a
forwarding rule in the presence of a
synchronous
communications, where no upper bound on the
packet transmission delay is known. Our solution
is made possible by not requiring any assumption
regarding the packet transmission delay. Instead,
this solution creates “clean-up” data packets
whose sole purpose is to help discover whether
in-flight packets of a flow marked with the old
rule version have left the core of the network.
Provided that flows of a given rule version take a
unique route in the core network, we guarantee
that after the clean-up packet of a flow has tra-
versed the core network, the old rule version for
this flow can be safely discarded. Our proposed
technique simply needs to store one additional
forwarding rule per flow at some switches before
garbage collection in order to guarantee that only
one version of a given rule per flow is stored the
rest of the time.
We complement our garbage collection tech-
nique with a rule installation procedure to offer a
full-fledged rule update technique that guarantees
per-packet consistency
in that each packet is han-
dled by a single rule version, and
blackhole-free-
dom
in that no packet is dropped due to rule
mismatch. Note that the proposed garbage col-
lection technique is general and could also be
integrated in other rule update solutions. It is not
restricted to any kind of network, as it does not
assume special connectivity; instead, it can work
in data center networks as well as wide area net-
Garbage Collection of Forwarding Rules in
Software Defined Networks
Md Tanvir Ishtaique ul Huque, Guillaume Jourjon, and Vincent Gramoli
A
dvances
in
N
etworking
S
oftware
The authors survey the
different techniques to
update rules, sometimes
relying on redundant
paths to reroute the
traffic during the update,
sometimes activating
rules at distinct switches
in a specific order, to
avoid looping packets.
This state of the art helps
understand another, often
overlooked, problem that
consists of determining
the appropriate point in
the update where it is
safe to garbage collect
old rules.
Md Tanvir Ishtaique ul Huque is with Data61-CSIRO and University of New South Wales; Guillaume Jourjon is with Data61-CSIRO;
Vincent Gramoli is with Data61-CSIRO and University of Sydney.
Digital Object Identifier:
10.1109/MCOM.2017.1601051
1...,31,32,33,34,35,36,37,38,39,40 42,43,44,45,46,47,48,49,50,51,...228
Powered by FlippingBook