Orchestrating Network Functions in Software-Defined Networks

Hongchao Hu, Lin Pang, Zhenpeng Wang, Guozhen Cheng

National Digital Switching System Engineering & Technological R&D Center, Zhengzhou, 450002, China

I. INTRODUCTION

The design of legacy Internet leads to definite discrepancy between high-level applications and low-level network functions, where the former evolve fast driven by outsourcing services to third-part OTT (over the top) companies like Google, Facebook etc., the latter innovate hardly as it present itself as the closed set. Many low-level appliances, or middleboxes, are systems that examine and modify packets and flows in sophisticated ways: e.g.,network address translators (NATs), intrusion detection systems (IDSs), load balancers,caching proxies, etc. Can such network functions evolve as fast as high-level applications?Fortunately, the paradigmatic shift from a legacy network of coupling the decision-making and packet-forwarding to a software-defined network (SDN) [1] of decoupling the decision-making and packet-forwarding is creating unprecedented opportunities for network function innovations. Via outsourcing network functions [2], this architecture shall inevitably boom network function innovations in the near future. However, with the absence of normal primitive interfaces, how shall we organize various network functions spread all over the network?

Before SDNs, new network functions may be embedded in end-hosts or added in switches and routers, even deploy middle-boxes [3]where needed. It is impossible for network operators to supervise and configure them in the cooperative way due to the lack of global information about them.

SDN strides the first step to open the hull of core network. It alleviates the increasingly complexity in the network equipment. A number of instances of network function inevitably co-exist in the network so that users could have more choices on which low-level isotopic function is served for them. At the same time, the network operators will have more freedom to control how the network should be run, since they can make different choices for different demands via selecting appropriate instances of functions to combine different optimal processing pipeline.

In contrast with the ebullience in various network innovations on the controllers, rare works engage in how to define interfaces for network functions. There is no mechanism to orchestrate them by selecting their instances provided by different third-part groups.Apparently, although the current SDN is not prepared to manage large numbers of function instances, the epoch of network function innovations is inevitably coming.

In this paper, we propose a model, called function combination model (FCM), to re-abstract low-level network functions. FCM define the network function with a six-tuple, and each network function can be identified based it. Third-part providers can register to provide instance for one class of network function.We then propose an approach to recognize low-level network functions to build function pipelines. The main contributions in this paper are following,

● We design a model, FCM, to standardize interfaces for network function so that it is easier to orchestrate the instances provided by different third-part groups. Based on SDN, we extract network functions. The goal of our model is to define the network function, and then dynamically combines available instances. The network functions can be developed and provided by any specialized companies, called external NF providers (NFP), not monopolized by infrastructure providers.

● We formulate the problem of composing network functions into 0-1 integer programming (BLP) under the global network views. Based on the pipeline confuted by network operator, we choose an optimal instance for each network function in the pipeline. Theoretically, we should enumerate all the possible solutions to find optimal ones. Considering the problem is a NP-hard, simulated annealing algorithm is designed to approach optimal solution for this BLP.

● Numerical results demonstrate our algorithm can approach a tradeoff between the cost and optimized pipeline.

The remainder of this paper is organized as follows. The next section gives the related works. Section III discusses the notions and preliminaries for FCM. Section IV presents the FCM and its Boolean linear problem. Section V indicates the algorithm for FCM. Section VI presents the design decisions involved in the development of Matchmaker. Section VII presents the experimental evaluation of our Matchmaker and several case studies. Section VIII concludes this paper and brie fly discusses some future research directions.

II. RELATED WORKS

It comes as no surprise that middleboxes are the most important appliances to extend core network function in legacy Internet for external minority enablers other than infrastructure providers. For example, deploying load balancer middlebox on the flow congest points [14]. Middlebox can be added only where needed, while we have to firstly determine where to place.

Recently, large strides have been taken on the controller in the SDNs since thefirst centralized art OpenFlow controller, called NOX[15], bring up. A mass of schemes have been provided and developed from multi-thread controllers, like Maestro[16] and Beacon[17], to the distributed system, like Hyper-Flow[18], Onix [19], SiBF [20], and Devolved Controllers [21] Kandoo [22] and ElastiCon[23] provide logically centralized but physically distributed control planes. Most of those works has taken more attentions on scalability and reliability. Alternatively, our work in this paper focuses on organizing various network functions by abstracting basic network functions.

Glen Gibb et al. [2] present an architecture for add network function via outsourcing to external feature providers who is the third-part capable companies. This architecture has the purpose of flourishing the network function innovations by introducing competitions among providers. However, outsourcing will bring more instances deployed by different providers that have similar or overlapped functions inevitably co-exist in the network. Unfortunately, this work does not point out the decision-making about the choice of appropriate instances from candidate to form a completely optimal processing pipeline.

Then, another work, called Beacon [8],aims to develop an interface-friendly framework and the runtime ability to start and stop existing and new applications. Although Beacon indicates us to a more modularized approach for network functions, it is short about how to operate them in the cooperative ways.At the high level, Frenetic [11] and Pyretic[12] give a composing language to manually arrange the application in SDN, but they present more stress on the rapid innovations. J. C.Mogul [13] et al. provide a design for control plane, called Corybantic, which supports composition of modular programs in independent controller and achieves both modular composition and optimization, while it limits itself in single controller and formulates the controller stack at a high layers. Our system decouples orchestral plan from instances that actually execute the plan, and associates through our FCM model to select instances distributed the network.

Lecture [24] takes Deep Packet Inspection(DPI) as a critical building block for the middleboxes. In its proposed orchestration structure, the traffic of any policy chain must first through a DPI before it is routed to other middleboxes. Our research is orthogonal with it,since our optimized FCM model can be used in the DPI-specialized policy chain’s orchestration.

Qazi et al. [25] provide a SIMPLE policy enforcement layer based on SDN to build the service chain. It focused on chaining middleboxes based on programmable switch. Our model is optimizing the selection of instances for each network function. Literature [26] is similar with [25]. It define an amazing flowtag with causal context. Our work could use this tag as the one of the identifiers for the network function.

IETF started the group of service function chain (SFC) architecture to decouple the physical topology and service function deployments [27]. In this group, several drafts have been submitted to show many user cases.They are focused on packet structure, security,control plane design etc. As stated in [28][29],researchers should promote some drafts to optimize SFC con figuration.

Our work is built on the prior works of [2]and [13] but differing from them for two aspects. Firstly, we re-abstract the low-level network functions into finer units, network functions, and expose them as the basic components. This can be in favor of standardization on northbound interface of SDN controller.Secondly, we extend the modular composition in the global network, and theoretically model the scenario as Boolean linear programming.

III. PRELIMINARIES

In this section, we will brie fly discuss the basic conceptions about network functions, combined chain and policy before presenting the FCM.

3.1 Network functions

The emergence of SDN is taken as one promising approach, with virtues of frequent innovation, agile programming as well as naturally convenient for management, and gradually evolve from centralized control to distributed control for WAN [30][31]. The control functions have a chance to outsource to the feature providers [2]. However, the absence of explicit criterion to basic components dispersing different layers of legacy Internet makes it impossible to manage diverse modules that are incrementally developing and instantiating.

For instance, Fig. 1 shows a typical SDN-enabled network. Controller A has the global network view. In the network, there are two IPS instances from different providers linked to switch E1 and E2 respectively. In the current architecture, the controller has difficulty in identifying them as the same one and deploys both of them. For example, if network operators want a policy that all traffic should traverse a node with monitor such as IPS before access some storage resource like Hash Table (HT) which could be used in the DNS.User 1 launches a connection to HT, the path from User 1 to HT will established between E1 and E2. The flow from User 1 will traverse IPS twice. It is difficult to identify two IPS instances as the same network function because there is no uniform interface for each type of network function. In fact, if modules like IPS and HT can be exposed with the standardized module name or ID to the controllers, the flow will be well-processed along with “IPS→HT”not “IPS→IPS→HT”.

Fig.1 a simple SDN topology

Our proposal is based on the idea of modularizing finer core network functions (like congestion control, flow control, routing, and fragmentation), namely network functions,that are offered by the network core. We believe that there is a basic network function set that can be used to combine complex processing pipeline. With the unified interface, we can customize its properties of each network function.

We identify an NF using the interface ＜Type, ID, Name, Attributes, Action, Provider＞.Type presents the class of the network function and determines its semantics. It is used as the publishing tag that is shared among controllers. ID is a number generated randomly to identify one of its instances, thus thisfield can be empty before the network function is instantiated. Name is used to naming its instances semantically when the network function is deployed. Attributes is a set of properties for configurations when instantiates it. The attributes can be grouped into objectives denoting what to be processed and demands denoting what to be subjected to. The action indicates that all the traffic the attributes identified will execute the action. We have many choices about actions. For example, the action can utilize the action set defined in OpenFlow. And the provider presents the manufacturer of its instances.

3.2 Policy

In this paper, a policy is configured by the network operator to manage schemes for network plan or control the given traffic flows for traffic engineering. It represents as ＜o(jì)bjective set, NF set, demand set＞. The objective set is the collection handled by execution set. In traffic engineering, it is a collection of traffic flows, {dstIP:192.168.0.0/16 dstPort: 1433},for instance. NF set is a list of NFs identified by types. The objective set must experience all listed NFs. However, the complete pipeline cannot violate the demand set no matter how complexity the process is. Demand set de-scribes the behavior pro file of global process measured by quality of services.

Definition 1 (Policy) The superset

is a policy iff:

Before arriving at enterprise network,ingress flows commonly undergo counter,monitor, NAT and load balancer. If network operators configure that the flows destined 10.1.2.0/8 and destined port 80 must be counted, monitored, NAT, and balanced as well as TTL-limited. Then, the policy is expressed as ＜{dst_ipv4:10.1.2.0/8 and dst_port:80},{counter, monitor, NAT, load balancer },{TTL＜5}＞. This rule-based policy, though simple, suffices for deployment described in this paper. We expect that future deployments will have more specialized policy needs.

3.3 Combined NFs specification

Combined NFs is specified as a collection of network functions that are combined sequentially on demands, called combined chain.Combined chain represents a more complex function primitive for a complete pipeline. The preceding example—“IPS→HT”, is a simple paradigm. In practice, the structure of combined chain is more complexity than as a complete pipeline come down to various NFs. The generic shape is “NF 1→NF 2... NF n”, where NF i is the specialized name for this NF.

Definition 2 (Combined Chain) Letis a non-empty NF set, i.e.,a sequence setis a combined chain, iff:

Fig.2 the structures of combined chains

There are various ways for individual network function can be integrated into combined chains. The possible structures of combined chains are sequential, parallel, and conditional and so on, shown in Fig. 2. In this paper, we only study the sequential structure since it is a basic one that others can be integrated with the sequential ones.

For a combined chain, we should select an instance for each NF to execute corresponding tasks. Each NF has a candidate instance set which may disperse over the network,and we should select one from it to instantiation. When all NFs in one combined chain are instantiated, an execution pipeline can be achieved, and we called execution path. The symbolic form of combined chain is as follow.Defining the symboldenotes instantiation, i.e.,meansis an instance of

Definition 3 (Execution Path) Letis NF set andis the instance set ofThenis the execution path of combined chainif the elements insatisfy to

The execution path can be written asa n dwhereis a direct successor of

IV. FUNCTION COMBINATION MODEL

In this section, we describe our FCM model about how to combine network functions spread over the network.

4.1 Mapping model

Before a policy configured by network operators is transformed into flow entries residing on the switches, there are several operations we have to accomplish. First, the policy is mapped into combined chain, and this “policy-combined chain” (P-CC, for short) operation can be symbolized as follow,

Operation 1 (P-CC)where

Second, we must select an existing instance for each NF in the combined chain, since a parameterized combined chain is merely an executing plan. Running back the illustration in Fig. 1, if nodes E1, E2 and E3 have flow entries for IPS, a choice should be determined for IPS to select a node from three instances.The rest may be deduced by analogy. Then a feasible executed path can be calculated under the constraints. This “combined chain-execution path” (CC-EP, for short) operation can be symbolized as follows.

Operation 2 (CC-EP)Letis a parameterized combined chain, anddenotes all the instances forrepresents all the instances forthe CC-EP operation is denoted as

CC-EP operation will success, ifthere is at least one feasible execution path for combined chain.

4.2 Function combination model

As we stated in the preceding subsection, we can readily get combined chain with numeric parameter from a valid policy, i.e., P-CC operation. However, finding the feasible even optimal execution path for combined chain on demand has more complexity in our scenario than in today’s network with only the shortest path policy. There are several main factors that contribute to this complexity. For one thing, many instances will be developed and deployed over the network by third-part companies, thus there is a candidate instances set for each NF. For another, the load distributions over the network have high diversity of patterns, and result in that the declared performances of NF instances by the owners in the geographic area dynamically change.

We should search appropriate instances for each element of combined chain under given constraints, called CC-EP problem, and then redirect the objective traffic to the nodes that our selected instance is resided in. before further study, given a topology G(V, L), where V is the nodes set, and L is links set. Suppose a network operator configures a policy, corresponding combined chain. We give the following explains about related symbols used in the reminders.

There are two ways to solve CC-EP problem, local composite model (LCM) and global composite model (GCM), LCM takes each parameterized network function in combined chainas independent task, and then the CCEP problem can be separated intosub-problems. Inth sub-problems, we should select an instance fromThis approach can divide CC-EP problem into several sub-problems that only local information is necessary,though, the ultimate solution often yields a point that is local optimization and even infeasible. For example, the instance for each network function inis an optimal solution respectively, but the incorporation is not the optimal or feasible one, because the route that links the entire execution path may not be optimal or feasible path. More importantly, LCM cannot handle the inter-constraints. For example, the preceding description about enterprise network is constrained on “TTL＜5”.

In the LCM, instance selection is done for each network function independently. In contrary to detach the network functions, the combined chainis cooperatively considered among network functions in the GCM.Each type of quality is calculated by. For each network function inthere is one and only o ne instance selected, namelyAnd each declared quality for network function only contributes to total quality pro file in the proportional way. We formulate GCM for selecting an optimal CC-EP as follow,

Where formula (1) is an objective function,and inequations (2) and (3) are the quality constraints that the executed path should satisfy. Inequation (4) is the capacity constraints for every instance.denotes the real number of pending requests in instance, andnotes the total number of requests the instancecould deal with. Equation (5) are 0-1 constraints, whereis variables set. In the problemobjective function and the constraints are linear,and the possible values of variables are 0 or 1,hence this is a Boolean linear program [32].

4.3 Utility function

Since different qualities may manifest opposite characteristics, i.e., the results ofare more optimal as some quality values are larger yet the others are smaller,we distinguish each other in inequation (2)and (3). Accordingly, we define a function to transform all qualities into consistent optimal direction so that network utility increases with the function no matter what characteristics the qualities present. Besides, the transform function should eliminate the effects stemming from various extents of qualities. And without loss of generality, we normalize them in range

Given a set of provider-declared values of k-th quality for instance setdenoted asbe the maximal value of elements inandbe the value of-th element, then

We introduce the quality ratioto normalizeand get

V. THE SOLUTION METHOD

5.1 Simulated annealing algorithm

To solve this problem, the general method is relaxation, i.e., the constraintsis replaced with linear inequationsor Lagrangian relaxationThen the problem is referred to LP relaxation(or Lagrangian relaxation) of Boolean linear program. Both the optimal value of LP and Lagrangian relaxations are the lower bound on the optimal value of Boolean linear program.The relaxations are far easier to solve than the original one. Finally, the optimal value of relaxations approximates to 0 or 1. But thefinal solutions of this approach maybe infeasible.

Alternatively, simulating annealing algorithm (SAA) [33], which is an effective searching technique for combinational optimal problem, can be used in our scenario.Letbe a solution of problemthat satisfies to constraints (2) ～ (6). We call a solution as a con figuration or state in SAA.Letbe the state space whose size is less thanandbe the energy at stateThe metropolis algorithm [34] is employed to calculate the transformation probability from stateunder temperature like that

In the SAA, the metropolis algorithm permits some degeneracy of solution during the iterations so that it has a chance to avoid local optimization. And the degeneracy is convergent as the temperaturediminishes.

The iteration path for the value of temperatureconstructs a Markov chain. The parameteris the length of this Markov chain during the-th iteration of Metropolis algorithm, and letbe the size of the local domain ofi.e.,To control the process of the algorithm, an attenuation function for temperature shown in the equation (16) proposed by Kirkpatrick et al[33] is used in our scenario.

?

5.2 Structure of state space

Although the SAA is more effective in time than exhaustive algorithm, it will also consume more time to approach optimal solution when the scale of the problem becomes large.Thus we must control the scale of the problem. One of techniques is to resorting to the heuristic information so that we can shrink the search space.

In practice, it is not necessary to select a configuration from the entire state space,since most con figurations are likely infeasible if we consider the topology.

Many scenarios in today’s Internet, such as data center network [35], compulsively offer several candidate paths between any two nodes. Only if the request service chain is instantiated along with those paths, the generated execution path is possibly valid. Then the search space of the problemis reduced to the compact multipath space. Note that network paths will not vanish unless the underlying topology changes. Furthermore,the time scale that topology changes is much longer, compared with the one that the operation policies instantaneously change [13]. Accordingly, we can take the compact multipath space as invariables when we calculate the problem

VI. THE NUMERICAL EXPERIMENT

6.1 The simulation results without topology

In this subsection, we observe the performance of our algorithm without topology. This scenario can be used to simulate the generations of service chains limited inside a network node.

We assume that there are 100 network functions, and 10 instances for each network function. The instance can be configured via 4 parametersrepresents the parameters whose values have the positive directions with the network performance, andrepresents the parameters have the reverse directions with the network performance. Without loss of generality, the simulation randomly generates the demands with three network functions and parameters demandsThat is mean the sum of each parameter of three network functions should satisfy the parameters demands. When any one of instances achieves upper limits(e.g., 40～50 times invocation), the simulation stops.

To the best of our knowledge, there does not exist any benchmarking tools for function combination models in the networking domain. To address this need, we implement an EA algorithm for the problemto achieve optimal solution in advance, and the results from SAA are compared with it. For each scenario, network functions are randomly distributed inside the network. And a total of 2000 connection requests are generated randomly.

Fig.3 The network load distributions among instances for the 1st time

Fig.4 The network load distributions among instances for the 2nd time

Fig.5 The network load distributions among instances for the 3rd time

We count the total pending requests on the network function instances as the network load. To omitting the random in fluence in the experiments, we repeat this experiment for three times. Fig. 3～Fig. 5 show the network load distribution at all ten instances of two network functions A and B. we can see that our algorithm can approach the balanced effects among instances with the exhaustive algorithm.

We then compare the time-consuming of two algorithms. Similarly, we run three times for our experiment as the number of requests increase from 500 to 3000 with the step 500.Fig. 6 shows the average time-consuming curves of two algorithms for three repeated experiments. The EA algorithm uses more time to response the same scale requests than our SAA algorithm. Furthermore, this gap is broadening as more requests arrive at the controller. The appendix gives the detail results of our experiments.

6.2 The simulation results with one topology

In this subsection, our simulation scenarios are based on a network topology with 6 nodes shown in Fig. 7. Without loss of generality,we suppose that all nodes and links in the topology are homogeneous, i.e., they have the same capacities. We use this simple topology because we can easily enumerate all paths between any two network nodes.

In this topology, there are totally 30 (src,dst) pairs whose paths are listed in Table. 1.Take a src-dst pair (1, 2) for example, we can find five paths from node 1 to node 2: (1,2)(1,6,3,2) (1,6,4,3,2) (1,5,4,3,2) (1,5,4,6,3,2).

If there are 100 network functions numbered from 1 to 100 in the network, and denoteinstances of different network functions randomly are installed on one node where the numberWe suppose that the instances for a network function are distributed over the network, but one network node deploys at most one instance for an network function.

We emulate to send data delivery requests including network functions, performance demands besides source and destination node. As stated in [36], CPU cycles are the bottle-neck compared with bandwidth and memory when controllers respond to the requests. Although the requests need various resources, we only divide the CPU cycles equally to 10,000 slices, and then we randomize the requested resource-consuming for each network function instance.

For example, a request may be like ＜ (1,(20,30,60) ＞ which means that searching an optimal path from node 1 to 2 so that there is an instance list of network functionthat require the node resource about (20,30,60) respectively.And thus we should search all the paths from node 1 to node 2 (1,2) (1,6,3,2) (1,6,4,3,2)(1,5,4,3,2) (1,5,4,6,3,2) which satisfy both the network functions and their resource demands.If there is more than one path satisfied, we randomly select one from the candidates and produce the service chain. It is noteworthy that each network function instance is concurrently shared by 40 ～ 50 service chains. We take the total pending requests on the network nodes as network load. Fig. 8 shows the average network loads of three repeated experiments at all six nodes when we force 10,000 requests on the network. We can see that our FCM mechanism can approach the network-wide load balance.

To simulate the situations without our FCM, we adopt the shortest path strategy on the controller to calculate the path in the same network topology. We send 10,000 requests limiting (src, dst) to (1, 2) and (1, 3) for both our orchestrator and the shortest path strategy.But the requests send to our orchestrators have network functions list demands, and the requests send to the shortest path strategy have no network functions demands.

We show the average network load distributions over the topology that is shown in Fig.9, we can observe that the scenario without orchestrator is prone to load imbalance, since the shortest path for requests (1, 2) and (1, 3)will exclude the node 4 and 5 in the topology shown in Fig. 7, and leads to node 4 and 5 have empty requests. The scenario with our orchestrator achieves load balance so that the network can support more traffic flows,since our orchestrator consider the request.The readers can refer to Appendix B about the experiment detailed results with the network topology.

Fig.6 The average time-consuming for a request

Fig.7 th e network topology for experiment

Table I The paths to all the pairs

F ig.8 The network load distributions on all six nodes

Fi g.9 The comparison of the network load distributions with and without our orchestrator

Fig.10 The compared time-consuming of our orchestrator with(out) multipath info

Finally, we measure the accelerated effects of our orchestrator using the multipath info.If there is no multipath info used to calculate the execution path, the system should search over the topology. We also compare the legacy multipath routing without considering the network function instantiation. Fig. 10 shows the time cost curves as the increasing requests arrived. We can observe that the accelerator with multipath info reduces the time cost of our orchestrator, and this improvement will become much evident as the requests increase.In addition, we also observe that our orchestrator only increase small delay than legacy multipath.

VII. CONCLUSION

In this paper, we give an abstraction to the application on the SDN controller, network function. Then we provide a network function combination model for network functions and formulate it into a Boolean linear problem. Via the proposed simulated annealing algorithm,we can approach the optimally orchestral schema. Finally, taken the algorithm as the core,we design the network function orchestrator,Matchmaker, over the SDN controller. The results are corroborated by two case studies and several numerical examples which show our orchestrator can achieve a much higher network utilities than the situation without orchestrator.

Our future work will emphasize on two aspects. Firstly, we will ful fill the residual works and upload manual and code online. Then,based on our abstractions, policy and network functions, we can easily develop graceful implementations about traffic engineering, and resource isolations, hence we can used our system in network management and network virtualization, even in the production networks.

ACKNOWLEDGMENT

This work is partly supported by the China Postdoctoral Fund Project (No.44603),the National Natural Science Foundation of China (No.61309020), the National key Research and Development Program of China(No.2016YFB0800100, 2016YFB0800101)and the National Natural Science Fund for Creative Research Groups Project(-No.61521003).

[1] N. McKeown, T. Anderson, H. Balakrishnan, G.Parulkar, et al., “Open flow: enabling innovation in campus networks,” SIGCOMM CCR, 2008,69–74.

[2] Glen Gibb, Hongyi Zeng, Nick McKeown, Outsourcing Network Function. HotSDN’12, August, 2012, Helsinki, Finland, 73-78.

[3] Wal fish, M., Stribling, J., Krohn, M., Balakrishnan,H., Morris, R., and Shenker, S. Middleboxes no longer considered harmful. In Proc. of OSDI ’04(Berkeley, CA, USA, 2004), USENIX Association,pp. 215–230.

[4] Caesar, M., Caldwell, D., Feamster, N., Rexford,J., Shaikh, A., and van der Merwe, J. Design and implementation of a routing control platform.In Proc. of USENIX NSDI ’05 (Berkeley, CA, USA,2005), NSDI’05, USENIX Association, pp. 15–28.[5] Casado, M., Freedman, M. J., Pettit, J., Luo, J.,McKeown, N., and Shenker, S. Ethane: taking control of the enterprise. SIGCOMM Comput.Commun. Rev. 37 (August 2007), 1–12.

[6] Greenberg, A., Hjalmtysson, G., Maltz, D. A., Myers, A., Rexford, J., Xie, G., Yan, H., Zhan, J., and Zhang, H. A clean slate 4D approach to network control and management. SIGCOMM Comput.Commun. Rev. 35 (October 2005), 41–54.

[7] Joseph, D. A., Tavakoli, A., and Stoica, I. A policy-aware switching layer for data centers.SIGCOMM Comput. Commun. Rev. 38, 4 (Aug.2008), 51–62.

[8] Tao Yu, Kwei-Jay Lin, Service selection algorithms for Web services with end-to-end QoS constraints.

[9] L. Zeng, “Dynamic Web Services Composition,”PhD thesis, Univ. of New South Wales, 2003.

[10] L. Zeng, B. Benatallah, M. Dumas, J. Kalagnanam, and Q.Z. Sheng, “Quality Driven Web Services Composition,” Proc. 12th Int’l Conf.World Wide Web (WWW), May 2003.

[11] N. Foster, R. Harrison, M. J. Freedman, C. Monsanto, J. Rexford, A. Story, and D. Walker. Frenetic: A Network Programming Language. In Proc.ICFP, pages 279–291, 2011.

[12] C. Monsanto, J. Reich, N. Foster, J. Rexford, and D. Walker. Composing Software-Defined Networks. In USENIX NSDI, 2013.

[13] J. C. Mogul, A. AuYoung, S. Banerjee, et al, “Corybantic: Towards the Modular Composition of SDN Control Programs” Hotnets’13 November,2013,, 1-7.

[14] Wal fish, M., Stribling, J., Krohn, M., Balakrishnan,H., Morris, R., and Shenker, S. Middleboxes no longer considered harmful. In Proc. of OSDI ’04(Berkeley, CA, USA, 2004), USENIX Association,pp. 215–230.

[15] N. Gude, T. Koponen, J. Pettit, B. Pfaff, M. Casado, N. Mckeown, and S. Shenker, “NOX: Towards an Operating System for Networks,” in SIGCOMM CCR, 2008.

[16] Z. Cai, A. L. Cox, and T. S. E. Ng, “Maestro: A system for scalable OpenFlow control,” Tech. Rep.TR10-11, CS Department, Rice University, Dec.2010.

[17] David Erickson, “The Beacon OpenFlow Controller,” In Proc. 1st Workshop on Hot Topics in Software Defined Networking (HotSDN 2013),pages 13-18, Hong Kong, 2013. ACM Press.

[18] A. Tootoonchian and Y. Ganjali, “HyperFlow:A Distributed Control Plane for OpenFlow,” in INM/WREN, 2010.

[19] Teemu Koponen, Martin Casado, Natasha Gude, Jeremy Stribling, Leon Poutievski, Min Zhu, Rajiv Ramanathan, Yuichiro Iwata, Hiroaki Inoue, Takayuki Hama, and Scott Shenker.Onix: a distributed control platform for largescale production networks. In Proc. 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2010), pages 351-364,Berkeley, 2010. USENIX Association.

[20] C. A. B. Macapuna, C. E. Rothenberg, and F.Magalh. In-packet bloom filter based data center networking with distributed openfow controllers. In Proceedings of IEEE International Workshop on Management of Emerging Networks and Services, pages 584-588, 2010.

[21] A.-W. Tam, K. Xi, and H. Chao. Use of devolved controllers in data center networks. In Processings of the IEEE Computer Communications Workshops, pages 596-601, 2011.

[22] Soheil Hassas Yeganeh and Yashar Ganjali.Kandoo: a framework for efficient and scalable offloading of control applications. In Proc. 1st Workshop on Hot Topics in Software Defined Networking (HotSDN 2012), pages 19-24, New York, 2012. ACM Press.

[23] A. Dixit, F. Hao, S. Mukherjee, T. Lakshman, R.Kompella, “Towards an Elastic Distributed SDN Controller,” In Proc. 1st Workshop on Hot Topics in Software Defined Networking (HotSDN 2013), pages 7-12, Hong Kong, 2013. ACM Press.

[24] Anat Bremler-Barr, Yotam Harchol, David Hay,Yaron Koral, Deep Packet Inspection as a Service. CoNEXT’14, December, 2014, Sydney, Australia, pp.271-282.

[25] Z.A. Qazi, C.-C. Tu, L. Chiang, R. Miao, V. Sekar,M. Yu, SIMPLE-fying middlebox policy enforcement using SDN, in: Proceedings of the SIGCOMM, 2013.

[26] Seyed Kaveh Fayazbakhsh, Luis Chiang, Vyas Sekar et al., Enforcing Network-Wide Policies in the Presence of Dynamic Middlebox Actions using FlowTags. in: Proceedings of the NSDI,ACM, 2014.

[27] P. Quinn, J. Halpern, Service function chaining(SFC) architecture, draftquinn-sfc-arch-05 (work in progress), IETF, May 2015. http://tools.ietf.org/html/draft-quinn-sfc-arch-05.

[28] S. Aldrin, C. Pignataro, N. Akiya, Service function chaining operations,administration and maintenance framework, draft-aldrin-sfcoam-framework-00, July 2014.

[29] P. Quinn, T. Nadeao, Service function chaining problem statement,Internet-Draft, draft-quinnsfc-problem-statement-03.txt, IETF, Dec.2013.

[30] Sushant Jain, Alok Kumar, Subhasree Mandal,Joon Ong, Leon Poutievski, Arjun Singh, “B4:Experience with a Globally-Deployed Software Defined WAN,” in Proc. of ACM SIGCOMM, Augest, 2013, 3-14.

[31] Chi-Yao Hong, Srikanth Kandula, Ratul Mahajan,Ming Zhang, Vijay Gill, Mohan Nanduri, Roger Wattenhofer, “Achieving High Utilization with Software-Driven WAN,” in Proc. of ACM SIGCOMM, Augest, 2013, 15-26.

[32] S. Boyd and L. Vandenberghe, Convex optimization. Cambridge university press, 2004.

[33] Kirkpatrick，S.， Gelett, C. D. and Vecchi, M. P..Optimization by simulated annealing. Science 220, 1983, 621-630.

[34] Metropolis，N.， Rosenbluth, A. W.， Rosenbluth, M. N.，Teller, A. H. and Teller, E.. Equation of state calculations by fast computing machines. J. Chem. Phys. 21,1953, 1087-1092.

[35] A. Greenberg, J. Hamilton, N. Jain, S. Kandula, C.Kim, P. Lahiri, D. Maltz, P. Patel, and S. Sengupta,“Vl2: a scalable and flexible data center network,” in Proc. of ACM SIGCOMM, 2009.

[36] Rob Sherwood, Glen Gibb, Kok-Kiong Yap et al.Can the Production Network Be the Testbed?. In Proc. OSDI’2010. 2010, 1-14.