Saturday, November 23, 2013

Hotnets '13: Plinko: Building Provably Resilient Forwarding Tables

Authors: Brent Stephens, Alan L. Cox, Scott Rixner (Rice University)

The Internet is designed to be robust with redundant paths between nodes so that data can be delivered in spite of failures. However, most networks today drop data, at least for some time, when a link fails. This paper introduces a new forwarding model, Plinko, which can tolerate up to t failures with no packet drops.

Plinko's algorithm initially chooses a set of default routes for all source/destination pairs. Once these routes are chosen, the algorithm iteratively increases resilience by installing new alternate routes to protect the paths built in the previous round. The main challenge with this approach is that the backup routes can end up forming loops. Plinko solves this problem by performing matching on the reverse path of a packet, which is accumulated in the packet's header.

In order to reduce the amount of state that needs to be stored, Plinko also utilizes compression, by grouping together rules with the same output path. A good feature of Plinko's compression is that the compression ratios achieved are much higher for larger numbers of nodes and increased resiliency requirements, where the state would also be correspondingly higher. This makes Plinko pretty scalable; it can be utilized to build a 4-resilient network for topologies with up to about ten thousand hosts.

Q) In the presence of failures, we may want to prioritize some paths over others. How will this affect you?
A) Perhaps we can use a reservation or bandwidth aware version of Plinko. Typically, in datacenters, you only need best-effort.