System and method for network slicing for service-oriented networks

Abstract

A computing system and a method are provided for determining a network traffic routing path through a service function chain (SFC). A joint network slicing and traffic engineering problem is provided that may be solved to identify network slicing configuration and traffic engineering parameters to provide a set of function nodes, the SFC, and the network traffic routing path from the source node to the destination node. The joint network slicing and traffic engineering problem P may be solved by minimizing a resource objective associated with the joint network slicing and traffic engineering problem, in accordance with a set of one or more constraints. Instructions may be transmitted to a network orchestrator to create the service function chain in a network slice on the set of network nodes in accordance with the identified network slicing configuration and traffic engineering parameters, to provide the network traffic routing path.

Claims

1. A method for determining a network traffic routing path from a source node to a destination node through a service function chain (SFC), the method comprising: determining a joint network slicing and traffic engineering problem (P), solution to which identifies network slicing configuration and traffic engineering parameters to provide a set of function nodes, the SFC, and the network traffic routing path from the source node to the destination node; solving the joint network slicing and traffic engineering problem by minimizing a resource objective associated with the joint network slicing and traffic engineering problem in accordance with a set of one or more constraints, wherein the joint network slicing and traffic engineering problem is solved by allowing binary variables to take on real values; and, transmitting instructions to a network orchestrator to create the SFC in a network slice on the set of function nodes in accordance with the network slicing configuration and the traffic engineering parameters to provide the network traffic routing path.

2. The method of claim 1, wherein the method is performed by at least one processor of a computing resource available on a network.

3. The method of claim 1, wherein the method is performed by a controller network function executed on a computing resource available on a network.

4. The method of claim 3, wherein an identity of at least one of: the source node, the destination node, or a set of available function nodes, is provided to a controller by the network orchestrator.

5. The method of claim 1, wherein the joint network slicing and traffic engineering problem comprises a Mixed Integer Linear Program.

6. The method of claim 1, wherein the resource objective comprises at least one of: one or more link rates; total computational capacity of the set of function nodes in the SFC; total communication cost associated with traversing the SFC; or minimum number of function nodes in the SFC.

7. The method of claim 1, wherein the resource objective comprises a summation of link rates through the SFC, and wherein an objective function comprises:
g(r)=Σ.sub.kΣ.sub.ijr.sub.ij(k).

8. The method of claim 1, wherein the rate of the flow on the link is the rate of the flow k on the link being equal to the sum of the rates of the virtual flows over the link: r.sub.ij(k)=Σ.sub.s=0.sup.nr.sub.ij(k,f.sub.s.sup.k), and wherein the set of one or more constraints further includes at least one of: each function is provided by a single function node: ΣiϵV.sub.fx.sub.i,f(k)=1; a link capacity constraint: Σ.sub.kr.sub.ij(k)≤c.sub.ij; a node capacity constraint; a second node capacity constraint expressed as a limit on a data rate λ(k) for flows processed by the single function node: Σ.sub.kΣ.sub.fx.sub.i,f(k)λ(k)≤μ.sub.i; or a flow conservation constraint at one or more of: the source node: Σ.sub.jr.sub.s(k)j(k,f.sub.0.sup.k)=λ(k), the destination node: Σ.sub.jr.sub.jD(k)(k, f.sub.n.sup.k)=λ(k), or flow conservation constraints at adjacent nodes in the SFC: Σ.sub.jr.sub.ji(k, f.sub.s−1.sup.k)−Σ.sub.jr.sub.ij(k, f.sub.s−1.sup.k)=x.sub.i,f.sub.s.sub.k(k)λ(k), or Σ.sub.jr.sub.ji(k, f.sub.s.sup.k)−Σ.sub.jr.sub.ij(k, f.sub.s.sup.k)=−x.sub.i,f.sub.s.sub.k(k)λ(k).

9. The method of claim 1, wherein the joint network slicing and traffic engineering problem is solved by adding a penalty term:
P.sub.ϵ(x)=Σ.sub.kΣ.sub.f ϵF(k)(∥x.sub.f(k)+ϵ1∥.sub.p.sup.p−c.sub.ϵ,f).

10. The method of claim 9, wherein the penalty term is differentiable and has a minimum value of 0.

11. The method claim 1, wherein the minimizing the resource objective is complete, based on satisfaction of at least one of: Tmax minimization iterations have been performed; when one or more real variables of the joint network slicing and traffic engineering problem have been resolved to binary components; when the one or more real variables of the joint network slicing and traffic engineering problem have been resolved to values close to a binary component binary components; or when the one or more real variables of the joint network slicing and traffic engineering problem have been resolved to values within a pre-defined range of a binary component.

12. The method of claim 1, wherein solving the joint network slicing and traffic engineering problem comprises: relaxing the joint network slicing and traffic engineering problem by allowing binary variables to assume real values and adding a penalty term to an objective; solving the relaxed and penalized problem to generate X.sup.t; calculating an iteration of a (PSUM) subproblem ∇P.sub.ϵ(X.sup.t).sup.TX; solving the (PSUM) subproblem ∇P.sub.ϵ(X.sup.t).sup.TX; and checking to determine if an algorithm is complete and if it is not complete calculating a next iteration of the (PSUM) subproblem ∇P.sub.ϵ(X.sup.t).sup.TX, and if the algorithm is complete, outputting a complete solution.

13. The method of claim 1, wherein the set of one or more constraints includes a rate of a flow on a link being equal to a sum of rates of virtual flows over the link.

14. A computing system operative to determine a network traffic routing path from a source node to a destination node through a service function chain (SFC), the computing system comprising: at least one processor; a non-transitory memory for storing programming instructions that, when executed by the at least one processor, cause the computing system to: determine a joint network slicing and traffic engineering problem (P), solution to which identifies network slicing configuration and traffic engineering parameters to provide a set of function nodes, the SFC, and the network traffic routing path from the source node to the destination node; solve the joint network slicing and traffic engineering problem by minimizing a resource objective associated with the joint network slicing and traffic engineering problem in accordance with a set of one or more constraints, wherein the joint network slicing and traffic engineering problem is solved by allowing binary variables to take on real values; and, transmit instructions to a network orchestrator to create the SFC in a network slice on the set of function nodes in accordance with the network slicing configuration and the traffic engineering parameters to provide the network traffic routing path.

15. The computing system of claim 14, wherein an identity of at least one of: the source node, the destination node, or a set of available function nodes, is provided by the network orchestrator available on a network.

16. The computing system of claim 14, wherein the joint network slicing and traffic engineering problem comprises a Mixed Integer Linear Program.

17. The computing system of claim 14, wherein the resource objective comprises at least one of: one or more link rates; total computational capacity of the set of function nodes in the SFC; total communication cost associated with traversing the SFC; or minimum number of function nodes in the SFC.

18. The computing system of claim 14, wherein the resource objective comprises a summation of link rates through the SFC, and wherein an objective function comprises:
g(r)=Σ.sub.kΣ.sub.ijr.sub.ij(k).

19. The computing system of claim 14, wherein the rate of the flow on the link is the rate of the flow k on the link being equal to the sum of the rates of the virtual flows over the link: r.sub.ij(k)=Σ.sub.s=0.sup.nr.sub.ij(k, f.sub.s.sup.k), and wherein the set of one or more constraints further includes at least one of: each function is provided by a single function node: Σ.sub.iεV.sub.fx.sub.i,f(k)=1; a link capacity constraint: Σ.sub.kr.sub.ij(k)≤c.sub.ij; a node capacity constraint; a second node capacity constraint expressed as a limit on a data rate λ(k) for flows processed by the single function node: Σ.sub.kΣ.sub.fx.sub.i,f(k)λ(k)≤μ; or a flow conservation constraint at one or more of: the source node: Σ.sub.jr.sub.s(k)j(k,f.sub.0.sup.k)=λ(k), the destination node: Σ.sub.jr.sub.jD(k)(k, f.sub.n.sup.k)=λ(k), or flow conservation constraints at adjacent nodes in the SFC: Σ.sub.jr.sub.ji(k, f.sub.s−1.sup.k)−Σ.sub.jr.sub.ij(k, f.sub.s−1.sup.k)=x.sub.i,f.sub.s.sup.k(k)λ(k), or Σ.sub.jr.sub.ji(k, f.sub.s.sup.k)−Σ.sub.jr.sub.ij(k, f.sub.s.sup.k)=−x.sub.i,f.sub.s.sub.k(k)λ(k).

20. The computing system of claim 14, wherein the joint network slicing and traffic engineering problem is solved by adding a penalty term: P.sub.ϵ(x)=Σ.sub.kΣ.sub.fϵF(k)(∥x.sub.f(k)+ϵ1∥.sub.p.sup.p −c.sub.e,f).

21. The computing system of claim 20, wherein the penalty term is differentiable and has a minimum value of 0.

22. The computing system of claim 14, wherein the minimizing the resource objective is complete, based on satisfaction of at least one of: Tmax minimization iterations have been performed; when one or more real variables of the joint network slicing and traffic engineering problem have been resolved to binary components; when the one or more real variables of the joint network slicing and traffic engineering problem have been resolved to values close to a binary component binary components; or when the one or more real variables of the joint network slicing and traffic engineering problem have been resolved to values within a pre-defined range of a binary component.

23. The computing system of claim 14, wherein the computing system is operative to solve the joint network slicing and traffic engineering problem by: relaxing the joint network slicing and traffic engineering problem by allowing binary variables to assume real values and adding a penalty term to an objective; solving the relaxed and penalized problem to generate X.sup.t; calculating an iteration of a (PSUM) subproblem ∇P.sub.ϵ(X.sup.t).sup.TX; solving the (PSUM) subproblem ∇P.sub.ϵ(X.sup.t).sup.TX; and checking to determine if an algorithm is complete and if it is not complete calculating a next iteration of the (PSUM) subproblem ∇P.sub.ϵ(X.sup.t).sup.TX, and if the algorithm is complete, outputting a complete solution.

24. The computing system of claim 14, wherein the set of one or more constraints includes a rate of a flow on a link being equal to a sum of rates of virtual flows over the link.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Further features and advantages will become apparent from the following detailed description, taken in combination with the appended drawings, in which:

(2) FIG. 1 is a network diagram illustrating a simplified example of an embodiment of a service-oriented network.

(3) FIG. 2 is a network node diagram illustrating an embodiment of a SFC model.

(4) FIG. 3A is a process flow diagram illustrates an embodiment of the PSUM algorithm.

(5) FIG. 3B, a simplified process flow diagram illustrates the main steps in an embodiment of a PSUM-R algorithm.

(6) FIGS. 4A, 4B, 4C are simplified process flow diagrams illustrating embodiments of a PSUM-R algorithm.

(7) FIG. 5A is a simplified network diagram of an example model network topology.

(8) Referring to FIG. 5B, histograms of the ratio between the obtained objective value and the optimal value for the relaxation LP are illustrated for embodiments of both PSUM and PSUM-R with a chain length=1.

(9) Referring to FIG. 5C, cumulative distribution functions of the ratio between the obtained objective value and the optimal value for the relaxation LP are illustrated for embodiments of both PSUM and PSUM-R with a chain length=2.

(10) Referring to FIG. 5D, histograms of the link capacity violation ratio and the node capacity violation ratio are illustrated for an embodiment of PSUM-R with a chain length=1.

(11) Referring to FIG. 5E, histograms of the link capacity violation ratio and the node capacity violation ratio are illustrated for an embodiment of PSUM-R with a chain length=2.

(12) FIG. 5F is a plot of time to compute for varying numbers of flow for embodiments of both PSUM and PSUM-R for a chain length=1.

(13) FIG. 5G is a plot of time to compute for varying numbers of flow for embodiments of both PSUM and PSUM-R for a chain length=2.

(14) FIG. 6 is a simplified block diagram of an embodiment of a computing system.

(15) It will be noted that throughout the appended drawings, like features are identified by like reference numerals.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

(16) In an implementation, a system and method is provided for routing data traffic on service-oriented networks that provides a joint solution for the combination of the network slicing problem and the traffic engineering problem.

(17) FIG. 1 is a network diagram illustrating a simplified example of an embodiment of a service-oriented network A 100 in communication with a Network B 105. Network A 100 and Network B 105 are illustrated as being hierarchical for illustrative purposes, however other network topologies are also possible. In the figure, a plurality of network nodes NN1 . . . NN14 are illustrated in Network A 100 making up the physical locations of each physical node of Network A 100. Some or all of the network nodes may comprise cloud computing nodes 120, illustrated with computing resources 110, which available to support a service or set of services. It will be appreciated that in some implementations all of the network nodes NN1 . . . NN14 may comprise computing nodes 120. In some implementations, only some of the network nodes NN1 . . . NN14 may comprise computing nodes 120. In some implementations, only some of the network nodes NN1 . . . NN14 may comprise computing nodes 120 available for some services supported by the Network A 100.

(18) Network B 105 is another network, or another domain of a larger network, that is connected to Network A 100. In some implementations, the services supported by Network A 100 may include a gateway to Network B 105. In some implementations, the services supported by Network A 100 may extend onto Network B 105.

(19) In the embodiment of FIG. 1, NN1 of Network A 100 includes an orchestrator 20 and a controller 10. The orchestrator 20 and controller 10 typically being implemented as network functions in the form of program code executable by one or more processors of computing resources available at one or more network nodes NN1 . . . NN14. The orchestrator 20 and controller 10 may be implemented as separate functions, as illustrated here, or may be combined into a combined function or set of functions.

(20) The orchestrator 20 is responsible for defining and establishing network slices on Network A 100. In some implementations, the orchestrator 20 may further be extended to other network nodes NN1 . . . NN14. In some implementations, a plurality of orchestrators 20 may be provided at a corresponding plurality of network nodes NN1 . . . NN14.

(21) Various network nodes NN1 . . . NN14 may comprise general purpose hardware that are customizable in software to provide network services. Some network nodes, such as NN5, NN6, NN8, NN9, NN11, NN12, NN13, NN14 may comprise specialized hardware to support access node functionality. In the embodiment of FIG. 1, for instance, the access nodes comprise radio access nodes (R)AN operative to provide wireless connectivity to the Network A 100 and some network nodes may provide routing services. Network nodes may also comprise a combination of general purpose hardware and specialized hardware as may be required for a particular implementation.

(22) When a network slice is to be established for a data traffic flow, the orchestrator 20 can determine the network node locations and sequence of network functions that support a network slice. The sequence of network functions is referred to as a service function chain (SFC). In the embodiment of FIG. 1, it is the task of the controller 10 to solve the joint network slicing problem and traffic engineering problem in order to support the orchestrator 20 in establishing and maintaining network slices. The controller 10 solves the joint problem and directs the orchestrator 20 regarding which of the network nodes NN1 . . . NN14 are to be selected to act as function nodes operative to support the network slice (i.e. “network slicing”) and the data traffic routing through those selected function nodes (i.e. “traffic engineering”).

(23) Referring to FIG. 2, an embodiment of a SFC model is presented. The SFC through which a flow k is sent is represented by a set of s functions, k: F(k)=(f.sub.1.sup.k, . . . , f.sub.s.sup.k, . . . , f.sub.n.sup.k). In the model, flow k is to be transmitted at a data rate λ(k) across i network nodes starting from a source node S(k) 200 and terminating at a destination node D(k) 210. Between the source node S(k) 200 and the destination node D(k) 210, are n network nodes operative to act as function nodes 215 (which may be logical entities within a network slice) selected from the set of available function nodes V.sub.f, each responsible for carrying out a network function f.sub.s. In the embodiment of FIG. 2 n=2 and there are two function nodes 215: function node 1 212 and function node 2 214. The computational capacity of each of the n function nodes 215, i.e. the “node capacity”, is represented as μ.sub.i. A binary variable x.sub.i,f(k) can indicate whether function node i provides function f for flow k. In this embodiment, the source node S(k) 200 and the destination node D(k) 210 do not provide for any functions operative on the flow k. In some embodiments, the source node S(k) 200 and/or the destination node D(k) 210 may provide for one or more functions operative on the flow k.

(24) A virtual flow (k,f.sub.s) denotes the flow k that has been processed by the s.sup.th function f.sub.s in the SFC. The rate of flow k on link (i,j) 220 in the flow path is r.sub.ij(k), and the rate of the virtual flow (k,f.sub.s) on link (i,j) 220 is represented as r.sub.ij(k,f.sub.s), with the flow through the first link being described as (k,f.sub.o) with none of the functions F(k) having operated on the flow at that point. Accordingly, the rate of flow k on link (i,j) 220 and the rate of the virtual flow (k,f.sub.s) on link (i,j) are related by the expression:
r.sub.ij=Σ.sub.s=0.sup.nr.sub.ij(k,f.sub.s.sup.k)  (1)

(25) Because it is assumed that there are is no splitting of a network function across function nodes, each function fϵF(k) is provided by a single function node 215. Accordingly, the sum of the binary variable x.sub.i,f(k) for all function nodes 215 is 1:
Σ.sub.i∈V.sub.fX.sub.i,f(k)=1  (2)

(26) A link capacity constraint that defines the maximum flow rate over link (i,j) 220 may be specified:
Σ.sub.kr.sub.ij(k)≤C.sub.ij  (3)

(27) A node capacity constraint. In some implementations, the node capacity constraint may be expressed in terms of the data rate λ(k) for flows that have been processed by the function node:
Σ.sub.kΣ.sub.fx.sub.i,f(k)λ(k)≤μ.sub.i  (4)

(28) Conservation of flow may be applied to derive constraints for the flow at the source node S(k) 200, the destination node D(k) 210, and the n function nodes 215. In particular, the flow at both the source node S(k) 200 and the destination node D(k) 210 must equal the data rate λ(k). Similarly, the flow through the n function nodes 215 must satisfy the flow condition at the boundaries and only flow through the utilised n function nodes 215.

(29) S(k) flow conservation constraint:
Σ.sub.jr.sub.s(k)j(k,f.sub.0.sup.k)=λ(k)  (5)
D(k) flow conservation constraint:
Σ.sub.jr.sub.jD(k)(k,f.sub.n.sup.k)=λ(k)  (6)
Function node flow conservation constraints:
Σ.sub.jr.sub.ji(k,f.sub.s-1.sup.k)−Σ.sub.jr.sub.ij(k,f.sub.s-1.sup.k)=x.sub.i,f.sub.s.sub.k(k)λ(k)  (7)
Σ.sub.jr.sub.ij(k,f.sub.s.sup.k)−Σ.sub.jr.sub.ij(k,f.sub.s.sup.k)=−x.sub.i,f.sub.s.sub.k(k)λ(k)  (8)

(30) Based on the above relations and constraints, the joint network slicing and traffic engineering problem may be expressed as:

(31) $\left(P\right)\underset{r,x}{\min }g$

(32) Subject to constraints (1)-(8) above, as well as:
r.sub.ij(k)≥0,r.sub.ij(k,f)≥0,∀(i,j),k,f
x.sub.ij(k)∈{0,1},∀k,f,i

(33) The objective function g is a resource objective associated with network slicing and traffic engineering including, without limitation, one or more link rates in the SFC, a total computational capacity in the function nodes supporting the functions in the SFC, a communication cost associated with traversing the SFC within a network slice, a minimum number of function nodes to support the SFC and connect the source node to the destination node, or a combination of the above. In this example the objective g is a summation of the link rates through the SFC:
g(r)=Σ.sub.kΣ.sub.ijr.sub.ij(k)

(34) The above joint network slicing and traffic engineering problem (P) is a mixed integer linear program, which in some embodiments has a feasibility proven as NP-complete. It may also be NP-Hard, regardless of which objective function, or combination of objective functions, is used.

(35) In a first embodiment, a solution to the problem P may be efficiently achieved through the inventors' “PSUM” algorithm (which will be discussed below, and in particular with respect to FIG. 3A) by relaxing the requirements of the binary variables to be either 1 or 0 to allow them to be real values, and by adding to the objective function a penalty term up to constant C.sub.ϵ,.sub.f. The penalty term being differentiable and taking a minimum value of 0. The binary components of an optimal solution of the relaxed and penalized problem may end up being binary at the optimal solution. Let
x.sub.k={x.sub.i,f(k)}.sub.i∈V.sub.f.sub., Then
∥x.sub.f(k)∥.sub.1=1 l.sub.p-norm function:
∥x∥.sub.p=(|x.sub.1|.sup.p+ . . . +|x.sub.n|.sup.p).sup.1/p(0<p<1) Penalty term:
P.sub.∈(x)=Σ.sub.kΣ.sub.f∈F(k)(∥x.sub.f(k)+∈1∥.sub.p.sup.p−c.sub.∈,f)

(36) With the relaxation of the binary values, and the addition of a penalty term, a penalized problem may be derived:

(37) $\underset{\stackrel{\_}{z}=\left(\stackrel{\_}{r},\stackrel{\_}{X}\right)}{\min }{g}_{\sigma }\left(\stackrel{\_}{z}\right)=g\left(\stackrel{\_}{r}\right)+\sigma P_{ϵ}\left(\stackrel{\_}{X}\right)$ Subject to constraints (1)-(8) above, and
r.sub.ij(k)≥0,r.sub.ij(k,f)≥0,∀(i,j),k,f
x.sub.ij(k)∈{0,1}∀k,f,i

(38) Applying a convergence analysis to the penalized problem it can be assumed that the positive sequence {σ.sub.t} is monotonically increasing and σ.sub.t.fwdarw.+∞, and z.sup.t is a global minimizer of the penalized problem with the objective function gσ.sub.t(z). Then any limit point of {z.sup.t} is a global minimizer of the problem P.

(39) As the penalized problem is not convex, a successive upper bound minimization approach may be used to find an optimal solution. In particular, a sequence of approximate objective functions may be solved:
P.sub.∈(X)≤P.sub.∈(X.sup.t)+∇P.sub.∈(X.sup.t).sup.T(X−X.sup.t)

(40) Based on this, the PSUM subproblem (in the t+1.sup.st iteration) may be framed as a linear program. If an iteration of PSUM returns an integer solution with an objective value being equal to g.sub.LP*, the lower bound of the optimal value of the l.sub.p relaxation problem P where the binary values are relaxed, then the solution must be a global optimal solution:

(41) $\underset{\stackrel{\_}{r},\stackrel{\_}{X}}{\min }g\left(\stackrel{\_}{r}\right)+{\sigma }_{t+1}\nabla {P_{\in }\left({\stackrel{\_}{X}}^t\right)}^T\stackrel{\_}{X}$ Subject to constraints (1)-(8) above, and
r.sub.ij(k)≥0,r.sub.ij(k,f)≥0,∀(i,j),k,f
x.sub.ij(k)∈{0,1},∀k,f,i

(42) Referring to FIG. 3A, a process flow diagram illustrates an embodiment of the PSUM algorithm. In initial step 300 the iteration index t may be set equal to 1. In step 305 solve for the relaxation of problem P by changing the binary variable to a real number to produce X.sup.t. In step 310, calculate ∇P.sub.ϵ.sub.t(X.sup.t). In step 320, solve the t+1.sup.st PSUM subproblem. In step 330, test for solution completion. If the solution is not complete, then the iteration index is incremented, and the process returns to step 310. If the solution is complete, then in step 340 the solution may be outputted for use by the orchestrator 20 if it is a final solution, or for further processing if it is an interim solution as is described below.

(43) In an embodiment, the solution is complete when sufficient minimizing iterations have been processed to solve for all of the binary components to produce a final solution. In an embodiment, the solution is ‘complete’ when a pre-defined maximum number of minimizing iterations, i.e. after q minimizing iterations t=T.sub.max, have been processed to reach an interim solution that may be output for further processing to reach a final solution. In some embodiments, an interim solution is considered complete when, after q minimizing iterations, a pre-defined number of relaxed real variables have been resolved to binary values. In some embodiments, an interim solution is considered complete when, after q minimizing iterations, a pre-defined number of relaxed real variables have been resolved to real values within a pre-defined range of a binary value. In some embodiments, the pre-defined range is relatively small such that it is likely the real value would resolve to the binary value given sufficient further minimizing iterations >q. When the relaxed real variables have been resolved to real values within a pre-defined range of a binary value, the resolved values may be rounded to the binary value that they would likely resolve to in time, with sufficient further minimizing iterations.

(44) In an embodiment, the PSUM algorithm may be extended as a PSUM-R(ounding) algorithm to allow for resource violation(s) in order to direct the algorithm to faster convergence. In some implementations, the resource violation may comprise rounding real values that have been resolved within a pre-defined range of a binary value to that binary value. In some implementations, the resource violation may comprise identifying an available function node jϵV.sub.f with a maximum remaining computational capacity as compared with the other available function nodes, and fixing function node j to provide a function for flow k. In some implementations, the resource violation comprises fixing the values of the binary variables, and solving problem (P) with an objective g+τΔ, the link capacity constraint being modified to allow for a resource violation of Δ, with a weight of τ in the objective function g. The link capacity constraint being modified to Σ.sub.kr.sub.ij(k)≤c.sub.ij+Δ,∀(i,j). In these implementations, the resource violation allows for limited violation of the link capacities to assist in simplifying the problem.

(45) Referring to FIG. 3B, a simplified process flow diagram illustrates the main steps in an embodiment of a PSUM-R algorithm. In this embodiment, both resource violation techniques are applied, though as discussed above in some embodiments one or more of the resource violation techniques may apply and depending upon the objective function one or more resource constraints may be relaxed. In step 350, an interim solution z=(r, X.sup.−) is obtained after completion of q minimizing iterations of the PSUM algorithm described above and output in step 340 of FIG. 3A. As discussed, the interim solution may be obtained when, after q minimizing iterations, a pre-defined number T.sub.max minimizing iterations have passed or a pre-determined number of real values have resolved to within a pre-defined range of a binary variable. In step 355, the real values of X.sup.− are rounded to binary values. As indicated above, in some embodiments the real values of X.sup.− are only rounded to binary values if they are within a pre-defined range of a binary value (e.g. if a component of X.sup.−≈1, X.sup.−≈0). In step 360, flow routing (i.e. traffic engineering) may be determined by relaxing at least one resource constraint. In the example of FIG. 3B, the resource constraint being violated is the link capacity.

(46) Referring to FIG. 4A, a simplified process flow diagram illustrates an embodiment of a PSUM-R algorithm. In step 400, an interim solution z=(r, X.sup.−) is obtained after completion of q minimizing iterations of the PSUM algorithm described above and output in step 340 of FIG. 3A. In step 405, the rounding operation of step 355 is performed selectively. In the embodiment of FIG. 4A, for each x.sub.f(k): if the maximum element≈1, the corresponding function node is set to provide a function for flow k (i.e. set x.sub.i,f(k)=1). In step 445, the rounded binary values are fixed. In step 450, the problem P is solved with the rounded binary variables using:
objective function: g+τΔ
link capacity constraint: Σ.sub.kr.sub.ij(k)≤C.sub.ij+Δ,∀(i,j)

(47) Referring to FIG. 4B, a simplified process flow diagram illustrates an embodiment of a PSUM-R algorithm. In step 400, an interim solution z=(r, X.sup.−) is obtained after completion of q minimizing iterations of the PSUM algorithm described above and output in step 340 of FIG. 3A. In step 405, the rounding operation of step 355 is performed selectively. In the embodiment of FIG. 4B, for each x.sub.f (k): if the maximum element≈1, set the corresponding function node to provide a function for flow k (i.e. set x.sub.i,f(k)=1). In step 410 a test is performed to determine if all x.sub.f(k) are now binary values. If all x.sub.f(k) are not binary values, then in step 420 the PSUM calculations are iterated using the partially rounded set of x.sub.f(k) to obtain another solution (interim or final). If all {circumflex over (x)}.sub.f(k) are binary values, then the process continues to steps 445 and 450 described above.

(48) Referring to FIG. 4C, a simplified process flow diagram illustrates an embodiment of a PSUM-R algorithm. In step 400, an interim solution z=(r, X.sup.−) is obtained after completion of q minimizing iterations of the PSUM algorithm described above and output in step 340 of FIG. 3A. In step 407, each x.sub.f(k) is evaluated to determine if the maximum element is ≈1. If the maximum element is ≈1 then in step 430 the corresponding function node is set to provide a function for flow k (i.e. set x.sub.i,f(k)=1). If the maximum element is not close to 1, then in step 435 an available function node jϵV.sub.f with a maximum remaining computational capacity, as compared with the other available function nodes, is found and function node j is set to provide a function for flow k. With all x.sub.f(k) accounted for, the process continues to steps 445 and 450 described above.

(49) Experimental results detailed below were calculated using MATLAB (2013b) executed on server with 2.30 GHz CPUs. The PSUM algorithm was executed using: q=T.sub.max=20 minimizing iterations, σ.sub.1=2, ϵ.sub.1=0.001, γ=1.1, η=0.7. The PSUM-R algorithm was executed using the embodiment of executing the PSUM algorithm for a pre-defined q=T.sub.max=7 minimizing iterations, and outputting the interim solution. The embodiment of the PSUM-R algorithm simulated is that described with reference to FIG. 4C.

(50) FIG. 5A is a simplified network diagram of an example model network topology used to simulate performance of embodiments of the invention. In the example, there are 112 network nodes and 440 directed links. The destination node D(k) is fixed, and the source node S(k) is randomly chosen from any one of the square network nodes for each flow of the simulation. Core routers are denoted by black triangles and are not enabled to act as function nodes. Network nodes which are enabled for network function virtualization and to act as function nodes are indicated by black diamonds. The white square nodes are network nodes that transfer flows, but do not act as function nodes.

(51) Referring to FIG. 5B, histograms of the ratio between the obtained objective value and the optimal value for the relaxation LP are illustrated for both PSUM and PSUM-R with a chain length=1. The simulation was executed with k=20 flows, each with traffic demand λ(k) being an integer in [1,5]. Link capacities are integers selected form the set [5, 50], and the node capacity=16. In 42 out of 50 trials, PSUM returned integer solutions with objective values matching the optimal value. In 45 out of 50 trials, PSUM-R returned integer solutions matching the optimal value of the relaxation LP.

(52) Referring to FIG. 5C, cumulative distribution functions of the ratio between the obtained objective value and the optimal value for the relaxation LP are illustrated for both PSUM and PSUM-R with a chain length=2. In 13 out of 50 trials, PSUM returned integer solutions with objective values matching the optimal value of the relaxation LP.

(53) Referring to FIG. 5D, histograms of the link capacity violation ratio (link capacity violation/link capacity) and the node capacity violation ratio (node capacity violation/node capacity) are illustrated for PSUM-R with a chain length=1.

(54) Referring to FIG. 5E, histograms of the link capacity violation ratio (link capacity violation/link capacity) and the node capacity violation ratio (node capacity violation/node capacity) are illustrated for PSUM-R with a chain length=2.

(55) FIG. 5F is a plot of time to compute for varying numbers of flow for each of PSUM and PSUM-R for a chain length=1.

(56) FIG. 5G is a plot of time to compute for varying numbers of flow for each of PSUM and PSUM-R for a chain length=2.

(57) FIG. 6 is a simplified block diagram of an embodiment of a computing system 600 that may be used for implementing the devices and methods disclosed herein. In particular, the network nodes may each include one or more computing systems 600. The network functions and scout functions described above may be instantiated by execution by processors on one or more computing systems 600. In some implementations, functions f.sub.s may be instantiated across a plurality of computing systems 600 across a plurality of geographic locations to support requisite network slicing.

(58) Specific devices may utilize all of the components shown or only a subset of the components, and levels of integration may vary from device to device. Furthermore, a device may contain multiple instances of a component, such as multiple processors, memories, transmitters, receivers, etc. The computing system 600 includes a processor 614, a bus 620 and a memory 608, and may optionally also include a mass storage device 604, a video adapter 610, and an I/O interface 612 (shown in dashed lines). The computing system 600 may further include one or more network interface(s) 606 for connecting the computing system 600 to communication networks 622.

(59) The processor 614 may comprise any type of electronic data processor, and may include one or more cores or processing elements. The memory 608 may comprise any type of non-transitory system memory such as static random access memory (SRAM), dynamic random access memory (DRAM), synchronous DRAM (SDRAM), read-only memory (ROM), or a combination thereof. In an embodiment, the memory 608 may include ROM for use at boot-up, and DRAM for program and data storage for use while executing programs. The bus 620 may be one or more of any type of several bus architectures including a memory bus or memory controller, a peripheral bus, or a video bus.

(60) The mass storage 604 may comprise any type of non-transitory storage device configured to store data, programs, and other information and to make the data, programs, and other information accessible via the bus 620. The mass storage 604 may comprise, for example, one or more of a solid state drive, hard disk drive, a magnetic disk drive, or an optical disk drive.

(61) The video adapter 610 and the I/O interface 612 provide optional interfaces to couple external input and output devices to the processing unit 602. Examples of input and output devices include a display 618 coupled to the video adapter 610 and an I/O device 616 such as a keyboard, touch-screen, mouse or other user input device coupled to the I/O interface 612. Other devices may be coupled to the computing system 600, and additional or fewer interfaces may be utilized. For example, a serial interface such as Universal Serial Bus (USB) (not shown) may be used to provide an interface for an external device. Alternatively, the computing system 600 may rely upon the network interface(s) 606 for connection to available mass storage(s), video adapter(s) 610, and I/O interface(s) 612 available on the networks 622.

(62) In some embodiments, a computing system 600 may comprise a standalone server. In other embodiments, the computing system may comprise rack mounted server components networked together for connectivity. In some embodiments, the network functions f.sub.j and/or scout functions S.sub.i described above may be instantiated within a virtualized computing environment supported by one or more computing systems 600.

(63) In some embodiments, a computer program product may be provided. The computer program product including a non-transitory computer readable memory storing computer executable instructions thereon that when executed by at least one processing element of a computing system 600 perform the above described method steps.

(64) Although the present application describes specific features and embodiments, it is evident that various modifications and combinations can be made thereto without departing from the invention. The specification and drawings are, accordingly, to be regarded simply as an illustration as defined by the appended claims, and are contemplated to cover any and all modifications, variations, combinations or equivalents that fall within the scope of those claims.