Genesis: Switch Table Synthesis for Policy Enforcement in ...

Genesis: Switch Table Synthesis for Policy Enforcement in ...

Genesis: Synthesizing Forwarding Tables in Multitenant Networks Kausik Subramanian Loris DAntoni, Aditya Akella 1 Cloud Network Network Policies Enterprise Network Enterprise Network 2

Tenant Network Policies Enterprise Network Reachability: A can talk to B Waypoints: C to B traffic goes through a Firewall B A C 3 Cloud Network Policies

Tenant 1 Network Policies Tenant 2 Network Policies Network isolation: Tenant 1 and 2s traffic must not affect each other Network resource management S1 S2 100Gbps

S3 100Gbps S4 100 Gbps 100Gbps S7 S5 S8 S9 S6

100Gbps S10 Fault tolerance 4 Software-defined Networks Centralized controller SDN Controller Programmable switch rules: Enforcing policies using conventional enforces policies Match: Packet headers distributedSnetworks S2is difficult. 1 Action: Forward to next switch SSH traffic at S3 is forwarded to S7

S3 S4 S5 S6 S7 S8 S9 S10 SSH

5 State of the Art Program individual switch behaviors in SDN Frenetic [ICFP11] Hard to express network-wide behavior Network-wide policies like regular paths (waypoints) NetKAT [POPL14] Merlin [CONEXT14] SIMPLE [SIGCOMM13] Cannot express hyperproperties like isolation Complex network-wide policies like waypoints and bandwidth guarantees Tailor-made and not easily extensible to new policies 6

Support for complex and diverse policies High-level language to specify policies Enforcing certain policies is NP-complete INPUT Genesis Switch forwarding tables Extensible and generalized search

OUTPUT Genesis uses Satisfiability Modulo Theories (SMT) solvers to synthesize forwarding tables 7 Outline of the Talk Motivation Synthesis of forwarding tables in Genesis Scaling to large workloads: Tactics and Divide-and-conquer Genesis extensions: Handling failures 8 Genesis Policy Support Reachability: G1 can talk to G2 Waypoints: B1 can talk to B2

Through FW (NP-complete) S3 S1 S2 FW S4 S5 S6 S7

S8 S9 S10 G1 B1 B2 G2 Tenant isolation: No shared links (NP-complete) Traffic engineering

9 Synthesis Approach High-level policies + Topology INPUT Abstract Representation (Fwd, Reach) Constraints on Fwd and Reach Paths from Fwd and

Reach solution Forwarding tables OUTPUT 10 Semantics of (Fwd, Reach) Fwd(S1, ID) = S2: Switch S1 forwards to S2 Reach(S2, ID) = 1: Specifies that S2 is reachable in 1 step from source Reach(S1, ID) = 0 Reach(S2, ID) = 1 Reach(S3, ID) = 2 Fwd(S1, ID) = S2 Fwd(S2, ID) = S3 S1

S2 S3 Paths extracted from the values of Fwd and Reach 11 Reachability Constraints S3 Fwd(S3, ID) = S4 Reach(S3, ID) = k - 1 SRC S1

Reach(S2, ID) = k - 1 S2 DST S4 S5 Reach(S4, ID) = k If a switch is reachable in k steps, one of its neighbors must be reachable in k - 1 steps 12 Policy Constraints Reach(S4, ID) = k

Waypoint: Blue Tenant specifies path must traverse through S4 Isolation: Blue Tenant and Red Tenant S1 paths do not share any link Traffic Engineering: Using SMT-OPT S4 S2 S5 S3 (S3, ID1) (S3, ID2) 13 THE END?

14 Baseline Synthesis Evaluation Setup Genesis implemented in Python, uses Z3 SMT solver Multi-tenant isolation: Each tenant has a single reachability policy, and all tenant paths are mutually isolated Medium-sized fat-tree datacenter topologies 15 Baseline Synthesis Evaluation ExponentialTo scale to large networks and workloads, Complexity we need to further optimize synthesis performance. Synthesis time for over 60 tenants takes >5000s

16 Scaling to Large Workloads TACTICS DIVIDE-AND-CONQUER 17 Tactics: Motivation Edge-to-edge paths: 272 Large search space Core Aggregate Use network structure to specify path properties Edge

Regular expressions using hierarchies 18 Tactics: Examples Core Valley-Free No Edge Tactic: Tactic: Edge Not (Edge Agg Core .* Edge Agg.*Edge Edge) Less Very restrictive;

restrictive; longer short paths paths Aggregate Edge 19 Tactics: Constraint Reduction Genesis uses tactics as a search strategy to eliminate constraints No Edge Tactic ensures no intermediate edge switch Reach(C1) = k - 1

C1 Reach(A1) = k - 1 A1 Reach(E1) = k - 1 E1 Reach(S) = k S 20

Tactics: Properties Specified using a restricted regular expression syntax Sound heuristic (paths satisfy tactic regular expression) Complete (if a solution exists where the paths satisfy the regular expressions, Genesis will return one) Policy-agnostic optimizations The operator can develop a repository of tactics based on their topology structure for reuse 21 Tactics: Evaluation Multi-tenant isolation workload Valley-Free Tactic and No Edge Tactic Valley-Free Tactic speedup: 400x 22

Divide-and-Conquer: Policy Graph Components Isolation Reachability Policy Synthesis Policy Graph

23 Divide-and-Conquer Synthesis Multiple solutions exist due to dense topology 1 3 Min-cut partitioning Unsatisfiable cores for iterating solutions 2x speedup for 40% of workloads with isolation 2

Synthesize partition 1 Synthesized path for 4 5 6 Synthesize partition 2 24 Outline of the Talk Motivation Synthesis of forwarding tables in Genesis Scaling Genesis: Tactics and Divide-and-Conquer Genesis extensions: Handling failures

25 Genesis Extensions Genesis Rich Policy Language Synthesis using SMT Resilient Paths Network Repair 26 Network Resilience

Cloud network Single path: Not resilient Link failure S1 S2 S3 t-resilience: For events under t arbitrary link failures, there exists a valid path 27 Policy-compliant Resiliency Cloud network Backup path

Isolation policy 1-resilient S1 S2 S3 For 1-resilience, Sound transformation backup pathofmust inputbepolicies edge-disjoint to provide fromt-resilience original path

28 Minimal Reactive Network Repair Cloud network Policies Policies Best repair: Minimize change overhead Genesis uses MaxSMT 29 Network Repair Evaluation Multi-tenant isolation workload One switch-failure, network repair such that number of switches affected is minimized

For larger workloads, repair is faster than re-synthesis. 30 High-level policies on paths and switches INPUT Genesis Switch forwarding tables satisfying policies OUTPUT Tactics Divide-andconquer

T-resilience Network repair Optimizations Extensions 31

Recently Viewed Presentations

  • Assembly Programming on the TI-89 - Compsci02.snc.edu

    Assembly Programming on the TI-89 - Compsci02.snc.edu

    Assembly Programming on the TI-89 ... The eighth of the address registers is the user stack pointer, a register which always holds the top value of the system stack The final register, the 16-bit CCR, holds the conditions of the...
  • St Clarets GFC Youth Presentation Evening 2012

    St Clarets GFC Youth Presentation Evening 2012

    St Clarets GFC Youth Presentation Evening 2012 The Under 10s with their trophies and managers The Under 12s with their coach Steve McElroy The Under 14s with their coach Mick Buckley The Under 16s with their coaches Mick Buckley and...
  •  5 lines 3 long lines which rhyme 2

    5 lines 3 long lines which rhyme 2

    Limerick There once was a musical king Who suddenly started to sing. The birds in the sky All started to fly Nearer that talented king. Limerick There once was a musical king Who suddenly started to sing.
  • NOEL Z. ALMERA Senior System Officer NATCCO I.T.

    NOEL Z. ALMERA Senior System Officer NATCCO I.T.

    However, the name Nokia wasn't yet born. It was the location of his second mill - on the banks of the Nokianvirta river - that inspired Idestam to name his company Nokia Ab, something which happened in 1871. They become...
  • A Study of Feature Processing on Accent Classification Given ...

    A Study of Feature Processing on Accent Classification Given ...

    CSCE 666. Term Project Presentation. Dec 11th, 2013. Background. Motivation: Accent Recognition(AR) helps improve Speech Recognition system and Speaker Identification system . Our work. Word-level Classifiers are built using different types of features, words and learning methods.
  • FY05 Arrearage Reduction MDEP - National Library of Australia

    FY05 Arrearage Reduction MDEP - National Library of Australia

    Deirdre Kiorgaard and Ann Huthwaite Presented by Ann Huthwaite 2005 ACOC seminar Authority control - why bother? Who benefits? catalogue users cataloguers libraries AACR2 Guidance on choosing access points for a bibliographic record Chapter 21 Guidance on formulating headings Chapters...
  • Realist international relations theory

    Realist international relations theory

    Republican liberalism is based on the claim that liberal democracies are more peaceful than other types of political system. Republican liberals argue that democracies do not fight each other. This is known as the "democratic peace" theory. This argument was...
  • Hermeneutics Intro and Rationale - Regent University

    Hermeneutics Intro and Rationale - Regent University

    References Abingdon's Strong's exhaustive concordance of the Bible (1890/1980). Nashville, TN: Abingdon. Hermeneutics Introduction and Rationale Dr. William Cox Ed.D. Summer 2007 Residency Purpose To enable both personal obedience and "faith-learning integration" in professional activities.