ReWiFlow: Restricted Wildcard OpenFlow Rules

Sajad Shirali-Shahreza, Yashar Ganjali (University of Toronto)
Appears in: 
CCR October 2015

The ability to manage individual flows is a major benefit of Software-Defined Networking. The overheads of this fine-grained control, e.g. initial flow setup delay, can overcome the benefits, for example when we have many time-sensitive short flows. Coarse-grained control of groups of flows, on the other hand, can be very complex: each packet may match multiple rules, which requires conflict resolution. In this paper, we present ReWiFlow, a restricted class of OpenFlow wildcard rules (the fundamental way to control groups of flows in OpenFlow), which allows managing groups of flows with flexibility and without loss of performance. We demonstrate how ReWiFlow can be used to implement applications such as dynamic proactive routing. We also present a generalization of ReWiFlow, called MultiReWiFlow, and show how it can be used to efficiently represent access control rules collected from Stanford’s backbone network.

Public Review By: 
Hitesh Ballani

Public Review for ReWiFlow: Restricted Wildcard OpenFlow Rules Sajad Shirali-Shahreza and Yashar Ganjali OpenFlow is the de-facto API to the data plane in software-defined networks (SDNs). It can be used to program the treatment of individual flows through exact match rules, and that of groups of flows through wildcard rules. Wildcard rules – specifying some of the header fields with the remaining left as don’t care – alleviate the overhead of querying the SDN controller regarding new flows at the expense of programming complexity. Such rules allow for creation of arbitrary rule lattices which makes basic rule operations, like addition, deletion, splitting and merging, hard to reason about. This paper tackles the complexity posed by OpenFlow wildcard rules. It proposes ReWiFlow, a restricted class of wildcard rules with a pre-defined linear ordering amongst the header fields. A rule can include a header field only if all header fields earlier in the order are also present. As shown in the paper, this leads to a “prefix property” which, in turn, makes it easier to manage wildcard rules. For example, the priority of ReWiFlow rules can simply be set to the number of header fields in the rule; if two rules are overlapping, then the longer rule is a subset of the shorter one and hence, should have higher priority. This also means that the rules can be matched using longest-prefix matching. Since many real-world networks are likely to require multiple orderings of header fields in order to express existing (and future) network policies, the authors also present a generalization called Multi-ReWiFlow which allows multiple groups of ReWiFlows, each with a different ordering of header fields. The reviewers appreciated that the core idea behind ReWiFlow is simple and intuitive. Wildcard rules existed even in the pre-SDN era; for example, in firewall ACLs. The paper formalizes the idea that managing arbitrary rule lattices is hard, and presents a very neatly scoped lattice space that makes wildcard rule management more tractable. The study of the Stanford ACL set showing that all the rules in that set can be expressed using five groups of ReWiFlow rules indicates the approach has promise. A key open question is, what is ReWiFlow giving up? The authors admit that ReWiFlow trades-off flexibility of wildcard rules for ease of programming. Quantifying this tradeoff seems hard yet important. Many practical issues also need to be tackled. For example, how can operators determine the ordering of header fields for their network? Can this be done automatically for the current set of network policies? Addressing such questions and evaluating ReWiFlow across a wider set of production networks will help make the proposal water-tight and ready to be considered by practitioners.