Merlin: A Language for Provisioning Network Resources

Robert Soulé, Shrutarshi Basu, Parisa Jalili Marandi, Fernando Pedone, Robert Kleinberg, Emin Gün Sirer, Nate Foster.

10th International Conference on emerging Networking EXperiments and Technologies (CoNEXT ’14)

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 maps these policies into a constraint problem that determines bandwidth allocations using parameterizable heuristics. It then generates code that can be executed on the network elements to enforce the policies. To allow network tenants to dynamically adapt policies to their needs, 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 effectiveness of Merlin on realworld topologies and applications. Overall, Merlin simplifies network administration by providing high-level abstractions for specifying network policies that provision network resources.

Managing the Network with Merlin

Robert Soulé, Shrutarshi Basu, Robert Kleinberg, Emin Gün Sirer, Nate Foster

Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks (HotNets-XII)

This paper presents a new network management framework called Merlin. With Merlin, network administrators express policies in a high-level, declarative language based on regular expressions. The compiler automatically partitions those policies into components that can be placed on a variety of devices including switches, middleboxes, and end hosts. The compiler uses a constraint-solver to determine the optimal placement strategy using paramaterizable heuristics. Sub-policies may be further constrained by network tenants, facilitating management of federated networks. Merlin provides techniques for verifying that both the partitioned program components and the delegated sub-policies conform to the global network policy. Overall, Merlin simplifies the task of network administration by providing high-level abstractions for specifying network policies and scalable infrastructure for enforcing them.

Exploring the impact of context sensitivity on blended analysis

Marc Fisher II, Bruno Dufour, Shrutarshi Basu and Barbara G. Ryder.

Proceedings of the 26th IEEE International Conference on Software Maintenance (ICSM 2010).

This paper explores the use of context sensitivity both intra- and interprocedurally in a blended (static/dynamic) program analysis for identifying source of object churn in framework- intensive Web-based applications. Empirical experiments with an existing blended analysis algorithm compare combinations of (i) use of a context-insensitive call graph with a context-sensitive calling context tree, and (ii) use (or not) of context-sensitive code pruning within methods. These experiments demonstrate achievable gains in scalability and performance in terms of several metrics designed for blended escape analysis, and report results in terms of object instances created, to allow more realistic conclusions from the data than were possible previously.

Application of formal grammars to the study of complex patterns and evolving systems

Shrutarshi Basu, Rhodes Baker and Khine Lin.

Proceedings of the National Conference on Undergraduate Research, 2009.

Nature expresses itself in a variety of patterns and complex structures. Understanding the rules and principles governing the creation of these patterns might allow us to create new structures and systems based on nature’s successes. Formal grammars in the form of Lindenmayer systems have accurately modeled the growth of various plant morphologies and other fractal systems. Our research explored the application of formal grammars to creating similar complex systems: urban building layouts, road networks and various artistic patterns showing a high degree of self-similarity. Rules for developing the system are specified as a parameterized formal grammar followed by the application of a probability model to create a variety of instances of systems that would all be consistent with the rules, but different in detail from each other.

In order to explore the general applications of formal grammars to multiple classes of problems, a computer system called Metaphor has been created. Metaphor allows for the definition of formal grammars as a set of parameterized rules in a simple metalanguage. These rules may then be supplied with various starting conditions using different combinations of parameters. The modular nature of Metaphor allows for the output from the grammar systems to be mapped to a variety of displays ranging from simple 2D line maps to 3D graphics. The ultimate goal is to provide a tool for researchers in non-computer science related fields to explore the patterns and combinations that continually recur in their fields of interest.