Skip to main content
To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorNarayana, Srinivas-
dc.contributor.authorArashloo, Mina T-
dc.contributor.authorRexford, Jennifer-
dc.contributor.authorWalker, David-
dc.identifier.citationNarayana, Srinivas, Mina Tahmasbi, Jennifer Rexford, and David Walker. "Compiling path queries." In 13th USENIX Symposium on Networked Systems Design and Implementation (2016): pp. 207-222.en_US
dc.description.abstractMeasuring 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 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 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).en_US
dc.format.extent207 - 222en_US
dc.relation.ispartof13th USENIX Symposium on Networked Systems Design and Implementationen_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleCompiling Path Queriesen_US
dc.typeConference Articleen_US

Files in This Item:
File Description SizeFormat 
CompilingPathQueries.pdf450.48 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.