Compiling Path Queries

Abstract:

Measuring the flow of traffic along network paths
is crucial for many management tasks, including traf-
fic engineering, diagnosing congestion, and mitigating
DDoS attacks. We introduce a declarative query language
for efficient path-based traffic monitoring. Path
queries are specified as regular expressions over predicates
on packet locations and header values, with SQLlike
“groupby” constructs for aggregating results anywhere
along a path. A run-time system compiles queries
into a deterministic finite automaton. The automaton’s
transition function is then partitioned, compiled into
match-action rules, and distributed over the switches.
Switches stamp packets with automaton states to track
the progress towards fulfilling a query. Only when packets
satisfy a query are they packet counted, sampled, or
sent to collectors for further analysis. By processing
queries in the data plane, users “pay as they go”, as datacollection
overhead is limited to exactly those packets
that satisfy the query. We implemented our system on top
of the Pyretic SDN controller and evaluated its performance
on a campus topology. Our experiments indicate
that the system can enable “interactive debugging”—
compiling multiple queries in a few seconds—while fitting
rules comfortably in modern switch TCAMs and the
automaton state into two bytes (e.g., a VLAN header).