{'fraction_non_alphanumeric': 0.027570669956552055, 'fraction_numerical': 0.004684510718947237, 'mean_word_length': 4.995283524493515, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
OpenFunction: Data Plane Abstraction for Software-Defined Middleboxes

The state-of-the-art OpenFlow technology only partially realized SDN vision of abstraction and centralization for packet forwarding in switches. OpenFlow/P4 falls short in implementing middlebox functionalities due to the fundamental limitation in its match-action abstraction. In this paper, we advocate the vision of Software-Defined Middleboxes (SDM) to realize abstraction and centralization for middleboxes. We further propose OpenFunction, an SDM reference architecture and a network function abstraction layer. Our SDM architecture and OpenFunction abstraction are complementary to existing SDN and Network Function Virtualization (NFV) technologies. SDM complements SDN as SDM realizes abstraction and centralization for middleboxes, whereas SDN realizes those for switches. OpenFunction complements OpenFlow as OpenFunction addresses network functions whereas OpenFlow addresses packet forwarding. SDM also complements NFV in that SDM gives NFV the ability to use heterogenous hardware platforms with various hardware acceleration technologies.


Introduction
The vision of Software-Defined Networking (SDN) is two-fold: abstraction and centralization. Abstraction means that heterogenous network devices of different vendors/architectures have common programming interfaces for implementing the functionalities needed by the control plane. Centralization means to use a logically centralized controller in the control plane to obtain a global view of a network and to manage network resources and functionalities in an orchestrated and flexible manner. Abstraction and centralization help SDN to achieve its two goals: breaking device vendor lockin and supporting network innovation. Abstraction helps to break device vendor lock-in by allowing third-party software to run on all SDN compliant network devices. In contrast, traditional network devices are black boxes where both hardware and software are tightly coupled as they are typically from the same vendor, which leads to both network ossification and vendor lock-in. Centralization helps to support network innovation by allowing network resources and functionalities to be dynamically and flexibly organized and managed. In contrast, on traditional networks, packet forwarding and middlebox functionalities are statically deployed, which makes adopting and experimenting new network services and protocols extremely difficult. SDN has been increasingly gaining market acceptance because of reduced cost (by abstraction) and new functionalities (by centralization).
Currently this SDN vision has only been realized for switches by OpenFlow [1,2] and its advanced version P4 [3], but not for middleboxes. A data communication network has two types of devices, switches and middleboxes. Switches (including routers in the broader sense) provide packet forwarding. Middleboxes provide a wide variety of networking and security functionalities such as Network Address Translation (NAT), Load Balancers (LB), firewalls (FW), WAN optimizers, proxies, IPSec gateways (VPN), and network Intrusion Detection/Prevention Systems (IDS/IPS). For a packet, switches decide which path the packet traverses and middleboxes decide what processing the packet receives.
Network Function Virtualization (NFV) attempts to address the issues of tight hardware/software coupling and hardware vendor lock-in for middleboxes by implementing middlebox functions purely in software running on commodity servers [4,5]. Unfortunately, NFV middleboxes are software, not software-defined. The key weakness of NFV middleboxes is low performance because commodity servers are designed for general computing purposes. The functions and requirements of packet processing are significantly different from those of general computing. Such differences warrant a wide variety of specialized hardware acceleration technologies such as ASIC chips and Network Processing Units (NPU), which typically have a 10-50 times performance improvement over commodity server based solutions [6]. This partially explains that market has been in favor of the closed-but-fast model, which uses proprietary hardware platform with fast packet processing capability, over the open-but-slow model, which uses commodity servers with slow packet processing capability.
The match-action abstractions in OpenFlow/P4 has too limited expression power to be applicable to middleboxes. First, for the action abstraction, OpenFlow/P4 limit themselves to a fixed number of actions. However, middleboxes, such as IPSec VPN, often need to perform complex payload actions such as encryption and decryption. To address this limitation, the OpenFlow standard has kept adding new actions. This is not a sustainable solution as packet processing actions can never be exhaustively standardized. Furthermore, frequent standardization of new action abstraction would lead to frequent redevelopment of software/hardware, which results in vertically integrated hardware-software that must be replaced all together in network upgrading [7]. Second, for the match abstraction, OpenFlow and P4 limit themselves to matching packet headers. OpenFlow can only specify matching conditions over a fixed number of predefined packet header fields. P4 improves OpenFlow by allowing users to extract customized packet header fields. However, many middleboxes, such as application firewalls and IPSes, need to match packet payload against signatures [8]. Third, the table abstraction in OpenFlow/P4 is fundamentally incapable of modeling the function of scheduling. Scheduling is essential to implement Quality-of-Service (QoS), which is further essential for many middlebox functionalities. This inability is because the table abstraction performs splitting an aggregate flow into multiple flows whereas scheduling performs merging multiple flows into an aggregate flow. In some sense, a table and a scheduler perform totally opposite functionalities, and one cannot model the other.
In this paper, we advocate the vision of Software-Defined Middleboxes (SDM) to realize abstraction and centralization for middleboxes. For abstraction, an SDM architecture should have a network function abstraction layer that is platform independent and fully programmable. Platform independence means to decouple the network function semantics and the underlying hardware that realizes the function. This allows any third-party SDM program to execute at any SDM boxes (i.e., SDM compliant middleboxes) with the same semantics but different performance depending on hardware adequacy. This abstraction layer should be hardware optimizable, which means that the performance of an SDM box can be optimized by various hardware acceleration technologies. An SDM programmer needs not to be aware of the underlying hardware features of SDM boxes. However, an SDM program can be trans-lated to a platform dependent program that fully leverages the hardware features of the underlying SDM box. Full programmability means that any middlebox functionality can be implemented by an SDM program. For centralization, an SDM architecture should have a logically centralized controller and a suite of communication protocols that allows the controller to dynamically program the functionality of an SDM box over the network.
To realize the vision of SDM, we propose OpenFunction, an SDM reference architecture and a network function abstraction layer, complementing what OpenFlow achieves for switches. Our OpenFunction architecture consists of a logically centralized OpenFunction controller and a number of OpenFunction boxes distributed around a network, as illustrated in Figure 2. Each network function, such as NAT, LB, or FW, is accomplished by a Control Plane (CP) process running on the Open-Function controller and a group of Data Plane (DP) processes running on different OpenFunction boxes. An DP process has a local view of the network, and its main role is to process packets in the data plane. Based on the processed traffic, it sends predefined events to its CP process, and receives commands from its CP process. The CP process has a global view of the network, and its main role is to make well-informed decisions for the group of DP processes that it manages. It receives events from DP processes, performs analyses, makes decisions, and sends commands to DP processes to enforce its decisions. The OpenFunction controller performs the management and scheduling of network resources, both CP and DP processes, and service chains. The CP processes interact with the OpenFunction controller through its northbound API. An OpenFunction box has a middleware layer called an OpenFunction shim layer, which manages all DP processes running on the device, such as installs a DP, starts a DP process, and terminates a DP process. The OpenFunction shim layer interacts with the controller through its southbound API. A DP process interacts with the hardware resources in an OpenFunction box through an OpenFunction abstraction layer, which provides a suite of atomic actions (i.e., APIs) for packet/flow/traffic processing. Each DP process is implemented using these atomic operations.
OpenFunction has five categories of predefined actions: (1) starting action, i.e., packet sending to NICs, (2) one-to-one actions such as packet encapsulation or TTL decreasing, (3) one-to-many actions such as flow classification based on exact match or pattern-match, (4) many-to-one actions such as flow scheduling based on strict priority and weighted round robin, (5) ending action, i.e., packet receiving from hardware NICs. For specifying customized actions beyond those predefined ones, OpenFunction has a platform-independent pseudo language. An OpenFunction pseudo program can  Figure 1: Software-Defined Middlebox Architecture be compiled to platform-dependent modules for better performance. For specifying packet processing procedures using predefined and customized actions, Open-Function has a platform-independent scripting language. An OpenFunction script implements a DP whereas an OpenFunction pseudo program implements an action. Through OpenFunction abstraction, the programmer defines what to do and the device decides how to do. The similarity between OpenFunction and Click modular router [9] is on the abstraction of actions. The concept of element in Click and the concept of action in OpenFunction are similar in that they are both abstractions of packet processing operations. The difference between OpenFunction and Click modular router [9] is two fold. First, in Click elements, both data plane operations and control plane operations are mixed together; in contrast, OpenFunction actions contains only data plane operations. Fundamentally, Click was not designed for SDN whereas OpenFunction is designed for SDN. Click elements cannot be used as a data plane network function abstraction, although we do use Click elements as references in designing OpenFunction. Second, Click is platform dependent whereas OpenFunction is platform independent. In Click, each element is implemented by C/C++ and a program using Click library needs to be compiled before running. In OpenFunction, pseudo programs and scripts do not need to be compiled before running; they can be distributed by the controller to Open-Function boxes and executed at run time.
OpenFunction realizes the abstraction vision of SDN for middleboxes by the network function abstraction layer in OpenFunction boxes. Through abstraction, for middleboxes, we decouple their hardware and software as well as their control plane and data plane. This abstraction layer eliminates hardware vendor lock-in because the underlying hardware architecture and vendor are transparent to DP processes. It also eliminates software vendor lock-in because any DP software can run on any OpenFunction boxes. This abstraction layer supports hardware/software heterogeneity and promotes hardware/software innovation as the abstraction layer can be implemented in a variety of hardware/software technologies such as ASIC, multi-core, FPGA, and GPU. This lowers the middlebox market barrier because as long as a hardware device supports the abstraction layer, it can immediately support DP processes and thus can be immediately deployed on existing networks to work with existing devices. This abstraction layer also significantly improves the programmability of middlebox functionalities because a DP developer does not need to implement those common operations in packet processing. From the software engineering perspective, this abstraction layer promotes software reuse. This will significantly shorten the time-to-market cycle.
OpenFunction realizes the centralization vision of SDN for middleboxes by the logically centralized Open-Function controller. As it is well understood that centralization in OpenFlow brings a long list of benefits to packet forwarding such as flexible path selection, better load balancing, finer-grained network control, less configuration errors, higher manageability, and increased reliability and security, centralization in OpenFunction brings many benefits to network functions. For example, the global view that a CP process obtains from the events generated by the group of DP processes that it manages helps the CP to make better informed decisions, e.g., an IDS CP process can perform correlation analysis on the events from its DP processes to better identify attack activities. For another example, the ability that a CP process can issue commands to its DP processes allows the CP to orchestrate the DP processes to collaboratively accomplish some tasks.
OpenFunction, together with OpenFlow, makes service chain construction and scheduling much easier than the current NFV architecture. A service chain is a sequence of middlebox functions that the network operator wants certain traffic to traverse in order. To construct and schedule service chains, the OpenFunction controller performs resource allocation according to a given optimization policy (e.g., load balancing) in collaboration with the forwarding plane authority (e.g., an OpenFlow controller). For example, suppose the network operator wants to allocate 10G bandwidth between two networks and also all traffic between the two networks to pass through an IDS", first, the OpenFlow controller finds an appropriate path between the two networks where each switch on the path has at least 10G bandwidth and the path contains at least one OpenFunction box, second, the OpenFunction controller starts a new IDS DP process on that OpenFunction box. In this SDM+SDN and Open-Function+OpenFlow paradigm, one technical challenge is service chain scheduling: given a service chain that a flow needs to traverse, the controller chooses a sequence of middlebox data plane processes (running on one or more OpenFunction boxes) to form the service chain. The scheduling needs to satisfy the three requirements of service chain constraints, device resource constraints, and flow conservation. Furthermore, it needs to be done in a load balancing way to minimize the maximum utilization of the resources in candidate devices. To address this challenge, in this paper, we formulate service chain scheduling as a NP-Hard problem, and proposed both offline and online scheduling algorithms.
OpenFunction, together with OpenFlow, helps to support the vision of service oriented network management. While OpenFlow makes switches easier to manage, currently middleboxes are still notoriously difficult to manage because the hardware and software of those middleboxes are often tightly coupled and different middleboxes of different vendors often have different management interfaces. Service oriented network management means to automate the translation from high-level service oriented network management requirement to low-level network device configurations. For example, a high-level service oriented network management requirement can be to "allocate 10G bandwidth between two networks and to ensure that all traffic between the two networks to pass through an IDS". While translating this high-level requirement to network device configurations in today networks is a complex, laborious, and error prone process, it can be easily done in our proposed OpenFunc-tion+OpenFlow architecture as a service chain.
Our SDM architecture and OpenFunction abstraction are complementary to existing SDN and NFV technologies. SDM realizes abstraction and centralization for middleboxes, whereas SDN realizes those for switches. SDM breaks device vendor lock-in and supports network innovation for middleboxes, whereas SDN does those for switches. OpenFunction addresses network functions whereas OpenFlow addresses packet forwarding. SDM complements NFV in that SDM gives NFV the ability to use heterogenous hardware platforms with various hardware acceleration technologies.
We implemented a working SDM system including one OpenFunction controller and three OpenFunction boxes based on Netmap, DPDK and FPGA respectively. We also develop two stateless network functions (i.e., NAT and IPsec), two stateful network functions (stateful firewall and IPS). We draw the following conclusions from our experimental results. First, middlebox functions implemented using OpenFunction abstraction can achieve high performance. For example, our FPGA platform can achieve near 10G bps throughput for NAT and IPSEC middleboxes. Second, the performance of Open-Function scripts is platform dependent. Third, for service chain scheduling, our offline algorithm can achieve near to optimal load balancing whereas our online algorithm is fast but the performance is suboptimal. Fourth, the overhead of enforcing service chain both across and inside OpenFunction boxes is negligible.

Background and Related Work
Router Abstraction: Some prior work is on designing an abstraction layer to support portability across heterogeneous platforms. Handley et al. built extensible routers on top of commodity platforms in XORP, focusing on breaking the complex control plane of routing protocols [10,11]. Mogul et al. advocated an abstraction layer called Orphal to support portability of third-party software in a position paper [12]. XORP and Orphal significantly differ from OpenFunction. First, XORP and Orphal are not designed for SDN whereas OpenFunction is. Second, XORP and Orphal are not platform independent whereas OpenFunction is. Furthermore, XORP focuses on routing whereas OpenFunction focuses middlebox functionalities, and Orphal is based on router specific hardware resources (such as TCAM and DPI engines) whereas OpenFunction is based on middlebox functionalities and is hardware agnostic. Song proposed a hardware abstraction called POF, which focuses on protocol-oblivious forwarding [13]. It extends the OpenFlow instructions with protocol-oblivious operations such as AddField and SetFieldFromValue. Answer et al. propose to decouple the processing at the controller and at middleboxes while providing an interface by which they can communicate [14]. This vision is similar to us; however, neither design nor implementation details were given in the two-page position paper [14].
Data Plane Programmability: Several systems focus on the data plane throughput of extensible softwarebased routers. These systems are orthogonal to Open-Function and they are useful to build OpenFunction boxes. RouteBricks exploits parallelism both across multiple servers and across multiple cores inside each single server [15]. PacketShader exploits the massive parallelism of GPU for batch processing [16]. GASPP focuses on stateful packet processing, and its GPU-accelerated framework can achieve multi-gigabit processing [17]. Some systems focus on data plane extensibility of new network forwarding protocols. The main direction is to pair the high-throughput ASIC processing path with a fully programmable co-processer to enhance the programmability. ServerSwitch uses x86 CPU as the coprocessor [18,19]. SSDP instead uses an NPU-driven subsystem [20]. SwitchBlade allows rapid prototyping in FPGA [21]. OpenDataPlane is an open-source crossplatform set of APIs for programming network processors [22]. OpenDataPlane abstraction is at a lower level than OpenFunction as OpenDataPlane specifies how to do by directly manipulating device resources whereas OpenFunction only specifies what to do and let each device decide how to implement each action.

OpenFunction Architecture Overview
OpenFunction architecture consists of a logically centralized OpenFunction controller and a number of Open-Function boxes distributed around a network where each box has a network function abstraction layer. Here we give an overview of OpenFunction from three perspectives: the data plane, middleboxes, and service chains. Data Plane View: OpenFunction exposes an extensible set of actions to the control plane as shown in Figure 2 (a). The semantics of an action is to take a packet as its input, perform some operations, and either push the packet to the next action or wait for the next action to pull the packet. OpenFunction is action oriented, similar to the object oriented programming paradigm. Each action object is an instance of an action class. An action class is a self-contained and functionally independent packet processing unit, such as decreasing the TTL field and calculating the TCP checksum. Each action class consists of some data members, which we call attributes. For example, a PacketCounter action may need to update its counter attribute whenever a packet passes through this action. An action may also send an event to the control plane. For example, a TCPSyncNotifier action may send a TCP sync event whenever a TCP sync packet passes through it. There are two kinds of actions: pre-defined actions and user-defined actions. Pre-defined actions are those supported by OpenFunction compliant boxes and user-defined actions are those written by users using a platform-independent pseudo language. We allow multiple DP processes running on the same Open-Function box, similar to router visualization, where in the same box, different DP processes belongs to different CP processes for different middlebox functions. Middlebox View: In OpenFunction, a network function (such as NAT, LB, or FW) is implemented by a Control Plane (CP) process and a set of Data Plane (DP) processes running on OpenFunction boxes, as shown in Figure 2 (b). A DP is modeled as a directed acyclic graph where each node is an action. A DP process has a lo-cal view of the network and its main role is to process data plane packets. Based on the processed traffic, it may sends events to its CP process, and receives commands from its CP process. The CP process has a global view (via the controller) and its main role is to make well-informed decisions for the group of DP processes that it manages, according to its middlebox functionality. It receives events from DP processes, performs analyses, makes decisions, and sends commands to DP processes to enforce its decisions. We call a CP process together with its group of DP processes a Software-Defined Middlebox (SDM). With OpenFunction, implementing a middlebox functionality on the data plane becomes much simpler as it mostly involves composing a graph of predefined actions, possibly with a few user-defined actions. Thus, SDM developers mostly focus on designing CP programs, which are often the most innovative part of their implementation. Service Chain View: A service chain is a series of middlebox functions that a packet needs to go through, as shown in Figure 2 (c). The OpenFunction schedules and enforces service chains. The controller monitors resource (such as CPU, memory, or a specific acceleration card) utilization and executes an service chain scheduling algorithm; it then coordinates with the forwarding plane authority (i.e., an OpenFlow controller) to enforce the chain. Each OpenFunction box has a middleware layer called an OpenFunction shim layer, which manages all DP processes running on the device, such as installs a DP, starts a DP process, and terminates a DP process. The shim layer is fully controlled by the controller and the controller monitors the resource unitization through it. Note that service chains needs to be enforced both across and inside boxes. An Openflow controller still controls the forwarding between boxes. The OpenFunctoon controller sends flow steering instructions to the Openflow controller. A dedicated IO process of the shim layer steers flows among functions according to their service chains. Figure 2 (c) shows a service chain SDM 1 → SDM 2 → SDM 3.

Abstraction Specification
OpenFunction uses a script for dataplane specification: an example of IPSEC middlebox data plane is shown in Algorithm 1. Hereby is the brief description of Open-Function script: each action instance definition line starts with a "@"; each line defines a connection between an egress port of one action and an ingress port of another action; action definitions and connection definitions together construct the action graph of a DP process.
To carefully tradeoff composability and optimizability, we analyze a number of middleboxes such as NAT, IPSec, and IDS, and design a suite of atomic actions that we classify into the following five categories: • starting action: These actions send packets to either hardware/virtualized NICs, or specific memory locations (e.g., FromDevice in the example ).
• one-to-many action: This category consists of actions based on the following four matches: exactmatch (e.g., used in the example), longest-prefixmatch (e.g., used in FIB), first-match (e.g., used in ACL), and pattern-match (e.g., used in DPI).
• many-to-one action: A flow scheduling action takes multiple flows as input, and outputs one combined stream of traffic. Example flow scheduling operations include strict priority (SP) and weighted round robin (WRR).
• one-to-ones action: These actions perform a single packet processing such as changing the length of a packet, either at the head (i.e., Encap/Decap) or the tail (i.e., Pad/Unpad), and modifying a field or the metadata of a packet (i.e., decreasing the IP TTL value and setting the ECN bit are two actions).
• ending action: These actions receive packets from either hardware/virtualized NICs, or specific memory locations (e.g., ToDevice in the example).
The attributes of an action can be set either at the configuration phase, or at run-time. Stick to the IPSEC example, for a given IPSEC tunnel, the IP SRC/IP DST attributes of ChangeSrcIP/ChangeDstIP actions are set at the configuration phase as parameters. While for the ESPEncap action, its security index SPI and replay parameter RPL should be negotiated by the control plain at run-time; the IPSEC DP process leaves the two attributes unset at first, and lets the CP process performs negotiation before setting the attribute value.
As the target of action operations, a packet class consists of three types of data: fields, metadata, and properties. The metadata is a piece of memory associated with a packet and is used to store modifiable information about the packet, such as the ID of the physical port from which the packet is received. The properties means some non-modifiable information about the packet, such as the packet size. Although some properties of a packet may change after certain actions, e.g., the length of a packet changes after Encap/Decap, the properties of a packet cannot be written or modified by action functions directly. Table 1   To prevent the exact fate of OpenFlow's vertical integration, we do not enforce any standard action. Instead, a set of actions are recommended; and for each such action, a default implementation written in OpenFunction pseudo language (next part) is provided together, An OpenFunction box can flexibly choose the action to optimize by exploiting their underlying hardware acceleration capabilities. For the actions whose optimized implementation is not available at the box, the default pseudo code can be used, like user-defined actionS.
Furthermore, we allow OpenFunction boxes to provide multiple implementations of the same action: for example, one version is CPU based and another version is GPU based. The controller can dynamically determine which version to load/unload based on the availability of network resources and the processing requirements of flows at run time. Later in Section 5, we consider this flexibility in formulating and solving the service chain scheduling problem.

Pseudo Language
We propose a platform-independent pseudo language that allows SDM developers to design arbitrary new middlebox data plane action, and supported by any Open-Function enabled device. The vendor of an OpenFunction box needs to provide a source-to-source translator, which takes a pseudo C program as its input and outputs a native program that exploits the hardware acceleration strength of the box. The output platform-dependent program is further compiled into executable components using the box's native compiler. As a proof-of-concept, shown in Section 6, in our prototype system an action class can be translated either to a platform-dependent C/C++ program such as a Click element, or a FPGA block (in Verilog).
We now introduce the packet field abstraction that the pseudo programs operate on. The whole packet is as-sumed to be stored in a continuous memory location as shown in Figure 3. There is large headroom/tailroom before/after the packet data. Such spaces are reserved for actions that change packet length (i.e., Encap/Decap and Pad/Unpad). We also assume the existence of a mandatory preprocessing step, which marks the start offset of link/network/tranport/app layers (if they exist). Each field is a continuous range of bytes in a packet memory range, defined by a tuple (header, offset, type) and can be attached with a name. For example, IP checksum can be defined as a field starts at the 10th bytes offset of the network header by the FIELD keyword. The length is automatically determined by its data type UNIT16. Note that a special type is DATA, which represents a raw array of bytes. The metadata of a packet is accessed as a named object (with keyword META). In OpenFunction, a (type, length) tuple defines a specific metadata object. The length configuration is required only when the type is DATA. This design provides the system with the freedom to arrange a meta object in its metadata memory. Packet properties (with keyword PROP) and action attributes (with keyword ATTR) are also accessed as named objects. Note that packet properties are limited to a small set of intrinsic packet characteristics and readonly to program. The additional feature of an attribute is that it can be read/written by another action or the control plane. Each event object is a continuous raw array of bytes. It is up to the action developer to decide the content of the event.
A key design decision is to separate packet access (Table 1) codes and normal codes. More specifically, we use character "@" at the start of a line to denote a data access line. Following the "@" letter, there should either be a packet variable definition of FIELD, META, PROP or ATTR, or LOAD/STORE to access the data. Currently, we do not support direct algorithmic operations over packet data variables; they are used to denote the physical locations in the packet. Instead, we first load them into local variables, perform calculation, and then store them back. The benefit is that all non-data-access codes can be written as normal C codes. Algorithm 5 shows an example pseudo program. This user-defined SetIPChecksum action accepts an incoming IP packet and calculates and sets its IP checksum field; here the action assumes that the incoming packets are with MAC headers. As an example, the iphlen is defined first (Line 1), and loaded into a local variable hlen before used (Line 5).

Service Chain Scheduling
One challenging task for OpenFunction controllers is to perform service chain scheduling: given a flow and a sequence of SDM functions that the flow needs to pass through, the controller needs to choose a sequence of DP processes of that SDM so that the flow can go through this sequence of DP processes. Note that if a specific action in the program has multiple implementations (e.g., both CPU-based and GPU-based), then the compiled SDM data plane also has multiple implementations. The controller can load any desired implementation according to the resource scheduling and flow requirements. For example, if a middlebox's data plane graph has 3 actions and each action has 2 implementations; in total there could be 2 3 = 8 implementations stored for this middlebox at the maximum. Due to the cheap price of storage, we consider this exponential increase in the number of implementations a trivial concern.
There are some related work in service chain scheduling and enforcement. CoMb exploits consolidation opportunities in NFV deployment to save cost [23]. It also provides solutions to resource management, traffic redirection, and coordination among different data plane processing elements. However, it requires that the middlebox processes of the whole service chain pertaining to a given session flow run on the same device. This is not optimal in many OpenFunction scenarios: image that one hardware platform has special optimization for IPSEC, and another platform has special optimization for cache; force the whole service chain in a single node compromises the benefits of global resource optimization. Some schemes have been proposed to solve the problem of steering traffic among physical middleboxes to follow the network policy (i.e., service chain). As a pioneer work, the pswitches (i.e., policy-aware switches) scheme adds a new layer-2 for data centers, which can steer the network traffic through unmodified middleboxes [24]. Using SDN, SIMPLE can enforce flow-level policy even if middleboxes modify the packets or change the session level semantics [25]. FlowTag makes a further step by attaching tags to flow packets to enable flow tracking. These existing schemes can be used in OpenFunction to control the service chain among middlebox platforms [26]. Table 2 summarizes the symbols used in this section. For a given flow, the OpenFunction controller needs the following three types of inputs to perform service chain scheduling.
• Chaining Requirement: Each flow has a classification rule that uniquely identifies the flow and estimated bandwidth. For the given flow, we use SDM 1 , SDM 2 , · · · , SDM K to denote the sequence of K SDMs that it needs to traverse. This flow specification is typically specified by network operators.
• Implementation Availability: For each SDM k , let V k denote the total number of different implementations of SDM k . Each implementation has its specific resource requirement, which is usually multidimensional as different actions in an implementation require different resources.
• Box Capability: Let N denote the set of OpenFunction boxes. Let Ω n,r denote the capabilities of resource r in each box n. Also, the existing utilization of resource r in OpenFunction box n is denoted as Γ n,r (in percentage). The OpenFunction controller obtains box capabilities by performing resource monitoring of each OpenFunction box in real time.
As a practical constraints, all packets in a given flow should traverse the same DP process for a given SDM in the chain. The amount of resource r is required to support a unit of flow for SDM k with implementation i. Γ n,r the existing utilization of resource r in box n. Ω n,r the capabilities of resource r in box n.

A f
The amount of flow f Z l, j,m, f k,i,n Binary variable to indicate if flow f is traversed from the SDM k with implementation i on box n to SDM l with implementation j on box m. X k,i,n The amount of flows traversing node n for SDM k with implementation i.

ILP Formulation
The optimization objective in service chain scheduling is load balancing across all resources of all nodes.
The main constraint is the flow conservation for each flow crossing the SDMs ∑ l, j,m≥n In addition, a flow may traverse from SDM k to SDM l only if SDM k is followed by SDM l on flow f 's service chain, Based on this flow conservation constraint, the traffic can be calculated by To derive an ILP formualation, we can introduce an auxiliary variable z to present the objective function and z should satisfy and the objective becomes minimize z (6) Therefore, the Integer Linear Programming (ILP) formulation of this problem can be summarized as the resource utilization optimization problem (RUOP). Obviously, the ILP model formulated above is intractable in large size network. Specifically, due to the large dimension of binary variable Z l, j,m, f k,i,n , there will be more than 10 7 binary variables in the model even if each index has only 10 possible values. Accordingly, we need to design an efficient heuristic to solve this problem. Offline Algorithm We first consider the offline scheduling, where a number of flows are given and can be optimized at one time. Since the most critical element which makes our problem intractable is the large number of binary variables, we consider relaxation and rounding method to solve this problem. For clear presentation, we call the enforced service chain (i.e., the ordered SDM realized by which box and with which implementation, as the path of this flow. Following the relaxation and rounding idea, we first relax the binary constraint of the variable Z l, j,m, f k,i,n , i.e., treat it as a real variable in the range [0, 1], and solve the derived Linear Programming model. With this solution, each flow may be split among multiple paths which are determined by the value of Z l, j,m, f k,i,n . To get unsplitable path for each flow, a simple method is to directly round each flow to the path which carries the largest fraction of this flow. However, this method cannot obtain a good result especially when there are a lot of boxes and many implementation versions for each SDM. In this case, each path may carry only a little fraction of the flow; directly rounding each flow to the path carrying maximum fraction of flow may deviate too far away from the ILP optimum. To solve this problem, we propose a progressive method for the rounding phase to get unsplitable paths.
Respect to progressive rounding, the main idea is to iteratively forbid some links that carrying very little fraction for each flow, till there is only one path for each flow or there is a path carrying most of the fraction of flow. Based on above discussions, we design Algorithm 4 to solve the RUOP formulation. In this algorithm, there is one step that has not been discussed. In Line 4, we should find a threshold ε to determine if a Z l, j,m, f k,i,n should be set to 0 for the rounding purpose. This epsilon can be set based on the tradeoff between the algorithm performance and the algorithm running time. With large epsilon, more Z l, j,m, f k,i,n will be set to 0 in each loop and hence there are fewer loops executed in the algorithm. With smaller epsilone, we can do derive a better solution. On the other hand, we should update the epsilon in each loop since the Z l, j,m, f k,i,n should become larger in each loop as there are fewer paths can be used by the flows with the algorithm execution. Accordingly, without updating the rounding threshold, there will be endless loop in the algorithm. From Offline to Online We can also extend the algorithm to online version of this problem, because in reality service chain requests may arrive randomly, not all at once. The first scheme is to hold the flows for a while to get a bulk of flows and then trigger the offline algorithm to reserve SDM resources for these flows. If the flow arriving rate is very small, hold flows to wait for the later flows may be a large overhead for the flow arriving earlier. In this case, we can treat each flow as a bulk to trigger Algorithm 4 to set up SDMs for each single flow. 6 Prototype Implementation

Platform
We build a proof-of-concept system to verify the Open-Function abstraction and get an estimation of achievable performance. Data Plane We develop two x64 platform OpenFunction boxes based on DPDK and Netmap, and one hardware box based on FPGA. Netmap is a tool designed for high speed packet I/O in commodity servers. Implemented as either a modified NIC driver or a kernel module, Netmap also enables high-speed processing in user space. Supported by Intel, Data Plane Development Kit (DPDK) is a combination of data plane libraries and NIC drivers for fast packet processing in user space. Poll mode drivers (PMD) are designed to enable direct packets exchange between a user space process and a NIC. A low overhead run-to-completion model is used to achieve fast data plane performance. In our testbed, there are 16 Dell R320 machines, each has a 10G Intel X520-SR1 ethernet NIC and is both DPDK and Netmap enabled. We also develop a prototype box in a FPGA card via Xilinx Vivado High-Level Synthesis tool, which supports C/C++ to describe designs and translates them into hardware description languages (HDL) such as VHDL or Verilog HDL [33]. The platform is a programmable FPGA card with a Xilinx Kintex 7 chip, two 10 Gbps NIC and four 1 Gbps NIC.
For each prototype box, we need to provide three support: OpenFunction script, OpenFunction language and in-box chaining. Regards the third requirement, the device needs to support dynamic DP function loading/unloading: consider the scenario initially flow 1 only passes through SDM 1 and SDM 2, later an operator decides to add an additional action to be performed on that flow and therefore SDM 3 is inserted into the service chain. There can be many scenarios for such a need. For example, a company can perform DPI, to block instant message packets (such as gtalk and Skype) only during the office hour. Such temporary insertion/deletion of data plane instances should be seamless as no packet loss is allowed. A simple solution could be to temporarily hold the packets of the flow, construct a new service chain, and switch to the new chain. However, this approach adds significant delay to packets processing during the transition. Instead, we prefer a bufferless solution. Control Plane OpenFunction controller sends flow steering instructions to the Openflow controller. We use OpenDaylight (ODL) [34] as the OpenFlow controller that manages OpenFlow capable switches and routers. OpenFunction controller runs as an OpenDaylight application. It uses many base functions provided by ODL to learn about the network and control network elements.
In our testbed, we use OpenvSwitch [35] as a switching element to steer traffic. We use a quad core 3.0 GHz AMD Phenom(tm) II X4 945 Processor system to host the OpenFunction controller, the OpenFlow controller and all SDM CP processes.

Script Support
Due to space limitation, we only explain how Netmap-Click and FPGA platforms works. Netmap tool does not provide enough native packet libraries; therefore, we use Click as the packet processing pipeline.
The translated Click script of the IPSEC data plane specification (Algorithm 1) is shown in Algorithm 2. One major challenge is the abstract parameters of actions in the specification: we either replace them with real parameters in Click format, or implement them as action attributes, and let the IPSEC CP process sets them in runtime. Another challenge is that we need to add additional MarkMACHeader and MarkIPHeader elements, after the input device action, for Click specific requirements.
In FPGA box, both OpenFunction script and pseudo language are translated to the special C/C++ code: the specification is translated to the top level block (composed by a call graph among low level blocks), while each pseudo language based action definition is translated to a low level block. The translation of data plane IPSEC specification (Algorithm 1) as shown in Algorithm 6, requires (1) defining the inter-link between functional actions (i.e., [5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][20]; and (2) using direct function calls to represent actions (e.g., . Note that in FPGA platform, we implement all parameters as action attributes, which are controlled by its corresponding CP process.

Language Support
In Netmap platform, we translate each action pseudo program to an element class definition in Click. Mostly, the generated codes are in the simple action function. Each special line in the pseudo language file is processed. For example, Algorithm 3 is the translated code of generating a pointer to IP header length field (Algorithm 5 Line 1). Other codes are input from the pseudo program as is.
OpenFunction language translation in Xilinx FPGA is similar to the operations of that in Netmap. The major difference is that: an additional C++ encapsulation class is required for each action class, to express the state transition semantics in FPGA hardware. Due to space limitation, we omit the details of both FPGA and DPDK platforms.

In-Box Service Chain
In this part, we use DPDK to illustrate the provisioning of in-box service chain. We use process group to realize the service chain and treat each SDM data plane instance as a separate process. As shown in Figure 4, a single IO process acts as a central process: it sets up all memory structures for use and handles packet reception and transmission. A pair of rings are setup between the IO process and a SDM process for packets exchange. When a new SDM DP process starts, it discovers both the rings and packet memory locations via DPDK library support. The IO process sends a packet's descriptor through the ring; a SDM data plane processes the packet and returns it via another ring.
The pair of rings is the key to realize dynamic load/unload. Each packet's metadata carry the service chain information: an array records the indexes of ring Similarly, to unload a service chain, when SDM 3 is removed from the service chain, the metadata of all subsequent packets change to the new service chain SDM 1 → SDM 2 again; the controller waits for a while, before it cleans up the SDM 3 process from the system. For performance consideration, we assume all processes of a group is running on a single CPU socket (possibly with multiple cores). Note that multiple process group is supported, if we start different process groups in different sockets.
We also support this feature in the FPGA platform. Unlike software, loading/uploading new data plane functions in programmable hardware needs direct support from hardware. Partial Reconfiguration is a feature of modern FPGAs, which allows a subset of the logic fabric of a FPGA to be dynamically reconfigured while the remaining logic continues to operate [36].

Developed SDMs
We implement NAT and IPSec gateway as two stateless SDMs on all Netmap and FPGA platforms. The NAT middlebox performs simple address translation; the mapping table is stored in its CP process and the mapping item is send to a DP process when the first packet of a flow comes in. The IPSec gateway uses ESP tunnel model with AES-EBC encryption. The control plain negotiates with the remote peer, and sends command to DP processes after security negotiation.
With Netmap, we also implement a simple stateful firewall and a stateful IPS. The stateful firewall monitors all path-through TCP connections; it removes the allow rules in both directions whenever a RESET flag is detected. The stateful IPS monitors FTP connections: some FTP commands are allowed only after the user authentication; otherwise an alert is raised.

Abstraction
First, we test the OpenFunction specification performance for the data plane abstraction of each SDM. For each SDM, we use same set of OpenFunction specifications. We test with both small size packets (60 bytes) and large size packets (1400 bytes). Table 3 shows the throughput performance.
For non-stateful SDMs: NAT and IPSEC, DPDK box achieves higher throughput than Netmap-based box in almost all the scenarios. This demonstrates that, even with the same OpenFunction abstraction implementation and the same hardware, the performance actually relies on underlying systems. In turn, the FPGA box is always better than DPDK. Key Takeaway 1 Our OpenFunction abstraction accommodates vendor differentiation with the same code across heterogeneous systems, which is beneficial for the NFV community. Next, we replace the SetIPChecksum and SetTCPChecksum actions in the specification with user defined versions (written in OpenFunction language and translated). The performance overhead caused by user defined versions is negligible: for these softwarebased boxes, without special acceleration treatment, the C compiler performs most of the optimization work. Also, for such an action, the efficiency of a translated version is similar to the implemented version.
For FPGA platform, the performance gap between optimized implementation and OpenFunction language generated version (i.e., FPGA-C) is significant (10x in this case) Table 3. The reason is that FPGA enables a programmer to introduce several optimizations. For example, for NAT function, the programmer may choose to calculate the checksum at line rate, without the need to receive complete packet. Key Takeaway 2 The performance of SDM data plane actions, if generated from OpenFunction pseudo language, is dominated by the nature of system. Similarly, for two stateful SDMs: FW and IPS, the performance is comparable to non-stateful SDMs. Key Takeaway 3 OpenFunction abstraction has the potential to support various stateful firewalls.

Centralization
In this section, we evaluate our algorithm by leveraging the traffic data collected from a production datacenter hosted by IBM global services. To this end, we conduct performance evaluation from two perspectives. First, we evaluate the impact of varying number of flows in the system on algorithm performance, and then the impact of threshold selected at line 4 in Algorithm 4 on algorithm performance.
Performance impact by varying the number of flows: In this section, we fix the box number to be 10, there are 6 SDMs and the required SDM number of each flow is evenly distributed in the range [1,5]. Each SDM has 2 or 3 versions implemented in the system. In addition, we set the forbidden threshold to be 0.2, i.e. 20% of the Z l, j,m, f k,i,n and the fraction value according to the LP solution will be set to 0 in each iteration. To see how the algorithm performance changes with the number of flows, we change the flow number from 100 to 1000, and the simulation results are shown in Fig. 5. We evaluate the performance of proposed online and offline algorithm and compare it to the LP solution, which treats all the flows as splittable, and hence the LP solution is a lower bound of our problem. From Figure 5, we make two observations: i) the online algorithm achieves performance very close to LP solution, and ii) its performance margin from offline approach improves with increasing number of flows in the system.
A single flow only needs very little system resource compared to the available system resources, and there- fore, we can treat all the flows as splittable in the system's point of view. As a result, the performance of offline algorithm is very close to the LP solution.
The performance of online algorithm deviates from the optimal solution as the number of flows increase in the system. This is for the reason that the online algorithm is a myopic algorithm and optimizes the flows one by one, whenever a flow enters the system, it optimizes the maximum resource utilization based on the current system utilization but does not consider future flow arrivals.
The impact of threshold ε: In this section, we study how the forbidden parameter impacts the offline algorithm performance. For this purpose, we inject 400 flows into the system and change the value of forbidden threshold from 0.1 to 0.95.
The simulation results, Fig. 6, show that for smaller thresholds, the offline algorithm performance degrades very slowly with increasing the value of forbidden threshold. However, when the threshold value exceeds a certain point, the algorithm performance degrades quickly. The reason is that in the LP solution, there are many Z l, j,m, f k,i,n with very little fraction, and they can be set to 0 at one time without impacting the performance significantly.
In addition, as the value of the forbidden threshold continues to increase, the performance degradation slows down. This happens because if we set too many Z l, j,m, f k,i,n as zero, the optimization space for the flows reduces significantly. Therefore, forbidding more Z l, j,m, f k,i,n cannot degrade the algorithm performance if the forbidden parameter is relatively large. Key Takeaway 4 OpenFunction abstraction has the potential to support various stateful firewalls.
Lastly, we consider two scenarios to evaluate Open-Function data plane overhead: (1) time it takes to start/stop a data plane process in the service chain; and (2) additional path delays due to our chain enforcement inside a box. In the first case, we are interested in understanding how much delay is incurred when a new service chain or SDM DP is added or removed from the network. To evaluate, we use a small topology with 5 DPDK middleboxes and generate TCP flows between source and destination. We have two DPDK boxes on path 1 and one DPDK box on path 2. We initiate flows on path 1 and path 2 which initiates flow rule installation in the switches along the datapath and calculate datapath setup times. Our evaluation shows that it takes less than 100 msec to add a new datapath or service chain in the network. In the second case, we are interested in understanding the additional delays caused by enforcing service chains in the MB's. Our evaluations shows that it adds less than 20 usec per SDM DP in the service chain.
In this case, we are interested in knowing the responsiveness of the controller to adapt to dynamic network conditions and we measure the time required to reconfigure the network in case of SDM DP failure or traffic overload in some of the service chains. We consider same topology as before, with DPDK middleboxes, and use Iperf [37] to generate TCP flows between source and destination. We first initiate flows on path1 and path2 by install rules in the switches along the datapath and distribute load evenly across the two paths. Next, we bring down the switch in path2 and observe how quickly network converges to the stable state and diverts traffic to path1. Our evaluation shows that network takes less than 200 msec to converge to a stable state and reconfigure flows to use other paths. We also dynamically change the datapaths, to replicate the SDM insertion and deletion scenarios, in our topology to steer network traffic through different paths and our evaluation shows that the network quickly adapts to these changes without any drop in the flow throughput. Key Takeaway 5 OpenFunction abstraction is flexible and has light overhead.

Conclusions
In this paper, we make three main contributions. First, we propose the concept of Software-Defined Middleboxes to realize abstraction and centralization for middleboxes, which are complement existing SDN effort. Second, we propose OpenFunction as an SDM reference architecture and a network function abstraction layer. Third, we implemented a working OpenFunction system including one OpenFunction controller, three Open-Function boxes, and four network functions including both stateful and stateless ones. Our experimental results show that the middlebox functions implemented using our OpenFunction abstraction can achieve high performance and platform independence.