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

Olivier Tilmans
UCLouvain

Routing Area Open Meeting
Nov. 15, 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

B
R112

3

2
R3

R2R4111C
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

1B
R1

1

2

3

2
R3R2R4

1
1

1

C

D1

D2

Trafﬁcdestination
4

IGPs cause operators to follow adescriptive management process.

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

1. Controlling distributed protocols
2. Fibbing today’s networks
3. Case study: On-demand load-balancing
4. Takeaways

Fibbing enables declarative management.

 Centralizes high level routing decisions.
Operators describe their requirements to a controller.

 Keeps the route installation distributed.
Each router independently computes its FIB.

 Leverages the IGP messages as API.
We study which message to send.

7

Operators specify paths that must be enforced.
requirements(A, R1, R2, C, blue)A

Fibbingcontroller

B
R1
R2

R3

R4
C
8

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

A1

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

B
R11232
R3R2R411

IGP
adjacency

1C12

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

1

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

B
R1

1232
R3

R2

R4

1
11C
15

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

1232
R3R2R41
11C18

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

fA2

A
1

1

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

B
R1

12

32
R3R2R4111C21

Augmented topologies translate intonew data-plane paths.
Control-Plane

Data-Plane

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

fA

2

A
1

1

1

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

B
R1123221

13R3R21R4112111C22

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

fA

2

A
1

1

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

B
R1

12

3

2
R3R2R4

111C
23

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
R3

R2

R4

111C23

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

fA2A
11B
fR1

2R11232R3R2R4111C23

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

11
B
fR1

2R1
3B
1

22

11C

fR1
R3

R2

R4

111R11232R3R2R41

111C24

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 overhead

25

Fibbing leverages the robustness of IGPs.

 Fast failure detection and recovery

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

26

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

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

1. Controlling distributed protocols
2. Fibbing today’s networks
3. Case study: On-demand load-balancing
4. Takeaways

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

29

The "forwarding address" has one other application.
It enables routers in the Autonomous System’s interior tofunction as "route servers".
RFC2328, §2.3—Use of external routing information

If the forwarding address is non-zero, [. . . ]install the AS external path to N, with next hop equal to
the list of next hops to the forwarding address
RFC2328, §16.4—Calculating AS external routes

Fake nodes can be injected using LSA types
5/7.

RFC2328, §A.4.5—AS-external-LSAs
32

Using T5/7 LSAs comes at a price.

 Different expressivity model Can only affect preﬁxes from other T5/T7 LSAs

 Does not exist in IS-IS!

33

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

34

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

1. Controlling distributed protocols
2. Fibbing today’s networks
3. Case study: On-demand load-balancing
4. Takeaways

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

1B
R1

1

2

3

2
R3R2R41
11C36

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

Control-Plane

30 S2A

Link load1130ServerB
R1

12

330 S160

2R3R260

R4

11C

1

Overloadedlink
D1

D2Client36

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

123fB
2R3R2R4

111C37

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

123fB
2R3R2R4

111C37

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

Data-Plane
30 S2A
112B
R1

12

330
fB

30 S130 30

2R3R230

R4

1
130

1C

D1

D237

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

Data-Plane
30 S2A
112B
fR12R112315 15fB
215R3R2R4

1
130 S122.522.5

11522.5 22.5

CD1D237

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

3A
1

12B
fR1

2R1

123fB
2R3

R2R4

11C

1

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

3A
1

12B
fR1

2

R1

123fB
2R3R2R4

1
11C38

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

3Data-Plane
30 S2A112BfR1

2R112

320 101120 20

220R3R2R430 S1fB1202020C

D1D238

The Fibbing controller reacts and adds morepaths to spread the load, in real time.
S2BS1

R2R3R1

R41 ﬂow

31 ﬂows 61 ﬂows

Throughput

A0C
D1

014

D235Time [s] We initially have 1 ﬂow from S1 to D1.
 At time t = 14s, we start 30 new ﬂows from S1 to D1.
 At time t = 35s, we start 30 ﬂows from S2 to D2.
39

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

1. Controlling distributed protocols
2. Fibbing today’s networks
3. Case study: On-demand load-balancing
4. Takeaways

Modifying the shared topology is powerful.

 Enables optimal, real-time, TE in the control plane Does not impact data-plane Gives some control over BGP/MPLS-LDP Simpliﬁes conﬁgurations through exception-based routing

41

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