Declarative Network Path Queries

October 13, 2016
2:50 - 4pm
Halligan 102
Speaker: Srinivas Narayana, MIT
Host: Fahad Dogar


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 overheads.

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 postdoctoral researcher at Massachusetts Institute of Technology with Hari Balakrishnan and Mohammad Alizadeh. He completed his PhD at Princeton University, working with Jennifer Rexford and David Walker. He is broadly interested in designing networked systems, and his current research focuses on building efficient measurement and diagnosis tools for network operators.