Rules Placement Problem in OpenFlow Networks: A Survey
---
paper_title: Frenetic: a network programming language

paper_content:

Modern networks provide a variety of interrelated services including routing, traffic monitoring, load balancing, and access control. Unfortunately, the languages used to program today's networks lack modern features - they are usually defined at the low level of abstraction supplied by the underlying hardware and they fail to provide even rudimentary support for modular programming. As a result, network programs tend to be complicated, error-prone, and difficult to maintain. This paper presents Frenetic, a high-level language for programming distributed collections of network switches. Frenetic provides a declarative query language for classifying and aggregating network traffic as well as a functional reactive combinator library for describing high-level packet-forwarding policies. Unlike prior work in this domain, these constructs are - by design - fully compositional, which facilitates modular reasoning and enables code reuse. This important property is enabled by Frenetic's novel run-time system which manages all of the details related to installing, uninstalling, and querying low-level packet-processing rules on physical switches. Overall, this paper makes three main contributions: (1) We analyze the state-of-the art in languages for programming networks and identify the key limitations; (2) We present a language design that addresses these limitations, using a series of examples to motivate and validate our choices; (3) We describe an implementation of the language and evaluate its performance on several benchmarks.
---
paper_title: OpenFlow: enabling innovation in campus networks

paper_content:

This whitepaper proposes OpenFlow: a way for researchers to run experimental protocols in the networks they use every day. OpenFlow is based on an Ethernet switch, with an internal flow-table, and a standardized interface to add and remove flow entries. Our goal is to encourage networking vendors to add OpenFlow to their switch products for deployment in college campus backbones and wiring closets. We believe that OpenFlow is a pragmatic compromise: on one hand, it allows researchers to run experiments on heterogeneous switches in a uniform way at line-rate and with high port-density; while on the other hand, vendors do not need to expose the internal workings of their switches. In addition to allowing researchers to evaluate their ideas in real-world traffic settings, OpenFlow could serve as a useful campus component in proposed large-scale testbeds like GENI. Two buildings at Stanford University will soon run OpenFlow networks, using commercial Ethernet switches and routers. We will work to encourage deployment at other schools; and We encourage you to consider deploying OpenFlow in your university network too
---
paper_title: On the co-existence of distributed and centralized routing control-planes

paper_content:

Network operators can and do deploy multiple routing control-planes, e.g., by running different protocols or instances of the same protocol. With the rise of SDN, multiple control-planes are likely to become even more popular, e.g., to enable hybrid SDN or multi-controller deployments. Unfortunately, previous works do not apply to arbitrary combinations of centralized and distributed control-planes. In this paper, we develop a general theory for coexisting control-planes. We provide a novel, exhaustive classification of existing and future control-planes (e.g., OSPF, EIGRP, and Open-Flow) based on fundamental control-plane properties that we identify. Our properties are general enough to study centralized and distributed control-planes under a common framework. We show that multiple uncoordinated control-planes can cause forwarding anomalies whose type solely depends on the identified properties. To show the wide applicability of our framework, we leverage our theoretical insight to (i) provide sufficient conditions to avoid anomalies, (ii) propose configuration guidelines, and (iii) define a provably-safe procedure for reconfigurations from any (combination of) control-planes to any other. Finally, we discuss prominent consequences of our findings on the deployment of new paradigms (notably, SDN) and previous research works.
---
paper_title: B4: experience with a globally-deployed software defined wan

paper_content:

We present the design, implementation, and evaluation of B4, a private WAN connecting Google's data centers across the planet. B4 has a number of unique characteristics: i) massive bandwidth requirements deployed to a modest number of sites, ii) elastic traffic demand that seeks to maximize average bandwidth, and iii) full control over the edge servers and network, which enables rate limiting and demand measurement at the edge. These characteristics led to a Software Defined Networking architecture using OpenFlow to control relatively simple switches built from merchant silicon. B4's centralized traffic engineering service drives links to near 100% utilization, while splitting application flows among multiple paths to balance capacity against application priority/demands. We describe experience with three years of B4 production deployment, lessons learned, and areas for future work.
---
paper_title: vCRIB: virtualized rule management in the cloud

paper_content:

Cloud operators increasingly need many fine-grained rules to better control individual network flows for various management tasks. While previous approaches have advocated placing rules either on hypervisors or switches, we argue that future data centers would benefit from leveraging rule processing capabilities at both for better scalability and performance. In this paper, we propose vCRIB, a virtualized Cloud Rule Information Base that allows operators to freely define different management policies without the need to consider underlying resource constraints. The challenge in our approach is the design of a vCRIB manager that automatically partitions and places rules at both hypervisors and switches to achieve a good trade-off between resource usage and performance.
---
paper_title: PAST: scalable ethernet for data centers

paper_content:

We present PAST, a novel network architecture for data center Ethernet networks that implements a Per-Address Spanning Tree routing algorithm. PAST preserves Ethernet's self-configuration and mobility support while increasing its scalability and usable bandwidth. PAST is explicitly designed to accommodate unmodified commodity hosts and Ethernet switch chips. Surprisingly, we find that PAST can achieve performance comparable to or greater than Equal-Cost Multipath (ECMP) forwarding, which is currently limited to layer-3 IP networks, without any multipath hardware support. In other words, the hardware and firmware changes proposed by emerging standards like TRILL are not required for high-performance, scalable Ethernet networks. We evaluate PAST on Fat Tree, HyperX, and Jellyfish topologies, and show that it is able to capitalize on the advantages each offers. We also describe an OpenFlow-based implementation of PAST in detail.
---
paper_title: Maturing of OpenFlow and Software Defined Networking through Deployments

paper_content:

Software-defined Networking (SDN) has emerged as a new paradigm of networking that enables network operators, owners, vendors, and even third parties to innovate and create new capabilities at a faster pace. The SDN paradigm shows potential for all domains of use, including data centers, cellular providers, service providers, enterprises, and homes. Over a three-year period, we deployed SDN technology at our campus and at several other campuses nation-wide with the help of partners. These deployments included the first-ever SDN prototype in a lab for a (small) global deployment. The four-phased deployments and demonstration of new networking capabilities enabled by SDN played an important role in maturing SDN and its ecosystem. We share our experiences and lessons learned that have to do with demonstration of SDN's potential; its influence on successive versions of OpenFlow specification; evolution of SDN architecture; performance of SDN and various components; and growing the ecosystem.
---
paper_title: OpenFlow: enabling innovation in campus networks

paper_content:

This whitepaper proposes OpenFlow: a way for researchers to run experimental protocols in the networks they use every day. OpenFlow is based on an Ethernet switch, with an internal flow-table, and a standardized interface to add and remove flow entries. Our goal is to encourage networking vendors to add OpenFlow to their switch products for deployment in college campus backbones and wiring closets. We believe that OpenFlow is a pragmatic compromise: on one hand, it allows researchers to run experiments on heterogeneous switches in a uniform way at line-rate and with high port-density; while on the other hand, vendors do not need to expose the internal workings of their switches. In addition to allowing researchers to evaluate their ideas in real-world traffic settings, OpenFlow could serve as a useful campus component in proposed large-scale testbeds like GENI. Two buildings at Stanford University will soon run OpenFlow networks, using commercial Ethernet switches and routers. We will work to encourage deployment at other schools; and We encourage you to consider deploying OpenFlow in your university network too
---
paper_title: B4: experience with a globally-deployed software defined wan

paper_content:

We present the design, implementation, and evaluation of B4, a private WAN connecting Google's data centers across the planet. B4 has a number of unique characteristics: i) massive bandwidth requirements deployed to a modest number of sites, ii) elastic traffic demand that seeks to maximize average bandwidth, and iii) full control over the edge servers and network, which enables rate limiting and demand measurement at the edge. These characteristics led to a Software Defined Networking architecture using OpenFlow to control relatively simple switches built from merchant silicon. B4's centralized traffic engineering service drives links to near 100% utilization, while splitting application flows among multiple paths to balance capacity against application priority/demands. We describe experience with three years of B4 production deployment, lessons learned, and areas for future work.
---
paper_title: A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks

paper_content:

The idea of programmable networks has recently re-gained considerable momentum due to the emergence of the Software-Defined Networking (SDN) paradigm. SDN, often referred to as a "radical new idea in networking", promises to dramatically simplify network management and enable innovation through network programmability. This paper surveys the state-of-the-art in programmable networks with an emphasis on SDN. We provide a historic perspective of programmable networks from early ideas to recent developments. Then we present the SDN architecture and the OpenFlow standard in particular, discuss current alternatives for implementation and testing of SDN-based protocols and services, examine current and future SDN applications, and explore promising research directions based on the SDN paradigm.
---
paper_title: Optimizing the "one big switch" abstraction in software-defined networks

paper_content:

Software Defined Networks (SDNs) support diverse network policies by offering direct, network-wide control over how switches handle traffic. Unfortunately, many controller platforms force applications to grapple simultaneously with end-to-end connectivity constraints, routing policy, switch memory limits, and the hop-by-hop interactions between forwarding rules. We believe solutions to this complex problem should be factored in to three distinct parts: (1) high-level SDN applications should define their end-point connectivity policy on top of a "one big switch" abstraction; (2) a mid-level SDN infrastructure layer should decide on the hop-by-hop routing policy; and (3) a compiler should synthesize an effective set of forwarding rules that obey the user-defined policies and adhere to the resource constraints of the underlying hardware. In this paper, we define and implement our proposed architecture, present efficient rule-placement algorithms that distribute forwarding policies across general SDN networks while managing rule-space constraints, and show how to support dynamic, incremental update of policies. We evaluate the effectiveness of our algorithms analytically by providing complexity bounds on their running time and rule space, as well as empirically, using both synthetic benchmarks, and real-world firewall and routing policies.
---
paper_title: Frenetic: a network programming language

paper_content:

Modern networks provide a variety of interrelated services including routing, traffic monitoring, load balancing, and access control. Unfortunately, the languages used to program today's networks lack modern features - they are usually defined at the low level of abstraction supplied by the underlying hardware and they fail to provide even rudimentary support for modular programming. As a result, network programs tend to be complicated, error-prone, and difficult to maintain. This paper presents Frenetic, a high-level language for programming distributed collections of network switches. Frenetic provides a declarative query language for classifying and aggregating network traffic as well as a functional reactive combinator library for describing high-level packet-forwarding policies. Unlike prior work in this domain, these constructs are - by design - fully compositional, which facilitates modular reasoning and enables code reuse. This important property is enabled by Frenetic's novel run-time system which manages all of the details related to installing, uninstalling, and querying low-level packet-processing rules on physical switches. Overall, this paper makes three main contributions: (1) We analyze the state-of-the art in languages for programming networks and identify the key limitations; (2) We present a language design that addresses these limitations, using a series of examples to motivate and validate our choices; (3) We describe an implementation of the language and evaluate its performance on several benchmarks.
---
paper_title: OpenFlow: enabling innovation in campus networks

paper_content:

This whitepaper proposes OpenFlow: a way for researchers to run experimental protocols in the networks they use every day. OpenFlow is based on an Ethernet switch, with an internal flow-table, and a standardized interface to add and remove flow entries. Our goal is to encourage networking vendors to add OpenFlow to their switch products for deployment in college campus backbones and wiring closets. We believe that OpenFlow is a pragmatic compromise: on one hand, it allows researchers to run experiments on heterogeneous switches in a uniform way at line-rate and with high port-density; while on the other hand, vendors do not need to expose the internal workings of their switches. In addition to allowing researchers to evaluate their ideas in real-world traffic settings, OpenFlow could serve as a useful campus component in proposed large-scale testbeds like GENI. Two buildings at Stanford University will soon run OpenFlow networks, using commercial Ethernet switches and routers. We will work to encourage deployment at other schools; and We encourage you to consider deploying OpenFlow in your university network too
---
paper_title: Optimizing the "one big switch" abstraction in software-defined networks

paper_content:

Software Defined Networks (SDNs) support diverse network policies by offering direct, network-wide control over how switches handle traffic. Unfortunately, many controller platforms force applications to grapple simultaneously with end-to-end connectivity constraints, routing policy, switch memory limits, and the hop-by-hop interactions between forwarding rules. We believe solutions to this complex problem should be factored in to three distinct parts: (1) high-level SDN applications should define their end-point connectivity policy on top of a "one big switch" abstraction; (2) a mid-level SDN infrastructure layer should decide on the hop-by-hop routing policy; and (3) a compiler should synthesize an effective set of forwarding rules that obey the user-defined policies and adhere to the resource constraints of the underlying hardware. In this paper, we define and implement our proposed architecture, present efficient rule-placement algorithms that distribute forwarding policies across general SDN networks while managing rule-space constraints, and show how to support dynamic, incremental update of policies. We evaluate the effectiveness of our algorithms analytically by providing complexity bounds on their running time and rule space, as well as empirically, using both synthetic benchmarks, and real-world firewall and routing policies.
---
paper_title: OFFICER: A general optimization framework for OpenFlow rule allocation and endpoint policy enforcement

paper_content:

The Software-Defined Networking approach permits to realize new policies. In OpenFlow in particular, a controller decides on behalf of the switches which forwarding rules must be installed and where. However with this flexibility comes the challenge of the computation of a rule allocation matrix meeting both high-level policies and the network constraints such as memory or link capacity limitations. Nevertheless, in many situations (e.g., data-center networks), the exact path followed by packets does not severely impact performances as long as packets are delivered according to the endpoint policy. It is thus possible to deviate part of the traffic to alternative paths so to better use network resources without violating the endpoint policy. In this paper, we propose a linear optimization model of the rule allocation problem in resource constrained OpenFlow networks with relaxing routing policy. We show that the general problem is NP-hard and propose a polynomial time heuristic, called OFFICER, which aims to maximize the amount of carried traffic in under-provisioned networks. Our numerical evaluation on four different topologies shows that exploiting various paths allows to increase the amount of traffic supported by the network without significantly increasing the path length.
---
paper_title: Maple: simplifying SDN programming using algorithmic policies

paper_content:

Software-Defined Networking offers the appeal of a simple, centralized programming model for managing complex networks. However, challenges in managing low-level details, such as setting up and maintaining correct and efficient forwarding tables on distributed switches, often compromise this conceptual simplicity. In this pa- per, we present Maple, a system that simplifies SDN programming by (1) allowing a programmer to use a standard programming language to design an arbitrary, centralized algorithm, which we call an algorithmic policy, to decide the behaviors of an entire network, and (2) providing an abstraction that the programmer-defined, centralized policy runs, conceptually, "afresh" on every packet entering a network, and hence is oblivious to the challenge of translating a high-level policy into sets of rules on distributed individual switches. To implement algorithmic policies efficiently, Maple includes not only a highly-efficient multicore scheduler that can scale efficiently to controllers with 40+ cores, but more importantly a novel tracing runtime optimizer that can automatically record reusable policy decisions, offload work to switches when possible, and keep switch flow tables up-to-date by dynamically tracing the dependency of policy decisions on packet contents as well as the environment (system state). Evaluations using real HP switches show that Maple optimizer reduces HTTP connection time by a factor of 100 at high load. During simulated benchmarking, Maple scheduler, when not running the optimizer, achieves a throughput of over 20 million new flow requests per second on a single machine, with 95-percentile latency under 10 ms.
---
paper_title: Frenetic: a network programming language

paper_content:

Modern networks provide a variety of interrelated services including routing, traffic monitoring, load balancing, and access control. Unfortunately, the languages used to program today's networks lack modern features - they are usually defined at the low level of abstraction supplied by the underlying hardware and they fail to provide even rudimentary support for modular programming. As a result, network programs tend to be complicated, error-prone, and difficult to maintain. This paper presents Frenetic, a high-level language for programming distributed collections of network switches. Frenetic provides a declarative query language for classifying and aggregating network traffic as well as a functional reactive combinator library for describing high-level packet-forwarding policies. Unlike prior work in this domain, these constructs are - by design - fully compositional, which facilitates modular reasoning and enables code reuse. This important property is enabled by Frenetic's novel run-time system which manages all of the details related to installing, uninstalling, and querying low-level packet-processing rules on physical switches. Overall, this paper makes three main contributions: (1) We analyze the state-of-the art in languages for programming networks and identify the key limitations; (2) We present a language design that addresses these limitations, using a series of examples to motivate and validate our choices; (3) We describe an implementation of the language and evaluate its performance on several benchmarks.
---
paper_title: Optimizing rule placement in software-defined networks for energy-aware routing

paper_content:

Software-defined Networks (SDN), in particular OpenFlow, is a new networking paradigm enabling innovation through network programmability. Over past few years, many applications have been built using SDN such as server load balancing, virtual-machine migration, traffic engineering and access control. In this paper, we focus on using SDN for energy-aware routing (EAR). Since traffic load has a small influence on power consumption of routers, EAR allows to put unused links into sleep mode to save energy. SDN can collect traffic matrix and then computes routing solutions satisfying QoS while being minimal in energy consumption. However, prior works on EAR have assumed that the table of OpenFlow switch can hold an infinite number of rules. In practice, this assumption does not hold since the flow table is implemented with Ternary Content Addressable Memory (TCAM) which is expensive and power-hungry. In this paper, we propose an optimization method to minimize energy consumption for a backbone network while respecting capacity constraints on links and rule space constraints on routers. In details, we present an exact formulation using Integer Linear Program (ILP) and introduce efficient greedy heuristic algorithm. Based on simulations, we show that using this smart rule space allocation, it is possible to save almost as much power consumption as the classical EAR approach.
---
paper_title: Openflow-based server load balancing gone wild

paper_content:

Today's data centers host online services on multiple servers, with a front-end load balancer directing each client request to a particular replica. Dedicated load balancers are expensive and quickly become a single point of failure and congestion. The OpenFlow standard enables an alternative approach where the commodity network switches divide traffic over the server replicas, based on packet-handling rules installed by a separate controller. However, the simple approach of installing a separate rule for each client connection (or "microflow") leads to a huge number of rules in the switches and a heavy load on the controller. We argue that the controller should exploit switch support for wildcard rules for a more scalable solution that directs large aggregates of client traffic to server replicas. We present algorithms that compute concise wildcard rules that achieve a target distribution of the traffic, and automatically adjust to changes in load-balancing policies without disrupting existing connections. We implement these algorithms on top of the NOX OpenFlow controller, evaluate their effectiveness, and propose several avenues for further research.
---
paper_title: Optimizing the "one big switch" abstraction in software-defined networks

paper_content:

Software Defined Networks (SDNs) support diverse network policies by offering direct, network-wide control over how switches handle traffic. Unfortunately, many controller platforms force applications to grapple simultaneously with end-to-end connectivity constraints, routing policy, switch memory limits, and the hop-by-hop interactions between forwarding rules. We believe solutions to this complex problem should be factored in to three distinct parts: (1) high-level SDN applications should define their end-point connectivity policy on top of a "one big switch" abstraction; (2) a mid-level SDN infrastructure layer should decide on the hop-by-hop routing policy; and (3) a compiler should synthesize an effective set of forwarding rules that obey the user-defined policies and adhere to the resource constraints of the underlying hardware. In this paper, we define and implement our proposed architecture, present efficient rule-placement algorithms that distribute forwarding policies across general SDN networks while managing rule-space constraints, and show how to support dynamic, incremental update of policies. We evaluate the effectiveness of our algorithms analytically by providing complexity bounds on their running time and rule space, as well as empirically, using both synthetic benchmarks, and real-world firewall and routing policies.
---
paper_title: Optimizing rules placement in OpenFlow networks: trading routing for better efficiency

paper_content:

The idea behind Software Defined Networking (SDN) is to conceive the network as one programmable entity rather than a set of devices to manually configure, and OpenFlow meets this objective. In OpenFlow, a centralized programmable controller installs rules onto switches to implement policies. However, this flexibility comes at the expense of extra overhead as the number of rules might exceed the memory capacity of switches, which raises the question of how to place most profitable rules on board. Solutions proposed so far strictly impose paths to be followed inside the network. We advocate instead that we can trade routing requirements within the network to concentrate on where to forward traffic, not how to do it. As an illustration of the concept, we propose an optimization problem that gets the maximum amount of traffic delivered according to policies and the actual dimensioning of the network. The traffic that cannot be accommodated is forwarded to the controller that has the capacity to process it further. We also demonstrate that our approach permits a better utilization of scarce resources in the network.
---
paper_title: MoRule: Optimized rule placement for mobile users in SDN-enabled access networks

paper_content:

With the surging popularity of smartphones and tablets, mobile network traffic has dramatically increased in recent years. Software defined network (SDN) provides a scalable and flexible structure to simplify network traffic management. It has been shown that rule placement plays an important role in the performance of SDN. However, since most existing work considers static network topologies of wired networks, it cannot be directly applied for mobile networks. In this paper, we propose MoRule, an efficient rule management scheme to optimize the rule placement for mobile users. To deal with the challenges of user mobility and rule capacity constraints of switches, we design a heuristic algorithm with low-complexity to minimize the rule space occupation while guaranteeing that the mobile traffic processed by local switches is no less than a threshold. By conducting extensive simulations, we demonstrate that our proposed algorithm significantly outperforms random solutions under various network settings.
---
paper_title: OFFICER: A general optimization framework for OpenFlow rule allocation and endpoint policy enforcement

paper_content:

The Software-Defined Networking approach permits to realize new policies. In OpenFlow in particular, a controller decides on behalf of the switches which forwarding rules must be installed and where. However with this flexibility comes the challenge of the computation of a rule allocation matrix meeting both high-level policies and the network constraints such as memory or link capacity limitations. Nevertheless, in many situations (e.g., data-center networks), the exact path followed by packets does not severely impact performances as long as packets are delivered according to the endpoint policy. It is thus possible to deviate part of the traffic to alternative paths so to better use network resources without violating the endpoint policy. In this paper, we propose a linear optimization model of the rule allocation problem in resource constrained OpenFlow networks with relaxing routing policy. We show that the general problem is NP-hard and propose a polynomial time heuristic, called OFFICER, which aims to maximize the amount of carried traffic in under-provisioned networks. Our numerical evaluation on four different topologies shows that exploiting various paths allows to increase the amount of traffic supported by the network without significantly increasing the path length.
---
paper_title: Maturing of OpenFlow and Software Defined Networking through Deployments

paper_content:

Software-defined Networking (SDN) has emerged as a new paradigm of networking that enables network operators, owners, vendors, and even third parties to innovate and create new capabilities at a faster pace. The SDN paradigm shows potential for all domains of use, including data centers, cellular providers, service providers, enterprises, and homes. Over a three-year period, we deployed SDN technology at our campus and at several other campuses nation-wide with the help of partners. These deployments included the first-ever SDN prototype in a lab for a (small) global deployment. The four-phased deployments and demonstration of new networking capabilities enabled by SDN played an important role in maturing SDN and its ecosystem. We share our experiences and lessons learned that have to do with demonstration of SDN's potential; its influence on successive versions of OpenFlow specification; evolution of SDN architecture; performance of SDN and various components; and growing the ecosystem.
---
paper_title: Network traffic characteristics of data centers in the wild

paper_content:

Although there is tremendous interest in designing improved networks for data centers, very little is known about the network-level traffic characteristics of data centers today. In this paper, we conduct an empirical study of the network traffic in 10 data centers belonging to three different categories, including university, enterprise campus, and cloud data centers. Our definition of cloud data centers includes not only data centers employed by large online service providers offering Internet-facing applications but also data centers used to host data-intensive (MapReduce style) applications). We collect and analyze SNMP statistics, topology and packet-level traces. We examine the range of applications deployed in these data centers and their placement, the flow-level and packet-level transmission properties of these applications, and their impact on network and link utilizations, congestion and packet drops. We describe the implications of the observed traffic patterns for data center internal traffic engineering as well as for recently proposed architectures for data center networks.
---
paper_title: FlowMaster: Early Eviction of Dead Flow on SDN Switches

paper_content:

High performance switches employ extremely low latency memory subsystems in an effort to reap the lowest feasible end-to-end flow level latencies. Their capacities are extremely valuable as the size of these memories is limited due to several architectural constraints such as power and silicon area. This necessity is further exacerbated with the emergence of Software Defined Networks SDN where fine-grained flow definitions lead to explosion in the number of flow entries. In this paper, we propose FlowMaster, a speculative mechanism to update the flow table by predicting when an entry becomes stale and evict the same early to accommodate new entries. We collage the observations from predictors into a Markov based learning predictor that predicts whether a flow is valuable any more. Our experiments confirm that FlowMaster enables efficient usage of flow tables thereby reducing the discard rate from flow table by orders of magnitude and in some cases, eliminating discards completely.
---
paper_title: Infinite CacheFlow in software-defined networks

paper_content:

Software-Defined Networking (SDN) enables fine-grained policies for firewalls, load balancers, routers, traffic monitoring, and other functionality. While Ternary Content Addressable Memory (TCAM) enables OpenFlow switches to process packets at high speed based on multiple header fields, today's commodity switches support just thousands to tens of thousands of rules. To realize the potential of SDN on this hardware, we need efficient ways to support the abstraction of a switch with arbitrarily large rule tables. To do so, we define a hardware-software hybrid switch design that relies on rule caching to provide large rule tables at low cost. Unlike traditional caching solutions, we neither cache individual rules (to respect rule dependencies) nor compress rules (to preserve the per-rule traffic counts). Instead we ``splice'' long dependency chains to cache smaller groups of rules while preserving the semantics of the network policy. Our design satisfies four core criteria: (1) elasticity (combining the best of hardware and software switches), (2) transparency (faithfully supporting native OpenFlow semantics, including traffic counters), (3) fine-grained rule caching (placing popular rules in the TCAM, despite dependencies on less-popular rules), and (4) adaptability (to enable incremental changes to the rule caching as the policy changes).
---
paper_title: Scalable rule management for data centers

paper_content:

Cloud operators increasingly need more and more fine-grained rules to better control individual network flows for various traffic management policies. In this paper, we explore automated rule management in the context of a system called vCRIB (a virtual Cloud Rule Information Base), which provides the abstraction of a centralized rule repository. The challenge in our approach is the design of algorithms that automatically off-load rule processing to overcome resource constraints on hypervisors and/or switches, while minimizing redirection traffic overhead and responding to system dynamics. vCRIB contains novel algorithms for finding feasible rule placements and adapting traffic overhead induced by rule placement in the face of traffic changes and VM migration. We demonstrate that vCRIB can find feasible rule placements with less than 10% traffic overhead even in cases where the traffic-optimal rule placement may be infeasible with respect to hypervisor CPU or memory constraints.
---
paper_title: SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks

paper_content:

OpenFlow is a popular network architecture where a logically centralized controller (the control plane) is physically decoupled from all forwarding switches (the data plane). Through this controller, the OpenFlow framework enables flow level granularity in switches thereby providing monitoring and control over each individual flow. Among other things, this architecture comes at the cost of placing significant stress on switch state size and overburdening the controller in various traffic engineering scenarios such as dynamic re-routing of flows. Storing a flow match rule and flow counter at every switch along a flow's path results in many thousands of entries per switch. Dynamic rerouting of a flow, either in an attempt to utilize less congested paths, or as a consequence of virtual machine migration, results in controller intervention at every switch along the old and new paths. In the absence of careful orchestration of flow storage and controller involvement, OpenFlow will be unable to scale to anticipated production data center sizes. In this context, we present SwitchReduce - a system to reduce switch state and controller involvement in OpenFlow networks. SwitchReduce is founded on the observation that the number of flow match rules at any switch should be no more than the set of unique processing actions it has to take on incoming flows. Additionally, the flow counters for every unique flow may be maintained at only one switch in the network. We have implemented SwitchReduce as a NOX controller application. Simulation results with real data center traffic traces reveal that SwitchReduce can reduce flow entries by up to approximately 49% on first hop switches, and up to 99.9% on interior switches, while reducing flow counters by 75% on average.
---
paper_title: vCRIB: virtualized rule management in the cloud

paper_content:

Cloud operators increasingly need many fine-grained rules to better control individual network flows for various management tasks. While previous approaches have advocated placing rules either on hypervisors or switches, we argue that future data centers would benefit from leveraging rule processing capabilities at both for better scalability and performance. In this paper, we propose vCRIB, a virtualized Cloud Rule Information Base that allows operators to freely define different management policies without the need to consider underlying resource constraints. The challenge in our approach is the design of a vCRIB manager that automatically partitions and places rules at both hypervisors and switches to achieve a good trade-off between resource usage and performance.
---
paper_title: PAST: scalable ethernet for data centers

paper_content:

We present PAST, a novel network architecture for data center Ethernet networks that implements a Per-Address Spanning Tree routing algorithm. PAST preserves Ethernet's self-configuration and mobility support while increasing its scalability and usable bandwidth. PAST is explicitly designed to accommodate unmodified commodity hosts and Ethernet switch chips. Surprisingly, we find that PAST can achieve performance comparable to or greater than Equal-Cost Multipath (ECMP) forwarding, which is currently limited to layer-3 IP networks, without any multipath hardware support. In other words, the hardware and firmware changes proposed by emerging standards like TRILL are not required for high-performance, scalable Ethernet networks. We evaluate PAST on Fat Tree, HyperX, and Jellyfish topologies, and show that it is able to capitalize on the advantages each offers. We also describe an OpenFlow-based implementation of PAST in detail.
---
paper_title: DevoFlow: scaling flow management for high-performance networks

paper_content:

OpenFlow is a great concept, but its original design imposes excessive overheads. It can simplify network and traffic management in enterprise and data center environments, because it enables flow-level control over Ethernet switching and provides global visibility of the flows in the network. However, such fine-grained control and visibility comes with costs: the switch-implementation costs of involving the switch's control-plane too often and the distributed-system costs of involving the OpenFlow controller too frequently, both on flow setups and especially for statistics-gathering. ::: In this paper, we analyze these overheads, and show that OpenFlow's current design cannot meet the needs of high-performance networks. We design and evaluate DevoFlow, a modification of the OpenFlow model which gently breaks the coupling between control and global visibility, in a way that maintains a useful amount of visibility without imposing unnecessary costs. We evaluate DevoFlow through simulations, and find that it can load-balance data center traffic as well as fine-grained solutions, without as much overhead: DevoFlow uses 10--53 times fewer flow table entries at an average switch, and uses 10--42 times fewer control messages.
---
paper_title: Shadow MACs: scalable label-switching for commodity ethernet

paper_content:

While SDN promises fine-grained, dynamic control of the network, in practice limited switch TCAM rule space restricts most forwarding to be coarse-grained. As an alternative, we demonstrate that using destination MAC addresses as opaque forwarding labels allows an SDN controller to leverage large MAC (L2) forwarding tables to manage a plethora of fine-grained paths. In this shadow MAC model, the SDN controller can install MAC rewrite rules at the network edge to guide traffic on to intelligently selected paths to balance traffic, avoid failed links, or route flows through middleboxes. Further, by decoupling the network edge from the core, we address many other problems with SDN, including consistent network updates, fast rerouting, and multipathing with end-to-end control.
---
paper_title: Effective switch memory management in OpenFlow networks

paper_content:

OpenFlow networks require installation of flow rules in a limited capacity switch memory (Ternary Content Addressable Memory or TCAMs, in particular) from a logically centralized controller. A controller can manage the switch memory in an OpenFlow network through events that are generated by the switch at discrete time intervals. Recent studies have shown that data centers can have up to 10,000 network flows per second per server rack today. Increasing the TCAM size to accommodate these large number of flow rules is not a viable solution since TCAM is costly and power hungry. Current OpenFlow controllers handle this issue by installing flow rules with a default idle timeout after which the switch automatically evicts the rule from its TCAM. This results in inefficient usage of switch memory for short lived flows when the timeout is too high and in increased controller workload for frequent flows when the timeout is too low. In this context, we present SmartTime - an OpenFlow controller system that combines an adaptive timeout heuristic to compute efficient idle timeouts with proactive eviction of flow rules, which results in effective utilization of TCAM space while ensuring that TCAM misses (or controller load) does not increase. To the best of our knowledge, SmartTime is the first real implementation of an intelligent flow management strategy in an OpenFlow controller that can be deployed in current OpenFlow networks. In our experiments using multiple real data center packet traces and cache sizes, SmartTime adaptive policy consistently outperformed the best performing static idle timeout policy or random eviction policy by up to 58% in terms of total cost.
---
paper_title: A flow entry management scheme for reducing controller overhead

paper_content:

In this paper, we advocate addressing the communication overhead problem between OpenFlow controllers and OpenFlow switches due to table-miss in a flow table. It may cause the communication overhead between controllers and switches because a switch has to send packet-in message to a controller for processing table-missed flows. We propose a simple flow entry management scheme for reducing the controller overhead by increasing the flow entry matching ratio. By using an LRU caching algorithm, a switch can keep the flow entries in a flow table as many as possible, and then the flow entry matching ratio can be increased.
---
paper_title: Network traffic characteristics of data centers in the wild

paper_content:

Although there is tremendous interest in designing improved networks for data centers, very little is known about the network-level traffic characteristics of data centers today. In this paper, we conduct an empirical study of the network traffic in 10 data centers belonging to three different categories, including university, enterprise campus, and cloud data centers. Our definition of cloud data centers includes not only data centers employed by large online service providers offering Internet-facing applications but also data centers used to host data-intensive (MapReduce style) applications). We collect and analyze SNMP statistics, topology and packet-level traces. We examine the range of applications deployed in these data centers and their placement, the flow-level and packet-level transmission properties of these applications, and their impact on network and link utilizations, congestion and packet drops. We describe the implications of the observed traffic patterns for data center internal traffic engineering as well as for recently proposed architectures for data center networks.
---
paper_title: An adaptive scheme for data forwarding in software defined network

paper_content:

Software Defined Network (SDN) is undergoing an increasingly high popularity among various schemes of networking deployment. The main advantage of SDN lies in its flexibility in controlling network traffic, which arises from decoupling the control plane and the data plane of network devices. However, despite of the valuable merits of SDN, the outage of data forwarding should not be ignored. The drawback mainly results from the length limitation of switch flow tables, the congestion between controllers and switches, and the deficiency of the controller capacity, which are all closely related to the timeout mechanism of flow table. In our study, the deficiency of SDN system will be analyzed explicitly. Moreover, we propose an adaptive control mechanism aiming at optimizing the idle timeout reset of flow tables and cooperation between controllers and switches. Our mechanism achieves higher matching ratio of flow tables as well as alleviates the congestion in the control channel, enabling more fluent data forwarding in SDN.
---
paper_title: FlowMaster: Early Eviction of Dead Flow on SDN Switches

paper_content:

High performance switches employ extremely low latency memory subsystems in an effort to reap the lowest feasible end-to-end flow level latencies. Their capacities are extremely valuable as the size of these memories is limited due to several architectural constraints such as power and silicon area. This necessity is further exacerbated with the emergence of Software Defined Networks SDN where fine-grained flow definitions lead to explosion in the number of flow entries. In this paper, we propose FlowMaster, a speculative mechanism to update the flow table by predicting when an entry becomes stale and evict the same early to accommodate new entries. We collage the observations from predictors into a Markov based learning predictor that predicts whether a flow is valuable any more. Our experiments confirm that FlowMaster enables efficient usage of flow tables thereby reducing the discard rate from flow table by orders of magnitude and in some cases, eliminating discards completely.
---
paper_title: An efficient flow cache algorithm with improved fairness in Software-Defined Data Center Networks

paper_content:

The use of Software-Defined Networking (SDN) with OpenFlow-enabled switches in Data Centers has received much attention from researchers and industries. One of the major issues in OpenFlow switch is the limited size of the flow table resulting in evictions of flows from the flow table. From Data Center traffic characteristics, we observe that elephant flows are very large in size (data volume) but few in numbers when compared to mice flows. Thus, Elephant flows are more likely to be evicted, due to the limited size of the switch flow table causing additional traffic to the controller. We propose a differential flow cache framework that achieves fairness and efficient cache maintenance with fast lookup and reduced cache miss ratio. The framework uses a hash-based placement and localized Least Recently Used (LRU)-based replacement mechanisms.
---
paper_title: Rule Optimization for Real-Time Query Service in Software-Defined Internet of Vehicles

paper_content:

Internet of Vehicles (IoV) has recently gained considerable attentions from both industry and research communities since the development of communication technology and smart city. However, a proprietary and closed way of operating hardwares in network equipments slows down the progress of new services deployment and extension in IoV. Moreover, the tightly coupled control and data planes in traditional networks significantly increase the complexity and cost of network management. By proposing a novel architecture, called Software-Defined Internet of Vehicles (SDIV), we adopt the software-defined network (SDN) architecture to address these problems by leveraging its separation of the control plane from the data plane and a uniform way to configure heterogeneous switches. However, the characteristics of IoV introduce the very challenges in rule installation due to the limited size of Flow Tables at OpenFlow-enabled switches which are the main component of SDN. It is necessary to build compact Flow Tables for the scalability of IoV. Accordingly, we develop a rule optimization approach for real-time query service in SDIV. Specifically, we separate wired data plane from wireless data plane and use multicast address in wireless data plane. Furthermore, we introduce a destination-driven model in wired data plane for reducing the number of rules at switches. Experiments show that our rule optimization strategy reduces the number of rules while keeping the performance of data transmission.
---
paper_title: DevoFlow: scaling flow management for high-performance networks

paper_content:

OpenFlow is a great concept, but its original design imposes excessive overheads. It can simplify network and traffic management in enterprise and data center environments, because it enables flow-level control over Ethernet switching and provides global visibility of the flows in the network. However, such fine-grained control and visibility comes with costs: the switch-implementation costs of involving the switch's control-plane too often and the distributed-system costs of involving the OpenFlow controller too frequently, both on flow setups and especially for statistics-gathering. ::: In this paper, we analyze these overheads, and show that OpenFlow's current design cannot meet the needs of high-performance networks. We design and evaluate DevoFlow, a modification of the OpenFlow model which gently breaks the coupling between control and global visibility, in a way that maintains a useful amount of visibility without imposing unnecessary costs. We evaluate DevoFlow through simulations, and find that it can load-balance data center traffic as well as fine-grained solutions, without as much overhead: DevoFlow uses 10--53 times fewer flow table entries at an average switch, and uses 10--42 times fewer control messages.
---
paper_title: NOX: towards an operating system for networks

paper_content:

As anyone who has operated a large network can attest, enterprise networks are difficult to manage. That they have remained so despite significant commercial and academic efforts suggests the need for a different network management paradigm. Here we turn to operating systems as an instructive example in taming management complexity. In the early days of computing, programs were written in machine languages that had no common abstractions for the underlying physical resources. This made programs hard to write, port, reason about, and debug. Modern operating systems facilitate program development by providing controlled access to high-level abstractions for resources (e.g., memory, storage, communication) and information (e.g., files, directories). These abstractions enable programs to carry out complicated tasks safely and efficiently on a wide variety of computing hardware. In contrast, networks are managed through low-level configuration of individual components. Moreover, these configurations often depend on the underlying network; for example, blocking a user’s access with an ACL entry requires knowing the user’s current IP address. More complicated tasks require more extensive network knowledge; forcing guest users’ port 80 traffic to traverse an HTTP proxy requires knowing the current network topology and the location of each guest. In this way, an enterprise network resembles a computer without an operating system, with network-dependent component configuration playing the role of hardware-dependent machine-language programming. What we clearly need is an “operating system” for networks, one that provides a uniform and centralized programmatic interface to the entire network. Analogous to the read and write access to various resources provided by computer operating systems, a network operating system provides the ability to observe and control a network. A network operating system does not manage the network itself; it merely provides a programmatic interface. Applications implemented on top of the network operating system perform the actual management tasks. The programmatic interface should be general enough to support a broad spectrum of network management applications. Such a network operating system represents two major conceptual departures from the status quo. First, the network operating system presents programs with a centralized programming model; programs are written as if the entire network were present on a single machine (i.e., one would use Dijkstra to compute shortest paths, not Bellman-Ford). This requires (as in [3, 8, 14] and elsewhere) centralizing network state. Second, programs are written in terms of high-level abstractions (e.g., user and host names), not low-level configuration parameters (e.g., IP and MAC addresses). This allows management directives to be enforced independent of the underlying network topology, but it requires that the network operating system carefully maintain the bindings (i.e., mappings) between these abstractions and the low-level configurations. Thus, a network operating system allows management applications to be written as centralized programs over highlevel names as opposed to the distributed algorithms over low-level addresses we are forced to use today. While clearly a desirable goal, achieving this transformation from distributed algorithms to centralized programming presents significant technical challenges, and the question we pose here is: Can one build a network operating system at significant scale?
---
paper_title: Constructing optimal IP routing tables

paper_content:

The Border Gateway Protocol (BGP) populates Internet backbone routers with routes or prefixes. We present an algorithm to locally compute (without any modification to BGP) equivalent forwarding tables that provably contain the minimal number of prefixes. For large backbone routers, the Optimal Routing Table Constructor (ORTC) algorithm that we present produces routing tables with roughly 60% of the original number of prefixes. The publicly available MaeEast database with 41315 prefixes reduces to 23007 prefixes when ORTC is applied. We present performance measurements on four publicly available databases and a formal proof that ORTC does produce the optimal set of routes.
---
paper_title: Source flow: handling millions of flows on flow-based nodes

paper_content:

Flow-based networks such as OpenFlow-based networks have difficulty handling a large number of flows in a node due to the capacity limitation of search engine devices such as ternary content-addressable memory (TCAM). One typical solution of this problem would be to use MPLS-like tunneling, but this approach spoils the advantage of flow-by-flow path selection for load-balancing or QoS. We demonstrate a method named "Source Flow" that allows us to handle a huge amount of flows without changing the granularity of flows. By using our method, expensive and power consuming search engine devices can be removed from the core nodes, and the network can grow pretty scalable. In our demo, we construct a small network that consists of small number of OpenFlow switches, a single OpenFlow controller, and end-hosts. The hosts generate more than one million flows simultaneously and the flows are controlled on a per-flow-basis. All active flows are monitored and visualized on a user interface and the user interface allows audiences to confirm if our method is feasible and deployable.
---
paper_title: The joint optimization of rules allocation and traffic engineering in Software Defined Network

paper_content:

Software-Defined Network (SDN) is a promising network paradigm that separates the control plane and data plane in the network. It has shown great advantages in simplifying network management such that new functions can be easily supported without physical access to the network switches. However, Ternary Content Addressable Memory (TCAM), as a critical hardware storing rules for high-speed packet processing in SDN-enabled devices, can be supplied to each device with very limited quantity because it is expensive and energy-consuming. To efficiently use TCAM resources, we propose a rule multiplexing scheme, in which the same set of rules deployed on each node apply to the whole flow of a session going through but towards different paths. Based on this scheme, we study the rule placement problem with the objective of minimizing rule space occupation for multiple unicast sessions under QoS constraints.We formulate the optimization problem jointly considering routing engineering and rule placement under both existing and our rule multiplexing schemes. Finally, extensive simulations are conducted to show that our proposals significantly outperform existing solutions.
---
paper_title: Bit Weaving: A Non-Prefix Approach to Compressing Packet Classifiers in TCAMs

paper_content:

Ternary content addressable memories (TCAMs) have become the de facto standard in industry for fast packet classification. Unfortunately, TCAMs have limitations of small capacity, high power consumption, high heat generation, and high cost. The well-known range expansion problem exacerbates these limitations as each classifier rule typically has to be converted to multiple TCAM rules. One method for coping with these limitations is to use compression schemes to reduce the number of TCAM rules required to represent a classifier. Unfortunately, all existing compression schemes only produce prefix classifiers. Thus, they all miss the compression opportunities created by non-prefix ternary classifiers. In this paper, we propose bit weaving, the first non-prefix compression scheme. Bit weaving is based on the observation that TCAM entries that have the same decision and whose predicates differ by only one bit can be merged into one entry by replacing the bit in question with . Bit weaving consists of two new techniques, bit swapping and bit merging, to first identify and then merge such rules together. The key advantages of bit weaving are that it runs fast, it is effective, and it is composable with other TCAM optimization methods as a pre/post-processing routine. We implemented bit weaving and conducted experiments on both real-world and synthetic packet classifiers. Our experimental results show the following: 1) bit weaving is an effective standalone compression technique (it achieves an average compression ratio of 23.6%); 2) bit weaving finds compression opportunities that other methods miss. Specifically, bit weaving improves the prior TCAM optimization techniques of TCAM Razor and Topological Transformation by an average of 12.8% and 36.5%, respectively.
---
paper_title: Infinite CacheFlow in software-defined networks

paper_content:

Software-Defined Networking (SDN) enables fine-grained policies for firewalls, load balancers, routers, traffic monitoring, and other functionality. While Ternary Content Addressable Memory (TCAM) enables OpenFlow switches to process packets at high speed based on multiple header fields, today's commodity switches support just thousands to tens of thousands of rules. To realize the potential of SDN on this hardware, we need efficient ways to support the abstraction of a switch with arbitrarily large rule tables. To do so, we define a hardware-software hybrid switch design that relies on rule caching to provide large rule tables at low cost. Unlike traditional caching solutions, we neither cache individual rules (to respect rule dependencies) nor compress rules (to preserve the per-rule traffic counts). Instead we ``splice'' long dependency chains to cache smaller groups of rules while preserving the semantics of the network policy. Our design satisfies four core criteria: (1) elasticity (combining the best of hardware and software switches), (2) transparency (faithfully supporting native OpenFlow semantics, including traffic counters), (3) fine-grained rule caching (placing popular rules in the TCAM, despite dependencies on less-popular rules), and (4) adaptability (to enable incremental changes to the rule caching as the policy changes).
---
paper_title: Compressing rectilinear pictures and minimizing access control lists

paper_content:

We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in common graphics software packages. Here the goal is to create a colored rectilinear pattern within an initially white rectangular canvas, and the basic operation is to choose a subrectangle and paint it a single color, overwriting all previous colors in the rectangle. Rectangle Rule List (RRL) minimization is the problem of finding the shortest list of rules needed to create a given pattern. ACL minimization is a restricted version of this problem where the set of allowed rectangles must correspond to pairs of IP address prefixes. Motivated by the ACL application, we study the special cases of RRL and ACL minimization in which all rectangles must be strips that extend either the full width or the full height of the canvas (strip-rules). We provide several equivalent characterizations of the patterns achievable using strip-rules and present polynomial-time algorithms for optimally constructing such patterns when, as in the ACL application, the only colors are black and white (permit or deny). We also show that RRL minimization is NP-hard in general and provide O(min(n1/3, OPT1/2))-approximation algorithms for general RRL and ACL minimization by exploiting our results about strip-rule patterns.
---
paper_title: Rule Optimization for Real-Time Query Service in Software-Defined Internet of Vehicles

paper_content:

Internet of Vehicles (IoV) has recently gained considerable attentions from both industry and research communities since the development of communication technology and smart city. However, a proprietary and closed way of operating hardwares in network equipments slows down the progress of new services deployment and extension in IoV. Moreover, the tightly coupled control and data planes in traditional networks significantly increase the complexity and cost of network management. By proposing a novel architecture, called Software-Defined Internet of Vehicles (SDIV), we adopt the software-defined network (SDN) architecture to address these problems by leveraging its separation of the control plane from the data plane and a uniform way to configure heterogeneous switches. However, the characteristics of IoV introduce the very challenges in rule installation due to the limited size of Flow Tables at OpenFlow-enabled switches which are the main component of SDN. It is necessary to build compact Flow Tables for the scalability of IoV. Accordingly, we develop a rule optimization approach for real-time query service in SDIV. Specifically, we separate wired data plane from wireless data plane and use multicast address in wireless data plane. Furthermore, we introduce a destination-driven model in wired data plane for reducing the number of rules at switches. Experiments show that our rule optimization strategy reduces the number of rules while keeping the performance of data transmission.
---
paper_title: Palette: Distributing tables in software-defined networks

paper_content:

In software-defined networks (SDNs), the network controller first formulates abstract network-wide policies, and then implements them in the forwarding tables of network switches. However, fast SDN tables often cannot scale beyond a few hundred entries. This is because they typically include wildcards, and therefore are implemented using either expensive and power-hungry TCAMs, or complex and slow data structures. This paper presents the Palette distribution framework for decomposing large SDN tables into small ones and then distributing them across the network, while preserving the overall SDN policy semantics. Palette helps balance the sizes of the tables across the network, as well as reduce the total number of entries by sharing resources among different connections. It copes with two NP-hard optimization problems: Decomposing a large SDN table into equivalent subtables, and distributing the subtables such that each connection traverses each type of subtable at least once. To implement the Palette distribution framework, we introduce graph-theoretical formulations and algorithms, and show that they achieve close-to-optimal results in practice.
---
paper_title: SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks

paper_content:

OpenFlow is a popular network architecture where a logically centralized controller (the control plane) is physically decoupled from all forwarding switches (the data plane). Through this controller, the OpenFlow framework enables flow level granularity in switches thereby providing monitoring and control over each individual flow. Among other things, this architecture comes at the cost of placing significant stress on switch state size and overburdening the controller in various traffic engineering scenarios such as dynamic re-routing of flows. Storing a flow match rule and flow counter at every switch along a flow's path results in many thousands of entries per switch. Dynamic rerouting of a flow, either in an attempt to utilize less congested paths, or as a consequence of virtual machine migration, results in controller intervention at every switch along the old and new paths. In the absence of careful orchestration of flow storage and controller involvement, OpenFlow will be unable to scale to anticipated production data center sizes. In this context, we present SwitchReduce - a system to reduce switch state and controller involvement in OpenFlow networks. SwitchReduce is founded on the observation that the number of flow match rules at any switch should be no more than the set of unique processing actions it has to take on incoming flows. Additionally, the flow counters for every unique flow may be maintained at only one switch in the network. We have implemented SwitchReduce as a NOX controller application. Simulation results with real data center traffic traces reveal that SwitchReduce can reduce flow entries by up to approximately 49% on first hop switches, and up to 99.9% on interior switches, while reducing flow counters by 75% on average.
---
paper_title: Optimizing the "one big switch" abstraction in software-defined networks

paper_content:

Software Defined Networks (SDNs) support diverse network policies by offering direct, network-wide control over how switches handle traffic. Unfortunately, many controller platforms force applications to grapple simultaneously with end-to-end connectivity constraints, routing policy, switch memory limits, and the hop-by-hop interactions between forwarding rules. We believe solutions to this complex problem should be factored in to three distinct parts: (1) high-level SDN applications should define their end-point connectivity policy on top of a "one big switch" abstraction; (2) a mid-level SDN infrastructure layer should decide on the hop-by-hop routing policy; and (3) a compiler should synthesize an effective set of forwarding rules that obey the user-defined policies and adhere to the resource constraints of the underlying hardware. In this paper, we define and implement our proposed architecture, present efficient rule-placement algorithms that distribute forwarding policies across general SDN networks while managing rule-space constraints, and show how to support dynamic, incremental update of policies. We evaluate the effectiveness of our algorithms analytically by providing complexity bounds on their running time and rule space, as well as empirically, using both synthetic benchmarks, and real-world firewall and routing policies.
---
paper_title: Too Many SDN Rules? Compress Them with MINNIE

paper_content:

Software Defined Networking (SDN) is gaining momentum with the support of major manufacturers. While it brings flexibility in the management of flows within the data center fabric, this flexibility comes at the cost of smaller routing table capacities. In this paper, we investigate compression techniques to reduce the forwarding information base (FIB) of SDN switches. We validate our algorithm, called MINNIE, on a real testbed able to emulate a 20 switches fat tree architecture. We demonstrate that even with a small number of clients, the limit in terms of number of rules is reached if no compression is performed, increasing the delay of all new incoming flows. MINNIE, on the other hand, reduces drastically the number of rules that need to be stored with a limited impact on the packet loss rate. We also evaluate the actual switching and reconfiguration times and the delay introduced by the communications with the controller.
---
paper_title: An Adaptable Rule Placement for Software-Defined Networks

paper_content:

There is a strong trend in networking to move towards Software-Defined Networks (SDN). SDNs enable easier network configuration through a separation between a centralized controller and a distributed data plane comprising a network of switches. The controller implements network policies through installing rules on switches. Recently the "Big Switch" abstraction [1] was proposed as a specification mechanism for high-level network behavior, i.e., the network policies. The network operating system or compiler can use his specification for placing rules on individual switches. However, this is constrained by the limited capacity of the Ternary Content Addressable Memories (TCAMs) used for rules in each switch. We propose an Integer Linear Programming (ILP) based solution for placing rules on switches for a given firewall policy while optimizing for the total number of rules and meeting the switch capacity constraints. Experimental results demonstrate that our approach is scalable to practical sized networks.
---
paper_title: Wildcard Compression of Inter-Domain Routing Tables for OpenFlow-Based Software-Defined Networking

paper_content:

In this paper we consider carrier networks using only OpenFlow switches instead of IP routers. Accommodating the full forwarding information base (FIB) of IP routers in the switches is difficult because the BGP routing tables in the default-free zone currently contain about 500,000 entries and switches have only little capacity in their fast and expensive TCAM memory. The objective of this paper is the compression of the FIB in acceptable time to minimize the TCAM requirements of switches. The benchmark is simple prefix aggregation as it is common in IP networks where longest-prefix matching is applied. In contrast, OpenFlow-based switches can match general wildcard expressions with priorities. Starting from a minimum-size prefix-based FIB, we further compress that FIB by allowing general wildcard expressions utilizing the Espresso heuristic that is commonly used for logic minimization. As the computation time of Espresso is challenging for large inputs, we provide means to trade computation time against compression efficiency. Our results show that today's FIB sizes can be reduced by 17% saving up to 40,000 entries and the compression time can be limited to 1 -- 2s sacrificing only 1% -- 2% compression ratio.
---
paper_title: OFFICER: A general optimization framework for OpenFlow rule allocation and endpoint policy enforcement

paper_content:

The Software-Defined Networking approach permits to realize new policies. In OpenFlow in particular, a controller decides on behalf of the switches which forwarding rules must be installed and where. However with this flexibility comes the challenge of the computation of a rule allocation matrix meeting both high-level policies and the network constraints such as memory or link capacity limitations. Nevertheless, in many situations (e.g., data-center networks), the exact path followed by packets does not severely impact performances as long as packets are delivered according to the endpoint policy. It is thus possible to deviate part of the traffic to alternative paths so to better use network resources without violating the endpoint policy. In this paper, we propose a linear optimization model of the rule allocation problem in resource constrained OpenFlow networks with relaxing routing policy. We show that the general problem is NP-hard and propose a polynomial time heuristic, called OFFICER, which aims to maximize the amount of carried traffic in under-provisioned networks. Our numerical evaluation on four different topologies shows that exploiting various paths allows to increase the amount of traffic supported by the network without significantly increasing the path length.
---
paper_title: Fast incremental flow table aggregation in SDN

paper_content:

In OpenFlow-based SDN, flow tables are TCAM-hungry and commodity switches suffer from limited concrete flow table size. One method for coping with the limitations is to use aggregation schemes to reduce the number of flow entries required to represent the same forwarding semantics. Unfortunately, the aggregation retards table updates and lengthens the updating time. During which, the data plane is inconsistent with the control plane, forwarding errors such as Reachability Failures, Forwarding Loops, Traffic Isolation and Leakage are prone to occur. Since network updates take place frequently in practice, the aggregation scheme must be efficient enough. In this paper we propose offline FFTA (Fast Flow Table Aggregation) and its online improver iFFTA to shrink the flow table size and to provide practical fast updates. iFFTA is the first online non-prefix aggregation scheme. Extensive experiments demonstrate: (1) FFTA is about 200× faster than the previously published best non-prefix aggregation scheme without loss of compression ratio on offline aggregation; and (2) iFFTA achieves about 3× faster than FFTA on online update incorporations with a loss of an acceptable compression ratio per update. Thus the user could make a combination use of FFTA and iFFTA for table aggregations: call iFFTA usually and recall the efficient FFTA once the switch is running out of concrete flow table space.
---
paper_title: Source flow: handling millions of flows on flow-based nodes

paper_content:

Flow-based networks such as OpenFlow-based networks have difficulty handling a large number of flows in a node due to the capacity limitation of search engine devices such as ternary content-addressable memory (TCAM). One typical solution of this problem would be to use MPLS-like tunneling, but this approach spoils the advantage of flow-by-flow path selection for load-balancing or QoS. We demonstrate a method named "Source Flow" that allows us to handle a huge amount of flows without changing the granularity of flows. By using our method, expensive and power consuming search engine devices can be removed from the core nodes, and the network can grow pretty scalable. In our demo, we construct a small network that consists of small number of OpenFlow switches, a single OpenFlow controller, and end-hosts. The hosts generate more than one million flows simultaneously and the flows are controlled on a per-flow-basis. All active flows are monitored and visualized on a user interface and the user interface allows audiences to confirm if our method is feasible and deployable.
---
paper_title: Network traffic characteristics of data centers in the wild

paper_content:

Although there is tremendous interest in designing improved networks for data centers, very little is known about the network-level traffic characteristics of data centers today. In this paper, we conduct an empirical study of the network traffic in 10 data centers belonging to three different categories, including university, enterprise campus, and cloud data centers. Our definition of cloud data centers includes not only data centers employed by large online service providers offering Internet-facing applications but also data centers used to host data-intensive (MapReduce style) applications). We collect and analyze SNMP statistics, topology and packet-level traces. We examine the range of applications deployed in these data centers and their placement, the flow-level and packet-level transmission properties of these applications, and their impact on network and link utilizations, congestion and packet drops. We describe the implications of the observed traffic patterns for data center internal traffic engineering as well as for recently proposed architectures for data center networks.
---
paper_title: Dynamic scheduling of network updates

paper_content:

We present Dionysus, a system for fast, consistent network updates in software-defined networks. Dionysus encodes as a graph the consistency-related dependencies among updates at individual switches, and it then dynamically schedules these updates based on runtime differences in the update speeds of different switches. This dynamic scheduling is the key to its speed; prior update methods are slow because they pre-determine a schedule, which does not adapt to runtime conditions. Testbed experiments and data-driven simulations show that Dionysus improves the median update speed by 53--88% in both wide area and data center networks compared to prior methods.
---
paper_title: DomainFlow: practical flow management method using multiple flow tables in commodity switches

paper_content:

A scalable network with high bisection bandwidth and high availability requires efficient use of the multiple paths between pairs of end hosts. OpenFlow is an innovative technology and enables fine-grained, flow level control of Ethernet switching. However, the flow table structure defined by OpenFlow is not hardware friendly and the scalability is limited by the switch device. OpenFlow is also not sufficient for fast multipath failover. To overcome these limitations, we propose DomainFlow in which the network is split into sections and exact matches are used where possible to enable practical flow management using OpenFlow for commodity switches. We applied a prototype of DomainFlow to multipath flow management in the Virtual eXtensible LAN (VXLAN) overlay network environment. The total number of flow entries was reduced to 1/128 using currently available commodity switches, which was not possible before.
---
paper_title: SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks

paper_content:

OpenFlow is a popular network architecture where a logically centralized controller (the control plane) is physically decoupled from all forwarding switches (the data plane). Through this controller, the OpenFlow framework enables flow level granularity in switches thereby providing monitoring and control over each individual flow. Among other things, this architecture comes at the cost of placing significant stress on switch state size and overburdening the controller in various traffic engineering scenarios such as dynamic re-routing of flows. Storing a flow match rule and flow counter at every switch along a flow's path results in many thousands of entries per switch. Dynamic rerouting of a flow, either in an attempt to utilize less congested paths, or as a consequence of virtual machine migration, results in controller intervention at every switch along the old and new paths. In the absence of careful orchestration of flow storage and controller involvement, OpenFlow will be unable to scale to anticipated production data center sizes. In this context, we present SwitchReduce - a system to reduce switch state and controller involvement in OpenFlow networks. SwitchReduce is founded on the observation that the number of flow match rules at any switch should be no more than the set of unique processing actions it has to take on incoming flows. Additionally, the flow counters for every unique flow may be maintained at only one switch in the network. We have implemented SwitchReduce as a NOX controller application. Simulation results with real data center traffic traces reveal that SwitchReduce can reduce flow entries by up to approximately 49% on first hop switches, and up to 99.9% on interior switches, while reducing flow counters by 75% on average.
---
paper_title: DevoFlow: scaling flow management for high-performance networks

paper_content:

OpenFlow is a great concept, but its original design imposes excessive overheads. It can simplify network and traffic management in enterprise and data center environments, because it enables flow-level control over Ethernet switching and provides global visibility of the flows in the network. However, such fine-grained control and visibility comes with costs: the switch-implementation costs of involving the switch's control-plane too often and the distributed-system costs of involving the OpenFlow controller too frequently, both on flow setups and especially for statistics-gathering. ::: In this paper, we analyze these overheads, and show that OpenFlow's current design cannot meet the needs of high-performance networks. We design and evaluate DevoFlow, a modification of the OpenFlow model which gently breaks the coupling between control and global visibility, in a way that maintains a useful amount of visibility without imposing unnecessary costs. We evaluate DevoFlow through simulations, and find that it can load-balance data center traffic as well as fine-grained solutions, without as much overhead: DevoFlow uses 10--53 times fewer flow table entries at an average switch, and uses 10--42 times fewer control messages.
---
paper_title: Shadow MACs: scalable label-switching for commodity ethernet

paper_content:

While SDN promises fine-grained, dynamic control of the network, in practice limited switch TCAM rule space restricts most forwarding to be coarse-grained. As an alternative, we demonstrate that using destination MAC addresses as opaque forwarding labels allows an SDN controller to leverage large MAC (L2) forwarding tables to manage a plethora of fine-grained paths. In this shadow MAC model, the SDN controller can install MAC rewrite rules at the network edge to guide traffic on to intelligently selected paths to balance traffic, avoid failed links, or route flows through middleboxes. Further, by decoupling the network edge from the core, we address many other problems with SDN, including consistent network updates, fast rerouting, and multipathing with end-to-end control.
---
paper_title: OFFICER: A general optimization framework for OpenFlow rule allocation and endpoint policy enforcement

paper_content:

The Software-Defined Networking approach permits to realize new policies. In OpenFlow in particular, a controller decides on behalf of the switches which forwarding rules must be installed and where. However with this flexibility comes the challenge of the computation of a rule allocation matrix meeting both high-level policies and the network constraints such as memory or link capacity limitations. Nevertheless, in many situations (e.g., data-center networks), the exact path followed by packets does not severely impact performances as long as packets are delivered according to the endpoint policy. It is thus possible to deviate part of the traffic to alternative paths so to better use network resources without violating the endpoint policy. In this paper, we propose a linear optimization model of the rule allocation problem in resource constrained OpenFlow networks with relaxing routing policy. We show that the general problem is NP-hard and propose a polynomial time heuristic, called OFFICER, which aims to maximize the amount of carried traffic in under-provisioned networks. Our numerical evaluation on four different topologies shows that exploiting various paths allows to increase the amount of traffic supported by the network without significantly increasing the path length.
---
paper_title: Optimizing rule placement in software-defined networks for energy-aware routing

paper_content:

Software-defined Networks (SDN), in particular OpenFlow, is a new networking paradigm enabling innovation through network programmability. Over past few years, many applications have been built using SDN such as server load balancing, virtual-machine migration, traffic engineering and access control. In this paper, we focus on using SDN for energy-aware routing (EAR). Since traffic load has a small influence on power consumption of routers, EAR allows to put unused links into sleep mode to save energy. SDN can collect traffic matrix and then computes routing solutions satisfying QoS while being minimal in energy consumption. However, prior works on EAR have assumed that the table of OpenFlow switch can hold an infinite number of rules. In practice, this assumption does not hold since the flow table is implemented with Ternary Content Addressable Memory (TCAM) which is expensive and power-hungry. In this paper, we propose an optimization method to minimize energy consumption for a backbone network while respecting capacity constraints on links and rule space constraints on routers. In details, we present an exact formulation using Integer Linear Program (ILP) and introduce efficient greedy heuristic algorithm. Based on simulations, we show that using this smart rule space allocation, it is possible to save almost as much power consumption as the classical EAR approach.
---
paper_title: Palette: Distributing tables in software-defined networks

paper_content:

In software-defined networks (SDNs), the network controller first formulates abstract network-wide policies, and then implements them in the forwarding tables of network switches. However, fast SDN tables often cannot scale beyond a few hundred entries. This is because they typically include wildcards, and therefore are implemented using either expensive and power-hungry TCAMs, or complex and slow data structures. This paper presents the Palette distribution framework for decomposing large SDN tables into small ones and then distributing them across the network, while preserving the overall SDN policy semantics. Palette helps balance the sizes of the tables across the network, as well as reduce the total number of entries by sharing resources among different connections. It copes with two NP-hard optimization problems: Decomposing a large SDN table into equivalent subtables, and distributing the subtables such that each connection traverses each type of subtable at least once. To implement the Palette distribution framework, we introduce graph-theoretical formulations and algorithms, and show that they achieve close-to-optimal results in practice.
---
paper_title: Optimizing the "one big switch" abstraction in software-defined networks

paper_content:

Software Defined Networks (SDNs) support diverse network policies by offering direct, network-wide control over how switches handle traffic. Unfortunately, many controller platforms force applications to grapple simultaneously with end-to-end connectivity constraints, routing policy, switch memory limits, and the hop-by-hop interactions between forwarding rules. We believe solutions to this complex problem should be factored in to three distinct parts: (1) high-level SDN applications should define their end-point connectivity policy on top of a "one big switch" abstraction; (2) a mid-level SDN infrastructure layer should decide on the hop-by-hop routing policy; and (3) a compiler should synthesize an effective set of forwarding rules that obey the user-defined policies and adhere to the resource constraints of the underlying hardware. In this paper, we define and implement our proposed architecture, present efficient rule-placement algorithms that distribute forwarding policies across general SDN networks while managing rule-space constraints, and show how to support dynamic, incremental update of policies. We evaluate the effectiveness of our algorithms analytically by providing complexity bounds on their running time and rule space, as well as empirically, using both synthetic benchmarks, and real-world firewall and routing policies.
---
paper_title: An Adaptable Rule Placement for Software-Defined Networks

paper_content:

There is a strong trend in networking to move towards Software-Defined Networks (SDN). SDNs enable easier network configuration through a separation between a centralized controller and a distributed data plane comprising a network of switches. The controller implements network policies through installing rules on switches. Recently the "Big Switch" abstraction [1] was proposed as a specification mechanism for high-level network behavior, i.e., the network policies. The network operating system or compiler can use his specification for placing rules on individual switches. However, this is constrained by the limited capacity of the Ternary Content Addressable Memories (TCAMs) used for rules in each switch. We propose an Integer Linear Programming (ILP) based solution for placing rules on switches for a given firewall policy while optimizing for the total number of rules and meeting the switch capacity constraints. Experimental results demonstrate that our approach is scalable to practical sized networks.
---
paper_title: OFFICER: A general optimization framework for OpenFlow rule allocation and endpoint policy enforcement

paper_content:

The Software-Defined Networking approach permits to realize new policies. In OpenFlow in particular, a controller decides on behalf of the switches which forwarding rules must be installed and where. However with this flexibility comes the challenge of the computation of a rule allocation matrix meeting both high-level policies and the network constraints such as memory or link capacity limitations. Nevertheless, in many situations (e.g., data-center networks), the exact path followed by packets does not severely impact performances as long as packets are delivered according to the endpoint policy. It is thus possible to deviate part of the traffic to alternative paths so to better use network resources without violating the endpoint policy. In this paper, we propose a linear optimization model of the rule allocation problem in resource constrained OpenFlow networks with relaxing routing policy. We show that the general problem is NP-hard and propose a polynomial time heuristic, called OFFICER, which aims to maximize the amount of carried traffic in under-provisioned networks. Our numerical evaluation on four different topologies shows that exploiting various paths allows to increase the amount of traffic supported by the network without significantly increasing the path length.
---
paper_title: The joint optimization of rules allocation and traffic engineering in Software Defined Network

paper_content:

Software-Defined Network (SDN) is a promising network paradigm that separates the control plane and data plane in the network. It has shown great advantages in simplifying network management such that new functions can be easily supported without physical access to the network switches. However, Ternary Content Addressable Memory (TCAM), as a critical hardware storing rules for high-speed packet processing in SDN-enabled devices, can be supplied to each device with very limited quantity because it is expensive and energy-consuming. To efficiently use TCAM resources, we propose a rule multiplexing scheme, in which the same set of rules deployed on each node apply to the whole flow of a session going through but towards different paths. Based on this scheme, we study the rule placement problem with the objective of minimizing rule space occupation for multiple unicast sessions under QoS constraints.We formulate the optimization problem jointly considering routing engineering and rule placement under both existing and our rule multiplexing schemes. Finally, extensive simulations are conducted to show that our proposals significantly outperform existing solutions.
---
paper_title: Infinite CacheFlow in software-defined networks

paper_content:

Software-Defined Networking (SDN) enables fine-grained policies for firewalls, load balancers, routers, traffic monitoring, and other functionality. While Ternary Content Addressable Memory (TCAM) enables OpenFlow switches to process packets at high speed based on multiple header fields, today's commodity switches support just thousands to tens of thousands of rules. To realize the potential of SDN on this hardware, we need efficient ways to support the abstraction of a switch with arbitrarily large rule tables. To do so, we define a hardware-software hybrid switch design that relies on rule caching to provide large rule tables at low cost. Unlike traditional caching solutions, we neither cache individual rules (to respect rule dependencies) nor compress rules (to preserve the per-rule traffic counts). Instead we ``splice'' long dependency chains to cache smaller groups of rules while preserving the semantics of the network policy. Our design satisfies four core criteria: (1) elasticity (combining the best of hardware and software switches), (2) transparency (faithfully supporting native OpenFlow semantics, including traffic counters), (3) fine-grained rule caching (placing popular rules in the TCAM, despite dependencies on less-popular rules), and (4) adaptability (to enable incremental changes to the rule caching as the policy changes).
---
paper_title: Rule Optimization for Real-Time Query Service in Software-Defined Internet of Vehicles

paper_content:

Internet of Vehicles (IoV) has recently gained considerable attentions from both industry and research communities since the development of communication technology and smart city. However, a proprietary and closed way of operating hardwares in network equipments slows down the progress of new services deployment and extension in IoV. Moreover, the tightly coupled control and data planes in traditional networks significantly increase the complexity and cost of network management. By proposing a novel architecture, called Software-Defined Internet of Vehicles (SDIV), we adopt the software-defined network (SDN) architecture to address these problems by leveraging its separation of the control plane from the data plane and a uniform way to configure heterogeneous switches. However, the characteristics of IoV introduce the very challenges in rule installation due to the limited size of Flow Tables at OpenFlow-enabled switches which are the main component of SDN. It is necessary to build compact Flow Tables for the scalability of IoV. Accordingly, we develop a rule optimization approach for real-time query service in SDIV. Specifically, we separate wired data plane from wireless data plane and use multicast address in wireless data plane. Furthermore, we introduce a destination-driven model in wired data plane for reducing the number of rules at switches. Experiments show that our rule optimization strategy reduces the number of rules while keeping the performance of data transmission.
---
paper_title: Optimizing rule placement in software-defined networks for energy-aware routing

paper_content:

Software-defined Networks (SDN), in particular OpenFlow, is a new networking paradigm enabling innovation through network programmability. Over past few years, many applications have been built using SDN such as server load balancing, virtual-machine migration, traffic engineering and access control. In this paper, we focus on using SDN for energy-aware routing (EAR). Since traffic load has a small influence on power consumption of routers, EAR allows to put unused links into sleep mode to save energy. SDN can collect traffic matrix and then computes routing solutions satisfying QoS while being minimal in energy consumption. However, prior works on EAR have assumed that the table of OpenFlow switch can hold an infinite number of rules. In practice, this assumption does not hold since the flow table is implemented with Ternary Content Addressable Memory (TCAM) which is expensive and power-hungry. In this paper, we propose an optimization method to minimize energy consumption for a backbone network while respecting capacity constraints on links and rule space constraints on routers. In details, we present an exact formulation using Integer Linear Program (ILP) and introduce efficient greedy heuristic algorithm. Based on simulations, we show that using this smart rule space allocation, it is possible to save almost as much power consumption as the classical EAR approach.
---
paper_title: Palette: Distributing tables in software-defined networks

paper_content:

In software-defined networks (SDNs), the network controller first formulates abstract network-wide policies, and then implements them in the forwarding tables of network switches. However, fast SDN tables often cannot scale beyond a few hundred entries. This is because they typically include wildcards, and therefore are implemented using either expensive and power-hungry TCAMs, or complex and slow data structures. This paper presents the Palette distribution framework for decomposing large SDN tables into small ones and then distributing them across the network, while preserving the overall SDN policy semantics. Palette helps balance the sizes of the tables across the network, as well as reduce the total number of entries by sharing resources among different connections. It copes with two NP-hard optimization problems: Decomposing a large SDN table into equivalent subtables, and distributing the subtables such that each connection traverses each type of subtable at least once. To implement the Palette distribution framework, we introduce graph-theoretical formulations and algorithms, and show that they achieve close-to-optimal results in practice.
---
paper_title: DomainFlow: practical flow management method using multiple flow tables in commodity switches

paper_content:

A scalable network with high bisection bandwidth and high availability requires efficient use of the multiple paths between pairs of end hosts. OpenFlow is an innovative technology and enables fine-grained, flow level control of Ethernet switching. However, the flow table structure defined by OpenFlow is not hardware friendly and the scalability is limited by the switch device. OpenFlow is also not sufficient for fast multipath failover. To overcome these limitations, we propose DomainFlow in which the network is split into sections and exact matches are used where possible to enable practical flow management using OpenFlow for commodity switches. We applied a prototype of DomainFlow to multipath flow management in the Virtual eXtensible LAN (VXLAN) overlay network environment. The total number of flow entries was reduced to 1/128 using currently available commodity switches, which was not possible before.
---
paper_title: Heterogeneous Flow Table Distribution in Software-defined Networks

paper_content:

Recently, Software-defined Network (SDN) has become an important and popular technology which provides for the flexibility of developing new protocols and the policies of real networks. The controller in SDN translates network policies into rules which are installed in the flow tables (Flow tables are usually stored in ternary content addressable memory (TCAM)) of switches in the networks. Hence, TCAM usually has some critical disadvantages (e.g., high costs, power consumption and high heat generation). Flow tables cannot scale beyond a few hundred entries. Therefore, switches may need to cache rules reactively (i.e., installing rules on demand). However, when cache misses happen, switches will send the packet-in message to the controller and reactively cache the rules, which causes packet delay and large buffers. In this thesis, we propose a rule partition and allocation algorithm that distributes rules across network switches to improve the performance. Our algorithm not only is applicable to small TCAM switch scenario, but also guarantees semantically-invariant (i.e., the global action of the network is unchanged). We implement our algorithm into the real world SDN scenario and the experiment result shows that our algorithm have obviously reduced TCAM usage.
---
paper_title: SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks

paper_content:

OpenFlow is a popular network architecture where a logically centralized controller (the control plane) is physically decoupled from all forwarding switches (the data plane). Through this controller, the OpenFlow framework enables flow level granularity in switches thereby providing monitoring and control over each individual flow. Among other things, this architecture comes at the cost of placing significant stress on switch state size and overburdening the controller in various traffic engineering scenarios such as dynamic re-routing of flows. Storing a flow match rule and flow counter at every switch along a flow's path results in many thousands of entries per switch. Dynamic rerouting of a flow, either in an attempt to utilize less congested paths, or as a consequence of virtual machine migration, results in controller intervention at every switch along the old and new paths. In the absence of careful orchestration of flow storage and controller involvement, OpenFlow will be unable to scale to anticipated production data center sizes. In this context, we present SwitchReduce - a system to reduce switch state and controller involvement in OpenFlow networks. SwitchReduce is founded on the observation that the number of flow match rules at any switch should be no more than the set of unique processing actions it has to take on incoming flows. Additionally, the flow counters for every unique flow may be maintained at only one switch in the network. We have implemented SwitchReduce as a NOX controller application. Simulation results with real data center traffic traces reveal that SwitchReduce can reduce flow entries by up to approximately 49% on first hop switches, and up to 99.9% on interior switches, while reducing flow counters by 75% on average.
---
paper_title: vCRIB: virtualized rule management in the cloud

paper_content:

Cloud operators increasingly need many fine-grained rules to better control individual network flows for various management tasks. While previous approaches have advocated placing rules either on hypervisors or switches, we argue that future data centers would benefit from leveraging rule processing capabilities at both for better scalability and performance. In this paper, we propose vCRIB, a virtualized Cloud Rule Information Base that allows operators to freely define different management policies without the need to consider underlying resource constraints. The challenge in our approach is the design of a vCRIB manager that automatically partitions and places rules at both hypervisors and switches to achieve a good trade-off between resource usage and performance.
---
paper_title: Rule caching in SDN-enabled mobile access networks

paper_content:

An SDN enabled mobile access network is a future network with great potential to support scalable and flexible network applications. To support various network applications, the SDN-enabled mobile access network usually uses forwarding rules in SDN devices. With a limited rule space in existing SDN devices, a rule caching mechanism is an efficient way to improve network performance. In this article we propose SRCMN, which is a new caching structure to improve network performance with a limited rule space in the SDN-enabled mobile access network. We design a two-layer rule space in each SDN device, which is managed by the SDN controller. We also design a cache prefetching mechanism with the consideration of user mobility. By conducting extensive simulations, we demonstrate that our proposed structure and mechanism significantly outperform original rule space management under various network settings.
---
paper_title: Optimizing the "one big switch" abstraction in software-defined networks

paper_content:

Software Defined Networks (SDNs) support diverse network policies by offering direct, network-wide control over how switches handle traffic. Unfortunately, many controller platforms force applications to grapple simultaneously with end-to-end connectivity constraints, routing policy, switch memory limits, and the hop-by-hop interactions between forwarding rules. We believe solutions to this complex problem should be factored in to three distinct parts: (1) high-level SDN applications should define their end-point connectivity policy on top of a "one big switch" abstraction; (2) a mid-level SDN infrastructure layer should decide on the hop-by-hop routing policy; and (3) a compiler should synthesize an effective set of forwarding rules that obey the user-defined policies and adhere to the resource constraints of the underlying hardware. In this paper, we define and implement our proposed architecture, present efficient rule-placement algorithms that distribute forwarding policies across general SDN networks while managing rule-space constraints, and show how to support dynamic, incremental update of policies. We evaluate the effectiveness of our algorithms analytically by providing complexity bounds on their running time and rule space, as well as empirically, using both synthetic benchmarks, and real-world firewall and routing policies.
---
paper_title: Optimizing rules placement in OpenFlow networks: trading routing for better efficiency

paper_content:

The idea behind Software Defined Networking (SDN) is to conceive the network as one programmable entity rather than a set of devices to manually configure, and OpenFlow meets this objective. In OpenFlow, a centralized programmable controller installs rules onto switches to implement policies. However, this flexibility comes at the expense of extra overhead as the number of rules might exceed the memory capacity of switches, which raises the question of how to place most profitable rules on board. Solutions proposed so far strictly impose paths to be followed inside the network. We advocate instead that we can trade routing requirements within the network to concentrate on where to forward traffic, not how to do it. As an illustration of the concept, we propose an optimization problem that gets the maximum amount of traffic delivered according to policies and the actual dimensioning of the network. The traffic that cannot be accommodated is forwarded to the controller that has the capacity to process it further. We also demonstrate that our approach permits a better utilization of scarce resources in the network.
---
paper_title: An Adaptable Rule Placement for Software-Defined Networks

paper_content:

There is a strong trend in networking to move towards Software-Defined Networks (SDN). SDNs enable easier network configuration through a separation between a centralized controller and a distributed data plane comprising a network of switches. The controller implements network policies through installing rules on switches. Recently the "Big Switch" abstraction [1] was proposed as a specification mechanism for high-level network behavior, i.e., the network policies. The network operating system or compiler can use his specification for placing rules on individual switches. However, this is constrained by the limited capacity of the Ternary Content Addressable Memories (TCAMs) used for rules in each switch. We propose an Integer Linear Programming (ILP) based solution for placing rules on switches for a given firewall policy while optimizing for the total number of rules and meeting the switch capacity constraints. Experimental results demonstrate that our approach is scalable to practical sized networks.
---
paper_title: MoRule: Optimized rule placement for mobile users in SDN-enabled access networks

paper_content:

With the surging popularity of smartphones and tablets, mobile network traffic has dramatically increased in recent years. Software defined network (SDN) provides a scalable and flexible structure to simplify network traffic management. It has been shown that rule placement plays an important role in the performance of SDN. However, since most existing work considers static network topologies of wired networks, it cannot be directly applied for mobile networks. In this paper, we propose MoRule, an efficient rule management scheme to optimize the rule placement for mobile users. To deal with the challenges of user mobility and rule capacity constraints of switches, we design a heuristic algorithm with low-complexity to minimize the rule space occupation while guaranteeing that the mobile traffic processed by local switches is no less than a threshold. By conducting extensive simulations, we demonstrate that our proposed algorithm significantly outperforms random solutions under various network settings.
---
paper_title: Shadow MACs: scalable label-switching for commodity ethernet

paper_content:

While SDN promises fine-grained, dynamic control of the network, in practice limited switch TCAM rule space restricts most forwarding to be coarse-grained. As an alternative, we demonstrate that using destination MAC addresses as opaque forwarding labels allows an SDN controller to leverage large MAC (L2) forwarding tables to manage a plethora of fine-grained paths. In this shadow MAC model, the SDN controller can install MAC rewrite rules at the network edge to guide traffic on to intelligently selected paths to balance traffic, avoid failed links, or route flows through middleboxes. Further, by decoupling the network edge from the core, we address many other problems with SDN, including consistent network updates, fast rerouting, and multipathing with end-to-end control.
---
paper_title: OFFICER: A general optimization framework for OpenFlow rule allocation and endpoint policy enforcement

paper_content:

The Software-Defined Networking approach permits to realize new policies. In OpenFlow in particular, a controller decides on behalf of the switches which forwarding rules must be installed and where. However with this flexibility comes the challenge of the computation of a rule allocation matrix meeting both high-level policies and the network constraints such as memory or link capacity limitations. Nevertheless, in many situations (e.g., data-center networks), the exact path followed by packets does not severely impact performances as long as packets are delivered according to the endpoint policy. It is thus possible to deviate part of the traffic to alternative paths so to better use network resources without violating the endpoint policy. In this paper, we propose a linear optimization model of the rule allocation problem in resource constrained OpenFlow networks with relaxing routing policy. We show that the general problem is NP-hard and propose a polynomial time heuristic, called OFFICER, which aims to maximize the amount of carried traffic in under-provisioned networks. Our numerical evaluation on four different topologies shows that exploiting various paths allows to increase the amount of traffic supported by the network without significantly increasing the path length.
---
paper_title: MicroTE: fine grained traffic engineering for data centers

paper_content:

The effects of data center traffic characteristics on data center traffic engineering is not well understood. In particular, it is unclear how existing traffic engineering techniques perform under various traffic patterns, namely how do the computed routes differ from the optimal routes. Our study reveals that existing traffic engineering techniques perform 15% to 20% worse than the optimal solution. We find that these techniques suffer mainly due to their inability to utilize global knowledge about flow characteristics and make coordinated decision for scheduling flows. To this end, we have developed MicroTE, a system that adapts to traffic variations by leveraging the short term and partial predictability of the traffic matrix. We implement MicroTE within the OpenFlow framework and with minor modification to the end hosts. In our evaluations, we show that our system performs close to the optimal solution and imposes minimal overhead on the network making it appropriate for current and future data centers.
---
paper_title: Infinite CacheFlow in software-defined networks

paper_content:

Software-Defined Networking (SDN) enables fine-grained policies for firewalls, load balancers, routers, traffic monitoring, and other functionality. While Ternary Content Addressable Memory (TCAM) enables OpenFlow switches to process packets at high speed based on multiple header fields, today's commodity switches support just thousands to tens of thousands of rules. To realize the potential of SDN on this hardware, we need efficient ways to support the abstraction of a switch with arbitrarily large rule tables. To do so, we define a hardware-software hybrid switch design that relies on rule caching to provide large rule tables at low cost. Unlike traditional caching solutions, we neither cache individual rules (to respect rule dependencies) nor compress rules (to preserve the per-rule traffic counts). Instead we ``splice'' long dependency chains to cache smaller groups of rules while preserving the semantics of the network policy. Our design satisfies four core criteria: (1) elasticity (combining the best of hardware and software switches), (2) transparency (faithfully supporting native OpenFlow semantics, including traffic counters), (3) fine-grained rule caching (placing popular rules in the TCAM, despite dependencies on less-popular rules), and (4) adaptability (to enable incremental changes to the rule caching as the policy changes).
---
paper_title: The nature of data center traffic: measurements & analysis

paper_content:

We explore the nature of trac in data centers, designed to su p- port the mining of massive data sets. We instrument the servers to collect socket-level logs, with negligible performance impact. In a 1500 server operational cluster, we thus amass roughly a petabyte of measurements over two months, from which we obtain and re- portdetailedviewsoftracandcongestionconditionsandp atterns. We further consider whether trac matrices in the clustermi ght be obtained instead via tomographic inference from coarser-grained counter data.
---
paper_title: Rule Optimization for Real-Time Query Service in Software-Defined Internet of Vehicles

paper_content:

Internet of Vehicles (IoV) has recently gained considerable attentions from both industry and research communities since the development of communication technology and smart city. However, a proprietary and closed way of operating hardwares in network equipments slows down the progress of new services deployment and extension in IoV. Moreover, the tightly coupled control and data planes in traditional networks significantly increase the complexity and cost of network management. By proposing a novel architecture, called Software-Defined Internet of Vehicles (SDIV), we adopt the software-defined network (SDN) architecture to address these problems by leveraging its separation of the control plane from the data plane and a uniform way to configure heterogeneous switches. However, the characteristics of IoV introduce the very challenges in rule installation due to the limited size of Flow Tables at OpenFlow-enabled switches which are the main component of SDN. It is necessary to build compact Flow Tables for the scalability of IoV. Accordingly, we develop a rule optimization approach for real-time query service in SDIV. Specifically, we separate wired data plane from wireless data plane and use multicast address in wireless data plane. Furthermore, we introduce a destination-driven model in wired data plane for reducing the number of rules at switches. Experiments show that our rule optimization strategy reduces the number of rules while keeping the performance of data transmission.
---
paper_title: Optimizing rule placement in software-defined networks for energy-aware routing

paper_content:

Software-defined Networks (SDN), in particular OpenFlow, is a new networking paradigm enabling innovation through network programmability. Over past few years, many applications have been built using SDN such as server load balancing, virtual-machine migration, traffic engineering and access control. In this paper, we focus on using SDN for energy-aware routing (EAR). Since traffic load has a small influence on power consumption of routers, EAR allows to put unused links into sleep mode to save energy. SDN can collect traffic matrix and then computes routing solutions satisfying QoS while being minimal in energy consumption. However, prior works on EAR have assumed that the table of OpenFlow switch can hold an infinite number of rules. In practice, this assumption does not hold since the flow table is implemented with Ternary Content Addressable Memory (TCAM) which is expensive and power-hungry. In this paper, we propose an optimization method to minimize energy consumption for a backbone network while respecting capacity constraints on links and rule space constraints on routers. In details, we present an exact formulation using Integer Linear Program (ILP) and introduce efficient greedy heuristic algorithm. Based on simulations, we show that using this smart rule space allocation, it is possible to save almost as much power consumption as the classical EAR approach.
---
paper_title: Palette: Distributing tables in software-defined networks

paper_content:

In software-defined networks (SDNs), the network controller first formulates abstract network-wide policies, and then implements them in the forwarding tables of network switches. However, fast SDN tables often cannot scale beyond a few hundred entries. This is because they typically include wildcards, and therefore are implemented using either expensive and power-hungry TCAMs, or complex and slow data structures. This paper presents the Palette distribution framework for decomposing large SDN tables into small ones and then distributing them across the network, while preserving the overall SDN policy semantics. Palette helps balance the sizes of the tables across the network, as well as reduce the total number of entries by sharing resources among different connections. It copes with two NP-hard optimization problems: Decomposing a large SDN table into equivalent subtables, and distributing the subtables such that each connection traverses each type of subtable at least once. To implement the Palette distribution framework, we introduce graph-theoretical formulations and algorithms, and show that they achieve close-to-optimal results in practice.
---
paper_title: Optimizing the "one big switch" abstraction in software-defined networks

paper_content:

Software Defined Networks (SDNs) support diverse network policies by offering direct, network-wide control over how switches handle traffic. Unfortunately, many controller platforms force applications to grapple simultaneously with end-to-end connectivity constraints, routing policy, switch memory limits, and the hop-by-hop interactions between forwarding rules. We believe solutions to this complex problem should be factored in to three distinct parts: (1) high-level SDN applications should define their end-point connectivity policy on top of a "one big switch" abstraction; (2) a mid-level SDN infrastructure layer should decide on the hop-by-hop routing policy; and (3) a compiler should synthesize an effective set of forwarding rules that obey the user-defined policies and adhere to the resource constraints of the underlying hardware. In this paper, we define and implement our proposed architecture, present efficient rule-placement algorithms that distribute forwarding policies across general SDN networks while managing rule-space constraints, and show how to support dynamic, incremental update of policies. We evaluate the effectiveness of our algorithms analytically by providing complexity bounds on their running time and rule space, as well as empirically, using both synthetic benchmarks, and real-world firewall and routing policies.
---
paper_title: An Adaptable Rule Placement for Software-Defined Networks

paper_content:

There is a strong trend in networking to move towards Software-Defined Networks (SDN). SDNs enable easier network configuration through a separation between a centralized controller and a distributed data plane comprising a network of switches. The controller implements network policies through installing rules on switches. Recently the "Big Switch" abstraction [1] was proposed as a specification mechanism for high-level network behavior, i.e., the network policies. The network operating system or compiler can use his specification for placing rules on individual switches. However, this is constrained by the limited capacity of the Ternary Content Addressable Memories (TCAMs) used for rules in each switch. We propose an Integer Linear Programming (ILP) based solution for placing rules on switches for a given firewall policy while optimizing for the total number of rules and meeting the switch capacity constraints. Experimental results demonstrate that our approach is scalable to practical sized networks.
---
paper_title: DevoFlow: scaling flow management for high-performance networks

paper_content:

OpenFlow is a great concept, but its original design imposes excessive overheads. It can simplify network and traffic management in enterprise and data center environments, because it enables flow-level control over Ethernet switching and provides global visibility of the flows in the network. However, such fine-grained control and visibility comes with costs: the switch-implementation costs of involving the switch's control-plane too often and the distributed-system costs of involving the OpenFlow controller too frequently, both on flow setups and especially for statistics-gathering. ::: In this paper, we analyze these overheads, and show that OpenFlow's current design cannot meet the needs of high-performance networks. We design and evaluate DevoFlow, a modification of the OpenFlow model which gently breaks the coupling between control and global visibility, in a way that maintains a useful amount of visibility without imposing unnecessary costs. We evaluate DevoFlow through simulations, and find that it can load-balance data center traffic as well as fine-grained solutions, without as much overhead: DevoFlow uses 10--53 times fewer flow table entries at an average switch, and uses 10--42 times fewer control messages.
---
paper_title: MoRule: Optimized rule placement for mobile users in SDN-enabled access networks

paper_content:

With the surging popularity of smartphones and tablets, mobile network traffic has dramatically increased in recent years. Software defined network (SDN) provides a scalable and flexible structure to simplify network traffic management. It has been shown that rule placement plays an important role in the performance of SDN. However, since most existing work considers static network topologies of wired networks, it cannot be directly applied for mobile networks. In this paper, we propose MoRule, an efficient rule management scheme to optimize the rule placement for mobile users. To deal with the challenges of user mobility and rule capacity constraints of switches, we design a heuristic algorithm with low-complexity to minimize the rule space occupation while guaranteeing that the mobile traffic processed by local switches is no less than a threshold. By conducting extensive simulations, we demonstrate that our proposed algorithm significantly outperforms random solutions under various network settings.
---
paper_title: Hey, you darned counters!: get off my ASIC!

paper_content:

Software-Defined Networking (SDN) gains much of its value through the use of central controllers with global views of dynamic network state. To support a global view, SDN protocols, such as OpenFlow, expose several counters for each flow-table rule. These counters must be maintained by the data plane, which is typically implemented in hardware as an ASIC. ASIC-based counters are inflexible, and cannot easily be modified to compute novel metrics. These counters do not need to be on the ASIC. If the ASIC data plane has a fast connection to a general-purpose CPU with cost-effective memory, we can replace traditional counters with a stream of rule-match records, transmit this stream to the CPU, and then process the stream in the CPU. These software-defined counters allow far more flexible processing of counter-related information, and can reduce the ASIC area and complexity needed to support counters.
---
paper_title: On the co-existence of distributed and centralized routing control-planes

paper_content:

Network operators can and do deploy multiple routing control-planes, e.g., by running different protocols or instances of the same protocol. With the rise of SDN, multiple control-planes are likely to become even more popular, e.g., to enable hybrid SDN or multi-controller deployments. Unfortunately, previous works do not apply to arbitrary combinations of centralized and distributed control-planes. In this paper, we develop a general theory for coexisting control-planes. We provide a novel, exhaustive classification of existing and future control-planes (e.g., OSPF, EIGRP, and Open-Flow) based on fundamental control-plane properties that we identify. Our properties are general enough to study centralized and distributed control-planes under a common framework. We show that multiple uncoordinated control-planes can cause forwarding anomalies whose type solely depends on the identified properties. To show the wide applicability of our framework, we leverage our theoretical insight to (i) provide sufficient conditions to avoid anomalies, (ii) propose configuration guidelines, and (iii) define a provably-safe procedure for reconfigurations from any (combination of) control-planes to any other. Finally, we discuss prominent consequences of our findings on the deployment of new paradigms (notably, SDN) and previous research works.
---
paper_title: DomainFlow: practical flow management method using multiple flow tables in commodity switches

paper_content:

A scalable network with high bisection bandwidth and high availability requires efficient use of the multiple paths between pairs of end hosts. OpenFlow is an innovative technology and enables fine-grained, flow level control of Ethernet switching. However, the flow table structure defined by OpenFlow is not hardware friendly and the scalability is limited by the switch device. OpenFlow is also not sufficient for fast multipath failover. To overcome these limitations, we propose DomainFlow in which the network is split into sections and exact matches are used where possible to enable practical flow management using OpenFlow for commodity switches. We applied a prototype of DomainFlow to multipath flow management in the Virtual eXtensible LAN (VXLAN) overlay network environment. The total number of flow entries was reduced to 1/128 using currently available commodity switches, which was not possible before.
---
paper_title: DevoFlow: scaling flow management for high-performance networks

paper_content:

OpenFlow is a great concept, but its original design imposes excessive overheads. It can simplify network and traffic management in enterprise and data center environments, because it enables flow-level control over Ethernet switching and provides global visibility of the flows in the network. However, such fine-grained control and visibility comes with costs: the switch-implementation costs of involving the switch's control-plane too often and the distributed-system costs of involving the OpenFlow controller too frequently, both on flow setups and especially for statistics-gathering. ::: In this paper, we analyze these overheads, and show that OpenFlow's current design cannot meet the needs of high-performance networks. We design and evaluate DevoFlow, a modification of the OpenFlow model which gently breaks the coupling between control and global visibility, in a way that maintains a useful amount of visibility without imposing unnecessary costs. We evaluate DevoFlow through simulations, and find that it can load-balance data center traffic as well as fine-grained solutions, without as much overhead: DevoFlow uses 10--53 times fewer flow table entries at an average switch, and uses 10--42 times fewer control messages.
---
paper_title: Theory and Applications of Robust Optimization

paper_content:

In this paper we survey the primary research, both theoretical and applied, in the area of Robust Optimization (RO). Our focus is on the computational attractiveness of RO approaches, as well as the modeling power and broad applicability of the methodology. In addition to surveying prominent theoretical results of RO, we also present some recent results linking RO to adaptable models for multi-stage decision-making problems. Finally, we highlight applications of RO across a wide spectrum of domains, including finance, statistics, learning, and various areas of engineering.
---
paper_title: Infinite CacheFlow in software-defined networks

paper_content:

Software-Defined Networking (SDN) enables fine-grained policies for firewalls, load balancers, routers, traffic monitoring, and other functionality. While Ternary Content Addressable Memory (TCAM) enables OpenFlow switches to process packets at high speed based on multiple header fields, today's commodity switches support just thousands to tens of thousands of rules. To realize the potential of SDN on this hardware, we need efficient ways to support the abstraction of a switch with arbitrarily large rule tables. To do so, we define a hardware-software hybrid switch design that relies on rule caching to provide large rule tables at low cost. Unlike traditional caching solutions, we neither cache individual rules (to respect rule dependencies) nor compress rules (to preserve the per-rule traffic counts). Instead we ``splice'' long dependency chains to cache smaller groups of rules while preserving the semantics of the network policy. Our design satisfies four core criteria: (1) elasticity (combining the best of hardware and software switches), (2) transparency (faithfully supporting native OpenFlow semantics, including traffic counters), (3) fine-grained rule caching (placing popular rules in the TCAM, despite dependencies on less-popular rules), and (4) adaptability (to enable incremental changes to the rule caching as the policy changes).
---
paper_title: The controller placement problem

paper_content:

Network architectures such as Software-Defined Networks (SDNs) move the control logic off packet processing devices and onto external controllers. These network architectures with decoupled control planes open many unanswered questions regarding reliability, scalability, and performance when compared to more traditional purely distributed systems. This paper opens the investigation by focusing on two specific questions: given a topology, how many controllers are needed, and where should they go? To answer these questions, we examine fundamental limits to control plane propagation latency on an upcoming Internet2 production deployment, then expand our scope to over 100 publicly available WAN topologies. As expected, the answers depend on the topology. More surprisingly, one controller location is often sufficient to meet existing reaction-time requirements (though certainly not fault tolerance requirements).
---
paper_title: vCRIB: virtualized rule management in the cloud

paper_content:

Cloud operators increasingly need many fine-grained rules to better control individual network flows for various management tasks. While previous approaches have advocated placing rules either on hypervisors or switches, we argue that future data centers would benefit from leveraging rule processing capabilities at both for better scalability and performance. In this paper, we propose vCRIB, a virtualized Cloud Rule Information Base that allows operators to freely define different management policies without the need to consider underlying resource constraints. The challenge in our approach is the design of a vCRIB manager that automatically partitions and places rules at both hypervisors and switches to achieve a good trade-off between resource usage and performance.
---
paper_title: OFFICER: A general optimization framework for OpenFlow rule allocation and endpoint policy enforcement

paper_content:

The Software-Defined Networking approach permits to realize new policies. In OpenFlow in particular, a controller decides on behalf of the switches which forwarding rules must be installed and where. However with this flexibility comes the challenge of the computation of a rule allocation matrix meeting both high-level policies and the network constraints such as memory or link capacity limitations. Nevertheless, in many situations (e.g., data-center networks), the exact path followed by packets does not severely impact performances as long as packets are delivered according to the endpoint policy. It is thus possible to deviate part of the traffic to alternative paths so to better use network resources without violating the endpoint policy. In this paper, we propose a linear optimization model of the rule allocation problem in resource constrained OpenFlow networks with relaxing routing policy. We show that the general problem is NP-hard and propose a polynomial time heuristic, called OFFICER, which aims to maximize the amount of carried traffic in under-provisioned networks. Our numerical evaluation on four different topologies shows that exploiting various paths allows to increase the amount of traffic supported by the network without significantly increasing the path length.
---

Title: Rules Placement Problem in OpenFlow Networks: A Survey

Section 1: BACKGROUND
Description 1: Write a background overview of SDN and OpenFlow, explaining their core principles and components.

Section 2: MOTIVATION
Description 2: Describe the motivations behind the OpenFlow rules placement problem, outlining use cases such as access control and traffic engineering.

Section 3: PROBLEM FORMALIZATION
Description 3: Formalize the OpenFlow rules placement problem, define the network model, and describe the essential inputs and constraints.

Section 4: CHALLENGES
Description 4: Discuss the primary challenges in the OpenFlow rules placement problem, namely resource limitations and signaling overhead.

Section 5: EFFICIENT MEMORY MANAGEMENT
Description 5: Survey and classify the techniques proposed in the literature for managing memory limitations in OpenFlow switches.

Section 6: REDUCING SIGNALING OVERHEAD
Description 6: Summarize the methods and ideas proposed to mitigate signaling overhead in OpenFlow rules placement.

Section 7: FUTURE RESEARCH DIRECTIONS
Description 7: Explore the potential future research areas and open questions within the context of the OpenFlow rules placement problem.

Section 8: CONCLUSION
Description 8: Conclude by summarizing the main points and the significance of solving the OpenFlow rules placement problem.