Source-linked AI summary
Merlin: A Language for Provisioning Network Resources
Robert Soulé, Shrutarshi Basu, Parisa Jalili Marandi, Fernando Pedone, Robert Kleinberg, Emin Gün Sirer, Nate Foster
TL;DR
Merlin addresses the limited expressiveness of existing SDN APIs for managing rich, network-wide policies. It provides a declarative language and compiler for specifying and enforcing packet handling, forwarding, transformations, and bandwidth, while negotiators support dynamic adaptation. Experiments report expressive policies and rapid provisioning of real-world networks, with improved application performance for data analytics and replication systems.
Problem
Existing SDN APIs and languages inadequately support real-world network management involving bandwidth, richer packet processing, and heterogeneous resources.
Method
Merlin uses a high-level policy language, constraint-based compilation, and negotiators that dynamically adjust delegated policies while preserving global constraints.
Results
Experiments demonstrate expressive policies, rapid provisioning and configuration of real-world networks, and better application performance for data analytics and replication systems.
Takeaways & Limitations
Merlin significantly simplifies network administration by raising abstraction while allowing tenants to tailor policies under administrator-enforced global constraints.
Takeaways & Limitations
Localized enforcement can underutilize resources when static allocations do not reflect actual usage, and deployment on end hosts assumes trusted administrative control.
Abstract
from arXiv · showhide
This paper presents Merlin, a new framework for managing resources in software-defined networks. With Merlin, administrators express high-level policies using programs in a declarative language. The language includes logical predicates to identify sets of packets, regular expressions to encode forwarding paths, and arithmetic formulas to specify bandwidth constraints. The Merlin compiler uses a combination of advanced techniques to translate these policies into code that can be executed on network elements including a constraint solver that allocates bandwidth using parameterizable heuristics. To facilitate dynamic adaptation, Merlin provides mechanisms for delegating control of sub-policies and for verifying that modifications made to sub-policies do not violate global constraints. Experiments demonstrate the expressiveness and scalability of Merlin on real-world topologies and applications. Overall, Merlin simplifies network administration by providing high-level abstractions for specifying network policies and scalable infrastructure for enforcing them.
1. INTRODUCTION
Merlin addresses the gap between low-level or limited SDN APIs and the needs of real-world network management. It combines expressive policy abstractions, resource-aware compilation, and dynamic adaptation, with experiments demonstrating practical expressiveness and performance.
- Existing SDN APIs inadequately support rich network-wide policies spanning heterogeneous devices, traffic demands, bandwidth, and packet processing.
- Merlin provides high-level constructs for packet classification, forwarding, packet transformations, and bandwidth limits or guarantees.
- The compiler unifies topology and policy constraints, using mixed integer programming for bandwidth guarantees and regular expressions and finite automata for other forwarding paths.
- Negotiators dynamically adjust bandwidth allocations and verify that delegated policy modifications preserve global constraints.
- A working prototype demonstrates expressive policies, including forwarding, middlebox-style transformations, bandwidth guarantees, and dynamic allocation schemes.
2. LANGUAGE DESIGN
Merlin expresses network behavior through packet predicates, regular-expression paths and transformations, and arithmetic bandwidth constraints. These constructs let policies describe global behavior while supporting compilation and distributed enforcement across network devices.
- A Merlin policy combines traffic statements with a logical formula expressing a global bandwidth constraint.
- Each policy statement identifies packets with a logical predicate and specifies forwarding paths or transformations with a regular expression.
- The language supports predicate composition, set literals, iteration, and cross products to simplify complex policy expressions.
- Regular expressions describe allowed sequences of network locations and can include packet-processing functions such as deep-packet inspection or network address translation.
- Presburger-arithmetic formulas specify bandwidth caps with max and guarantees with min, including aggregate constraints such as max(x + y, 50MB/s).
- Policies can be distilled into component constructs and distributed across devices to collectively enforce a global policy.
3. COMPILER
Merlin compiles declarative policies into enforceable network configurations by combining topology representations, regular-expression path constraints, and constraint-based bandwidth provisioning. Its compiler constructs logical topologies and solves path assignments subject to routing and capacity requirements.
- Compiler overview: The compiler translates Merlin policies into locally enforceable policies, selects paths, places packet transformations, allocates bandwidth, and generates device instructions.Its inputs include the Merlin policy, physical topology, and mappings needed to realize transformations.
- Localization: Bandwidth constraints are localized to network elements to improve scalability, but static allocations can underutilize resources when actual traffic differs from assumptions.Negotiators dynamically adjust allocations to address this scalability–utilization tradeoff.
- Guaranteed-rate provisioning: For guaranteed rates, Merlin formulates path selection as a mixed-integer constraint problem resembling multi-commodity flow, with integral route choices and regular-expression constraints.The MIP uses binary edge variables, flow conservation, and per-link reservation variables to enforce bandwidth feasibility.
- Logical topology: Merlin represents each statement’s permitted physical paths as a logical graph formed from the network topology and a regular-expression automaton.The policy graph is a union of disjoint per-statement components.
- Logical topology: A path satisfies a statement’s regular expression exactly when the corresponding logical graph contains a source-to-sink path with a compatible automaton state sequence.This correspondence is stated as Lemma 1 and established by the graph construction.
4. DYNAMIC ADAPTATION
Merlin supports dynamic policy adaptation through negotiators that delegate, transform, and verify sub-policies while preserving global constraints. Tenants can refine classifications, paths, and bandwidth allocations, subject to containment and allocation rules.
- Dynamic adaptation: Negotiators let tenants modify delegated policies while verifying that changes do not violate the administrator’s original global policy.They use Merlin’s predicates, regular expressions, and explicit bandwidth reservations as the basis for verifiable transformations.
- Negotiator architecture: Negotiators form a hierarchical tree in which children may refine policies only when the refinement implies the parent policy.Sibling negotiators may also renegotiate resource assignments cooperatively without violating parent policies.
- Policy transformations: Tenants can refine packet classifications, further constrain forwarding paths, and revise bandwidth allocations.These are the three supported policy transformations.
- Bandwidth transformation: Bandwidth re-allocation preserves validity when the sum of new allocations does not exceed the original allocation.Merlin redistributes limits and guarantees after refinement to improve utilization.
- Policy transformations: A policy example divides a 100MB/s cap into 50MB/s for logged HTTP traffic, 25MB/s for SSH, and 25MB/s for remaining traffic through DPI.The revised policy imposes distinct classifications, transformations, and bandwidth maxima.
- Verification: Verification checks path-language inclusion and whether overlapping refined bandwidth constraints imply the original constraints.The comparison is performed pairwise across statements with overlapping predicates.
- Runtime adaptation: Bandwidth re-allocation can occur rapidly without recompiling the global policy, whereas path-constraint changes require global recompilation and forwarding-rule updates.Implemented negotiators support min-max fair sharing and additive-increase, multiplicative-decrease allocation schemes.
5. IMPLEMENTATION
Merlin is implemented as a working system using established networking, optimization, and verification components. Its implementation supports policy delegation and verification alongside compiler and network-control infrastructure.
- Implementation: The prototype combines OCaml and C with Gurobi, Frenetic, Click, and Linux networking utilities.These components respectively support constraint solving, OpenFlow rule installation, software middleboxes, and Linux end hosts.
- Policy delegation and verification: Merlin delegates policies by intersecting predicates and regular expressions, then projecting the resulting policy onto a sub-network.
- Evaluation: Figure 4 measures Merlin expressiveness with policies for the Stanford campus network topology.
- Policy delegation and verification: Verification uses Z3 to check predicate disjointness and Dprle to check inclusions between regular expressions.
6. EVALUATION
Merlin’s evaluation examines policy expressiveness, application performance, and scalability across practical network policies, real applications, and diverse topologies. The results show concise policy expression, improved application outcomes under bandwidth contention, and fast compilation and verification for many settings.
- 6.1 Expressiveness: 10% of traffic classes received a 1Mbps guarantee and 1Gbps cap, while 11 policy lines generated over 1600 OpenFlow rules, 90 TC rules, and 248 queue configurations.The bandwidth policy demonstrates that compact source code can expand into many low-level rules and queue settings when guarantees are enforced.
- 6.2 Application Performance: Merlin’s bandwidth guarantee for Ring-Paxos Service 2 preserved its allocation without sacrificing utilization, because Service 1 could use unused bandwidth.The experiment compares the two services without and with Merlin on the shared bottleneck machine.
- 6.3 Compilation and Verification: The compiler took less than 50ms for most Internet Topology Zoo networks and less than 600ms for all but one, with the largest 754-switch topology taking 4 seconds.The dataset contained 262 topologies averaging 40 switches, with a standard deviation of 30 switches.
- 6.3 Compilation and Verification: Policy verification scaled linearly for increasing predicates and allocations but quadratically for regular expressions, taking about 3.5 seconds for a thousand-node parse tree.Predicate and allocation verification completed in milliseconds up to tens of thousands of allocations and statements.
7. RELATED WORK
Prior systems address selected network-management functions, but Merlin unifies policy control across switches, middleboxes, and end hosts while adding richer programming and delegation abstractions.
- This paper expands Merlin’s preliminary design with a complete design, implementation, and experimental evaluation.
- Merlin extends prior bandwidth, traffic-filtering, and forwarding approaches with a unified interface and central control point for switches, middleboxes, and end hosts.
- SIMPLE optimizes middlebox placement but does not specify its programming interface or how policies are represented and analyzed.
- Existing SDN languages such as Frenetic, Pyretic, and Maple generally lack support for middlebox functionality, bandwidth allocation, and policy delegation.
- Unlike PANE, Merlin partitions functionality across diverse network devices and supports delegation for entire policies rather than individual flows.
8. CONCLUSION
Merlin raises the abstraction level for network management by letting administrators specify whole-network functionality while the compiler handles component configurations. It also lets tenants tailor policies while preserving global constraints, simplifying administration.
- Merlin allows administrators to specify the functionality of an entire network, leaving low-level component configuration to the compiler.
- Tenants can tailor policies to their needs while administrators retain assurance that global constraints are enforced.
- The approach significantly simplifies network administration and supports future research on network programmability.