SDN with Link-State Routing Protocols

Olivier Tilmans
UCLouvain

PIRL
8th March 2016

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

IPv6 comes with a unique opportunity

IPv6 transition
new network
current network

IPv6 comes with a unique opportunity
to improve configuration automation

IPv6 transition
new network
current network

IPv6 comes with a unique opportunity
to simplify the protocol stack

IPv6 transition
new network
current network

RSVP
IGP

BGP
MPLS

IPv6 comes with a unique opportunity
to change network designs

The state of the art includes two networking models
based on opposite principles

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

SDN(e.g., OpenFlow, Segment Routing)SDN simplifies control-plane and management,
but sacrifices robustness of distributed protocols
Traditional

SDN

IGP, tunnelling(RSVP-TE)

Manageability

low

high

Flexibility

lowhighest

Scalability

by design

ad hocRobustness

highlow

SDN simplifies control-plane and management,
but sacrifices robustness of distributed protocols
Traditional

SDN

IGP, tunnelling(RSVP-TE)

Manageability

lowhigh

Flexibility

lowhighest

Scalability

by design

ad hocRobustness

highlowWe propose Fibbing, a network architecture which
combines advantages of SDN and traditional networking
Fibbing
central control over a single link-state IGPSDN with Link-State Routing Protocols

1Manageability

2

Flexibility

3

Scalability & Robustness

SDN with Link-State Routing Protocols

1Manageability
achieving central control2

Flexibility

3

Scalability & Robustness

Consider this simple network(implemented with Cisco routers)

AB

X

Csource

destination
12

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

control-planeA

1

B
1

10C

3Xshortest paths

13

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

control-plane

data-plane

A
A

1B

B
1

10X
C

3

X

Ctraffic flow
14

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

requirement(C,A,B,X)

A

1

B
1

10

C

3X

15

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

A

1

B
1

10C

3

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

X

16

Informations are floodedto all IGP routers in the network

requirement(C,A,B,X)

A

1B
110C

3

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

X

17

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

A

1

1

10

V1
1B

C

3

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

X

18

Augmented topologies translate
into new control-plane paths

requirement(C,A,B,X)

A

1

1

10

V1
1B

C

3

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

X

19

Augmented topologies translate
into new data-plane paths

requirement(C,A,B,X)
AA11B
1

10V1C

3

B

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

XXC

20

SDN with Link-State Routing Protocols

1Manageability

2Flexibility

3

Scalability & Robustness

Fibbing can enforce
any set of forwarding DAGs

22

Fibbing can enforce
any set of forwarding DAGs
paths for the same destination not creating loops

23

SDN with Link-State Routing Protocols

1Manageability

2

Flexibility
fine-grained control

3

Scalability & Robustness24

In the following network,
the blue destination is subject to a DoS attack

B551A

105CX1510Dscrubber
25

Fibbing can steer away
traffic on a per-destination basis
requirement(C,D,X) and(B,C,D,X)

B
551

A

105CX

1510
D
1fA
26

SDN with Link-State Routing Protocols

1Manageability

2

Flexibility
per-destination load-balancing

3

Scalability & Robustness

27

Leveraging multiple paths is hardwhen links/flows have different capacities/demands
Higher traffic
demandB
10A

10Higher link
bandwidth
5C

10

5X

10DLower link
bandwidth28

Fibbing has fine-grained control over ECMP routingAdding new equal-cost path

B
10A

105C

5requirement(A,C,X) and(A,B,X) and(A,D,X)

X

151010fA
D

29

Fibbing has fine-grained control over ECMP routing
Introducing uneven load-balancing

BfA

105requirements
splittingRatios{(A,B): 2(A,C): 1}

15A

10C

105X

10D

30

SDN with Link-State Routing Protocols

1Manageability

2

Flexibility
backup paths provisioning

3

Scalability & Robustness31

Link failures may inducecongestion or increased delays

B5A

105C

10X

2020
D32

Fibbing can provision backup paths

B5A

10requirement(A,D,X) asBackupOf (A,B,X)
5C10X

152020fA
D

33

SDN with Link-State Routing Protocols

1Manageability

2Flexibility

3Scalability & Robustness
IGP on steroids

We implemented a Fibbing controller

Supports all presented use-cases
Source-code on Github

Works with vanilla OSPF and off-the-shelf routers
IS-IS requires a protocol extension

Induces very little overhead on the routers
No impact on SPF computation

35

By building upon the underlying IGP,
Fibbing is robust and reactive to failures

Fibbing easily deals with network failures
1. IGP is sufficient for some failures [Filsfils07]
2. IGP provides a default for partitions

Fibbing naturally supports replicated controllers
1. IGP provides sync primitives
2. replica failures have no impact on forwarding

36

Fibbing shows the benefits ofcentral control over distributed protocols

Realizes SDN management model
network-wide automated control

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

Simplifies network designIGPs are in charge of all intra-domain paths

37

SDN with Link-State Routing Protocols
fibbing.net

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

Olivier Tilmans
olivier.tilmans@uclouvain.beSDN with Link-State Routing Protocols

Backup slides

MPLS+RSVP-TE/SR
can solve all the presented use-cases

Need to provision one tunnel per ingress point
Hard to add/remove equal-paths for elephant flows
Fibbing also controls path cost seen by other protocols
40

Fibbing manipulates IGP topology, sodoes MTR, what’s the difference?
MTR is CLI-driven (configuration changes to do on
every router vs flooding)Cannot do uneven load-balancing

41

Why shouldn’t I use
Policy-Based Routing?
PBR is CLI-driven (configuration changes to do on
every router vs flooding)
PBR decisions are local to a single routerCPU fallback
42

How am I supposed to troubleshoot anetwork with fake elements?
The controller is the primary source of information
Fake elements can be quickly identified in LSDBs

43

Openflow solves everything

The controller has to setup flow entries on every switch
Switches rely on the controller to handle failures
IGPs are getting extensions to support Flowspec, …

44

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

1 000

0.7

5 000

6.8

10 00014.5

50 00076.0

100 000

153>> # real routers

CPU utilization always under 4%
45

The controller can choose between a (very) fastalgorithm or one that minimize the augmented topology
Rocketfuel topology of AS1239 (300+ routers)46

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

link-state IGP
input

function

outputweighted

shortest-path

forwarding

topology

computationpaths

47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

computation

paths

48

To control IGP output, the Fibbing controller
inverts the shortest-path function

Inverseweighted

shortest-path

forwarding

topology

computation

paths

49

SDN achieves high manageability
by relying on a centralized controller

high-level
requirements

network
controller

computes paths
derives FIB entries
install FIB entries

configuration

50

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

requirements

Fibbing
controller

computes paths

51

Fibbing keeps installation distributed,
relying on distributed protocols

distributed
control-plane

data-planecomputes FIB entries
install FIB entries

52

Distributed installation is controlled
by injecting carefully-computed information

control-plane
messages

53

Fibbing combines advantagesof SDN and traditional networking

Traditional

Fibbing

SDN

IGP, tunnelling(RSVP-TE)

Manageability

lowhighhigh

Flexibility

lowhighhighest

Scalability

by design

by design

ad hocRobustness

highhighlowFibbing combines advantagesof SDN and traditional networking

Fibbing

centralized
controller
Manageability

highFlexibility

highScalability

by design

Robustness

highper-destination
full control
some functions
are distributed

Our prototype includes algorithms
to compute augmented topologies of limited size

Compilation

Augmentation

Optimization

Injection/
Monitoring+

path
reqs.

network
topology

per-destination
forwarding DAGs

augmentedtopology

reducedtopology

running
network

56

The controller listens through an OSPF adjacency
to keep an up-to-date view of the topology

Compilation

Augmentation

Optimization

Injection/
Monitoring+

path
reqs.

network
topology

per-destination
forwarding DAGs

augmented
topology

reducedtopology

running
network

57