PGA: Using Graphs to Express and Automatically Reconcile Network Policies

• SDN 41
• middlebox 7
• NFV 1

diverse parties (networking operators, application admins, tenants/end-users) and control programs (SDN Apps, network services) … generate network policies independently and dynamically … large organizations, multiple policy sub-domains exist (e.g., server admin, network engineers, DNS admins, different departments) … applied to the network components they own or manage. Admins and users who share a network have to manually coordinate … → eagerly and automatically detect and resolve conflicts between individual policies and compose them into a coherent conflict-free policy set

• [10] Service Function Chaining Architecture. https://tools.ietf.org/html/draft-merged-sfc-architecture-02
• [11] Service Function Chaining General Use Cases. https://tools.ietf.org/html/draft-liu-sfc-use-cases-08

1 contribution

• a high-level Policy Graph Abstraction (PGA) for sub-domain (diverse source) to separately express networking policies on endpoints, … naturally incorporates network middleboxes

  besides ACL policies, PGA models and composes service chaining policies, i.e., the sequence of middleboxes to be traversed

  policies for arbitrary selection of endpoints based on logical endpoint properties

• algorithms … automatically and scalably compose multiple policy graphs. The composition maintains the individually specified invariants from each policy graph … determines an appropriate service order when merging service chains

  merging multiple service chain requirements into conflict-free composed chains

• implementation of PGA … uses Pyretic to represent middlebox functionality and analyze service chains. … can compose over 20K ACL policies from a real policy dataset under 600s, while incurring sub-millisecond latency for the first packet of a flow when running reactively.

  PGA treats the underlying network as “one big switch”, which … may not reflect all the low level policy requirements: e.g., traffic engineering decisions regarding specific switches/routers/network path 32

  We also do not focus on run-time network state conflicts 33, 39 local, 13.

2.2 Challenges in policy composition

(Pyretic composition) cannot directly compose P1 and P2: e.g., P1 » P2 composition fails … a correct composition requires carefully decomposing each of P1 and P2 into ACL and service requirements and recomposing them into a single program.

order of the FW-LB chain is chosen using the operator’s interal knowledge of the service functions.

System overview

resolving or flagging conflicts/errors and reporting them to users, possibly with suggested fixes … PGA’s eager policy composition is orthogonal to the lower-level compilation methodology … 2015/10/09 03:30:41, check more

6. PROTOTYPE

Our prototype implementation contains ≈2.5K SLOC in Python, including the following Pyretic extensions.

6.1 Abstractions

To support policy graph specification, we extend Pyretic with three primitives: EPGs, Function boxes and Whitelists.

Function boxes

expressed in our extended Pyretic programming language

this expression is required for analyzing dependencies and conflicts between function boxes to determine their intermixed order when merging edges …

6.2 System operation

a composer module takes all the graphs and any auxiliary inputs and generates a composed graph by implementing the algorithm of §5 … the composed graph is stored as an in-memory hash table keyed with the source and destination EPGs for fast lookup of policies at runtime.

8. SYSTEM EVALUATION

three data sets

D1: the synthetic running example from §4 and §5.

D2: the large enterprise dataset §7.2.

D3: D2 with randomly added function boxes.

analyze and compose thousands of policies producing nearly a million edges in under 600s when considering only ACLs and 800s in most cases for policy graphs with both ACLs and service chains .

emulate switches and hosts with mininet 2.1.0 and openvswitch 2.0.2 on the server in order to create a topology and generate packets between hosts in different EPGs

• D1: The composed graph has 8 EPGs and 11 edges .
• D2: the composed graph has nearly 4K unique EPGs and over 76× the number of edges as the input graphs
  • high edge multiplication occurred in graph normalization because some input graph EPGs were defined by top-level labels in the label hierarchy.

Runtime Overhead

• the additional runtime latency incurred at the controller for the first packet of a flow by relying on PGA for determining the policy from the composed graphs of D1 and D2 — .1-.7ms
  • D1: the input samples (pairs of EPGs) were randomly picked
  • D2, picked more samples that had a large number of edges (10-30) between the EPG pair.
• number of edges per EPG pair
  • 95% of EPG pairs have less than 4 edges between them and 99% below 11

graph composition

PGA composes input graphs eagerly … still needs to be able to handle very large inputs in a reasonable amount of time and with practical consumption of resources.

• D2: The largest input (entire D2) … produced nearly 1M edges in the composed graph
  • required less than 1.2 GB of memory while completing in under 10 minutes
• D3: up to 3500 functions boxes added to D2, larger than 1900 middleboxes observed from very large enterprises (>100K hosts) [37].
  • for most cases the composition time is <800 seconds and memory consumption is <20 GB.
  • cached and reused the results of intermediate chain analysis to prevent redundant computations and to save memory.

reference

• 32 H.H.Liu,S.Kandula,R.Mahajan,M.Zhang,andD.Gelernter. Traffic Engineering with Forward Fault Correction. In SIGCOMM, 2014.
• 33 J.C.Mogul,A.AuYoung,S.Banerjee,L.Popa,J.Lee, J. Mudigonda, P. Sharma, and Y. Turner. Corybantic: Towards the Modular Composition of SDN Control Programs. In HotNets, 2013. to check
• 39 local P. Sun, R. Mahajan, J. Rexford, L. Yuan, M. Zhang, and A. Arefin. A Network-state Management Service. In SIGCOMM, 2014.
• 13 A. AuYoung, Y. Ma, S. Banerjee, J. Lee, P. Sharma, Y. Turner, C. Liang, and J. C. Mogul. Democratic Resolution of Resource Conflicts Between SDN Control Programs. In CoNEXT, 2014