Compiling Path Queries in Software-Defined Networks
Concept of compiling path queries in software-defined networks to locate packet loss and enhance network efficiency through direct switch measurements. Learn about the path query system designed to analyze packet paths directly in the data plane, addressing the challenges of observing packets independently at different switches.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Compiling Path Queries in Software-Defined Networks Srinivas Narayana Jennifer Rexford and David Walker Princeton University
Wheres the packet loss? Faulty network device(s) along the way. But where? A B 100 pkts 25 pkts 2
Wheres the packet loss? Solution idea: Check how far packets get from A to B before being dropped somewhere. A B 100 pkts 25 pkts Fine-grained packet counters + Forwarding Complex policies 3
Wheres the packet loss? Instead: nice to get A B packet counts each step along paths where A B traffic flows 25 25 A B 50 25 100 25 0 50 50 100 pkts 25 pkts 4
Wouldnt it be nice to ask questions about packet paths in a network? Problem: we only observe a given packet independently at different switches. 5
Weve designed a path query system that analyzes packet paths directly in the data plane. 6
Problem statement 1. Operator/application specifies network path queries 2. Translate into efficient and direct switch measurements (i.e., data plane rules) 7
Problem statement Independent specifications Query Query Forwarding Compiled into data plane rules 8
Solution architecture 1. Path query language Regular expressions of packet location & headers Query expressions Statistics 2. Query compiler and runtime SDN controller Payloads 9 Statistics
Lets write some queries! (1/3) Count packets reaching switch S1, then S2 with an internal source IP address (10.0/16) switch=S1 A hop on the wire ^ switch=S2, srcip=10.0/16 11
Lets write some queries! (2/3) Capture packets evading a firewall in the network ingress egress ingress egress ingress egress ingress() ^ (switch != FW)* ^ egress() 0 or more repetitions 12
Lets write some queries! (3/3) Switch-level traffic matrix: E2 ... E1 I1 250 100 ... I2 120 95 ... ... ... ... ... 13
Lets write some queries! (3/3) Switch-level traffic matrix: Flow #pkts ingress() * 1000 ^ Count all packets, going from any ingress to any egress. (true)* ^ egress() 14
Lets write some queries! (3/3) Switch-level traffic matrix: Flow #pkts groupby(ingress(), [switch]) ^ sw=I1, sw=E1 250 sw=I1, sw=E2 100 ... ... Group counts by packet s ingress and egress switch! (true)* ^ Traffic matrix! groupby(egress(), [switch]) 15
Lets write some queries! More example queries in the paper 16
How to analyze packet paths in the data plane? 18
Packet paths on data plane Main idea: Record path information in packets [{sw: S1 port: 1 srcmac: ... srcip: ... ...}] [{sw: S1, ...}, {sw: S2, ...}, {sw: S3 port: 2 ...}] [{sw: S1, ...}, {sw: S2 port: 3 srcmac: ... ...}] As such, too much state! 19
Reducing path state on packets Observation 1: Queries already tell us what s needed! Only record path state needed by queries Observation 2: Queries are regular expressions Regular expressions Finite automaton (DFA) Distinguish only paths corresponding to DFA states 20
Reducing path state on packets Observation 1: Queries already tell us what s needed! Only record path state needed by queries Record only DFA state on packets (1-2 bytes) Observation 2: Queries are regular expressions Regular expressions Finite automaton (DFA) Distinguish only paths corresponding to DFA states Use existing tag fields (e.g., VLAN) 21
Example: Query Compilation (1/3) Query: (switch=S1, srcip=10.0.0.1) ^ (switch=S2, dstip=10.0.0.3) S1 S2 switch=S1, srcip=10.0.0.1 switch=S2, dstip=10.0.0.3 Q0 Q1 Q2 22
Example: Query Compilation (2/3) switch=S1, srcip=10.0.0.1 switch=S2, dstip=10.0.0.3 Q0 Q1 Q2 Switch Match Action S1 state=Q0, srcip=10.0.0.1 state=Q1 DFA transition S2 state=Q1, dstip=10.0.0.3 state=Q2 S2 state=Q1, dstip=10.0.0.3 count DFA accept 23
Example: Query Compilation (3/3) DFA- Transitioning Forwarding DFA- Accepting All acting on the same data plane packets! Frenetic composition operators (details in paper) 24
Implementation Prototype on the Pyretic (NSDI 13) SDN controller Implementation publicly available online http://frenetic-lang.org/pyretic/ Evaluation: Payload collection bandwidth Rule space See paper. 25
Summary DFA state can be used to track packet paths directly on the data plane. Measurement and forwarding can be specified independently. 26
Happy to answer queries ;) narayana@cs.princeton.edu 27
