Fibbing: Central Control over Distributed Routing
www.ﬁbbing.net

Olivier Tilmans
UCLouvain

IRTF Open Meeting
Nov. 14, 2016

Joint work withS. Vissicchio (UCL), L. Vanbever (ETH Zürich) and J. Rexford (Princeton)

Fibbing

Fibbing
Control routers’ FIB, lying to routers

Consider this example network.
RouterLink

3

Consider this example network.
Router

A
Link
B

R1
R2

R3

R4C

3

Link-state Interior Gateway Protocols (IGPs)
exchange reachability information toinfer the topology of the network.
A
1

1

Link weight

BR1

123

2R3R2R4111C
Destination Preﬁx

4

The intra-domain trafﬁc ﬂows along theshortest path on the shared topology.
Control-Plane

Data-PlaneA

Trafﬁc ﬂow

1

1
B
R1

12

3

2
R3R2

R4

1
1

1

C

D1

D2

Trafﬁcdestination
4

IGPs cause operator to follow adescriptive management process.

Operator
 Express requirements

IGPs cause operator to follow adescriptive management process.
Protocolconﬁguration
operationOperator
 Express requirements
 Computes paths
 Figures out how toimplement them

IGPs cause operator to follow adescriptive management process.
Protocolconﬁguration
operation

Operator
 Express requirements
 Computes paths
 Figures out how to
implement themDistributed
Control-Plane Derives FIB entries
 install FIB entries
5Software-Deﬁned Networking (SDN) enables
declarative management.

Centralized
control plane

6Software-Deﬁned Networking (SDN) enables
declarative management.

Operator
 Express requirements

6

Software-Deﬁned Networking (SDN) enables
declarative management.
SDN Controller Compute paths
 Derives FIB entries
 install FIB entries

Operator

Well-deﬁned API

 Express requirements

6

SDN sacriﬁces the robustness and scalabilityof distributed protocols.

Traditional

SDN

Manageability

low

highFlexibility

lowhighest

Scalability

by design

ad hocRobustness

highlow7

The networking world has two paradigm,
based on opposed principles.

Traditional

SDN

Manageability

low

high

Flexibility

lowhighestScalability

by design

ad hocRobustness

highlow7

We propose a middleground approach,named Fibbing.

Traditional

Fibbing

SDN

Manageability

low

high

high

Flexibility

lowhighhighest

Scalability

by design

by design

ad hocRobustness

highhighlow7

Fibbing: Central Control over Distributed Routing
www.ﬁbbing.net

1. Controlling distributed protocols
2. Case study: surviving ﬂash crowds
3. Fibbing today’s networks
4. Food for thoughts

Fibbing uses an hybrid control plane.

Centralizedcontrol plane

Distributed
control plane

Fibbing centralizes high level routing decisions.
Fibbing Controller Compute paths

Operator
 Express requirements

Fibbing keeps the route installation distributed.
Fibbing Controller Compute paths

Operator
 Express requirements

Distributed
Control-Plane Derives FIB entries
 install FIB entries

We study which IGP messages to inject.
Fibbing Controller Compute pathsIGP messages

Operator Express requirements

Distributed
Control-Plane Derives FIB entries
 install FIB entries
9Operators specify paths that must be enforced.
requirements(A, R1, R2, C, blue)

A

B
R1
R2

R3R4C
10

The controller injects one IGP message adding
a fake node and links.
requirements(A, R1, R2, C, blue)A1

1

node fA (blue),
link (fA, A, 2),
map (fA, A) to (A, R1)

B
R1

1

2

32
R3R2R41
11C
14

IGP ﬂooding propagates the information.
requirements(A, R1, R2, C, blue)

A1

1node fA (blue),link (fA, A, 2),
map (fA, A) to (A, R1)

B
R1

1232R3R2R41
11C17

The Fibbing message augments the topology.
requirements(A, R1, R2, C, blue)

fA

2

A
1

1

node fA (blue),
link (fA, A, 2),
map (fA, A) to (A, R1)

B
R1

1

2

3

2
R3R2

R41
11

C20

Augmented topologies translate into newcontrol-plane paths.
requirements(A, R1, R2, C, blue)

fA

2

A
1

1

node fA (blue),
link (fA, A, 2),
map (fA, A) to (A, R1)

B
R11232
R3R2R4111C23

Augmented topologies translate into
new data-plane paths.
Control-Plane

Data-Plane

requirements(A, R1, R2, C, blue)

fA

2A
1

1

1

node fA (blue),
link (fA, A, 2),imap (fA, A) to (A, R1)

B
R1

12

32

21

13
R3R2

1R4

1
121

11C

24

Chaining multiple fake nodes enables toprogram complex paths.
requirements(A, R1, R4, C,blue)

fA

2A
1

1

node fA (blue),link (fA, A, 2),
map (fA, A) to (A, R1)

B
R1

12

32
R3R2R4

111C25

Chaining multiple fake nodes enables toprogram complex paths.
requirements(A, R1, R4, C,blue)

fA

2

A
1

1

node fR1 (blue),
link (fR1, R1, 2),
map (fR1, r1) to (R1, R4)

B
fR1

2

R1

12

3

2
R3R2

R4

11

1C
25

Chaining multiple fake nodes enables toprogram complex paths.
requirements(A, R1, R4, C,blue)

fA

2

A
1

1B
fR1

2

R1

1232R3R2R4

111C25

Augmented topologies can be reduced tooptimize the number of fake nodes.
Naive augmentation

Reduced augmentation

requirements(A, R1, R4, C,blue)

requirements(A, R1, R4, C,blue)

AA

fA

2

1

1
B
fR1

2

R1
3

B
1

2

2

1
1

C

fR1
R3

R2

R4

1

1

1

R1

123

2
R3

R2

R4

1

1
11C

26

Fibbing preserves the scalability of IGPs.

 We can compute augmented topologies in O(ms)Ensures quick reaction to changes

 We can reduce augmented topologies in O(s)Ensures limited control-plane overhead27

Fibbing leverages the robustness of IGPs.

 Fast failure detection and recovery

 Survive controller failure Support fail-close and fail-open semantics

28

Fibbing can enforce any set of loop-free paths, on a perdestination basis.

Fibbing: Central Control over Distributed Routing
www.ﬁbbing.net

1. Controlling distributed protocols
2. Case study: surviving ﬂash crowds
3. Fibbing today’s networks
4. Food for thoughts

Flash crowds cause service disruption.

 Video delivery services require good network performance31Flash crowds cause service disruption.

 Video delivery services require good network performance Protecting the services against ﬂash crowds ischallenging:
1. Traditional trafﬁc engineering techniques perform poorly;
2. Over-provisioning is expensive.

31

Fibbing reduces the need for over-provisioning
by enabling real-time trafﬁc engineering.

Experiment setup Network with 2 video streaming servers

 Multiple clients are competing for bandwidth The network controller is able to detect ﬂash crowds

32

The initial IGP conﬁguration has a bottlenecktowards router C.
Control-Plane

Data-PlaneA

Link load1

13030 S1

B
R1

12330 S2
Videoserver60

2R3R260

R4

11C

1Overloadedlink
D1

D2Videoclient33

Fibbing can program on-demand ECMP tospread the load
Control-Plane

Data-Plane
30 S2A
1

12B
R1

12

330
fB

30 S130 30

2
R3

R230

R4

1
130

1C

D1

D2

Fibbing can program on-demand ECMP to
spread the load
Control-Plane

Data-Plane
30 S2A
1

12B
fR1

2R1

1

2

315 15fB
215R3R2R4

1
130 S122.522.5

11522.5 22.5

C

D1D234

Fibbing controls the splitting ratios acrossequal-cost paths.
Control-Plane
fA

3Data-Plane
30 S2A
1

12BfR12R1

12

320 101
120 20220R3R2R430 S1fB

120

2020C

D1

D235

As the demand increases, the Fibbing
controller adds more paths to spread the load.
S2

B

S1

R2

R3

R1

R4

1 stream 31 streams 61 streams

Throughput

A

A–R1
B–R2
B–R30C
D10D2

1435
Time [s] We initially have 1 video stream from S1 to D1.
 At time t = 14s, we start 30 new streams from S1 to D1.
 At time t = 35s, we start 30 streams from S2 to D2.
36

Fibbing: Central Control over Distributed Routing
www.ﬁbbing.net

1. Controlling distributed protocols
2. Case study: surviving ﬂash crowds
3. Fibbing today’s networks
4. Food for thoughtsWe have a working Fibbing controller prototype

 The controller maintains an OSPF adjacency to one router Topology discovery using the adjacency

 Tested against IOS, NX-OS, JunOS

38

Fake nodes can be injected using LSA types 5/7

 Leverages the forwarding address ﬁeld
Advertize reachability towards preﬁx, with cost, using
speciﬁed IP next hop The controller multiplexes multiple virtual routers
N successive fake nodes towards the same preﬁx require
N different router-ids

39

Using T5/7 LSAs has (almost) no overhead onrouters and is fast.

 No measurable impact on SPF duration

 10 000 LSAs eat 14.5 MB of DRAM

 900µs to push one ﬁbbed route to the FIB

40

Using T5/7 LSAs comes at a price Different expressivity model Can only affect preﬁxes from other T5/T7 LSAs

 Does not work with IS-IS!

41

Fibbing: Central Control over Distributed Routing
www.ﬁbbing.net

1. Controlling distributed protocols
2. Case study: surviving ﬂash crowds
3. Fibbing today’s networks
4. Food for thoughts

Centrally modifying the shared topology ispowerful

 Gives some control over BGP/MPLS-LDP Simplify conﬁgurations through exception-based routing

 Enables optimal, real-time TE43

What would be the right abstraction?

Fibbing: Central Control over Distributed Routing
www.ﬁbbing.net

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

Olivier Tilmans
olivier.tilmans@uclouvain.be