Declarative Network Path Queries

Abstract

Effective management of computer networks is crucial to ensure the availability

and performance of "always online" Internet 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

little attention on programmatic measurement of networks.

This thesis focuses on a broad class of measurement questions that analyze the

flow of traffic along network paths. Today, network operators measure traffic

flow by "synthesizing" multiple data streams---including updates to

forwarding, traffic observations from 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 between measurement accuracy and overhead.

In this thesis, we 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. We realize these principles in three parts, as

follows.

First, we present a declarative query language, that enables paths to be

specified as regular expressions over predicates on packet locations and header

values. The language also has SQL-like "groupby" constructs for aggregating

results anywhere along a path. We show several realistic measurement queries

corresponding to resource management, policy enforcement, and troubleshooting.

Second, we present a query run-time system that translates path queries into

accurate 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

(that run on commodity hardware), and distributed over the switches. Storing the

automaton state requires only a small amount of extra space (2-4 bytes) on

packets.

Third, we present optimizations which address fundamental bottlenecks in

compilation, caused by queries and forwarding policies requiring different

actions on overlapping sets of packets. Experiments indicate that our run-time

system can enable "interactive debugging," allowing an operator to compile

multiple queries in a few seconds. Further, the generated switch rules fit

comfortably in modern switch rule memories.