Central Control over Distributed Routing
fibbing.net

Stefano Vissicchio
UCLouvain

SIGCOMM
18th August 2015

Joint work with
O. Tilmans (UCLouvain), L. Vanbever (ETH Zurich) and J. Rexford (Princeton)

SDN is based on antithetical architecturewith respect to traditional networking

Traditional(e.g., IGP, distributed MPLS)

SDN(e.g., OpenFlow, Segment Routing)

Centralization improves network management,
but sacrifices robustness of distributed protocols
Traditional

SDN

IGP, tunnelling(RSVP-TE)

Manageability

lowhigh

Flexibility

lowhighest

Scalability

by design

ad hocRobustnesshighlowWe propose Fibbing, a hybrid SDN architecture

Fibbing
central control over link-state IGPs

Fibbing combines advantagesof SDN and traditional networking

Traditional

Fibbing

SDN

IGP, tunnelling(RSVP-TE)

Manageability

low

high

high

Flexibility

low

high

highestScalability

by design

by design

ad hocRobustness

highhighlow

Fibbing combines advantagesof SDN and traditional networking

Fibbingsame as SDN
Manageability

highFlexibility

highScalability

by design

Robustness

highper-destination
full control
some function
are distributed
thanks to partialdistribution

Central Control over Distributed Routing
fibbing.net

1

Manageability

2

Flexibility

3

Scalability

4Robustness

Central Control over Distributed Routing
fibbing.net

1Manageability

2

Flexibility

3Scalability

4Robustness

SDN achieves high manageability
by centralizing both computation and installation

requirements
computes pathse.g., OpenFlow
controller or RCP

derives FIB entries
install FIB entries

Fibbing is as manageable as SDN,
but centralizes only high-level decisions

requirements

Fibbing
controller

computes paths

Fibbing keeps installation distributed,
relying on distributed protocols

distributed
control-plane

data-planecomputes FIB entries
install FIB entries

Distributed installation is controlled
by injecting carefully-computed information

control-plane
messagesWe study which messages to inject
for controlling intra-domain routing protocols

link-state IGP
input

function

outputweighted

shortest-path

forwarding

topology

computation

paths

The output of the controlled protocol
is specified by operators’ requirements

provided by operators
or controller optimizers(e.g., DEFO)
link-state IGP
input

function

outputweighted

shortest-path

forwarding

topology

computationpaths

To control IGP output, the Fibbing controllerinverts the shortest-path function

Inverseweighted

shortest-path

forwardingtopology

computationpaths

Central Control over Distributed Routing
fibbing.net

1

Manageability

2

Flexibility

3Scalability

4Robustness

Consider this simple network(implemented with Cisco routers)

A

B

X
D1

C
sourceD2
destination

An IGP control-plane computes
shortest paths on a shared weighted topology

control-plane

A

1

B
1

10C

3

X

D1
D2

shortest paths

IGP shortest paths are translated into
forwarding paths on the data-plane

control-plane

data-plane

AA

1

B

B
1

10X
C

3

X

D1
D2

D1C

D2

traffic flow

In Fibbing, operators can ask
the controller to modify forwarding paths

requirement(C,A,B,X,D2)

A

1

B
1

10C

3X

D1
D2

The Fibbing controller injects information on
fake nodes and links to the IGP control-planerequirement(C,A,B,X,D2)

A

1

node V1,link (V1,C),
map (V1,C) to (C,A)

B
1

10C

3

X

D1
D2

Informations are flooded
to all IGP routers in the network

requirement(C,A,B,X,D2)

A

1

node V1,link (V1,C),
map (V1,C) to (C,A)

B
1

10C

3X

D1
D2Fibbing messages augment
the topology seen by all IGP routersrequirement(C,A,B,X,D2)
D2

A1110V1
1

node V1,link (V1,C),
map (V1,C) to (C,A)

B

C

3X

D1
D2

Augmented topologies translate
into new control-plane paths

requirement(C,A,B,X,D2)
D2

A

1110

V1
1

node V1,link (V1,C),
map (V1,C) to (C,A)

B

C

3X

D1
D2

Augmented topologies translate
into new data-plane paths

requirement(C,A,B,X,D2)
A
D2

A

11B
110V1

B

node V1,link (V1,C),
map (V1,C) to (C,A)

XC3X

D1
D2

D1C

D2

Fibbing can program
arbitrary per-destination paths

Theorem

Any set of forwarding DAGs can be enforced by Fibbing

Fibbing can program
arbitrary per-destination paths

Theorem

Any set of forwarding DAGs can be enforced by Fibbing

paths to the same destination do not create loops

By achieving full per-destination control,
Fibbing is highly flexible

Theorem

Any set of forwarding DAGs can be enforced by Fibbing

fine-grained traffic steering (middleboxing)
per-destination load balancing (traffic engineering)
backup paths provisioning (failure recovery)

Central Control over Distributed Routing
fibbing.net

1

Manageability

2

Flexibility

3

Scalability

4Robustness

We implemented a Fibbing controller

Compilation

Augmentation

Optimization

Injection/
Monitoring

+

path
reqs.

network
topology

per-destination
forwarding DAGs

augmented
topology

reducedtopology

running
networkWe also propose algorithms
to compute augmented topologies of limited size

Compilation

Augmentation

Optimization

Injection/
Monitoring

+

path
reqs.

network
topology

per-destination
forwarding DAGs

compilation
heuristics

augmented
topology

per-destinationaugmentation

reducedtopology

cross-destination
optimization

running
network

For our Fibbing controller, we propose
algorithms to be run in sequence

Compilation

Augmentation

Optimization

Injection/
Monitoring

+

path
reqs.

network
topology

per-destination
forwarding DAGs

compilation
heuristics

augmented
topology

reducedtopology

per-destination cross-destination
optimization
augmentation1.
simple2.
mergerrunning
network

Consider the following example,
with a drastic forwarding path change

A

1

B

1C

1A

1

E

10B

1100
D1F

C

100

1D

1E

10original shortest-pathdesired shortest-path“down and to the right”“up and to the right”

FSimple adds one fake node for everyrouter that has to change next-hop

1A

1B

11C

11100

D
11E
110F

Merger iteratively merges fake nodes(starting from Simple’s output)

1
A

1

B

1

1C

1

1100

D
11E
110F

Merger iteratively merges fake nodes(starting from Simple’s output)

1
A

1

B

11C

1

1100

D
1

1

E

10F

This way, Merger programs multiple
next-hop changes with a single fake node

A

1B

1C

1

1100

D1E10F

This way, Merger programs multiple
next-hop changes with a single fake nodeA1

B1C1

1100

D1E

10

F

Previous SDN solutions (e.g., RCP) cannot do the same

Simple and Merger achieve different trade-offs
in terms of time and optimization efficiency

We ran experiments on Rocketfuel topologies,
with at least 25% of nodes changing next-hops

Simple runs in milliseconds
Merger takes 0.1 seconds

Merger reduces fake nodes by up to 50%
and up to 90% with cross-destination optimization

We implemented the machinery tolisten to OSPF and augment the topology

Compilation

Augmentation

Optimization

Injection/
Monitoring+path
reqs.

network
topology

per-destination
forwarding DAGs

augmented
topology

reducedtopology

running
network

OSPF interaction
moduleExperiments on real routers show thatFibbing has very limited impact on routers# fakenodes

routermemory (MB)

1 000

0.7

5 000

6.8

10 00014.5

50 00076.0

100 000

153>> # real routers

DRAM is cheap

Experiments on real routers show thatFibbing has very limited impact on routers# fakenodesroutermemory (MB)

1 000

0.7

5 000

6.810 000

14.5

50 00076.0

100 000

153

DRAM is cheap

CPU utilization always under 4%

Experiments on real routers show thatFibbing does not impact IGP convergence

Upon link failure, we registered no difference in the(sub-second) IGP convergence withno fake nodes
up to 100,000 fake nodes and destinations

Experiments on real routers show thatFibbing achieves fast forwarding changes# fakenodes

installation
time (seconds)

1 000

0.9

5 000

4.5

10 0008.9

50 00044.7

100 000

89.50

894.50 μs/entry

Central Control over Distributed Routing
fibbing.net1Manageability

2

Flexibility

3

Scalability

4Robustness

Fibbing improves robustness
by relying on the underlying IGP

no controller action needed in some cases
IGPs re-converge quickly [Filsfils07]

IGP provides fast failure detection and control-plane sync
thanks to its shared topology

Fibbing supports fail-open and fail-close semantics
see paperWe ran a failure recovery case study,
with distributed Fibbing controller( fail-close(D1) );( fail-open(D2) );

D2

ABCX

V1
D1
D2

Fibbing survives replica failureswith no impact on forwarding( fail-close(D1) );( fail-open(D2) );replica
fails

D2AB

V1CX

D1
D2

Throughput (Mbps)

1.2

(A,B)
fails

(B,X)
fails

1.8.6
.4.2

flow 1flow 200

51015202530

Time (s)Fibbing reacts to network failures
quickly re-optimizing forwarding( fail-close(D1) );( fail-open(D2) );replica
fails

ACBX

D1
D2

Throughput (Mbps)

1.2

(A,B)
fails

(B,X)
fails

1.8.6.4.2

flow 1flow 200

5

1015

20

2530

Time (s)Fibbing reacts to partitions,
respecting fail-close and fail-open semantics( fail-close(D1) );( fail-open(D2) );replica
fails

ACBX

D1
D2Throughput (Mbps)

1.2

(A,B)
fails

(B,X)
fails

(B,X
up

1.8
.6
.4
.2

flow 1flow 2

00

5

10

15

20

25

30

Time (s)3

Fibbing recovers correctly(as soon as failures are fixed)( fail-close(D1) );( fail-open(D2) );

D2

A

V1
C

Throughput (Mbps)

1.2

(A,B)
fails

(B,X)
fails

B

1.8.6
.4

X.2

D1
flow 1flow 2
D200510(B,X)
(A,B)
fails
up

(B,Xup030

5 103540 1545 2050 25
55 30

3Time (s)Time (s)1.2
Throughput (Mbps)

replicafails

replica(B,X) (A,B)
fails
up fails

1
.8
.6
.4
.2

flow 1flow 2015

2025

Fibbing shows the benefits ofcentral control over distributed protocols

Realizes SDN management model
network-wide automated control

Simplify controllers and improves robustness
heavy work is still done by routers

Works today, on existing networks
avoids SDN deployment hurdles

Central Control over Distributed Routing
fibbing.net

Tell me lies, tell me sweet little lies
— Fleetwood Mac

Stefano Vissicchio
stefano.vissicchio@uclouvain.be