Sweet Little Lies:
Fake Topologies for Flexible Routing

Stefano Vissicchio
University of Louvain

HotNets
27th October 2014

Joint work withLaurent Vanbever (Princeton) and Jennifer Rexford (Princeton)

Fibbing

Fibbing
control routers’ FIB, lying to routers???
Fibbing
control routers’ FIB, lying to routers

We use lies to overcome inflexibilitiesof traditional networks

traditional networks

We use lies to work around challengesof OpenFlow-like networks

OpenFlow networks

We use lies to combine the advantages ofOpenFlow and of traditional networking

FibbingOperators need flexibility for intra-domain routing

fine-grained traffic engineering
optimize the available resources
provision backup paths
quickly and predictably react to failures
deploy advanced services
e.g., steer traffic through middleboxes

Consider this network wherea source sends traffic to 2 destinations

ABCD

sourcedestination
traffic flowAs congestion appears on the (C,D) link,
operators may want to divert the blue flow to A
initialdesiredABABCDCDMoving only the orange flow to A is impossible
with an IGP as both destinations are connected to DA

initialdesired1??

10B1C

3DA??

B??

C??

Dimpossible byreweighing the IGP links

Currently, operators have two ways
to improve flexibility

virtual circuit based solutions (MPLS)

SDN based solutions (OpenFlow)Both solutions comes at a significant costvirtual circuit based solutions (MPLS)
control- and data-plane overhead
SDN based solutions (OpenFlow)
deployment costs, new challenges of a novel paradigm

Fibbing achieves flexible routing
in an existing network, “à la SDN”

Fibbing achieves flexible routing
in an existing network, “à la SDN”

unmodified routers(checked in testbed!)

Fibbing achieves flexible routing
in an existing network, “à la SDN”

what does it mean?

The Fibbing controller program routers!
(bypassing proprietary configuration languages)

Controller

central control of forwarding paths

Control-Plane

Control-Plane

Control-Plane

Data-Plane

Data-Plane

Data-Plane

Cisco

Juniper

Alcateldistributed
forwarding
pathcomputation

The controller uses an API that all routers understand(hint: not OpenFlow)

Controller?

?

?

Control-Plane

Control-Plane

Control-Plane

Data-Plane

Data-Plane

Data-Plane

CiscoJuniper

AlcatelLink-state IGPs are actually good for something,
to control router behavior

messages are standardized
all routers must speak the same language
behaviors are well-defined and understoode.g., shortest-path routing
implementations are robust and widely-deployednearly all networks out there run OSPF or IS-IShow?

Fibbing achieves flexible routing
in an existing network, “à la SDN”

the controller tricks IGP routers with small lies
about fake nodes, links and destinations

Fibbing achieves flexible routing
in an existing network, “à la SDN”

As congestion appears on the (C,D) link,operators may want to divert the blue flow to AinitialA

1

10desiredBA

BC

D

1
C

3

D

Fibbing can move the orange flow by adding
a fake node announcing the blue destination

Afake node

V1

1

10B

1

1

C

3

D

Fibbing can move the orange flow by adding
a fake node announcing the blue destination

AV1

new control-plane
path for C

1

10

B

1

1

C

3

D

Fibbing can move the orange flow by adding
a fake node announcing the blue destination

new data-planenext-hop of CA1

V1

B

1
1

C

3

D

Fibbing works today!
(tested with off-the-shelf Cisco routers)

A

1

V1

B

1
1

C

3

D

Is Fibbing expressive?
Does Fibbing scale?

Is Fibbing expressive?
Does Fibbing scale?

Yes!

Fibbing is expressive

Theorem

Any set of forwarding DAGs can be enforced by Fibbing

Fibbing is expressive

Theorem

Any set of forwarding DAGs can be enforced by Fibbing

paths to the same destination do not create loops

Fibbing enables high flexibility

Theorem

Any set of forwarding DAGs can be enforced by Fibbing

fine-grained traffic steering to middleboxes
per-destination load balancing for traffic engineering
backup paths provisioningIs Fibbing expressive?
Does Fibbing scale?

Yes!

Fibbing can scale and quickly react to failurescomputing augmented topologies of limited size
we have an ILP to strategically place fake nodes
pre-computing response to failures
to quickly repair augmented topologies
applying quickly failure responses
relying on the effectiveness of IGP for failure reaction

Given a physical topology and a set of path requirements,
a linear program computes an optimized virtual topology

physicalforwarding DAGs

topology+IntegeraugmentedLinear Program

topology

Optimizer

minimize topology size

Few lies can realize multiple shortest-path deviations

2

5

1020

nodes
edges

1

# of fake topology components

50(preliminary evaluation on Rocketfuel)

5

10

15

20

# IGP shortest path violations25

Fibbing enables flexible routing à la SDN, today!

Reduce controller concerns
most of the heavy work is still done by the routers
Maintains operators’ mental model
good old protocols running, easier troubleshooting
Facilitates SDN deployment
unified interface to routers and SDN switchesSweet Little Lies:
Fake Topologies for Flexible Routing

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

Stefano Vissicchio
stefano.vissicchio@uclouvain.be