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 lan-guage for efficient path-based traffic monitoring. Path queries are specified as regular expressions over predi-cates on packet locations and header values, with SQL-like “groupby ” constructs for aggregating results any-where 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 pack-ets 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 data-collection 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 perfor-mance on a campus topology. Our experiments indicate that the system can enable “interactive debugging”— compiling multiple queries in a few seconds—while fit-ting rules comfortably in modern switch TCAMs and the automaton state into two bytes (e.g., a VLAN header). 1