Sweet Little Lies: Fake Topologies for Flexible Routing

Authors: Stefano Vissicchio, Laurent Vanbever, and Jennifer Rexford
Proceedings of the 13th ACM Workshop on Hot Topics in Networks 2014


ink-state routing protocols (e.g., OSPF and IS-IS) are widely used because they are scalable, robust, and based on simple abstractions. Unfortunately, these protocols are also relatively inflexible, since they direct all traffic over shortest paths. In contrast, Software Defined Networking (SDN) offers fine-grained control over routing, at the expense of controller overhead, failover latency, and deployment challenges.

We argue that future networks can achieve the benefits of both approaches through central control over the distributed route computation. The key idea, which we call Fibbing, is to have the controller trick the routers into seeing a fake topology that is carefully constructed to achieve the desired Forwarding Information Base (FIB). Given an acyclic forwarding graph for each destination, the controller computes an augmented topology with fake nodes (and destinations to announce there) and fake links (and link weights). The controller injects these “lies” into the link-state routing protocol, and the routers simply compute the paths accordingly. The controller can also select an augmented topology that triggers the use of specific backup paths when real links and routers fail. To reduce router load, our Fibbing algorithms compute augmented topologies of minimal size. Our preliminary evaluation on realistic ISP topologies shows that Fibbing works well in practice.



	title={Sweet little lies: Fake topologies for flexible routing},
	author={Vissicchio, Stefano and Vanbever, Laurent and Rexford, Jennifer},
	booktitle={Proceedings of the 13th ACM Workshop on Hot Topics in Networks},

DOI: 10.1145/2670518.2673868