TY - GEN
T1 - Compiling path queries
AU - Narayana, Srinivas
AU - Arashloo, Mina Tashmasbi
AU - Rexford, Jennifer
AU - Walker, David
PY - 2016/1/1
Y1 - 2016/1/1
N2 - 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).
AB - 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).
UR - http://www.scopus.com/inward/record.url?scp=85077018369&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85077018369&partnerID=8YFLogxK
M3 - Conference contribution
T3 - Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016
SP - 207
EP - 222
BT - Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016
PB - USENIX Association
T2 - 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016
Y2 - 16 March 2016 through 18 March 2016
ER -