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.