Systems Seminar: Nick Feamster, Georgia Tech

Improving Internet Reliability with Path Splicing

Abstract

This talk presents the design, evaluation, applications, and current deployment status of path splicing, a new primitive that improves the reliability of networked communication by providing network nodes access to a large number of paths to each destination. The main idea of path splicing is to construct end-to-end network paths by computing multiple distinct routing trees ("slices") over a single network topology and then composing end-to-end paths using segments from each of these trees. Path splicing has three salient aspects. First, it populates each node's forwarding table with multiple different trees to the destination. Multiple trees can be generated by running multiple routing protocol instances or by installing alternate paths into the forwarding tables of each router. Second, it allows traffic to switch trees at any hop en route to its destination. This mechanism provides end systems access to a much larger number of alternate paths, since each end system can use any combination of path segments from these trees to form an end-to-end path. Third, it gives end systems some control over the paths they see without necessarily interfering with the goals of network operators: By changing a small number of additional bits in the packet header, end systems can change the path along which traffic is forwarded without explicitly controlling the path itself.

We evaluate the ability of path splicing to recover from failures for both intradomain and interdomain routing. In both cases, path splicing achieves near-optimal reliability for only a small increase in latency and storage overhead; path splicing does not create persistent loops, and it does not introduce adverse effects on traffic. Our evaluation shows that end systems can quickly discover working paths to one another as long as the underlying network remains connected. For the case of interdomain routing, we also show that path splicing provides significant benefits even when only a small fraction of ASes deploy it. Finally, we describe our prototype implementation of path splicing and our plans for deployment and further evaluation. We also explore how path splicing might be applied to other routing protocols and for other applications.

Speaker Bio

Nick Feamster is an assistant professor in the College of Computing at Georgia Tech. He received his Ph.D. in Computer science from MIT in 2005, and his S.B. and M.Eng. degrees in Electrical Engineering and Computer Science from MIT in 2000 and 2001, respectively. His research focuses on many aspects of computer networking and networked systems, including the design, measurement, and analysis of network routing protocols, network operations and security, and anonymous communication systems. His honors include a Sloan Research Fellowship, the NSF CAREER award, the IBM Faculty Fellowship, and award papers at SIGCOMM 2006 (network-level behavior of spammers), the NSDI 2005 conference (fault detection in router configuration), Usenix Security 2002 (circumventing web censorship using Infranet), and Usenix Security 2001 (web cookie analysis).