[talks] Srinivas Narayana will present his Pre-FPO on Wednesday, November 11, 2015 at 1:30pm in CS 301

[Nicki Gotsis]

Srinivas Narayana will present his Pre-FPO on Wednesday, November 11, 2015 at 1:30pm in CS 301.

The members of his committee are:  Jennifer Rexford (adviser), David Walker (reader), Sanjay Rao (Purdue, reader), Nick Feamster (non-reader) and Aarti Gupta (non-reader).

Everyone is invited to attend his talk.  The talk title and abstract follow below:


Title: Declarative Network Path Queries

Abstract:

Effective management of computer networks by operators is crucial to ensure the
availability and performance of "always online" services that we depend
on. Towards this goal, programmatic tools can remove slow and expensive human
involvement in management. Recently, Software-Defined Networking (SDN)
technology has eased programmatic *control* of networks, but there has been
relatively little attention on programmatic *measurement* of networks.

My thesis focuses on a broad class of network measurement questions that analyze
the flow of traffic along network paths. Such questions are crucial for many
network management tasks, including traffic engineering, diagnosing congestion,
mitigating DDoS attacks, localizing packet loss in networks, and several
others. With the current state-of-the-art, network operators measure traffic
flow by "synthesizing" multiple data streams from the network---including
updates to forwarding rules, traffic observations from counters and packet
samples, and changes in network topology. However, this approach has significant
limitations: it makes measurements indirect for operators to express, and forces
operators to make a difficult trade-off up front between the accuracy and
overhead of their measurements.

In my thesis, I approach network path measurement with two key principles: (1)
Enable operators to specify the measurements they need in a declarative query
language; and (2) Drive network measurement according to operator-specified
queries. This enables the collection of *exactly* the traffic that satisfies the
operator-specified queries, with accurate results for those queries at low
overhead. There are three important pieces in my research that realize these
principles in practice.

First, I will present an declarative query language that enables efficient
path-based traffic monitoring. Path queries are specified as regular expressions
over predicates on packet locations and header values, with SQL-like ``groupby''
constructs for aggregating results anywhere along a path. Packets can be
captured either before or after they traverse a path that satisfies a query,
returning results as packet or byte counters, entire packets (mirrored to
collectors), or packet and flow sampled records (from commonly deployed
packet-sampling technologies). A network operator writes each query indepedently
of the forwarding policy in the network, as well as other queries, without
worrying about the specifics of switch hardware. We show that she is able to
specify several realistic measurement questions corresponding to network
resource management, policy enforcement, and fault diagnosis.

Second, I will present a query run-time system that translates the
operator-specified queries into accurate data plane measurement that runs on
commodity switch hardware. The run-time first compiles queries into a
deterministic finite automaton. The automaton's transition function is then
partitioned, compiled into `match-action' rules (which can run on commodity
hardware), and distributed over the switches. Switches stamp packets with
automaton states to track their progress towards fulfilling a query. Only when
packets satisfy a query are they counted, sampled, or sent to collectors for
further analysis. By processing queries in the data plane, users ``pay as they
go'', as data-collection overhead is limited to exactly those packets that
satisfy the query. Further, storing the automaton state requires only a small
amount of extra space (2-4 bytes) on each packet---for example a VLAN or MPLS
header.

Third, I will present optimizations to our prototype run-time system that is
built on top of the Pyretic SDN controller, an open source platform. These
optimizations address fundamental bottlenecks in compilation, caused by queries
and forwarding policies performing different actions on overlapping sets of
packets. Combining such actions into a unified rule set can result in
exponential increases in query compile time and the output rule set. The
optimizations leverage key insights into the structure of the constituent
policies, and recent advances in commodity hardware, to reduce compile times and
rule set sizes by 3-4 orders of magnitude. Experiments indicate that the system
can enable ``interactive debugging''---compiling multiple queries in a few
seconds---while fitting rules comfortably in modern switch rule memories.

Together, the query language and run-time system enable expressive measurement
specification, as well as accurate and efficient network measurement, furthering
the state-of-the-art of network management on commodity hardware.