|Title||:||Compiling Network Path Queries|
|Speaker||:||N. G. Srinivas (Princeton University, USA)|
|Details||:||Wed, 6 Jan, 2016 3:00 PM @ BSB 361|
|Abstract:||:||Measuring the flow of traffic along network paths is crucial for many
management tasks, including traffic engineering, diagnosing
congestion, and mitigating DDoS attacks. However, conventional
approaches to collecting path-based measurements rely on complex
joins of multiple sources of data (i.e., forwarding, topology and
traffic), resulting in inaccurate results, or unnecessarily high
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 SQL-like 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 data-collection overhead is limited to exactly those packets that satisfy the query.
We implemented our system on top of the open source Pyretic SDN controller and evaluated its performance on campus and ISP topologies. 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 2-4 bytes (e.g., a VLAN or MPLS header).
Bio: Srinivas Narayana is a sixth year PhD student working with Prof. Jennifer Rexford at Princeton University. He is broadly interested in designing networked systems, and his current research focuses on building efficient measurement and diagnosis tools for network operators.