Central Control Over Distributed Routing
http://fibbing.net

Stefano Vissicchio∗, Olivier Tilmans∗, Laurent Vanbever†, Jennifer Rexford‡∗∗

Université catholique de Louvain, † ETH Zurich, ‡ Princeton University

name.surname@uclouvain.be, †lvanbever@ethz.ch, ‡jrex@cs.princeton.edu

ABSTRACTCentralizing routing decisions offers tremendous flexibility, but sacrifices the robustness of distributed protocols. In this paper, we present Fibbing, an architecturethat achieves both flexibility and robustness throughcentral control over distributed routing. Fibbing introduces fake nodes and links into an underlying linkstate routing protocol, so that routers compute theirown forwarding tables based on the augmented topology. Fibbing is expressive, and readily supports flexible
load balancing, traffic engineering, and backup routes.
Based on high-level forwarding requirements, the Fibbing controller computes a compact augmented topology and injects the fake components through standard
routing-protocol messages. Fibbing works with any unmodified routers speaking OSPF. Our experiments also
show that it can scale to large networks with many
forwarding requirements, introduces minimal overhead,and quickly reacts to network and controller failures.

part of the network. As a network operator, you suspect
a denial-of-service attack (DoS), but cannot know forsure without inspecting the traffic as it could also be a
flash crowd. Your goal is therefore to: (i) isolate theflows destined to these IP addresses, (ii) direct them
to a scrubber connected between B and C, in order to“clean” them if needed, and (iii) reduce congestion byload-balancing the traffic on unused links, like (B, E).
scrubber

10

S1

fake noderoutersource
B

1

C
5

5

A
1

flow
S2

1

D

SA

IGP
weight

E

S3

5

F

D2
D1

1
1
A

B

1

C

10

5

2

5

1

1

1
E

5

D

F

destination(a) Initial topology(b) Augmented topology

Figure 1: Fibbing can steer the initial forwarding paths (see (a)) for D1 through a scrubber byadding fake nodes and links (see (b)).

CCS Concepts•Networks → Routing protocols; Network architectures; Programmable networks; Network management;

Keywords
Fibbing; SDN; link-state routing

1.

INTRODUCTION

Consider a large IP network with hundreds of devices,
including the components shown in Fig. 1a. A set of
IP addresses (D1 ) see a sudden surge of traffic, frommultiple entry points (A, D, and E), that congests a∗

S. Vissicchio is a postdoctoral researcher of F.R.S.-FNRS.

Permission to make digital or hard copies of all or part of this work for personalor classroom use is granted without fee provided that copies are not made or
distributed for profit or commercial advantage and that copies bear this noticeand the full citation on the first page. Copyrights for components of this work
owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute tolists, requires prior specific permission and/or a fee. Request permissions frompermissions@acm.org.

SIGCOMM ’15, August 17 - 21, 2015, London, United Kingdom
c 2015 ACM. ISBN 978-1-4503-3542-3/15/08. . . $15.00
DOI: http://dx.doi.org/10.1145/2785956.2787497

Performing this routine task is very difficult in traditional networks. First, since the middlebox and thedestinations are not adjacent to each other, the configuration of multiple devices needs to change. Also,
since intra-domain routing is typically based on shortest path algorithms, modifying the routing configuration is likely to impact many other flows not involvedin the attack. In Fig. 1a, any attempt to reroute flows
to D1 would also reroute flows to D2 since they hometo the same router. Advertising D1 from the middlebox
would attract the right traffic, but would not necessarily alleviate the congestion, because all D1 traffic would
traverse (and congest) path (A, D, E, B), leaving (A, B)
unused. Well-known Traffic-Engineering (TE) protocols(e.g., MPLS RSVP-TE [1]) could help. Unfortunately,
since D1 traffic enters the network from multiple points,
many tunnels (three, on A, D, and E, in our tiny example) would need to be configured and signaled. This
increases both control-plane and data-plane overhead.
Software Defined Networking (SDN) could easily solve
the problem as it enables centralized and direct control of the forwarding behavior. However, moving awayfrom distributed routing protocols comes at a cost. In-

forwarding paths:- configuration- manageability- path installation
robustness:- network failures- controller failures- partitions
routing policies:

centralized/SDN
OpenFlow [2], PCE [3], SR [4]distributed/traditional
IGP [5, 6], RSVP-TE [1]hybridFibbing

simple (declarative & global)
high (direct control)
slow (by controller, per-device)complex (indirect & per-device)
low [7, 8] (need for coordination)
fast (by device, distributed)

simple (declarative & global)
high (direct control)
fast (by device, distributed)

slow (by controller)
hard (ad-hoc synch)
hard (uncontrollable devices)highest (any path)fast (local)
native (distributed)
best (distributed)- low for IGP (shortest paths)- highest for RSVP (any path)fast (local)
easy (synch via IGP)
best (fallback on distributed)
high (any non-loopy paths)

Table 1: Fibbing combines the advantages of existing control planes, avoiding the main drawbacks.
deed, IGPs like OSPF and IS-IS are scalable (support
networks with hundreds of nodes), robust, and quickly
react to failures. Building a SDN controller with comparable scalability and reliability is challenging. It must
compute and install forwarding rules for all the switches,and respond quickly to topology changes. Even the simple task of updating the switch rule tables can then become a major bottleneck for a central controller managing hundreds of thousands of rules in hundreds ofswitches. In contrast, distributed routing protocols naturally parallelize this work. For reliability and scalability, a SDN controller should also be replicated andgeographically distributed, leading to additional challenges in managing controller state. Finally, the deployment of SDN as a whole is a major hurdle as many
networks have a huge installed base of devices, management tools, and human operators that are not familiar
with the technology. As a result, existing SDN deployments are limited in scope, e.g., new deployments ofprivate backbones [8, 9] and software deployments atthe network edge [10].
This paper introduces Fibbing, a technique that offers
direct control over the routers’ forwarding informationbase (FIB) by manipulating the input of a distributed
routing protocol. Fibbing relies on traditional link-state
protocols such as OSPF [5] and IS-IS [6], where routers
compute shortest paths over a synchronized view of the
topology. Fibbing controls routers by carefully lying tothem, removing the need to configure them. It coaxes
the routers into computing the target forwarding entries by presenting them with a carefully constructedaugmented topology that includes fake nodes (providing fake announcements of destination address blocks)
and fake links (with fake weights). In essence, Fibbing
inverts the routing function: given the forwarding entries (i.e., the desired output) and the routing protocol(i.e., the function), Fibbing automatically computes therouting messages to send to the routers (i.e., the input).
Fibbing can solve the problem in Fig. 1a adding two
fake nodes (Fig. 1b), connected to A and E with the depicted weights. Both fake nodes advertise that they canreach D1 directly. Based on the augmented topology, D
starts to use A to reach D1 , as the new cost (3) is lower

than the original one (6). A and E also select different
paths. Since the fake nodes do not really exist, packets
forwarded by A or E actually flow through B. Routers
B and C do not change their forwarding decisions.
Table 1 gives an overview of how Fibbing improves
flexibility and manageability by adopting a SDN-likeapproach while keeping the advantages of distributed
protocols (e.g., robustness and fast FIB modifications).
Fibbing is expressive. Fibbing can steer flows along
any set of per-destination loop-free paths. In otherwords, it can exert full control at a per-destination granularity. For this reason, Fibbing readily supports advanced forwarding applications such as: (a) traffic engineering, (b) load balancing, (c) fast failover, and (d)traffic steering through middleboxes. By relying on
destination-based routing protocols, Fibbing does notsupport finer-grained routing and forwarding policies
such as matching on port numbers. Though, those policies can easily be supported via middleboxes.
Fibbing scales and is robust to failures. Lying
to routers is powerful but challenging. Indeed, Fibbing must be fast in computing augmented topologies
to avoid loops and blackholes upon network failures.
At the same time, Fibbing must compute small augmented topologies since routers have limited resources.
Finally, Fibbing must be reliable and gracefully handle
controller failures. We address all three challenges.
Fibbing differs from previous approaches that
rely on routing protocols to program routers.
Prior approaches like the Routing Control Platform [11]rely on BGP as a “poor man’s” SDN protocol to install a forwarding rule for each destination prefix oneach router. In contrast, Fibbing leverages the routingprotocol implementation on the routers. Doing so, Fibbing can adapt the forwarding behavior of many routersat once, while allowing them to compute forwardingtable entries and converge on their own. That is, while
the controller computes the routing input centrally, therouting output is still computed in a distributed fashion.
Fibbing works on existing routers. We implemented
a fully-functional Fibbing prototype and used it to pro-Compilation

Augmentation§2§3

Optimization

Injection/
Monitoring

pol
s
r
p
n
b

§4

§3

+

path
reqs.

network
topology

per-destination
forwarding DAGs

augmented
topology

reducedtopology

running
network

::=
::=
::=
::=
::=
::=

(s1 ; . . . ; sn )p|bp1 and p2 | p1 or p2 | p
Path(n+ )id | ∗ | n1 and n2 | n1 or n2
r as backupof ((id1 , id2 )+ )Fibbing Policy
Requirement
Path Req.
Path Expr.
Node Expr.
Backup Req.

Figure 2: The four-staged Fibbing workflow.

Figure 3: Syntax of Fibbing high-level language.

gram real routers (both Cisco and Juniper). Based on
an augmented topology, these routers can install hundreds of thousands of forwarding entries with an average installation time of less than 1ms per entry. This
offers much greater scale and faster convergence thanis possible with state-of-the-art SDN switches [12, 13],
without requiring the deployment of new equipment andper-device actions from the controller. This also meansthat Fibbing can implement recent SDN proposals, like
Google’s B4 [8] and Microsoft’s SWAN [9]—on top ofexisting networks.
Our earlier work showed that Fibbing can enforce
any set of forwarding DAGs [14]. This paper goes further by describing the complete design, implementation,and evaluation of a Fibbing controller managing intradomain routing. Rather than focusing on specific use
cases (like traffic engineering), we describe its support
for different higher-level approaches (e.g., [8, 9]). We
make the following contributions:

itoring (§4) stage turns fake information into actual“lies” that the controller injects into the network.
In this section, we present the high-level language andcompilation process (§2.1), and show that Fibbing can
express a wide range of forwarding behaviors (§2.2).

• Abstraction: We show how to express and realize
high-level forwarding requirements by manipulating a distributed link-state routing protocol (§2).
• Algorithms: We propose new, efficient algorithms
to compute compact augmented topologies (§3).
• Implementation: We describe a complete Fibbing implementation which works with unmodified
Cisco and Juniper routers (§4).
• Evaluation: We show that our Fibbing controller
quickly generates small augmented topologies, inducing minimal load on routers (§5).

2.

FLEXIBLE FIBBING

Fibbing workflow proceeds in four consecutive stages
based on two inputs: the desired forwarding graphs (oneDirected Acyclic Graph, or DAG, per destination) andthe IGP topology (Fig. 2). The forwarding DAGs caneither be provided directly or expressed indirectly, at ahigh-level, using a simple path-based language. In thelatter case, the Compilation (§2) stage starts by compiling the requirements into concrete forwarding DAGs.
Then, the Topology Augmentation (§3) stage computes an augmented topology that achieves these forwarding DAGs. While computing an augmented topology is fast, the resulting topology can be large. As such,the job of the next Topology Optimization (§3) stage
is to reduce the augmented topology while preserving
the forwarding paths. Finally, the Injection & Mon-

2.1

Fibbing high-level language

Fibbing language (Fig. 3) provides operators with asuccinct and easy way to specify their forwarding requirements. A Fibbing policy is a collection of requirements, naturally expressed as regular expressions on
paths. Each requirement is either a path requirement
which specifies how traffic should flow to a given destination, or a backup requirement which specifies how
traffic should flow if the IGP topology changes. Eachpath requirement is recursively defined as a compositionof path requirements through logical AND and OR. Operators can express load-balancing requirements using a
conjunction of n requirements. Similarly, they can ensure that traffic to a specific destination will take oneof n paths (e.g., containing a firewall) using disjunction. Path requirements are composed of a sequenceof node requirements. A node requirement is either anode (router) identifier or the wildcard *, representing
any sequence of nodes. Like path requirements, noderequirements can be combined using logical AND and
OR. Whenever no path requirement is stated, the original IGP paths should be used. This way, operators
do not have to express all the unmodified paths, only
deviations from the IGP shortest paths.
The following example illustrates the main features ofthe language. It states that traffic between E and D1
should be load-balanced on two paths, traffic between
A and D2 should cross B or C and that traffic from F
to D3 should be rerouted via G if the link (F, H) fails.
( ( E , C , D1 ) and ( E , G , D1 ) ;( ( A , ∗ , B , ∗ , D2 ) or ( A , ∗ , C , ∗ , D2 ) ) ;( F , G , ∗ , D3 ) as backupof ( ( F , H ) ) ) ; )Fibbing policies are compiled into per-destination forwarding DAGs by finding convenient network paths (ifany). Compilation works in two consecutive stages.
First, the compiler expands any requirement with wildcards into paths. This step can be computationally expensive as, in general, a network can have a number ofpaths exponential in the number of nodes. While thisis unlikely, especially for networks designed according
to best practices, we bounded the number of paths thatcan be expanded out of a single requirement. We only
expand again if no solution is found with the current
set of paths. Once all requirements are expanded, thecompiler groups them by destination and computes the
Disjunctive Normal Form (DNF) of each requirement.
To finally produce a forwarding DAG, the compiler iterates over the disjunction of path requirements andchecks whether the resulting graph is loop-free.

2.2

Fibbing expressiveness3

Beyond steering traffic along a given path (§1), we
now show that Fibbing can also: (i) balance load overmultiple paths and; (ii) provision backup paths.
Fibbing can forward any flow on any set of paths.
Fibbing can load-balance traffic over multiple paths tomaximize throughput, minimize response time, or increase reliability. For example, consider the network in
Fig. 4a where three sources S1 , S2 , and S3 send traffic
to three corresponding destinations. Demands and link
capacities are such that link (F, G) is congested. One
way to alleviate congestion is to split traffic destined toD2 over the top (via (B, C)) and bottom (via (F, G))
paths. Load-balancing traffic coming from E on multiple paths is possible under conventional link-state routing (e.g., by re-weighting links (F, G) to 15. However,this would force the traffic from S2 and S3 to spreadover both paths, creating congestion. More generally, it
is impossible to route the traffic destined to D2 and D3
on different links under conventional link-state routing.
demand0.75
0.75 S1

A

3

B

1

1 C

10

0.50 S20.75 S3(A, D, E, F ). This is another example of a requirementthat is impossible to achieve with link-state routing,
and would require significant control-plane overhead in
MPLS. In contrast, it is easily done with Fibbing.

E

3

link
capacity
3

0.75

D

D1

H

D2
D3

10
F

1

1 G

3

0.75
0.50

(a) Initial topology

A

3

B

6
1
E

3

F

1 1
C

3

1

3

0.25

1 G
0.75
0.25

D

10
H

(b) Augmented topology

Figure 4: Fibbing supports multi-path forwarding. Here, it avoids the initial congestion (see(a)) by load-balancing traffic for D2 (see (b)).
This simple requirement can easily be expressed as:( ( S2 , E , B , C , H , D2 ) and ( S2 , E , F , G , H , D2 ) )Fig. 4b shows the augmented topology which realizes
this requirement. A fake node announcing D1 (with aweight of 6) is inserted between E and B. After introducing this node, E has two shortest paths (of cost 7)
to reach D2 and, hence, splits D2 traffic over B and
F . In this example, Fibbing enables maximum network
efficiency as each link is used to its full capacity.
Fibbing can provision backup paths for any flow.
Fibbing can provision backup paths to prevent congestion or increased delays after link and node failures.
As an illustration, consider the network in Figure 5a.
The failure of link (E, F ) leads to congestion since traffic flows for D1 and D2 are both rerouted to the same
path via link (A, B). To prevent congestion, traffic destined to D1 and D2 should be split over the two remaining disjoint paths but only upon failure on the path

0.50 S1
0.50 S2

.75
1

A
5

B

1 D
.5

3

0.50
0.50
1

C

E

1

5
G

3

3

H
5

(a) Initial topology

F

D1
D2

A
1
3

.75
1

B

3

0.50

1 D

1

.5

0.50

G

C
3
E

1

F

5
H

5

(b) Augmented topology

Figure 5: Fibbing can provision backup paths.
Here, possible congestion upon a link failure (see(a)) is avoided by adding a fake node (see (b)).
Backup paths can be specified in our language as:( A , B , ∗ , D1 ) and ( A , G , ∗ , D2 )as backupof ( ( A , D ) or ( D , E ) or ( E , F ) )Fig. 5b shows the corresponding augmented topology,
which has a single fake node advertising D2 . Weights
are set to prevent A from using the fake node to reach
D2 unless a failure occurs along the path (A, D, E, F ).
While successful for this example, Fibbing cannot satisfy all possible requirements for backup paths (§3.3).

3.

AUGMENTING TOPOLOGY

In this section, we detail the augmentation problem(§3.1), and we show how the Fibbing controller quickly
computes small augmented topologies from a set of forwarding DAGs. We rely on a divide-and-conquer approach based on three consecutive steps.
1) Topology initialization (§3.2): We modify the
initial weights in the link-state protocol (if necessary),
to guarantee that any set of forwarding DAGs can be
enforced by Fibbing. If needed, this operation has tobe done only once, when Fibbing is first deployed.
2) Per-destination augmentation (§3.3): Startingfrom an initialized topology, we compute a suitable augmentation, individually for every destination of an input forwarding DAG. We designed two algorithms forthis step, achieving different trade-offs between computation time and augmentation size. The fastest one,
Simple, can compute augmented topologies within milliseconds, and works by injecting a dedicated fake nodefor every router that changes its next-hop. The relatively slower one, Merger, reduces the augmentation
size by re-using the same fake nodes to program multiple routers. Simple and Merger are suited for different
goals. The speed of Simple is useful for quick failure reaction. In contrast, Merger can be run in background toprogressively re-optimize the augmented topology. We
evaluate the trade-offs achieved by each algorithm in §5.
3) Optimization across destinations (§3.4): We
merge the augmentations obtained in the per-destination
augmentation step to further reduce the number of fake

nodes and edges. Namely, whenever safe, we replace
multiple fake nodes announcing different destinations
with a single fake node which either announces all thedestinations or creates a new path (a shortcut) between
routers in the augmented topology.

3.1

The Topology Augmentation Problem

We start the description of the topology augmentation algorithms by precisely defining the basic concepts
on which they rely and the problem that they solve.
Fake nodes scoping. A Fibbing controller can generate both locally-scoped lies (targeted to a single router)and globally-scoped lies (targeted to all routers). Locallyscoped lies are useful as they enable local actions on one
router without creating side effects on other routers.
Globally-scoped lies affect the entire network. Hence,
if carefully computed, they can reduce the size of theaugmented topology. All of our previous examples used
globally-scoped lies. We detail how to implement bothkinds of lies in the current OSPF in §4.
Fake edges to forwarding next-hop mapping function. Fibbing can modify the routing path computed by
any IGP router r. In particular, it can augment the IGP
topology so that r’s shortest path is no longer the one in
the original topology but includes some fake sub-paths.
Throughout the paper, we assume that a fake edge inthe shortest path from any router r to any destination dcorresponds to the ability to force the next-hop of r ford to be any of its neighbors. In the example in Fig. 1,
for instance, the fake edge between the A and its adjacent fake node translates into A forwarding traffic to
B. We discuss in §4 how to achieve this ability in thecurrent OSPF protocol, as well as in future IGPs.
Topology augmentation problem. Since we assume
an arbitrary mapping between fake edges and forwarding next-hops, the topology augmentation problem isdefined as follows: Given an initial topology G and aset of forwarding DAGs, compute an augmented topology G0 ⊃ G such that for each path (u, v, . . . , d) in theforwarding DAG for d, the next-hop of u in one of its
shortest paths for d in G0 is either v or a fake node.

3.2

Topology Initialization

In the topology initialization, we scale the link weightsof the original IGP topology G to guarantee arbitrary
per-destination control through Fibbing and help reduce the size of topology augmentations. In particular, we proportionally increase link weights (multiplying them by a constant factor) if they are too low in G.
Moreover, we set very high announcement cost for any
destination, at least equal to the length of the longest
path in G times the maximum link weight.
Topology initialization enables full Fibbing expressivity. Indeed, it makes the IGP topology Fibbing compliant, which provably avoids cases in which
a forwarding DAG cannot be implemented by Fibbing(see [15]). We say that a topology is Fibbing compliant if for every destination d, the cost of the shortest
path from every router (including the ones announcingd) to d exceeds 2. In Fibbing compliant topologies, for
any router r and destination d the controller can always compute a fake path P such that (i) P is shorter
than the original shortest path from r to d; and (ii) P
is longer than the original shortest path from any otherrouter v 6= r to d. As proved by the following theorem,
this implies the ability of Fibbing to forward flows forthe same destination on any set of loop-free paths.
Theorem 1. Any set of per-destination forwarding
DAGs can always be enforced by augmenting a Fibbingcompliant topology even only with globally-scoped lies.
Proof. We prove the statement by showing a simple
topology augmentation procedure. Let G be the initial
topology. For every forwarding DAG with destinationd, we add for each node r in the network a fake node fr
announcing d. This generates a new fake path (r, fr , d)in the augmented topology. We set the total cost of
this newly added fake path to 2. Since G is Fibbing
compliant, then the cost of the shortest path from r to din G is greater than 2. Hence, the shortest path of every
node r in the augmented topology will be (r, fr , d). The
forwarding DAG is then implemented by mapping the
fake link on the right physical link.
Note that Theorem 1 applies to destinations in theaugmented topology. Those destinations do not need tomatch the destination prefixes announced in the original IGP. Hence, Fibbing allows to control flows for deaggregation of the original IGP destinations (up to IP
address granularity) or even non-overlapping prefixes.
Topology initialization is non-intrusive. Since it
is based on the adaptation of a few configurable parameters, our initialization procedure can be applied
to any link-state routing configuration, and preserves
the original forwarding paths. It can be carried out ina running network, using known lossless reconfiguration techniques [16]. Moreover, it is strictly needed no
more than once in the network lifetime. Indeed, since
Fibbing compliance does not depend on the routing requirements or the presence of specific links, any topology remains Fibbing compliant independently of new
requirements or the failures of nodes or links. Finally,
topologies growing in size can be easily kept Fibbing
compliant by ensuring that the new destinations are announced with high costs and the new links have weights
consistent with pre-existing ones.

3.3

Per-destination augmentation

We now describe Simple and Merger. We use Figure 6
to illustrate the difference of the two algorithms.

3.3.1

SimpleSimple relies solely on locally-scoped lies to avoid having to compute any fake path cost. For every destina-

initial

5

A

B

F

C

50
required(a) Requirements

1
1
f1

1
1

10

B
f2
1

100

C

10

30
10

X
1
f3 1

F

1

15

D

X
15

f0
10

10

5

5

A

25
A

30
10

25

locallyscoped
node

25

1

1

10

C

f4

1

D
50

100

(b) Simple augmentation

123
f3

15
globallyscoped
node

B

F
30

10

10
50

X
1

f4

D

100

118

(c) Merger augmentation

Figure 6: Outcome of our per-destination augmentation algorithms. Simple produces larger topologies (with locally-scoped lies) in a very short time, while Merger reduces the size of the augmentation
by relying on globally-scoped lies and a longer computation.
tion d and corresponding forwarding DAG D, the algorithm adds fake nodes to each router whose next-hops
in the original topology differ from those in D. Precisely, for every router r that changes its next-hop ford, Simple adds a fake node fr,d and a fake link (r, fr,d ).
Node fr,d announces d to r with a locally-scoped lie.
We set the total cost of path (r, fr,d , d) to 2. Since thetopology is Fibbing compliant, r is ensured to change
its shortest path. Also, since the lie is locally-scoped,
other routers are not affected by it.
Figure 6b shows the output of Simple for the example
of Figure 6a. Nodes A, B, C and X are required tochange their respective next-hops. Moreover, A needs
to load-balance on B and C. Thus, Simple creates five
locally-scoped nodes (two connected to A), all providing
fake paths to the destination with a cost of 2.

3.3.2

MergerTo reduce the number of fake nodes, Merger relies on
globally-scoped lies that can change the forwarding behavior of multiple routers at once. When applied to Figure 6a, Merger creates only two fakes nodes (see Fig. 6c)to change the next-hops of A, B, C and X, instead of
the five used by Simple. The added fake nodes createload-balancing on A (cost 134) via B and C, as required.
Merger performs the topology augmentation for any
destination d in two phases. First, it adds an excessive
number of fake nodes, and computes the lower and upper bounds for their respective cost. Second, it merges
fake nodes whenever possible, based on the value of thecomputed bounds. We now provide an intuitive description of those two phases. Additional details about themand Merger correctness proofs are reported in [15].
Step 1. Fake bounds computation. Merger starts
by adding fake nodes to every router r that is required tochange the next-hop (according to the input forwarding
DAG) for d. In this case, one new fake node fr,d is connected to r for every new r’s next-hop in the input forwarding DAGs. However, to enable merging of globallyvisible fake nodes, Merger calculates lower and upperbounds for every newly-added fake path (r, fr,d , d). As
the initial positioning of fake nodes is as in Simple, we
illustrate bound computations referring to Figure 6b.

The upper bound ub(fr,d ) represents the maximum
value of the fake path cost that changes r’s shortest
path to (r, fr,d , d). It is easy to compute by staticallyconsidering the non-augmented topology G. Indeed, it
is equal to dist(r, d, G) − 1, where dist(u, v, G) is thecost of the shortest path from u to v in G.
The lower bound lb(fr,d ) represents the minimal valueof the fake path cost that does not change the shortest
path of any real node different from r. To computeit, we divide nodes in two sets, depending on whether
the input forwarding DAG prescribes to change theirrespective next-hops or not.
For the next-hop preserving nodes whose shortest pathdoes not traverse r in the input topology, we imposethat their original shortest path is not modified by fr,d .
For example, when computing lb(f0 ) in Figure 6b, weensure that f0 does not change the shortest path of F ,by constraining lb(f0 ) + 25 > dist(F, d, G) = 110, thatis, lb(f0 ) = 86. More generally, for every fake nodefr,d and every next-hop preserving neighbor n of r, we
impose that lb(fr,d ) > dist(n, d, G) − dist(n, r, G).
For next-hop changing nodes (connected to other fakenodes), the final value of their shortest paths is notknown in advance, but is determined by the augmentation itself. That is, the lower bound of any fakenode generally depends on the lower bound of other fakenodes. For example, in Figure 6b, f 4 changes the shortest path of X only if lb(f 4) < dist(X, C, G) + lb(f 3).
To avoid that real nodes pass through fake nodes notdirectly connected to them, Merger runs a lower boundpropagation procedure. This procedure takes as input
the lower bounds initialized with values from next-hop
preserving nodes. It then fixes one lower bound at thetime, following a specific order and adjusting the others
to be consistent with the fixed one. This order guarantees that each lower bound must be considered only
once. Sometimes, lower bounds cannot be made consistent. Indeed, Theorem 1 does not provide guarantees
if fake nodes are connected only to next-hop changing
nodes. We solve these cases by using locally-visible lie.
Step 2. Fake nodes merging. In this step, Merger
tries to merge fake nodes together. More precisely, ititerates over every simple path from a source to d inthe input forwarding DAG. For each of those paths, itmerges pairs of fake nodes whenever safe.
To assess when it is safe to merge a fake nodes f 0
into f 00 , Merger sequentially performs three checks. We
illustrate these checks by considering the required path
(A, B, X, D) and the merge of f1 into f2 in Figure 6b.
First, Merger assesses whether the IGP shortest paths
are compliant with the considered source-sink path in
the DAG. In our example, it verifies that the shortest path from A and B (i.e., (A, B)) is a sub-path of
the required (A, B, X, D). If A had predecessors in therequired path not connected to a fake node, this check
would have been repeated for those predecessors as well.
Second, Merger checks the possibility to use f 00 aspart of the shortest path of the real node connected
to f 0 without changing the current next-hops of any
node. To this end, the algorithm assess the existence offeasible post-merging bounds for f 00 . More precisely, it
re-computes the modified lower bound of f 00 as the minimum value (if any) that forces the new shortest pathof the real node connected to f 0 and its next-hop preserving predecessors in the required path through f 00 ,without affecting nodes previously not crossing f 00 . In
our example, the lower bound of f2 is modified to exclude the constraint of not changing A’s next-hop, hence
it is decreased to lb(f2 ) = 81 (it was greater before, for
A’s next-hop to be f1 ). The upper bound of f 00 is also
modified to ensure that the real node connected to f 0
and its next-hop preserving predecessors use the fakepath via f 00 . In our example, ub(f2 ) is modified to 129,as the cost of the original shortest path from A to thedestination is 135 and those between A and B is 5.
Third, Merger simulates the merge to assess whether
all bounds can be consistently adjusted network-wide,
given that the merging f 0 into f 00 would change thebounds of f 00 and remove one fake node. To this end, we
re-run the lower bound propagation procedure, devoting
special attention to fake nodes used for load-balancing.
In our example, for instance, we constrain the lower
bound of f0 to be equal to the cost of path (A, B, f2 , d),meant to be used by A after the merging.
If all the three checks pass, then Merger actually
perform the merge, by removing f 0 and updating thebounds of all other fake nodes (including f 00 ) according
to the values computed during the last check.

3.3.3

Dealing with backup requirements

Backup requirements can be specified by providing
additional sets of (tagged) forwarding DAGs to our algorithms. Let G0 be an augmented topology computed
to accommodate primary requirements. To deal withbackup ones, slight variants of Simple and Merger canbe run after the computation of G0 . The main modification of Simple consists in setting the cost of the
fake paths added for backup requirements to 3 insteadof 2. In contrast, backup requirements are supported
in Merger by imposing that lower bounds are always
greater than the cost of the shortest path in G0 .

25

25
5

A

B

F

133 1
90
100

10

C

15

10
50

X
1
118

71

D

5

B

133 1

30
10

A

100
90
100

100

F

100

30
10

10
C

15

10
X
19

globally
scopedshortcut

50
1

D
500

100
asymmetricweight(a) Fake destination merging. (b) Fake shortcuts creation.

Figure 7: Cross-destination optimizations.
Contrary to primary requirements (see Theorem 1),
Fibbing may not enforce backup requirements, even ina Fibbing-compliant topology (see [15]). Indeed, if thecost of the original shortest path of a node r is equal
to a fake one (used for a primary requirement) in G0 ,then backup paths different from the original shortest
path cannot be implemented on r. In those cases, wenotify the operator on the impossibility to implement
the given backup paths.

3.4

Cross-Destination Optimization

Fake nodes computed on a per-destination basis may
be redundant. We reduce such redundancy in two ways,
namely, by (i) merging fake nodes connected to the same
real node, and (ii) replacing fake destination announcements with fake paths connecting real nodes.
Cross-destination merging. After per-destination
augmentations, two fake nodes f1 and f2 announcing
different destinations d1 and d2 can be connected to thesame node r and used to force traffic to the same reallink (r, n). Those fake nodes can always be merged. Indeed, we can replace f1 and f2 with a new fake node f 0such that (i) cost(r, f 0 ) = min{cost(r, f1 ), cost(r, f2 )},and (ii) f 0 announces both d1 and d2 , with cost(f 0 , di ) =cost(r, fi , di ) − cost(x, f 0 ) for i = 1, 2. For example, assume that in the network in Figure 6 additional destinations are attached to C and F as in Figure 7a. The
result of the cross-destination merging is shown in Figure 7a, where both A and X have a single fake neighborannouncing multiple destinations (rather than multiple
fake neighbors each announcing a single destination).
This reduces the number of fake nodes from 4 to 2.
Creating shortcuts. One of the most appealing features (unmatched by competitor solutions) of Fibbing
is that a single lie can change the paths for multiple destinations. To this end, we need however to replace fake
destination announcements with fake paths connecting
real nodes together, i.e., fake shortcuts.
Currently, we use fake shortcuts only if a real linkis never traversed in different directions. Consider, forexample, the link between X and D in Figure 7a. It is
traversed from X to D for the destinations attached to
D and F , and never from D to X. In those cases, we
try to transform X’s fake neighbor into a fake shortcut,
as in Figure 7b. Let u and v be the two real nodes
at the endpoints of the shortcut. First, we check if ashortcut cost c exists such that all the shortest paths1
are kept the same with and without the shortcut. If thiscondition is met, given a fake node f used to enforce
the subpath (u, . . . , v) in the input forwarding DAGs,
all fake destinations announced by f are replaced by a
fake shortcut (u, f, v) and the cost of (u, f, v) is set to c.
Figure 7b illustrates that we found such a value c = 20
for X in our example. Also, we use asymmetric weights
to prevent the fake shortcut from being traversed in the
opposite direction. To this end, the cost of path (v, f, u)
is set to a very high value, e.g., by setting a high weightof the directed link (v, f ). In Figure 7b, we indeed set
the weight of the link from D to the fake node in the
shortcut to 500.

4.

IMPLEMENTATION

We built a complete prototype of Fibbing in Python(algorithmic part) and C (interaction with OSPF) byextending Quagga [17]. Fibbing code base spans over
2300 (resp. 400) lines of Python (resp. C) code. It
is available at http://www.fibbing.net. In this section, we present our prototype (§4.1), describe how Fibbing works with current OSPF routers (§4.2), and propose two small modifications to link-state protocols thatwould make Fibbing even more efficient (§4.3). Finally,
we describe how to ensure controller reliability (§4.4).

4.1

Fibbing Controller

Our prototype consists of three main components:
Fake topology generator applies (i) the compilation
algorithms (§2) to turn forwarding requirements into
forwarding DAGs and (ii) the augmentation algorithms(§3) to convert the forwarding DAGs into fake nodes
and links. The topology generator uses a JSON interface to register for update events produced by theevent manager. Upon network updates, the generator
automatically recomputes the augmented topology either using Simple to ensure fast convergence, or Merger
to reduce the size of the topology. To ensure fast convergence and a small augmented topology, the generator also pre-computes augmentations with Merger, e.g.,
those needed for any single link failure, and stores themin a deltas database.
Link-state translator interacts with the routers by
establishing routing adjacencies to inject lies and track
topology changes. Thanks to the flooding mechanism
used by link-state protocols, a single adjacency is sufficient to send and receive all routing messages to/from
all routers. Though, maintaining several adjacencies isuseful for reliability. In this case, the translator simply
injects the lies via all adjacencies. While this slightly
increase the flooding load, doing so does not impact the1
By definition of the shortest path, we only need to check thepaths from v and from u neighbors to each destination.

routers memory as each message has a unique identifier
and routers only maintain one copy per ID in memory.
Event manager maintains an update-to-date view of
the network topology by (i) parsing the routing messages collected by the translator and (ii) constructing
a network graph for the topology generator. The event
manager checks whether each new event (e.g., a node
failure or addition) affects any of the forwarding requirements. If so, it first checks the deltas database for a
pre-computed lie, and otherwise notifies the topology
generator to request a new augmented topology.

4.2

Fibbing with Unmodified OSPF

Our Fibbing prototype works with unmodified OSPFspeaking routers (tested on Cisco and Juniper). To creates lies, our prototype leverages the Forwarding Address (FA) [18] field of OSPF messages. Suppose thecontroller wants routers to think that destination d is
directly attached to the router with IP address y. Then,the controller injects the route for d with a forwarding
address of y and the desired cost for the fake edge fromy to d. Router y ignores the message, and all otherrouters compute the cost of the route as the sum of
their cost to y plus the cost in the message.
Locally-scoped lies in OSPF. To support locallyscoped lies, we reserve a set of IP addresses to be used asFAs. All those addresses are propagated network-widein OSPF. However, every router is configured not to install routes to all those addresses. Consequently, only
the directly-connected router can reach any of those addresses, and accept routes specifying that address as FA.
Both allocation and configuration of FA-associated IP
addresses can be done just once in the network lifetime.
Globally-scoped lies in OSPF, and limitations.
OSPF readily supports globally-scoped lies by simply
propagating OSPF messages with the FA set to an IP
address announced in OSPF. However, some subtle constraints hold in an unmodified OSPF network due to
how FAs are resolved on the router. Prominently, (i)OSPF fake nodes are actually fake routes to the specified FA, hence both their positioning and the path to be
used for reaching them are constrained; and (ii) OSPF
routers discard any OSPF message whose FA is one ofits own IP address and computes its shortest path according to the topology without the fake node. The
combination of these two constraints limit the power ofglobally-scoped lies in OSPF, making them insufficient
to implement all possible forwarding DAG. An exampleof those cases is reported in [15].
Overcoming OSPF limitations. To support the full
expressiveness of Fibbing, our prototype controller uses
an OSPF-compliant implementation of Merger with a
combination of locally and globally-scoped lies. This
implementation uses globally-scoped lies whenever possible, and falls back to locally-scoped lies for any requirements that cannot be met that way.

4.3

Proposed Protocol Enhancements

Other link-state protocols, like IS-IS [6], do not support forwarding addresses, and even the OSPF implementation of lies has limitations. However, minor protocol extensions can enable more flexible Fibbing in future routers. Fully-fledged Fibbing needs for the routing protocol to support two functions: (i) the creationof adjacencies (with fake nodes) on the basis of a received message; and (ii) a third-party next-hop mechanism which allows to specify in a route the forwarding
next-hop to be used if that route is selected. Support
for these functions can be added to protocol specifications (without impacting current functionalities), andcan be deployed through router software updates.
Preliminary discussions with router vendors confirm
that these changes are reasonable and could be integrated into current protocol implementations. Moreover, backwards compatibility can easily be achieved aslegacy routers would simply ignore any Fibbing-specificprotocol features. Our algorithms can be modified toaccount for the fact that the shortest path of a legacy
router is never changed by any fake node.

4.4

Controller Replication

As any network component, a Fibbing controller canfail at any time. Reliability can be ensured by running
multiple copies the Fibbing controller in parallel andconnecting them to different places in the network.
No state needs to be synchronized between the replicas besides the input forwarding requirements (mostly
static anyway). Indeed, Fibbing algorithms are deterministic, hence all replicas will always compute exactly
the same augmented topology. The only dynamic state
maintained by a Fibbing replica is the network graph.
This state, however, is implicitly synchronized throughthe shared topology offered by the underlying IGP: thelink-state flooding mechanism keeps the network graphup to date and eventually consistent across all replicas.
The determinism of our algorithms enables all replicas to inject (the same) lies at the same time. However,this would increase the amount of flooded information.
To limit control-plane overhead, our implementation
relies on a primary-backup architecture with a single
active replica and an inexpensive election process. A
pre-defined range of router IDs is reserved for controller
replicas. The replica with the lowest router ID acrossall running ones is the active replica. It is the only
one injecting lies, while the others only compute thetopology augmentation. When the controller is booted
or when an active replica fails, running replicas receive
IGP messages on the current network topology. Basedon those messages, every replica independently infers
the possible presence of other replicas; it also checks
whether it is the new active replica by comparing its
router ID with the one of the other running replicas.

5.

EVALUATION

We now evaluate Fibbing along three axis. First, weshow that existing routers are perfectly capable of handling the extra load induced by Fibbing (§5.1). We
then demonstrate the efficiency of Fibbing’s augmentation algorithms in terms of speed and size of the topology (§5.2). Observe that Fibbing behaves as a plain
IGP at the network level. Hence, given its negligible
impact on single routers and the efficiency of our controller, current ISP networks can be seen as the bestlarge-scale evaluation for Fibbing. We therefore complete the evaluation by illustrating how Fibbing can beused in a realistic case (§5.3).

5.1

Router measurements

By increasing the size of the link-state routing topology, Fibbing could increase the CPU and memory overhead on the routers, or slow down protocol convergence.
Our experiments demonstrate that the impact on loadand convergence time is negligible. All our measurements were performed using OSPF on a recent Cisco
ASR9K running IOS XR v5.2.2 equipped with 12GB of
DRAM assigned to the routing engine, as well as on a (7year-old) Juniper M120 running JunOS v9.2, equippedwith 2GB of DRAM. Both routers are representative oftypical edge devices (i.e., aggregation routers) found incommercial networks. We draw the same conclusions
on both router platforms, and focus on measurements
collected on the Cisco device in the following.
Fibbing induces very little CPU and memory
overhead on routers. We first measured the memory increase caused by a growing number of fake nodes(Table 2). Two processes are impacted by the presenceof fake nodes: (i) the RIB process, which maintains
information about all the routes known to each destination, and (ii) the OSPF process which maintains theentire OSPF topology. Even with a huge number offake nodes (100,000), the total overhead on both processes was only 154MB—a small fraction of the total
memory available. We collected the CPU utilization on
the router every minute immediately after we started
injecting fake nodes. The utilization was systematicallylow, at most 4%. This is easily explained as Fibbing
relies on OSPF Type-5 LSAs which do not cause therouters to recompute their shortest paths to each other.
# fake nodes

RIB memory (MB)OSPF memory (MB)

1,000
5,000
10,00050,000100,000

0.09
1.58
3.56
19.67
39.78

0.56
5.19
10.96
56.37
113.17

Table 2: Routers easily sustain Fibbing-induced
load, even with huge augmented topologies.

20

40

60

80

100

1.0
0.8
0.6
0.0

0

% of nodes changing next−hop(a) Per-destination time

0.4

fraction of experiments

60
40
0

0

merger (cross opt)
mergersimple0.2

80

simplemerger (95−th)merger (median)merger (5−th)20# of fake nodes (% of total nodes)

time (sec)

0.001

0.1

10

simplemerger (95−th)merger (median)merger (5−th)

20

40

60

80

0

% of nodes changing next−hop(b) Per-destination augmentation size

5

10

15

20

25

# of fake nodes (% of total nodes)(c) Cross-destination reduction

Figure 8: Evaluation of our augmentation algorithms.

5.2
Fibbing can quickly program forwarding entries.
In a second experiment, we measured how long it took
for a router to install a growing number of forwarding
entries (Table 3). We injected a growing number of fakenodes, one per destination, and measured the total installation time, by tracking the time at which the router
updated the last entry in its FIB. The time to process and install one entry was constant (around 900µs),
independent of the number of entries. This result isseveral orders of magnitude better than any OpenFlow
switches currently on the market [12, 13]. Since installation of forwarding entries is distributed, routers caninstall their entries in parallel, meaning Fibbing can program thousands of network-wide entries within 1 second.
# fake nodes

installation time (s)avg time/entry (µs)

1,000
5,000
10,00050,000100,000

0.89
4.46
8.96
44.74
89.50

886.00891.40894.50894.78894.98

Table 3: Programming a forwarding entry in arouter with Fibbing is fast, sub 1ms.
Fibbing does not have any impact on routingprotocol convergence time. Finally, we compared
the total time for routers to converge with and without
fake nodes. We failed a link and measured the time forthe last FIB entry to be updated considering two cases:(i) no lie was injected and (ii) one lie per destination
was injected. Similar to the previous experiments, werepeated the measurements for a growing number ofdestinations and lies, between 100 and 100,000. In all
our experiments, the presence of lies did not have any
visible impact. The total convergence times with orwithout lies were systematically within 4ms, with therouter being even faster to converge in the presence oflies in some cases.

Topology Augmentation Evaluation

We now evaluate Simple and Merger (§ 3) according to: (i) the time they take to compute an augmented
topology for a given requirement, and (ii) the size of theresulting augmented topology. Results are depicted inFig. 8. Our evaluation is based on simulation performedon realistic ISP topologies [19], whose sizes range from80 nodes to over 300. On these topologies, we generated forwarding requirements by randomly changing
the next-hop of randomly selected nodes. Destinationsof requirement DAGs were also randomly generated.
Fibbing augments network topologies within ms.
Fig. 8a shows the time (on the y-axis) taken by Simple
and Merger for an increasing number of nodes that mustchange their next-hop (on the x-axis). The plot refers tosimulations we ran on the biggest Rocketfuel topology(AS1239). The time taken by Simple to compute theper-destination augmentation varies in the order of milliseconds, ranging from 0.5 ms to 8 ms. While Merger
took more time (as expected), its performance is still
one order of magnitude lower than the second. For bothalgorithms, the computation time does not vary muchwith the number of nodes changing their next-hops.
Merger and cross-optimization effectively reduce
the size of the augmented topology. Fig. 8b plots
the fake topology size (on the y-axis) when the numberof nodes that have to change their next-hop increases(on the x-axis) for a single destination on all topologies. The plot shows that Merger reduces the numberof fake nodes by about 25% in the average case and almost 50% in the best case. Fake topology reduction isfurther corroborated by our cross-destination optimization procedures (see §3.4). Fig. 8c shows a cumulative
distribution function (CDF) of the topology augmentation size computed by Simple, Merger, and Merger
with cross-destination optimization. The figure refers
to simulations with a number of destinations varying
between 1 and 100 with 26% of the nodes changing
their nexthop. In more than 90% of our simulations,cross-destination optimization achieves a reduction of
the augmented topology. Depending on the experi-ment, such a reduction is up to about 10% with respect
to Merger without cross-destination optimization, and
20% with respect to Simple.

5.3

Case Study

We now show the practicality of Fibbing by improving the performance of a real network consisting of fourrouters (Cisco 3700 running IOS v12.4(3)) connected ina square with link of 1 Mbps capacity (see Fig. 9a). In
this network, we introduce two sources (bottom left)that send traffic to two destinations (bottom right) using iperf. The first source is introduced at time t = 0,
the second one at time t = 5. OSPF weights are configured such that all traffic flows along link (C, X).
without Fibbing
1

10

5
flow2

C

X

5
flow1

with Fibbing
A

1

B

1
f1

1.2

B

Throughput (Mbps)

A

1
.8
.6
.4
.2

flow 1flow 2

0
10

2
C

5

5

0
X

(a) Topology

5

10

16

20

25

Time (s)(b) Throughput evolution

Figure 9: Case study on how Fibbing can alleviate congestion. At t = 16, a fake node is added toshift one flow to the upper path in the network,
increasing the total available bandwidth.
Such a network suffers from two inherent inefficiencies: (i) the upper path is never used and (ii) the twoflows systematically traverse the same path, competingfor bandwidth, no matter what the link weights are.
Fig. 9b plots the throughput of each flow. Immediately
after the introduction of the second flow at t = 5s, thetwo flows start competing for the available bandwidth.
To improve network efficiency, the Fibbing controller
injects a fake node f1 connected to C and announces
one destination at time t = 16. A few ms after the injection, we see that the throughput of both flows double
as each of them now traverses a different path.

6.

REACTION TO FAILURES

We now analyze Fibbing’s reaction to different kindsof failures. We distinguish between network (affecting real router or router-to-router links) and controller(shutting down replicas or replica-to-router links) failures. Also, we separately deal with failures inducing
network partitions and non-partitioning ones.
Fibbing quickly reacts to non-partitioning failures. Upon network failures, forwarded flows fall in
one of the following three cases. First, some flows are
not impacted by the failure as their pre-failure forwarding path is not disrupted. Second, flows for which no

input requirements have been specified require only the
IGP to establish a new path, but no action from the Fibbing controller. Reaction to failures is extremely fast in
this case (sub-second even in large networks), thanks tofast convergence [20] and local fast re-route [21] featurescommonly supported by current IGP implementations.
Third, the remaining flows are forwarded on paths modified by the Fibbing controller. They require reaction
from the controller, both to remove possible blackholes
or loops due to previously injected lies [14], and to avoid
requirement violations due to new IGP paths. Theoretically, the total failure reaction time is equal to thesum of the notification time (for the controller to be
notified of the failure), the processing time (for the controller to compute the new topology augmentation) andthe IGP convergence time (for all routers to install the
new lies). Our evaluation (§5) shows that the processing time is negligible, especially for the Simple algorithm. Moreover, the notification time is bounded by
the IGP convergence time, as flooding is faster thanre-convergence. Thus, in the worst case, the total reaction time is twice the IGP convergence time, that is,still below 2 seconds [20]. Also, in the average case,the notification time is smaller than IGP convergence,
because the controller is notified about the failure before all other routers complete convergence; hence, thecontroller injects new lies during the IGP convergence,and the total failure reaction time is slightly higher than
IGP convergence without Fibbing.
In addition, if one or more controller replicas fail but
others are running, we have no impact on forwarded
flows, unless the failed replica is the active one and someof its injected lies expire before the new active replica is
elected. Even in the latter case, the new active replica isquickly elected, in a time which is approximately equal
to the detection and flooding of the failure event by the
IGP. The short election time makes it unlikely that lies
expire before the new active replica is elected, and limits
the period with possible disruptions.
Fibbing can implement both fail-open and failclose semantics to deal with partitions. Even if
unlikely, catastrophic events like a simultaneous failureof all the controller replicas or network partitions may
happen. As for any centralized solution, a major risk inthose cases is to leave the network uncontrolled. This
happens, for example, if some routers are not reachable by a controller replica after a network partition.
With respect to pure SDN solutions, Fibbing has the
additional possibility to delegate control to the underlying IGP. This way, Fibbing can implement both the
fail-open or fail-close semantics, on a per-destinationbasis. For non-critical (optimization) requirements liketraffic engineering ones, the corresponding destinations
can be injected in the IGP, so that connectivity canbe preserved as long as the partition leaves at least one
source-destination path. For stringent requirements likesecurity ones (e.g., firewall traversal), Fibbing can im-replica
fails

Throughput (Mbps)

1.2

(A,B)
fails

(B,X)
fails

(B,X)
up

while the violet flow keeps using the IGP shortest path.
Finally, re-adding the failed links allows the running
replica to re-take control of the network: it re-buildsa (safe) path for the red flow upon (B, X) restoration,and re-optimizes the distribution of both flow over theavailable paths when (A, B) is restored.

(A,B)
up

1
.8
.6
.4
.2

flow 1flow 2

0
0

5

10

7.
15

20

25

30

35

40

45

50

55

Time (s)Figure 10: Case study on how Fibbing reacts
to failures, and can successfully implement failclose (flow 1) and fail-open (flow 2) semantics.

plement fail-close semantics by not announcing the corresponding destinations in the IGP. As such, the corresponding flows stop to be forwarded in the absence ofthe controller. To quickly reach this configuration, we
can set a low validity time of the injected lies, making
them rapidly expire if not refreshed. This then comesat the cost of additional control-plane overhead.
We confirmed Fibbing resilience. We consider again
the topology in Figure 9a, and we connect two controller
replicas respectively to routers A and B. The active
replica is initially the one connected to A. We assume astrict policy on the red flow forcing it to cross the link
(C, X). We then configure a fail-close semantics to it,
and a fail-open to the other flow. Starting from a statein which both replicas and all links are up, we successively fail (i) the active replica at time t = 5; (ii) link
(A, B) at t = 12; and (iii) link (B, X) at t = 20. Finally, we re-establish both failed links, one at the time(at t = 36 and t = 48).
The results of this experiment, collected via iperf,
are reported in Figure 10. Concretely, the failure of
the active replica has no impact on the forwarded flows.
Indeed, the initially passive replica (connected to B)
quickly detects the failure of the other replica, and start
refreshing the injected lies by the failed controller. When
(A, B) fails, the active replica needs to remove the fakenode f 1: Since the physical path (C, A, B, X) is notavailable anymore, this fake node is creating a loop between C and A for the violet flow. Upon failure detection, the controller then sends the LSA to remove
f 1, re-establishing the connectivity for the disrupted
flow in approximately 1s. Note that this time can belowered by relying on fast failure detection mechanisms(like BFD). When (B, X) also fails, we create a partition that makes it impossible for the running replica tointeract with routers A, C, and X. After about 1s, theinjected lies disappear, because they are not refreshedanymore by any controller. Consistent with the configured failure semantics, the red flow is blackholed (toavoid the IGP routing it over policy-violating paths)

FREQUENTLY ASKED QUESTIONS

We now provide answers to high-level concerns often raised against Fibbing. Since empirical analyses are
hardly applicable to those concerns (e.g., debuggability), we describe qualitative considerations.
Is Fibbing a long-term solution? Yes. We believe
Fibbing is here to stay. In the short run, Fibbing offers programmability and is easy to deploy, at very little cost. A network that ultimately needs even greater
flexibility could deploy finer-grained SDN functionality at the edge, and solutions like Fibbing in the core,
as advocated by major industry [22] and academic actors [10, 23]. By combining the best of centralized anddistributed routing, Fibbing fits the needs of the network core (flexibility, robustness, low overhead) better
than current forwarding paradigms.
Does Fibbing make networks harder to debug?
No. Fibbing relies on “tried and true” protocols. Thishas several implications. First, Fibbing routing matches
the current mental model of operators, a major advantage with respect to other SDN proposals. Moreover,Fibbing is compatible with any existing management,
monitoring, and debugging tools. Finally, the Fibbing
controller can expose a higher-level interface for debugging, including a mapping between the injected lies andtheir usage (matched requirements and how).
Does Fibbing sum the complexities of centralized and distributed approaches? No. Fibbing
uses the underlying IGP in a very simple way. The
IGP output is easy to predict and provides the controller with a powerful API to program routers. As aresult, the design of the Fibbing controller is significantly simpler than for existing SDN controllers (e.g.,[24, 25, 26, 27]) since heavy tasks such as path computation and topology maintenance are offloaded to therouters. Even basic primitives for controller replication
and replica consistency are mainly delegated to current
distributed routing protocols (see §6).
Does Fibbing impact security? No. The lies introduced by the Fibbing controller can easily be authenticated, e.g., using MD5-based authentication [28, 29].
Since Fibbing can only program loop-free paths,
can it support middleboxes chaining? Partially.
Forwarding loops can be encountered when steering traffic through a chain of middleboxes (e.g., [30] and [31]).
These requirements can be satisfied in Fibbing with local support from routers to break the loops. For instance, a router could match on the input interface inaddition to the destination IP address using policybased routing, a feature widely available on existing
routers [32, 33] and provisioned centrally using BGP
flowspec [34, 35]. Alternatively, middlebox traffic steering could be implemented through SDN functionality at
the network edge, while still using Fibbing in the core.

8.

RELATED WORK

Fibbing contributes to the larger debate about centralized and distributed control over routing by identifying a new point in the design space.
Centralized configuration of distributed routing
protocols: A centralized management system can perform traffic engineering by optimizing the link weights
in link-state routing protocols [36, 37]. Fibbing is moregeneral, since it can implement any forwarding paths byinjecting fake nodes and links into the link-state routing
topology. The extra flexibility enables even better loadbalancing, as well as a wider range of functionality.
Centralized control using existing routing protocols as a control channel: RCP [11] is a logicallycentralized platform that uses BGP to install forwarding entries into routers. RCP must install forwarding
entries one-by-one, on each device. In contrast, Fibbing
can adapt the forwarding behavior of many routers at
once, with little input (e.g., one fake node), and let themcompute their own forwarding entries.
Centralized control over the routing/forwarding
tables: In SDN, a central controller installs packetprocessing rules directly in the switches, possibly reacting to the reception of specific packets. While more
flexible (e.g., enabling stateful control logic) than Fibbing, SDN requires updating the switch-level rules oneby-one, and forgoes the scalability and reliability benefits of distributed routing. Recently, the IETF developed I2RS [38] which offers a new management interface
for centralized updates the routing information bases(RIBs) in the routers. Still, I2RS must push RIB entries individually to each router.
The Fibbing language for expressing requirements issimilar in spirit to Merlin [39], but the mechanism forsatisfying the requirements (i.e., fake nodes/links) is entirely different. Our main contributions are the Fibbing
techniques and algorithms, not the language.
For the networks which require the extra flexibility
provided by OpenFlow, Fibbing helps during the transition by providing access to the FIBs of legacy routers
to any SDN controller [40]. This contrasts to techniques like Panopticon [41], where programmability is
only available in the SDN-enabled parts of the network.

9.

CONCLUSIONS

The advent of SDN makes it clear that network operators want their networks to be more programmable andeasier to manage centrally. In this paper, we show how
Fibbing can achieve those objectives, by centrally andautomatically controlling forwarding without forgoing
the benefits of distributed routing protocols. Fibbing is
expressive, scalable, and works with existing routers. In
future work, we plan to look at extensions of IGP protocols (e.g., for source-destination routing [42] or network
service header awareness) to enable finer-grained control via Fibbing. Abstractly, Fibbing shows how centralized and distributed approaches can be profitably
combined. We believe that new research can further
explore this direction, for example, investigating an alternative division of tasks between centralized and distributed network components.

Acknowledgements
We are grateful to SIGCOMM anonymous reviewers
and our shepherd, Teemu Koponen, for insightful comments. We thank Jo Segaert from BELNET and Dave
Ward, Clarence Filsfils and Kris Michielsen from Cisco
Systems for their support in testing Fibbing on realrouters. This work has been partially supported by the
EC Seventh Framework Programme (FP7/2007-2013)
grant no. 317647 (Leone) and by the ARC grant 13/18054 from Communauté française de Belgique.

10.

REFERENCES[1] D. Awduche et al., “RSVP-TE: Extensions to
RSVP for LSP Tunnels,” RFC 3209, 2001.
[2] N. McKeown et al., “OpenFlow: enabling
innovation in campus networks,” ACM
SIGCOMM CCR, vol. 38, no. 2, pp. 69–74, 2008.
[3] A. Farrel, J.-P. Vasseur, and J. Ash, “A Path
Computation Element (PCE)-BasedArchitecture,” RFC 4655, 2006.
[4] C. Filsfils et al., “Segment Routing Architecture,”Internet Draft, 2014.
[5] B. Clouston and B. Moore, “Definitions ofManaged Objects for HPR using SMIv2,” RFC
2238, 1997.
[6] D. Oran, “OSI IS-IS Intra-domain Routing
Protocol,” RFC 1142, 1990.
[7] A. Pathak, M. Zhang, Y. C. Hu, R. Mahajan, and
D. A. Maltz, “Latency inflation with MPLS-based
traffic engineering,” in IMC, 2011.
[8] S. Jain et al., “B4: Experience with a
Globally-Deployed Software Defined WAN,” in
SIGCOMM, 2013.
[9] C.-Y. Hong et al., “Achieving High Utilization
with Software-Driven WAN,” in SIGCOMM, 2013.
[10] M. Casado et al., “Fabric: A retrospective on
evolving sdn,” in HotSDN, 2012.
[11] M. Caesar et al., “Design and implementation of arouting control platform,” in NSDI, 2005.
[12] X. Jin et al., “Dynamic scheduling of network
updates,” in SIGCOMM, 2014.

[13] C. Rotsos, N. Sarrar, S. Uhlig, R. Sherwood, andA. W. Moore, “OFLOPS: An Open Framework
for Openflow Switch Evaluation,” in PAM, 2012.
[14] S. Vissicchio, L. Vanbever, and J. Rexford, “Sweet
little lies: Fake topologies for flexible routing,” inHotnets, 2014.
[15] S. Vissicchio, O. Tilmans, L. Vanbever, and
J. Rexford, “Central Control over Distributed
Routing (Extended Version),” Technical Report,
2015.
[16] L. Vanbever, S. Vissicchio, C. Pelsser, P. Francois,and O. Bonaventure, “Seamless Network-Wide
IGP Migrations,” in SIGCOMM, 2011.
[17] “Quagga routing suite,” www.nongnu.org/quagga.
[18] J. Moy, “OSPF Version 2,” RFC 2328, Apr. 1998.
[19] N. Spring, R. Mahajan, and D. Wetherall,“Measuring ISP topologies with Rocketfuel,” in
SIGCOMM, 2002.
[20] P. Francois, C. Filsfils, J. Evans, andO. Bonaventure, “Achieving Sub-second IGP
Convergence in Large IP Networks,” ACM
SIGCOMM CCR, vol. 35, no. 3, 2005.
[21] C. Filsfils, P. Francois, M. Shand, B. Decraene,
J. Uttaro, N. Leymann, and M. Horneffer,“Loop-Free Alternate (LFA) Applicability in
Service Provider (SP) Networks,” RFC 6571, 2012.
[22] T. Koponen et al., “Network Virtualization in
Multi-tenant Datacenters,” in NSDI, 2014.
[23] “Time for an SDN Sequel? Scott Shenker Preaches
SDN Version 2,” www.sdxcentral.com/articles/
news/scott-shenker-preaches-revised-sdn-sdnv2/
2014/10/.
[24] “ONOS: Open Network Operating System,”
http://onosproject.org/.
[25] T. Koponen et al., “Onix: A distributed control
platform for large-scale production networks,” in
OSDI, 2010.
[26] “Project Floodlight,”
http://www.projectfloodlight.org/floodlight/.
[27] N. Foster et al., “Languages for software-defined
networks,” IEEE Comm. Mag., 2013.
[28] “Cisco OSPF MD5 Authentication,”
http://www.cisco.com/c/en/us/support/docs/ip/
open-shortest-path-first-ospf/13697-25.html.
[29] “Juniper OSPF MD5 Authentication,” http://
www.juniper.net/documentation/en US/junos14.
2/topics/topic-map/ospf-authentication.html.

[30] Z. A. Qazi et al., “Simple-fying middlebox policy
enforcement using sdn,” in SIGCOMM, 2013.
[31] S. K. Fayazbakhsh et al., “Enforcing network-wide
policies in the presence of dynamic middlebox
actions using flowtags,” in NSDI, 2014.
[32] “Cisco. Configuring Policy-Based Routing,”
http://www.cisco.com/c/en/us/td/docs/ios/12
2/qos/configuration/guide/fqos c/qcfpbr.html.
[33] “Juniper. Configuring Filter-Based Forwarding toa Specific Outgoing Interface or Destination IP
Address,” http://www.juniper.net/techpubs/en
US/junos12.2/topics/topic-map/
filter-based-forwarding-policy-based-routing.html.
[34] “Cisco. Implementing BGP Flowspec,”
http://www.cisco.com/c/en/us/td/docs/routers/
asr9000/software/asr9k r5-2/routing/configuration/guide/b routing cg52xasr9k/b
routing cg52xasr9k chapter 011.html.
[35] “Juniper. Enabling BGP to Carry
Flow-Specification Routes,”
https://www.juniper.net/documentation/en US/
junos12.3/topics/example/
routing-bgp-flow-specification-routes.html.
[36] B. Fortz and M. Thorup, “Internet trafficengineering by optimizing OSPF weights,” in
INFOCOM, 2000.
[37] B. Fortz, J. Rexford, and M. Thorup, “Trafficengineering with traditional IP routing protocols,”
IEEE Comm. Mag., vol. 40, no. 10, pp. 118–124,
2002.
[38] A. Atlas, J. Halpern, S. Hares, and D. Ward, “AnArchitecture for the Interface to the Routing
System,” Internet Draft, 2013.
[39] R. Soulé et al., “Merlin: A language forprovisioning network resources,” in CoNEXT,
2014.
[40] S. Vissicchio, L. Vanbever, and O. Bonaventure,“Opportunities and research challenges of hybrid
software defined networks,” ACM SIGCOMM
CCR, vol. 44, no. 2, pp. 70–75, 2014.
[41] D. Levin, M. Canini, S. Schmid, F. Schaffert, and
A. Feldmann, “Panopticon: Reaping the Benefitsof Incremental SDN Deployment in Enterprise
Networks,” in USENIX ATC, 2014.
[42] F. Baker, “IPv6 Source/Destination Routing using
OSPFv3,” Internet Draft, 2013.