Talk
Arjun Guha, University of Massachusetts, Amherst
Monday, November 30, 1:30PM
CITP Conference room, 3rd floor Sherrerd Hall

A Fast Compiler for NetKAT

In the past few years, high-level programming languages have played a key role
in several networking platforms, by providing abstractions that streamline
application development. Unfortunately, current compilers can take tens of
minutes to generate forwarding state for even relatively small networks. This
forces programmers to either work around performance issues or revert to using
lower-level APIs.

In this talk, we first present a new compiler for NetKAT (a network programming
language) that is two orders of magnitude faster than existing systems. Our key
insight is a new intermediate representation based on a variant of binary
decision diagrams that can represent network programs compactly and supports
fast, algebraic manipulation. We argue that our compiler scales to large
networks using a diverse set of benchmarks.

In addition to speed, our new intermediate representation lets us build a
powerful new abstraction for network programming. Existing languages provide
constructs for programming individual switches, which forces programmers to
specify whole-network behavior on a switch-by-switch basis. For the first time,
we can compile programs that syntactically represent sets of end-to-end paths
through the network.  To do so, our compiler automatically inserts stateful
operations (e.g., VLAN tagging) to distinguish overlapping paths from each
other.

Finally, we present a very general implementation of network virtualization that
leverages our ability to compile end-to-end paths.  The key insight is to give
packets two locations--physical and virtual--and synthesize a program that moves
packets along physical paths to account for hops in the virtual network. We show
that different synthesis strategies can be used to implement global
requirements, such as shortest paths, load-balancing, and so on.

Arjun Guha is an assistant professor of Computer Science at UMass Amherst. He
enjoys tackling problems in systems using the tools and principles of
programming languages. Apart from network programming, he has worked on Web
security and system configuration languages. He received a PhD in Computer
Science from Brown University in 2012 and a BA in Computer Science from Grinnell
College in 2006.