Compiling path queries

Srinivas Narayana, Mina Tashmasbi Arashloo, Jennifer Rexford, David Walker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

41 Scopus citations

Abstract

Measuring the flow of traffic along network paths is crucial for many management tasks, including traffic 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 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 the packets 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 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).

Original languageEnglish (US)
Title of host publicationProceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016
PublisherUSENIX Association
Pages207-222
Number of pages16
ISBN (Electronic)9781931971294
StatePublished - Jan 1 2016
Event13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016 - Santa Clara, United States
Duration: Mar 16 2016Mar 18 2016

Publication series

NameProceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016

Conference

Conference13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016
CountryUnited States
CitySanta Clara
Period3/16/163/18/16

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Compiling path queries'. Together they form a unique fingerprint.

Cite this