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.