Network Slicing for Service-Oriented Networks Under Resource Constraints
Nan Zhang Ya-Feng Liu Hamid Farmanbar Tsung-Hui Chang Mingyi Hong Zhi-Quan Luo








































































Network Slicing for Service-Oriented Networks Under Resource Constraints
    Nan Zhang, Ya-Feng Liu, Hamid Farmanbar, Tsung-Hui Chang, Mingyi Hong, and Zhi-Quan Luo
This work is supported by NSF, grant number CCF-1526434, and by NSFC, grant number 61571384.
N. Zhang is with the School of Mathematical Sciences, Peking University, China. Email: zhangnan625@pku.edu.cn
Y.-F. Liu is with the State Key Laboratory of Scientific and Engineering Computing, Institute of Computational
Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China. Email: yafliu@lsec.cc.ac.cn
H. Farmanbar is with Huawei Canada Research Center, Ottawa, Canada. Email: hamid.farmanbar@huawei.com
M. Hong is with the Department of Electrical and Computer Engineering, University of Minnesota, USA. Email: mhong@umn.edu


T.-H. Chang and Z.-Q. Luo are with Shenzhen Research Institute of Big Data, and the Chinese University of Hong Kong, Shenzhen, China. Emails: changtsunghui@cuhk.edu.cn, luozq@cuhk.edu.cn









    December 30, 2023
==================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================






To support multiple on-demand services over fixed communication networks, network operators must allow flexible customization and fast provision of their network resources. One effective approach to this end is network virtualization, whereby each service is mapped to a virtual subnetwork providing dedicated on-demand support to network users. In practice, each service consists of a prespecified sequence of functions, called a service function chain (SFC), while each service function in a SFC can only be provided by some given network nodes. Thus, to support a given service, we must select network function nodes according to the SFC and determine the routing strategy through the function nodes in a specified order.
A crucial network slicing problem that needs to be addressed is how to optimally localize the service functions in a physical network as  specified by the SFCs, subject to link and node capacity constraints.
In this paper, we formulate the network slicing problem as a mixed binary linear program and establish its strong NP-hardness. Furthermore, we propose efficient penalty successive upper bound minimization (PSUM) and PSUM-R(ounding) algorithms, and two heuristic algorithms to solve the problem. Simulation results are shown to demonstrate the effectiveness of the proposed algorithms.




Software Defined Network, Network Function Virtualization, Traffic Engineering.


















§ INTRODUCTION


Today's communication networks are expected to support multiple services with diverse characteristics and requirements. To provide such services efficiently, it is highly desirable to make the networks agile and software reconfigurable. Network function virtualization (NFV) <cit.> is an important technology to achieve this goal, which virtualizes network service functions so that they are not restricted to the dedicated physical devices.

Different from the traditional networking where service functions are assigned to special network hardware, NFV enables service operators to flexibly deploy network functions and service providers to intelligently integrate a variety of network resources owned by different operators to establish a service customized virtual network (VN) for each service request. In practice, each service consists of a predefined sequence of service functions, called a service function chain (SFC) <cit.>. Meanwhile, a service function can only be provided by certain specific nodes, called NFV-enabled nodes. As all of the VNs share a common resource pool, we are led to the problem of network resource allocation to meet diverse service requirements, subject to the capacity constraints at NFV-enabled nodes and at network links.


Recently, reference <cit.> proposed a novel 5G wireless network architecture MyNET and an enabling technique called SONAC (Service-Oriented Virtual Network Auto-Creation). In SONAC, there are two key components: software defined topology (SDT) and software defined resource allocation (SDRA). SDT determines a VN graph and a VN logical topology for each service request. The determination of the VN logical topology, also called VN embedding, locates the virtual service functions onto the physical NFV-enabled infrastructures so that each function in the corresponding SFC is instantiated.

SDRA maps the logical topology to physical network resources, including both communication and computational resources. 


In software defined networks, centralized control enables joint VN embedding and SDRA, a problem called network slicing. Specifically, network slicing controls the flow routing such that each flow gets processed at NFV-enabled nodes in the order of service functions defined in the corresponding SFC. There are some works related to the network slicing problem <cit.>.
Reference <cit.> considered a simplified problem where there is a single function in each SFC and a single path for each service, and solved the formulated problem approximately.
References <cit.> simplified “routing" by either considering only one-hop routing or selecting paths from a predetermined path set. Reference <cit.> considered the so-called consolidated middleboxes where a flow could receive all the required functions. It proposed a two-stage heuristic algorithm to route each flow through a single associated NFV-enabled node. Such formulation is not applicable to the case where each SFC contains multiple functions which need to be instantiated in sequence at NFV-enabled nodes. An important common assumption in <cit.> is that the instantiation of a service function for a traffic flow can be split over multiple NFV-enabled nodes. The service splitting assumption significantly simplifies the optimization problem since no binary variable is needed in the problem formulation. However, service splitting would result in high coordination overhead in practice, especially when the number of service requests is large. Reference <cit.> allowed service splitting in a different way by assuming that a service function can be instantiated in the form of multiple instances of virtual network functions (with different throughputs and resource demands) at multiple nodes.
References <cit.> did not allow service splitting and assumed the data of any flow are processed in only one NFV-enabled node for any function in the chain. They solved their problems by either existing integer optimization solvers or heuristic algorithms that may lead to violations of resource constraints.



In this paper, we consider the network slicing problem with practical constraints, where a set of service requests are simultaneously processed and routed. Our considered problem differs from most of the aforementioned works in that we allow traffic flows to be transmitted on multiple paths and require that the data of any flow are processed by only one NFV-enabled node for any function in the corresponding function chain.
We formulate the problem as a mixed binary linear program and show that checking the feasibility of this problem is strongly NP-hard in general. Moreover, we propose an efficient penalty successive upper bound minimization (PSUM) algorithm, a PSUM-R algorithm, and two heuristic algorithms for this problem. The simulation results show that the proposed PSUM and PSUM-R algorithms can find a near-optimal solution of the problem efficiently.







§ SYSTEM MODEL AND PROBLEM FORMULATION

In this section, we introduce the model and present a formulation of the network slicing problem.

Consider a communication network represented by a graph 𝒢=(𝒱,ℒ), where 𝒱={i} is the set of nodes and ={(i,j)} is the set of directed links. Denote the subset of function nodes (NFV-enabled nodes) that can provide a  service function f as V_f. Each function node i has a known computational capacity μ_i, and we assume that processing one unit of data flow requires one unit of computational capacity.
Suppose that there are K data flows, each requesting a distinct service in the network. The requirement of each service is given by a service function chain (k), consisting of a set of functions that have to be performed in the predefined order by the network.
Different from the aforementioned works <cit.>, we require that each flow k receives each service function in (k) at exactly one function node, i.e., all data packets of flow k should be directed to the same function node to get processed by a service function,
so that there does not exist coordination overhead caused by service splitting in practice.
Notice that this requirement does not prevent a common function in different SFCs from being served by different nodes. 
The source-destination pair of flow k is given as (S(k),D(k)), and the arrival data rate of flow k is given as λ(k).
The network slicing problem is to determine the routes and the rates of all flows on the routes while satisfying the SFC requirements and the capacity constraints of all links and function nodes. 

Let r_ij(k) be the rate of flow k over link (i,j). The capacity of link (i,j) is assumed to be C_ij which is a known constant. This assumption is reasonable when the channel condition is stable during the considered period of time.
The total flow rates over link (i,j) is then upper bounded by C_ij, i.e., 

    ∑_k=1^Kr_ij(k)≤ C_ij, ∀ (i,j)∈.


To describe VN embedding, we introduce binary variables x_i,f(k) which indicate whether or not node i provides function f for flow k (i.e., x_i,f(k)=1 if node i provides function f for flow k; otherwise x_i,f(k)=0).
To ensure that each flow k is served by exactly one node for each f∈(k), we have the following constraint 

    ∑_i∈ V_f x_i,f(k)=1, ∀ f∈(k), ∀ k.





We assume that each function node provides at most one function for each flow: 

    ∑_f∈(k) x_i,f(k)≤ 1,  ∀ k, ∀ i.

This assumption is without loss of generality.
This is because, if a function node can provide multiple services for a flow, we can introduce virtual nodes such that each virtual node provides one function for the flow and all these virtual nodes are connected with each other.


Suppose that the function chain of flow k is (k)=(f^k_1→ f^k_2→…→ f^k_n).
To ensure flow k goes into the function nodes in the prespecified order of the functions in (k),
we introduce new virtual flows labelled (k,f): flow k just after receiving the service function f, and denote as (k,f^k_0) the flow k just coming out of the source node S(k) without receiving any service function.
See Fig. <ref> for an illustration.

Let r_ij(k,f) be the rate of flow (k,f) over link (i,j).
Since each function node provides at most one function for each flow (as shown in (<ref>)), the following flow conservation constraints must hold for all nodes i and s=1,…,n: 

    λ(k)x_i,f_s(k)=∑_j:(j,i)∈r_ji(k,f_s-1)-∑_j:(i,j)∈r_ij(k,f_s-1),


    λ(k)x_i,f_s(k)=∑_j:(i,j)∈r_ij(k,f_s)-∑_j:(j,i)∈r_ji(k,f_s),


    ∑_j:(S(k),j)∈r_S(k)j(k,f_0)=λ(k),


    ∑_j:(j,D(k))∈r_jD(k)(k,f_n)=λ(k),

where (<ref>) and (<ref>) imply that if x_i,f_s=1, then flow (k,f_s-1) going into node i and flow (k,f_s) coming out of node i both have rate λ(k); otherwise each virtual flow (k,f_s) coming out of node i and going into node i should have the same rate; (<ref>) and (<ref>) ensure that flow k coming out of S(k) and going into D(k) both have rate λ(k).
These constraints guarantee that each flow k gets served at function nodes in the order prespecified by (k) and with the required data rate λ(k).


By the definitions of r_ij(k,f) and r_ij(k), we have 

    r_ij(k)=∑_f∈(k)∪{f^k_0} r_ij(k,f), ∀ k, ∀ (i,j)∈.




Since processing one unit of data flow consumes one unit of computational capacity, the node capacity constraint can be expressed as 

    ∑_f∑_kλ(k) x_i,f(k)≤μ_i,  ∀ i.


Now we present our problem formulation of network slicing to minimize the total link flow in network: 

    [                                 min_,                  g()=∑_k,(i,j)r_ij(k);                                                            (<ref>)-(<ref>),;                                                 r_ij(k)≥ 0,  ∀ k, ∀ (i,j)∈,;                                         r_ij(k,f)≥ 0, ∀ f∈(k),∀ k,∀ (i,j)∈,;                                       x_i,f(k)∈{0,1}, ∀ i∈ V_f,∀ f∈(k),∀ k, ]

where :=( {r_ij},{r_ij(k,f)}), :={x_i,f(k)}.
The objective function g()=∑_k,(i,j)r_ij(k) is set to avoid cycles in choosing routing paths.
There can be other choices of objective functions, such as the cost of the consumed computational resources and the number of activated function nodes.

Problem (<ref>) is a mixed binary linear program which turns out to be strongly NP-hard.
The proof is based on a polynomial time reduction from the 3-dimensional matching problem <cit.>.




   Checking the feasibility of problem (<ref>) is strongly NP-complete, and thus solving problem (<ref>) itself is strongly NP-hard. 


We give the proof of Theorem <ref> in Appendix A.





§ PROPOSED PSUM AND PSUM-R ALGORITHMS


Since problem (<ref>) is strongly NP-hard, it is computationally expensive to solve it to global optimality.
In this section, we propose efficient PSUM and PSUM-R algorithms to solve it approximately.
The basic idea of our proposed PSUM algorithm is to relax the binary variables in problem (<ref>) and add penalty terms to the objective function to induce binary solutions. The PSUM-R algorithm combines PSUM and a rounding technique so that a satisfactory solution can be obtained more efficiently than PSUM.




 §.§ PSUM Algorithm


Notice that problem (<ref>) becomes a linear program (LP) when we relax the binary variables to be continuous.
Problem (<ref>) and its LP relaxation are generally not equivalent (in the sense that the optimal solution of the LP relaxation problem may not be binary).
The following Theorem <ref> provides some conditions under which the two problems are equivalent. 
The proof of Theorem <ref> is given in Appendix B.

  Suppose μ_i≥μ̅ for all i, and C_ij≥C̅ for all (i,j), where
   
    μ̅=∑_k=1^Kλ(k), C̅=∑_k=1^Kλ(k)(|(k)|+1),

     and |(k)| denotes the number of functions in (k).
     Then the LP relaxation of problem (<ref>) always has a binary solution of {x_i,f(k)}.
     Moreover, the lower bounds in (<ref>) are tight in the sense that there exists an instance
     of problem (<ref>) such that its LP relaxation problem does not have a binary solution of {x_i,f(k)} if one of the lower bounds is violated. 



Theorem <ref> suggests that, if the link and node capacity are sufficiently large, then problem (<ref>) and its LP relaxation problem (which relaxes the binary variables to be continuous) are equivalent.
Moreover, if the link and node capacity are fixed, problem (<ref>) becomes more difficult to solve as the number of flows and the number of functions in the SFC increase, because the lower bounds in Theorem <ref> will be more likely violated.


To solve the general problem (<ref>), our basic idea is to add an L_p penalty term to the objective of the LP relaxation problem of (<ref>) to enforce the relaxed variables end up being binary.

Let _f(k)={x_i,f(k)}_i∈ V_f. Then, we can rewrite
(<ref>) as 

    _f(k)_1=1, ∀ f∈(k), ∀ k.

We have the following fact <cit.>.

Fact: For any k and any f∈(k), consider 

    [                             min__f(k) _f(k)+ϵ1_p^p:=∑_i∈ V_f (x_i,f(k)+ϵ)^p;                                                                  _f(k)_1=1,;                                                  x_i,f(k)∈ [0,1], ∀ i∈ V_f, ]

where p∈(0,1) and ϵ is any nonnegative constant. The optimal solution of problem (<ref>) is binary, that is, only one element is one and all the others are zero (see an example in Fig. <ref>), and its optimal value is
c_ϵ,f:=(1+ϵ)^p+(|V_f|-1)ϵ^p. Moreover, the objective function in problem (<ref>) is differentiable with respect to each element x_i,f(k)∈[0,1] when ϵ>0. 



Motivated by the above fact, we propose to solve the following penalized problem 

    [                                  min_,                            g()+σ P_ϵ();                                                              (<ref>)-(<ref>),;                                                   r_ij(k)≥ 0,  ∀ k, ∀ (i,j)∈,;                                           r_ij(k,f)≥ 0, ∀ f∈(k),∀ k,∀ (i,j)∈,;                                        x_i,f(k)∈ [0,1], ∀ i∈ V_f,∀ f∈(k),∀ k, ]

where σ>0 is the penalty parameter, and 


    P_ϵ()= ∑_k∑_f∈(k)( _f(k)+ϵ1_p^p-c_ϵ,f).




For ease of presentation, we define =(,) and g_σ()=g()+σ P_ϵ().
The following Theorem <ref> reveals the relationship between the optimal solutions of problems (<ref>) and (<ref>). The proof is relegated to Appendix <ref>. 


 For any fixed ϵ>0, let ^k be a global minimizer of problem (<ref>) with the objective function g_σ_k(). Suppose the positive sequence {σ_k} is monotonically increasing and σ_k→ +∞. Then any limit point of {^k} is a global minimizer of problem (<ref>). 


Theorem <ref> suggests that the penalty parameter σ should go to infinity to guarantee that the obtained solution {x_i,f(k)} of (<ref>) is binary. In practice, however, the parameter σ only needs to be large enough so that the values of the binary variables {x_i,f(k)} are either close to zero or one. Then, a (feasible) binary solution of (<ref>) can be obtained by rounding.


Solving (<ref>) directly is not easy since it is a linearly constrained nonlinear program. To efficiently solve (<ref>), we apply the SUM (Successive Upper bound Minimization) method <cit.>, which solves a sequence of approximate objective functions which are lower bounded by the original objective function. Due to the concavity of P_ϵ(), the first order approximation of P_ϵ() is an upper bound of itself, i.e., P_ϵ()≤ P_ϵ(^t)+∇ P_ϵ(^t)^T(-^t), where ^t is the current iterate.
At the (t+1)-st iteration, we solve the following problem 


    [                                        min_,                         g()+σ_t+1∇ P_ϵ(^t)^T;                                                                          (<ref>)-(<ref>),;                                              r_ij(k)≥ 0, r_ij(k,f)≥ 0, ∀ f,∀ k, ∀ (i,j)∈,;                                                    x_i,f(k)∈ [0,1], ∀ i∈ V_f,∀ f∈(k),∀ k. ]

Notice that each subproblem (<ref>) is a linear program which can be efficiently solved to global optimality. 




Adding Additional Constraints. The feasible region of the PSUM subproblem (<ref>) is actually enlarged compared with that of the original problem (<ref>), as the binary variables are relaxed while all the other constraints are unchanged.
To improve the feasibility of the obtained solution to the original problem, we will add some valid cuts. This idea is popular in combinatorial optimization.

To this end, we add some constraints related to the binary variables and strengthen the node capacity constraints, which are redundant for problem (<ref>) but can significantly reduce the feasible solution set of problem (<ref>).

We first define two new binary variables. Let x_i,f be the binary variable indicating whether node i provides function f (i.e., x_i,f=1 if node i provides f, otherwise x_i,f=0), and x_i be the binary variable indicating whether node i is active for providing network services (i.e., x_i=1 if node i is active, otherwise x_i=0). By the definitions of binary variables, we have

    x_i,f(k) ≤ x_i,f≤ x_i, ∀  i∈ V_f, f∈(k), k.


Since the computational resource at each node i is available only when node i is active, the node capacity constraint (<ref>) can be strengthened in the following way.

    ∑_f∑_kλ(k)x_i,f(k)≤ x_iμ_i, ∀ i.

Moreover, for each function f that node i can provide, the computational resource at node i is available for function f only when the node provides function f. Therefore, the consumed computational resource on function f at node i is upper bounded by x_i,fμ_i, as shown in equation (<ref>).

    ∑_kλ(k)x_i,f(k)≤ x_i,fμ_i, ∀ i∈ V_f, f.



With the above constraints added to problem (<ref>), the problem in the (t+1)-st PSUM iteration becomes

    [                                        min_,                         g()+σ_t+1∇ P_ϵ(^t)^T;                                                         (<ref>)-(<ref>), (<ref>)-(<ref>),;                                              r_ij(k)≥ 0, r_ij(k,f)≥ 0, ∀ f,∀ k, ∀ (i,j)∈,;                                                         x_i∈ [0,1], x_i,f∈ [0,1], ∀  i,f,;                                                    x_i,f(k)∈ [0,1], ∀ i∈ V_f,∀ f∈(k),∀ k. ]


The proposed PSUM algorithm for solving problem (<ref>) is presented in Algorithm <ref>, where γ and η are two predefined constants satisfying 0<η<1<γ.


We remark that 1) the parameter ϵ is adaptively updated as the iteration number increases, which turns out to be very helpful in improving numerical performance of the algorithm <cit.>; 2) since the difference of two consecutive PSUM subproblems only lies in the objective function, the warm-start strategy can be applied in PSUM to solve the sequence of LP subproblems, i.e., let ^t be the initial point of the (t+1)-st PSUM subproblem; 3) reference <cit.> proposed a Penalty-BSUM algorithm that relaxes some equality constraints and applies Block-SUM to solve the penalized problem, while our Penalty-SUM algorithm is designed to enforce the relaxed variables being binary.






 §.§ PSUM-R: A Combination of PSUM and A Rounding Technique


As we have mentioned before, in practice the penalty parameter σ only needs to be sufficiently large so that the values of binary variables {x_i,f(k)} are either close to zero or one.
To obtain a satisfactory solution and save computational efforts, we can obtain a suboptimal solution by the PSUM-R algorithm, using the PSUM algorithm with an effective rounding strategy. 

Suppose a solution of problem (<ref>) is obtained after a few PSUM iterations with some binary elements {(x̅_i,f(k))_i∈ V_f} being fractional.
We aim to construct a binary solution {x_i,f(k)} on the basis of {(x̅_i,f(k))_i∈ V_f}.
However, systematic rounding is difficult since the link and node capacity constraints (<ref>) and (<ref>)
couple the transmission of all K flows. Thus we turn to round some elements to one while some elements to zero in a heuristic way.

Our strategy is to first obtain a binary solution of , then solve the routing problem to obtain a solution of .
In particular, if _f(k) is binary, then we simply let _f(k)=_f(k); for each _f(k) that is not binary, our main idea of rounding is to respect the value of _f(k) (i.e., round the maximum element to one) when there exists one element being very close to one, otherwise to give priority to the node with the largest computational capacity.
In particular, we first check the value of its maximum element, if the maximum element is sufficiently close to one, then let the corresponding node provide function for flow k, that is, if x̅_j,f(k)=max_i∈ V_fx̅_i,f(k)≥θ where θ∈(0,1) is a predefined positive threshold, then we set

    x_j,f(k)=1, and  x_i,f(k)=0, ∀  i∈ V_f∖{j};

otherwise, we find the node v∈ V_f with the maximum remaining computational capacity, and let node v provide function for flow k, i.e., set

    x_v,f(k)=1, and  x_i,f(k)=0, ∀  i∈ V_f∖{v}.

 In this way, we obtain a binary solution {x_i,f(k)}. Notice that the node capacity constraints may be violated after the rounding.

To determine the routing solution , we fix the values of binary variables {x_i,f(k)} and
solve the original problem with objective function being g+τΔ, and
modify the link capacity constraints by

    ∑_kr_ij(k)≤ C_ij+Δ, ∀  (i,j)∈,

where the new variable Δ is the maximum violation on link capacity and the positive constant τ is the weight of Δ in the objective function.
Finally, we obtain the solution of both the service instantiation and the routing. The PSUM-R algorithm is given in Algorithm <ref>.


Moreover, after we obtain the solution, the violations of link and node capacity can be respectively measured by

    δ_ij=max{0,∑_kr_ij(k)-C_ij}, ∀  (i,j)∈ℒ,


    π_i=max{0,∑_k∑_fλ(k)x_i,f(k)-μ_i}, ∀ i.

If there is no violation on link and node capacity constraints, the obtained solution is feasible to problem (<ref>). Practically, the obtained solution is satisfactory if the resource violation is sufficiently small.
We will show later in Section <ref> that the PSUM-R algorithm can obtain a satisfactory solution with small resource violations within less time than PSUM.






§ LOW-COMPLEXITY HEURISTIC ALGORITHMS




In practice, service requests arrive randomly with little future information of network resources or other requests, and the network must be sliced as soon as a request arrives. An online algorithm with high competitive ratio is needed <cit.>. In this section, we propose two low-complexity heuristic algorithms to solve problem (<ref>), including one online algorithm (heuristic algorithm I).


The idea of our proposed low-complexity algorithms is to decouple the joint service instantiation and traffic routing problem (<ref>) into two separate problems. More specifically, the first step is to determine the set of instantiated nodes given a requested service/requested services, and the second step is to perform traffic routing given the selected instantiated nodes.

In particular, after fixing the values of the binary variables to determine the service instantiation, the remaining flow routing can be realized by solving problem (<ref>), which is an LP problem. To ensure that the routing problem always has a feasible solution, we adopt a strategy similar to PSUM-R, i.e., modify the link capacity constraints by (<ref>) and set the objective function to g+τΔ.

To determine which function node a service function should be instantiated for each request, Openstack scheduling <cit.> provides a method of filtering and weighting. The filtering step selects eligible nodes in view of computational resource, CPU core utilization, and the number of running instances etc. The weighting step determines the instantiation node after computing a weighted sum cost for each eligible node.
Inspired by Openstack scheduling, we perform service instantiation in a similar way. In particular, for each service function in a SFC, we first select eligible function nodes in terms of their remaining computational resource, then compute the weighted sum cost of each eligible node i by

    z_i=∑_m w_m ×ncost(i,m), ∀ i,

where ncost(i,m) is the normalized cost of node i in terms of capability m.
For example, if we consider the weighting factors of path length and available computational resource, the weighted sum cost can be computed by

    z_i=w_1(h^S(k)_i+h^D(k)_i)+w_21/μ̃_i,

where h^S(k)_i (resp. h^D(k)_i) is the number of hops between nodes i and S(k) (resp. D(k)), μ̃_i is the current capacity of node i, and w_1, w_2 are weights.
After computing the weighted costs, we let the node with the smallest cost be the instantiation node.
Notice that there may be violations of node computational capacities.
In Algorithms <ref> and <ref>, we present heuristic algorithms I and II respectively.


Heuristic algorithm I. We sequentially perform service instantiation and traffic routing for each flow (request).
As shown in Algorithm <ref>, for each flow k, we first locate the nodes that provide functions in SFC (k) by filtering and weighting, next route flow k from its source node to its destination node while going through the instantiation nodes in the specified order, then update node capacity and link capacity before proceeding to the next flow.





Heuristic algorithm II. We first perform service instantiation for all flows, then route all flows at the same time. Since the routing problem considers all flows, the violation on link capacity tends to be smaller than that in heuristic algorithm I.















































































§ NUMERICAL EXPERIMENTS


In this section, we present numerical results to illustrate the effectiveness of the proposed algorithms.
We shall compare our proposed PSUM algorithm, PSUM-R algorithm, and heuristic algorithms I and II with heuristic algorithm III (which is modified from the algorithm in <cit.>) and heuristic algorithm IV (which is proposed in <cit.>).
We give the detailed description of heuristic algorithms III and IV in Appendix D.
All simulations are done in MATLAB (R2013b) with 2.30 GHz CPUs. All LP subproblems are solved by the optimization solver Gurobi 7.0.1 <cit.>.




To show the performance of these algorithms, we will compare the quality of the obtained solutions in terms of their objective function values, the CPU time, and the amount of violations of the network resource capacities. We define the worst-case violation ratio of link capacity by max_ijδ_ij/C_ij, and the worst-case violation ratio of node capacity by max_iπ_i/μ_i, where δ_ij and π_i are defined in (<ref>) and (<ref>) respectively.
We will consider two network topologies: a mesh topology in Fig. <ref> and a fish topology in Fig. <ref>.

In the PSUM algorithm, we set T_max=20,  σ_1=2,  ϵ_1=0.001,  γ=1.1, and η=0.7. In the PSUM-R algorithm, we set t_max=7 and θ=0.9. In heuristic algorithms I and II, we set weights w_1=1 and w_2=10max_iμ_i in (<ref>). 



 §.§ Mesh Network Topology



We consider a mesh network with 100 nodes and 684 directed links. The topology of this network is shown in Fig. <ref>, where the nodes located in the 4 middle columns are function nodes.
Suppose there are in total 5 service functions {f_1,…,f_5} and 10 candidate function nodes for each function (|V_f|=10 for each function f).
We consider K=30 flows with demands λ(k)=1 for all flow k. The SFC (k)=(f^k_1→ f^k_2) and
(S(k),D(k)) are uniformly randomly chosen for each flow (f^k_1≠ f^k_2, S(k),D(k)∉ V_f^k_s,s=1,2). The link capacity C_ij is uniformly randomly chosen in [0.5,5.5] and the node capacity μ_i is uniformly randomly chosen in [0.5,8].

We randomly generate 50 instances of problem (<ref>) and apply the six algorithms to solve them.


Let g_PSUM^* be the objective value of problem (<ref>) at the solution returned by the PSUM algorithm and let  g_LP^* be the optimal value of the corresponding LP relaxation problem.
We find that g^*_PSUM=g^*_LP in 4 instances and the objective value ratio g^*_PSUM/g^*_LP is less than 1.09 in all of 50 instances, which implies that the solutions returned by the PSUM algorithm are close to be global optimal. We also find that in 21 instances the PSUM-R algorithm already obtains a feasible solution before the rounding step, which further shows that the PSUM algorithm converges fast.
As shown in Fig. <ref>, the objective value ratios corresponding to the PSUM-R algorithm and heuristic algorithm III are in [1.0, 1.26], the ratios corresponding to heuristic algorithms I and II are in [1.25, 1.7), and those corresponding to heuristic algorithm IV are in [2.2, 3.5] which are much larger. In terms of the returned objective value, the PSUM algorithm gives the best solutions and heuristic algorithm IV performs the worst among the six algorithms.




The statistics of worst-case violation ratios are plotted in Fig. <ref>. Since there is no resource violation in the solutions obtained by the PSUM algorithm and heuristic algorithm IV, we only show the violation ratios returned by PSUM-R, heuristic algorithms I, II, and III.
From Fig. <ref> we can see that the violation ratios returned by heuristic algorithms I and II are small, and those returned by heuristic algorithm III are generally much larger.
Moreover, the violation ratios of node capacity returned by heuristic algorithms I and II are smaller than those returned by PSUM-R and heuristic algorithm III, as the node capacity has already been taken into consideration in the service instantiation step in our proposed heuristic algorithms I and II.





 §.§ Fish Network Topology


We consider another network with 112 nodes and 440 directed links. The topology of this network is shown in Fig. <ref>, where the 6 diamond nodes are function nodes and the triangular nodes cannot be chosen as a source node of any flow.
We consider K=20 flows with a common destination which is the circular node in Fig. <ref>.
According to the distance (counted by the number of hops) to the destination node, the network nodes are divided into 11 layers.
We set the node capacity μ_i to 16 for any function node i, and choose the value of link capacity C_ij from [1, 55] which is
further divided into 10 sub-intervals.
In particular, the capacities of the links connecting layer m+1 and layer m are uniformly randomly chosen from the (11-m)-th
sub-interval. Suppose there are in total 4 service functions {f_1,…,f_4} and all of them can be provided by any of the 6 function
nodes.                                                                                                                                   
In each instance of problem (<ref>), the demand λ(k) is an integer number randomly chosen in [1,5], the source node S(k) is randomly chosen from the available network nodes excluding the function nodes, and the SFC (k) is an ordered sequence of functions randomly chosen from {f_1,…,f_4} for each flow.


We first set the chain length to 1, i.e., each SFC (k) consists of only one service function, and randomly generate 50 instances of problem (<ref>).
We find that  g^*_PSUM=g^*_LP in 42 instances and g^*_PSUM-R=g^*_LP in 45 instances. This implies that LP relaxation is tight for at least 42 instances (in the sense that the LP relaxation of problem (<ref>) and problem (<ref>) have same optimal values) and the PSUM algorithm finds global optimal solutions for these instances. Moreover, the objective value ratio g^*_PSUM/g^*_LP is less than 1.002 in all of 50 instances, which implies that the obtained solution is very close to the global optimal solution.
As shown in Fig. <ref>, heuristic algorithm III generates better solutions in terms of the objective value among the heuristic algorithms.


The statistics of worst-case violation ratios are plotted in Fig. <ref>. 
We can see from Fig. <ref> that there is no link/node capacity violation in the solutions obtained by PSUM-R and heuristic algorithms I and II in over 40 simulations, while larger violations on node capacity in the solutions obtained by heuristic algorithm III.



We set the chain length to 2, i.e., each SFC (k) consists of two different service functions.
Fig. <ref> shows the statistics of the objective value ratios.
In this case, the ratio g^*_PSUM/g^*_LP is below 1.09 in all 50 instances and is below 1.01 in 30 instances, and the ratios returned by heuristic algorithms IV are in [1.3, 1.7], which are very similar to those returned by heuristic algorithms I and II. One reason for the better performance of heuristic algorithm IV in this topology (compared to the mesh topology in Section <ref> where the chain length is also 2) is that, the multi-layer routing problem solved in heuristic IV becomes less complicated when |V_f| decreases. Fig. <ref> plots the violation ratios, from which we can see that the violation ratios become larger (compared to the case where the chain length is 1), especially for heuristic algorithm III.





From the results above we find that the performance of PSUM, PSUM-R and all four heuristic algorithms deteriorates when the chain length increases from 1 to 2. As shown in Theorem <ref>, if the link and node capacity are fixed, the LP relaxation of problem (<ref>) and itself are less likely to be equivalent as the chain length increases, and problem (<ref>) becomes more difficult to solve. Therefore, the gap between g^*_LP and g^*_PSUM tends to become larger when the chain length increases.


Finally, we plot the CPU time (in seconds) per instance with different problem sizes in Fig. <ref>.
Among the six algorithms, heuristic algorithms I and IV are the fastest ones as the LP problems to be solved are in small scales.
The PSUM algorithm requires more time. Meanwhile, the time of PSUM-R (which performs 7 PSUM iterations) is about 80% of the time of PSUM (whose maximum number of iterations is set to 20), which means the number of iterations performed in PSUM to obtain a feasible solution is usually much smaller than 20.
Heuristic algorithm III is more time-consuming than PSUM. This is because heuristic algorithm III usually needs to solve more LP problems and the warm-start strategy cannot be used in solving the LP problems.






 §.§ Summary of Simulation Findings


From the above simulation results we can conclude that:


  * Our proposed heuristic algorithms I and II are efficient and can find satisfactory solutions with moderate resource violations;

  * Heuristic III gives better solutions than heuristic algorithms I, II, and IV in terms of objective values, but has larger resource violations and is more time-consuming;

  * Heuristic algorithm IV can find feasible solutions with satisfactory objective values, but its performance is not stable under different numerical settings;

  * Our proposed PSUM algorithm guarantees perfect satisfaction of resource constraints and returns the best solution among all algorithms, but is slower than the heuristic algorithms I, II, and IV (albeit it is faster than heuristic algorithm III);

  * Our proposed PSUM-R algorithm achieves a good balance of solution quality and algorithm efficiency.







§ CONCLUSION


In this work, we study the network slicing problem.
Different from most of the existing works, we assume that each flow receives any service function in the corresponding service function chain at exactly one function node, a requirement that is strongly motivated by reducing practical coordination overhead. We formulate the problem as a mixed binary linear program and prove its strong NP-hardness.
To effectively solve the problem, we propose a PSUM algorithm, a variant PSUM-R algorithm, and two low-complexity heuristic algorithms, all of which are easily implemented.
Our simulation results demonstrate that PSUM and PSUM-R can approximately solve the problem by returning a solution that is close to the optimal solution. Moreover, the PSUM algorithm completely respects the resource capacity constraints, and the PSUM-R algorithm achieves a good balance of solution quality and algorithm efficiency. 



§ ACKNOWLEDGMENT




The authors would like to thank Navid Reyhanian for his help in numerical simulations.


IEEEtran


section


§ PROOF OF THEOREM <REF>

We will prove that for an instance of problem (<ref>), the problem of checking its feasibility is as hard as a 3-dimensional matching problem, which is known as strongly NP-complete.


We first construct an instance of problem (<ref>) as follows.


  * The set of service functions: F=F_1∪ F_2∪ F_3, where F_1,F_2,F_3 are disjoint.

  * The SFC of flow k: (k)=(f^k_1→ f^k_2→ f^k_3), where f^k_j∈ F_j, j=1,2,3, k=1,…,K. Moreover, the SFCs of any two flows are different in the sense that f^k_j≠ f^m_j for all k≠ m, j=1,2,3.

  * The set of network nodes: =∪ X∪ Y∪ Z∪, where  is the set of source nodes,  is the set of destination nodes, X,Y,Z are disjoint sets of function nodes, and these sets have the same number of elements, i.e., K=||=|X|=|Y|=|Z|=||. See Fig. <ref> for an illustration. Moreover,
    any node x∈ X can provide all functions in F_1, and for any function f∈ F_1, V_f=X;
    any node y∈ Y can provide all functions in F_2, and for any function f∈ F_2, V_f=Y;
    any node z∈ Z can provide all functions in F_3, and for any function f∈ F_3, V_f=Z.

  * The set of links consists of 3 parts: ={(s,x)| s∈,  x∈ X}∪_R∪{(z,d)| z∈ Z, d∈}, where _R is determined by a set R⊆ X× Y× Z in the sense that any (x,y,z)∈ R implies that there exist directed links (x,y)∈_R, (y,z)∈_R.

  * All flows have the same rate, i.e., λ(k)=λ for all k.

  * The link capacity C_ij is sufficiently large that C_ij≥ 4Kλ for any (i,j)∈.

  * For any function node i∈ X∪ Y∪ Z, the value of μ_i is chosen to ensure that node i provides at most one function, e.g., μ_i∈[λ, 2λ), which ensures that function node i provides at most one function due to the limited node capacity.



In the following, we prove that the constructed above instance of problem (<ref>) has a feasible solution
if and only if there exists a 3-dimensional matching of R.


  (i) problem (<ref>) has a feasible solution ⟹
there exists a 3-dimensional matching of R.

Since problem (<ref>) has a feasible solution, then for each flow k,
there exist function nodes x^k∈ X, y^k∈ Y, z^k∈ Z such that x^k
provides f^k_1, y^k provides f^k_2, z^k provides f^k_3, and
(x^k,y^k),(y^k,z^k) are directed links in _R.

Let us define a subset of X× Y× Z by M={(x^k,y^k,z^k)|
k=1,…,K}. By the definition of _R, we have M ⊆ R.
Moreover, for any (x^k,y^k,z^k), (x^t,y^t,z^t)∈ M (k≠ t), we have
x^k≠ x^t, y^k≠ y^t,z^k≠ z^t. This is because that each node
provides at most one function. Therefore, M is a 3-dimensional matching of
R.


  (ii) M⊆ R is a 3-dimensional matching ⟹
problem (<ref>) has a feasible solution.

Since M is a 3-dimensional matching of R, M consists of K triplets.
We can build a one-to-one mapping between the K flows and the K triplets in
M. We denote the triplet that flow k is mapped to as (x^k,y^k,z^k).
Let x^k provide f^k_1, y^k provide f^k_2, and z^k provide f^k_3 for
any flow k. Since (x^k,y^k,z^k)∈ R, (x^k,y^k),(y^k,z^k) ∈ and
for any t≠ k we have x^k≠ x^t, y^k≠ y^t,z^k≠ z^t. Thus this
instantiation strategy is feasible. The routing problem is also feasible
because the link capacity is sufficiently large. In this way, we obtain a
feasible solution of problem (<ref>). 


We can see obviously from the above description that the construction of
this instance can be completed in polynomial time. Since the 3-dimensional
matching problem is strongly NP-complete, finding a feasible solution of (<ref>)
is also strongly NP-complete, and thus solving problem (<ref>) itself is strongly
NP-hard. The proof is completed.




§ PROOF OF THEOREM <REF>

By the constraint ∑_f∈(k) x_i,f(k)≤ 1 and the node capacity constraint ∑_f∑_kλ(k) x_i,f(k)≤μ_i, we have

    ∑_k∑_fλ(k)x_i,f(k)≤∑_kλ(k)· 1=μ̅.

By the relationship between r_ij(k) and r_ij(k,f) and the fact that
r_ij(k,f)≤λ(k) for all (i,j),f∈(k), we have

    ∑_kr_ij(k)=∑_k∑_f∈(k)∪{f^k_0}r_ij(k,f)≤∑_kλ(k)(|(k)|+1)=C̅.

Therefore, the link and node capacity constraints are automatically
satisfied if μ_i≥μ̅ for all i and C_ij≥C̅ for all
(i,j). Then the LP relaxation of problem (<ref>) reduces to

    [                                           ∑_(i,j)∑_k∑_f∈(k)∪{f^k_0} r_ij(k,f);                                              ∑_i∈ V_f x_i,f(k)=1,  ∀ k,f∈(k),;                                                ∑_f∈ F(k) x_i,f(k)≤ 1,  ∀ k,i,;                                                flow conservation constraints,;                                        r_ij(k,f)≥0, x_i,f(k)∈ [0,1], ∀ k,f,i,;                                        ]

which decouples among different flows. Thus, solving problem (<ref>)
is equivalent to solving K subproblems, and the kth subproblem aims at
minimizing the total link rates in directing flow k from its source node
to its destination node while sequentially going through the instantiation
nodes in the order of the functions in the chain (k). Let us denote
ℙ_k as the set of the shortest paths from S(k) to D(k) that
sequentially go through nodes that provide f^k_1,f^k_2,…,f^k_n. We
have the following claim which can be proved by contradiction.

Claim: The optimal solution of problem (<ref>) for each flow k
is to transmit with rate of λ(k) (or λ(k) amount of flow)
along any path in ℙ_k.

In fact, we can always find an optimal solution of problem (<ref>) that has
binary components of {x_i,f(k)}. For each flow k, we select a path
from ℙ_k and an instantiation node on the path for each required
service function (this is feasible due to the definition of ℙ_k),
and let all data of flow k be transmitted on this path. Then we obtain a
solution of problem (<ref>). According to the above claim, such
solution must be an optimal solution of problem (<ref>). Therefore,
problem (<ref>) has an optimal solution with binary components of
{x_i,f(k)}, which implies the first conclusion in Theorem 2.


Next, we prove by contradiction that the bounds in (<ref>) on {μ_i, C_ij} are tight, i.e., there exists an instance of problem (<ref>) where some μ_i or C_ij is below the bound and the LP relaxation problem does not have an optimal solution with components of {x_i,f(k)} being binary.


Let us consider the network shown in Fig. <ref>. Suppose there is one flow with demand λ=1, the source node is S and the destination node is D, and the service function chain is ={f_1}.
In this network, only nodes 3 and 6 can provide f_1. By (<ref>), we can compute the bounds for this case: μ̅=λ=1,  C̅=2λ=2.

Since V_f_1={v_3, v_6}, we have that the shortest path ℙ_1={(S, v_1, v_2, v_3, v_1, v_2, D)} with the number of hops being 6 (see the path in red in Fig. <ref> (a)), and another feasible path is (S, v_4, v_5, v_6, v_7, v_8, v_9, D) with the number of hops being 7 (see the path in blue in Fig. <ref> (b)). To minimize the total-link-rate objective function in problem (<ref>), the flow should transmit as many data as possible on the shortest path ℙ_1.


(i) Let μ_3=1-ϵ<μ̅ where ϵ∈(0,1),
μ_6>μ̅, and C_ij is no less than C̅ for any link (i,j).


Since v_3 is on the shortest path and μ_3=1-ϵ, v_3 can
process at most 1-ϵ units of data. Therefore, in the optimal
solution of the LP relaxation problem, 1-ϵ units of data are transmitted
on the shortest path ℙ_1, while the remaining ϵ units of
data are transmitted on the other feasible path. The optimal solution of
{x_i,f(1)} is not binary.


(ii) Let C_12=2(1-ϵ)<C̅, the capacity of other links are
larger than C̅, and the capacity of any function node is larger than
μ̅.

Since link (1,2) is on the shortest path, by the same analysis in (i) we
have that the amount of data transmitted on the shortest path is at most
1-ϵ. The remaining ϵ units of data must be transmitted on
the other feasible path. Therefore, the optimal solution of {x_i,f(1)}
of the LP relaxation problem is not binary.

From the above two cases we can conclude that the lower bounds of
{μ_i,C_ij} given in (<ref>) are tight. The proof is completed.



§ PROOF OF THEOREM <REF>

For ease of presentation, we define P^k=P_ϵ(^k) and g^k=g(^k).
Since ^k is a global minimizer of problem (<ref>) with the objective function g_σ_k(), it follows that 

    g_σ_k(^k)≤ g_σ_k(^k+1),  g_σ_k+1(^k+1)≤ g_σ_k+1(^k), ∀ k.

Combining the above with the assumption σ_k≤σ_k+1, we obtain 

    σ_k(P^k-P^k+1)≤ g^k+1-g^k≤σ_k+1(P^k-P^k+1), ∀ k,

which shows that {g^k} is increasing and {P^k} is decreasing.

Suppose that ^* is a global minimizer of problem (<ref>). Then P_ϵ(^*)=0. By the definition of ^k, we have
g_σ_k(^k)≤ g_σ_k(^*)=g(^*), which further implies that 


    0≤ g^k+σ_k P^k≤ g(^*).



This, together with the facts that g^k≥ 0, P^k≥ 0, and σ_k→ +∞, shows that σ_kP^k→ 0 and P^k→ 0 as k→ +∞.

Let =(,) be any limit point of {^k}, and {^k}_ be a subsequence converging to . Since P^k→ 0, we have P_ϵ()=0, which shows that  is feasible for (<ref>). Furthermore, taking limit along  in (<ref>), we have g()≤ g(^*). Therefore, g()=g(^*) and  is a global minimizer of (<ref>).



§ DESCRIPTION OF HEURISTIC ALGORITHMS III AND IV 

As shown in Algorithm <ref> below, heuristic algorithm III is modified from the heuristic algorithm in <cit.>.
In this modified algorithm, we denote the set of binary variables {x_i,f(k)} as , the set of {x_i,f(k)} which take value of one as _1, and those taking value of zero as _0. The basic idea is to first determine the value of the binary variable by “bootstrapping iteration" and “greedy selection" and then perform traffic routing.


Heuristic algorithm IV is proposed in <cit.>, for which we describe in Algorithm <ref>.
This heuristic algorithm reduces solving problem (<ref>) to solving a sequence of subproblems which are defined between two consecutive layers.
A layer f is defined as a set of function nodes in V_f (i.e., the set of nodes that can provide function f), and layer f^k_0 (resp. f^k_n+1) refers to the source (resp. destination) node of flow k.
For each flow k, we will route it between layers to bring the traffic from the first layer (S(k)) to the last layer (D(k)).
In particular, for each subproblem defined between layer f^k_s and layer f^k_s+1, we first determine the instantiation of function f^k_s+1 for flow k by solving a multidimensional knapsack problem,
next solve a multi-source multi-sink Minimum Cost Flow (MCF) problem to route the traffic,
and finally perform local search to improve the obtained solution (for example, change the instantiation node to see whether the cost can be reduced).


























