Compiling Path Queries in Software Defined Networks

• SDN 41
• network monitoring 2
• HotSDN 4
• Y2014 3

http://dl.acm.org/citation.cfm?id=2620736

2015/12/08 01:57:12 cited by 10

Monitoring the flow of traffic along network paths … For example, traffic engineering requires measuring the ingress-egress traffic matrix; debugging a congested link requires determining the set of sources sending traffic through that link; and locating a faulty device might involve detecting how far along a path the traffic makes progress.

Past path-based monitoring systems operate by diverting packets to collectors that perform “after-the-fact” analysis, at the expense of large data-collection overhead … this paper … do more efficient “during-the-fact” analysis.

We introduce a query language that allows each SDN application to specify queries independently of the forwarding state or the queries of other applications. The queries use a regular-expression-based path language that includes SQL-like “groupby” constructs for count aggregation. We track the packet trajectory directly on the data plane by converting the regular expressions into an automaton, and tagging the automaton state (i.e., the path prefix) in each packet as it progresses through the network.

The SDN policies that implement the path queries can be combined with arbitrary packet forwarding policies supplied by other elements of the SDN platform. A preliminary evaluation of our prototype shows that our “during-the-fact” strategy reduces data-collection overhead over “after-the-fact” strategies.

aggregate statistics at individual links

path-based queries can be achieved using one of two broad approaches

1. Hoarders record as much information as possible, so users can specify a wide range of more refined queries after the fact.
2. Neat Freaks specify queries ahead of time, allowing them to collect and store much less data, but support a narrower range of pre-determined queries.

this paper … develop … a “tunable” Neat Freak for path queries in SDNs. Our query language allows users to ask questions about packets traversing paths specified using regular expressions of boolean packet predicates.

Our run-time system implements these queries by generating OpenFlow rules that analyze packets as they flow through the network’s data plane, to avoid directing every packet (or postcard) to collectors for analysis … record packets’ past trajectories onto bits on the packets themselves (i.e., tags) … the necessary information is just the packet’s current state on a Deterministic Finite Automaton (DFA) that represents the path queries

contributions are

• a query interface that allows compositional specification of path queries, through a regular expression-based language with grouping constructs (§2),
• a runtime system that directly observes packet paths on the data plane
• preliminary results

3. PATH QUERY COMPILATION

… the main objective of the path query implementation is to find a way to use existing switch-level primitives (e.g., specified by the OpenFlow API) to recognize packets directly on the data plane as they move through trajectories satisfying the path queries …

1. conversion of the set of path queries into a Deterministic Finite Automaton (DFA)
2. construction of packet-tagging and capturing/counting policies from the DFA
3. merging tagging and counting policies with the packet forwarding policy to form a full policy for the network

use Pyretic as an intermediate language to translate the DFA

3.1 From Path Queries to DFA

3.2 From a DFA to Tagging/Counting Policies

3.3 From Tagging/Counting to Pyretic Policy

The final step is merging the policies generated from the DFA with the global packet forwarding policy generated by other SDN applications.

Our compiler assembles

(1) the tagging policy: DFA transitions on packets

(2) an unaffected: identity function on those packets that do not undergo a state change

(3) fwding, forwarding policy

(4) counting identifies the accepted packets

  ((tagging + unaffected) >> fwding) + counting

for each packet, we either tag (initiating a state change) or leave the packet unchanged, and then forward it. In parallel, we count the packet (or send it to the controller).

5. RELATED WORK

Traffic query languages and systems

Gigascope [8] and Frenetic [9] support SQL-like queries on packet streams at a single point in the network

reference

• [1] Y. Zhang, M. Roughan, N.Duffield, and A. Greenberg, “Fast accurate computation of large-scale IP traffic matrices from link loads,” in Proc. ACM SIGMETRICS, 2003.
• [2] N. G. Duffield and M. Grossglauser, “Trajectory sampling for direct traffic observation,” IEEE/ACM Trans. Networking, June 2001.
• [8] C. Cranor, T. Johnson, O. Spataschek, and V. Shkapenyuk, “Gigascope: A stream database for network applications,” in Proc. ACM SIGMOD, 2003.