http://www.cs.cornell.edu/~jnfoster/papers/merlin.pdf
ABSTRACT Merlin language includes logical predicates to identify sets of packets, regular expressions to encode forwarding paths, and arithmetic formulas to specify bandwidth constraints. Merlin compiler maps these policies into a constraint problem that determines bandwidth allocations using parameterizable heuristics. … Merlin delegates control of sub-policies and for verifying modifications made to sub-policies do not violate global constraints.
existing APIs for SDN programming are either too low-level or too limited in functionality to enable effective implementation of rich network-wide policies.
Network orchestration frameworks provide powerful mechanisms that handle a larger set of concerns including middlebox placement and bandwidth, but they either fail to provide a programmable API to those mechanisms, or expose APIs that are extremely simple (sequence of middleboxes).
Merlin policy language gives constructs … specify the intended
behavior … at a high level of abstraction. … to allow nat
… Merlin uses tag-based routing scheme …
rewrites formula sothat the bandwidth constraints apply to packets at
a single location; given a formula with one term over n identifiers,
the compiler divides bandwidth equally among the local terms.
split identifiers
[x : (ip.src = 192.168.1.1 and
ip.dst = 192.168.1.2 and
tcp.dst = 20) -> .* dpi .* ;
y : (ip.src = 192.168.1.1 and
ip.dst = 192.168.1.2 and
tcp.dst = 21) -> .* ;
z : (ip.src = 192.168.1.1 and
ip.dst = 192.168.1.2 and
tcp.dst = 80) -> .* dpi *. nat .* ],
max(x + y,50MB/s) and min(z,100MB/s)
localized to
[x : (ip.src = 192.168.1.1 and
ip.dst = 192.168.1.2 and
tcp.dst = 20) -> .* dpi .* ;
y : (ip.src = 192.168.1.1 and
ip.dst = 192.168.1.2 and
tcp.dst = 21) -> .* ;
z : (ip.src = 192.168.1.1 and
ip.dst = 192.168.1.2 and
tcp.dst = 80) -> .* dpi *. nat .* ],
max(x,25MB/s) and
max(y,25MB/s) and
min(z,100MB/s)
if h1, h2, m1 are the three locations capable of running deep
packet inspection, then the regular expression
.* dpi .*
would be transformed into
.* (h1|h2|m1) .*.
multi-commodity flow problem1
programmers can invoke Merlin with one of the three optimization criteria: weighted shortest-path, min-max ratio, min-max reserved.
best-effort rates for traffic requiring only best-effort rates, .. compiler only needs to compute sink-trees that obey the path constraints expressed in the policy
Switches. For basic forwarding, Merlin generates instructions for
OpenFlow enabled switches.
Middleboxes. For functionality such as deep packet inspection, load
balancing, or intrusion detection, Merlin generates Click [38]
configuration scripts.
End hosts. Traffic filtering and rate limiting are implemented using
the standard Linux utilities iptables and tc.
Merlin allows administrators to delegate policies to tenants who may then refine them. Tenants can refine a policy by adding addition constraints to the regular expression. For example, an expression that says all packets must go through a traffic logger (LOG) function:
.* log .*
can be modified to, additionally pass through a DPI function:
.* log .* dpi .*
one more example, global policy
( ipSrc = 192.168.1.1 and
ipProto = 0x06)
-> .* h3 at max(100Mb/s)
is refined by tenant: require waypoint a monitoring middlebox,
allocate additional bandwidth to SSH traffic:
( ipSrc = 192.168.1.1 and
ipProto = 0x06 and tcpDst = 80)
-> .* dpi .* h3 at max(50Mb/s)
( ipSrc = 192.168.1.1 and
ipProto = 0x06 and tcpDst = 22)
-> .* dpi .* h3 at max(25Mb/s)
( ipSrc = 192.168.1.1 and
ipProto = 0x06 and
!(tcpDst = 22 | tcpDst = 80))
-> .* dpi .* h3 at max(25Mb/s)
Merlin leverages the policy language representation to check policy inclusion.
Bandwidth re-allocation does not require recompilation of the global policy, and can thus happen quite rapidly.
synthesis is when compilation does not work
packet rewriting