SIGCOMM2013: Maple: Simplifying SDN Programming Using Algorithmic Policies

Presenter: Andreas Voellmy
Authors: Andreas Voellmy, Junchang Wang, Y. Richard Yang, Bryan Ford, Paul Hudak

Maple targets solving complexity in SDN controllers (openflow), which is important to keep SDN configurations tractable.

Background and motivation:

Exact match rules cannot distinguish between the rules that are created by the first packet and the subsequent packets. Also provision for negative rules are not available in Openflow and priorities are being used for the same. The authors explore the following question in this work - Can the rule generation be moved from user level action to "under the hood"?

The key idea is to abstract how packet should be routed and not how tables are configured. That is, the rule abstraction should be conceptually invoked on every packet entering network, while being easy to use like normal prog language, say, Java or Python.

Algorithmic policy specification:
- makes programming model intuitive and easy
- avoids flow table configuration

Implementing algorithmic policies:

Maple introduces:
- routing policy function f defined as a programming language construct
- dependency of f on packet data and builds trace tree (a decision tree)
- compiles recorded executions in flow table
- refines trace as the new paths in the decision tree are explored

The priorities are recorded  using an in-order traversal and finally, the compilation can be performed to generate the flow rules. However, the authors observe that a basic compilation results in two problems:
- generates redundant flow rules
- generates more priorities than necessary.

Their proposed solution is to annotate:
- TT nodes with meta data (completeness)
- with priorities dependency

Implementation Status: Implemented using Haskell  on Openflow 1.0
Evaluation:
- Using ACL - constructing ACL compiler with Maple
- Filter set interpreter as an algorithmic policy in Maple.

Observations:
- Maple generates compact flow tables.
- Maple uses fewer priority levels
- Maple reduces HTTP connection time

Q: Question was unclear.
A: Maple can generate policy specifications for more than one objective in the function.

Q: Global list of priorities are not honored by all the nodes. That is, what if there are some switches that don't honor priority.
A: Authors make the assumption that priority semantics is honored.