Method for dynamically allocating resources in an SDN/NFV network based on load balancing

Abstract

The present application provides a method for dynamically allocating resources in an SDN/NFV network based on load balancing. For multimedia services with different demands, a virtual link mapping target, a constraint and a load state of a physical link are associated. A subtask is adaptively mapped to a network node according to the load state of the physical link. The method effectively distinguishes used resources and remaining resources of a physical node and a link to balance the load, and thereby improve the utilization of network resources and avoid occurrence of a local optimum or current optimum. The solution involves performing a subtask mapping to find a server node satisfying constraints for each subtask in a service request. The model for mapping the subtask is $\underset{T.fwdarw.V}{\min }{\mathrm{Target}}_1$$s.t.C_1,C_2,C_3,C_4.$
A virtual link mapping is then performed to find a physical path for each virtual link in the service request, which satisfies the capability constraint of the virtual link. The dynamic virtual mapping is described as $\underset{E_T.fwdarw.E_s}{\min }{\mathrm{Target}}_2$$s.t.C_1^{},C_2^{},C_3^{}.$

Claims

1. A method for dynamically allocating resources in an SDN/NFV network based on load balancing, comprising: creating a task-network model, which comprises a directed acyclic graph DAG of a service and an undirected graph of a network; and creating an allocation model based on the task-network model to achieve mappings for subtasks and for virtual links; wherein creating the allocation model based on the task-network model comprises: determining physical nodes for respective subtasks which satisfy a first constraint, to obtain a model for mapping subtasks onto physical nodes; and determining physical paths for respective virtual links which satisfy a second constraint, to achieve the mapping for the virtual links; wherein the first constraint comprises the following constraints: Constraint 1: each task can be performed only on one physical node, $C_1\text{:}\underset{iZ}{\overset{}{.Math.}}{x}_{\mathrm{it}}=1tT;$ Constraint 2: each physical node can perform at least one subtask, $C_2\text{:}\underset{tT}{\overset{}{.Math.}}{x}_{\mathrm{it}}1iZ;$ Constraint 3: if a physical node i is performing a subtask t, a physical node j which is to perform the next subtask t+1 must be connected to the physical node i, $C_3\text{:}{e}_{\mathrm{ij}}=\{\begin{array}{cc}1& \mathrm{if}{x}_{\mathrm{it}=1}\mathrm{AND}{x}_{j,\left(t+1\right)}=1\\ 0& \mathrm{otherwise}\end{array}i,jZ;$ and Constraint 4: available resources on physical node i cannot be less than resources required by subtask t, and 10% of the resources are reserved for redundancy and backup, $C_4\text{:}\{\begin{array}{c}90\%.Math.{\mathrm{CPU}}_{\mathrm{available}}^i{\mathrm{CPU}}_{\mathrm{required}}^t\\ 90\%.Math.{\mathrm{Memory}}_{\mathrm{available}}^i{\mathrm{Memory}}_{\mathrm{required}}^t\end{array}.$

2. The method of claim 1, wherein creating the task-network model comprises: creating the DAG of the service, which is represented as D.sub.T=(T, E.sub.T), where T=(T.sub.1, T.sub.2, . . . , T.sub.) is a node in the DAG, and E.sub.T=(e.sub.uv) represents a virtual link from node u to node v, and each node in the DAG representing a subtask; and allocating a physical node and a path to each subtask for performing according to requirements of the service and remaining capacities of physical nodes and paths to obtain the undirected graph of the network, which is represented as G=(V, E.sub.s), where V={1, . . . , i, . . . , N} represents a physical node, and E.sub.s={e.sub.ij} is a set of undirected edges and represents physical links, and each physical node having a specific available resource.

3. The method of claim 1, wherein determining physical nodes for respective subtasks which satisfy a first constraint, to obtain a model for mapping subtasks onto physical nodes, comprises: calculating a level of balancing of the physical nodes according to the following formula: ${}_{\mathrm{server}}^2=[\underset{i=1}{\overset{N}{.Math.}}{\left({\mathrm{CPU}}_{\mathrm{consumed}}^i-\stackrel{\_}{\mathrm{CPU}}\right)}^2+\underset{i=1}{\overset{N}{.Math.}}{\left({\mathrm{Memory}}_{\mathrm{consumed}}^i-\stackrel{\_}{\mathrm{Memory}}\right)}^2]/2N,$ where N is the number of the physical nodes, CPU and Memory are average CPU consumption and memory consumption of the physical nodes; determining a first objective function based on the level of balancing of the physical nodes, wherein an expression of the first objective function is:
Target.sub.1=.Math..sub.server.sup.2+.Math.N, where and are normalized weights for the level of balancing and the average of the number of the physical nodes respectively, and +=1; and determining the model for mapping subtasks based on the first constraint and the first objective function, with a maximum level of balancing and least physical nodes, wherein model for mapping subtasks is: $\underset{T->V}{\min }{\mathrm{Target}}_1$ $s.t.C_1,C_2,C_3,C_4.$

4. The method of claim 1, wherein the second constraint comprises the following constraints: Constraint 1: a bandwidth that a virtual link requires is not larger than a remaining available bandwidth of a physical link onto which the virtual link is mapped, and the constraint on bandwidth for the mapping of the virtual link is
C.sub.1: B(E.sub.T(u,v))R.sup.B(E.sub.S(i,j)); Constraint 2: a length of a physical path is not larger than an upper tolerance of a path length of a virtual link, and the constraint on the physical path is:
C.sub.2: len(ps)len(E.sub.T), where len(ps) is a length of the physical path ps, which is the number of links contained in the physical path; and Constraint 3: during the mapping of the virtual link E.sub.T(u, v), the sum of directed flows of physical nodes which a task flow passes through except for the source node and the destination node is 0, $C_3^{}\text{:}\underset{i,jT}{.Math.}{f}_{\mathrm{ij}}^{\mathrm{uv}}-\underset{i,jT}{\overset{}{.Math.}}{f}_{\mathrm{ji}}^{\mathrm{uv}}=\{\begin{array}{cc}1,& \mathrm{if}{x}_i^u=1\\ -1,& \mathrm{if}{x}_j^v=1\\ 0,& \mathrm{otherwise}\end{array}u,vT,f_{\mathrm{ij}}^{\mathrm{uv}}\left\{0,1\right\}.$

5. The method of claim 4, wherein determining physical paths for respective virtual links which satisfy a second constraint, to achieve the mapping for the virtual links, comprises: determining a normalized cost=f(bandwidth, CPU) as $\mathrm{cost}=\underset{tT}{\overset{}{.Math.}}{\mathrm{CPU}}_{{\mathrm{SDN}}_t}+\underset{tT}{\overset{}{.Math.}}\underset{\left(i,j\right)L}{\overset{}{.Math.}}{}_{i,j}{B}_{\left(i,j\right)},$ where t is a subtask being executed in a link, L is a physical path during performing of subtask, B(i,j) represents a bandwidth occupied on a link from physical node i to physical node j, and .sub.i,j is a weight for the bandwidth occupied on the link by a task flow from physical node i to physical node j, ${}_{i,j}=\frac{B_{\left(i,j\right)\mathrm{consumed}}+}{B_{\left(i,j\right)\mathrm{total}}},$ where B.sub.(i,j)consumed is a bandwidth consumed on the link from physical node i to j, B.sub.(i,j)total is a total bandwidth of the link from physical node i to j, and is a random number for preventing the numerator from being 0; determining a formula for calculating a normalized QoS as:
QoS(C)=SL.sub.SL+PL.sub.PL+PJ.sub.PJ+PD.sub.PD+BW.sub.BW, where .sub.i represents a weight corresponding to a factor i, and the factor i comprises a sudden loss (SL), packet loss (PL), packet jitter (PJ), packet delay (PD), and bandwidth (BW); determining a second objective function based on the normalized QoS and the normalized cost, wherein the second objective function is:
Target.sub.2=.Math.QoS(C)+.Math.cost(C), where QoS(C) is the normalized QoS and cost(C) is the normalized cost, and and are weighting factors for QoS(C) and cost(C) respectively, which vary depending on services; and determining a model for mapping virtual links based on the second objective function and the second constraint, wherein the model for mapping virtual links is: $\underset{E_T->E_s}{\min }{\mathrm{Target}}_2$ $s.t.C_1^{},C_2^{},C_3^{}.$

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a DAG diagram showing a task chain according to the present application.

(2) FIG. 2 is a diagram showing a SDN/NFV network model according to the present application.

(3) FIG. 3 is a flow chart of the present application.

(4) FIG. 4 is a diagram of showing the usage of a CPU after balancing according to the present application.

(5) FIG. 5 is a diagram showing the usage of a memory after balancing according to the present application.

(6) FIG. 6 is a diagram showing the usage of a CPU before balancing according to the present application.

(7) FIG. 7 is a diagram showing the usage of a memory before balancing according to the present application.

(8) FIG. 8 is a diagram showing the contrast for mapping links according to the present application.

(9) FIG. 9 is a diagram showing the contrast of impacts of balancing on QoS according to the present application.

DETAILED DESCRIPTION

(10) The above-mentioned and other techniques, features and effects of the present application will become apparent on examination of the following detailed description of embodiments illustrated with reference to FIG. 1 to FIG. 9. The description relating to structures hereafter are all described with reference to the drawings.

(11) Embodiment 1 provides a method for dynamically allocating resources in an SDN/NFV network based on load balancing, comprising the following steps:

(12) S1: creating a task-network model.

(13) 1. A general serial DAG is used to represent different services, which is represented as D.sub.T=(T, E.sub.T), where T={T.sub.1, . . . , T.sub.t, . . . , T.sub.} represents a subtask of a service, and E.sub.T=(e.sub.uv) represents a virtual link from a node u to a node v. Each node in the DAG represents a subtask. A binary number x.sub.it represents a performing state of the subtask t in the node i, and x.sub.it indicates that the node i is performing the subtask t when its value is 1. FIG. 1 illustrates a DAG for a service chain. The QoS of the service is optimized on the whole by reasonably mapping nodes that perform subtasks of different services and mapping paths, with the balancing of traffic carried by a link ensured.

(14) 2. Based on the SDN/NFV network model, a substrate network is modeled as an undirected graph G=(V, E.sub.S), where a vertex V={1, . . . , i, . . . , N} represents a physical network node, and a set of undirected edges E.sub.S={e.sub.ij} represents a network link. Each network element has specific available resources. Different services have different demands and task parameters, and consume a processing capability of nodes and bandwidth of links. A node performing a subtask and a path are allocated according to service demands. The node's remaining capacity is taken into consideration in selecting a node and a path. It is desirable to select a node or a link with a large remaining capacity. The load of the whole network is thus balanced, and the transmission of the service is achieved with high quality.

(15) S2: creating an allocation model on the basis of S1, to achieve mappings for subtasks and virtual links.

(16) 1. A server node satisfying a constraint is found for a subtask in a service request. The formula for mapping the subtask is:
M.sub.task:T.fwdarw.V.

(17) Its constraints are as follows:

(18) Constraint 1: each task t can be performed on only one node, namely,

(19) $C_1\text{:}\underset{iZ}{.Math.}{x}_{\mathrm{it}}=1tT;$

(20) Constraint 2: each node can perform at least one subtask, namely,

(21) $C_2\text{:}\underset{tT}{.Math.}{x}_{\mathrm{it}}1iZ;$

(22) Constraint 3: if a node i is performing a task t, a node j which is to perform a task (t+1) (the next task) must be connected to the node i, namely,

(23) $C_3\text{:}{e}_{\mathrm{ij}}=\{\begin{array}{cc}1& \mathrm{if}{x}_{\mathrm{it}=1}\mathrm{AND}{x}_{j,\left(t+1\right)}=1\\ 0& \mathrm{otherwise}\end{array}i,jZ;$

(24) Constraint 4: each node has specific available resources, and each subtask requires specific CPU and memory from the server node. Therefore, the available resources of the node i cannot be less than resources that the subtask t needs, and 10% of the resources are reserved for redundancy and backup, namely,

(25) $C_4\text{:}\{\begin{array}{c}90\%{\mathrm{CPU}}_{\mathrm{available}}^i{\mathrm{CPU}}_{\mathrm{required}}^t\\ 90\%{\mathrm{Memory}}_{\mathrm{available}}^i{\mathrm{Memory}}_{\mathrm{required}}^t\end{array}.$

(26) The mapping of subtasks is achieved with optimal balancing and minimum server nodes. The number of server nodes is represented with N. The balancing is represented with a variance of the consumed resources of server nodes, and is expressed as:

(27) ${}_{\mathrm{server}}^2=[\underset{i=1}{\overset{N}{.Math.}}{\left({\mathrm{CPU}}_{\mathrm{consumed}}^i-\stackrel{\_}{\mathrm{CPU}}\right)}^2+\underset{i=1}{\overset{N}{.Math.}}{\left({\mathrm{Memory}}_{\mathrm{consumed}}^i-\stackrel{\_}{\mathrm{Memory}}\right)}^2]/2N,$
where CPU and Memory are average consumption quantities of the CPU and the memory of a server node respectively. The objective function is:
Target.sub.1=.Math..sub.server.sup.2+.Math.N,
where and are normalized weights for the level of balancing and average of the number of nodes, and +=1.

(28) A model for mapping subtasks is expressed as:

(29) $\underset{T->V}{\min }{\mathrm{Target}}_1$$s.t.C_1,C_2,C_3,C_4.$

(30) 2. After VNFs is mapped to network nodes, a physical path satisfying capability constraints of the virtual link in the service request is found for the virtual link, and an SDN controller implements the mapping of the virtual link. The formula for mapping the virtual link is expressed as:
M:E.sub.T.fwdarw.E.sub.S.

(31) Constraint 1: a required bandwidth of the virtual link cannot be larger than a remaining available bandwidth of the physical link to which the virtual link is mapped, namely, the constraint on the bandwidth for the mapping of the virtual link is:
C.sub.1:B(E.sub.T(u,v))R.sup.B(E.sub.S(i,j)).

(32) Constraint 2: considering a delay demand of service transmission, a length of a physical path cannot be larger than an upper tolerance of a path length of a virtual link. The constraint on the path is:
C.sub.2:len(ps)len(E.sub.T),
where len(ps) is the length of the physical path ps, i.e., the number of links contained in the path.

(33) Constraint 3: during the mapping of the virtual link E.sub.T(u, v), the sum of directed flows of physical nodes which a task flow passes through except for the source node and the destination node is 0,

(34) $C_3^{}\text{:}\underset{i,jT}{.Math.}{f}_{\mathrm{ij}}^{\mathrm{uv}}-\underset{i,jT}{\overset{}{.Math.}}{f}_{\mathrm{ji}}^{\mathrm{uv}}=\{\begin{array}{cc}1,& \mathrm{if}{x}_i^u=1\\ -1,& \mathrm{if}{x}_j^v=1\\ 0,& \mathrm{otherwise}\end{array}u,vT,f_{\mathrm{ij}}^{\mathrm{uv}}\left\{0,1\right\}.$

(35) An objective function for network resource allocation is defined. The objective function includes costs and benefits of a link and of a node performing a task and weights corresponding to different services. The formula is defined as:
Target.sub.2=.Math.QoS(C)+.Math.cost(C),
where QoS(C) and cost(C) are the normalized QoS and cost, and and are weighting factors of QoS(C) and cost(C) respectively, which vary depending on services.

(36) Costs involve nodes and links. A cost function is cost=f(bandwidth, CPU), and the specific formula is as follows:

(37) 0$\mathrm{cost}=\underset{tT}{\overset{}{.Math.}}{\mathrm{CPU}}_{{\mathrm{SDN}}_t}+\underset{tT}{\overset{}{.Math.}}\underset{\left(i,j\right)L}{\overset{}{.Math.}}{}_{i,j}{B}_{\left(i,j\right)},$
where t is the task being performed on a link, L is a routing path when performing the task, B.sub.(i,j) represents a bandwidth occupied from node i to j node, and .sub.i,j is a weight for the bandwidth of the link occupied by a task flow from node i to node j.

(38) ${}_{i,j}=\frac{B_{\left(i,j\right)\mathrm{consumed}}+}{B_{\left(i,j\right)\mathrm{total}}},$
where B.sub.(i,j)consumed and B.sub.(i,j)total are a consumed bandwidth and a total bandwidth of the link from node i to node j, and is a very small number preventing the numerator from being 0.

(39) QoS involves many factors. Certain factors include a sudden loss (SL), packet loss (PL), packet jitter (PJ), packet delay (PD) and bandwidth (BW). A weight corresponding to each factor is calculated using an analytic hierarchy process. The formula for calculating the normalized QoS (QoS(C)) is thus obtained, which is:
QoS(C)=SL.sub.SL+PL.sub.PL+PJ.sub.PJ+PD.sub.PD+BW.sub.BW,
where .sub.i (such as .sub.SL and .sub.PD) represents a weight corresponding to a factor i, and the weight is calculated using the analytic hierarchy process and has passed the consistency check, and thus can well represent a proportion of impact exerted by its corresponding factor on the overall QoS.

(40) To conclude, a dynamic virtual mapping is expressed as:

(41) $\underset{E_T->E_s}{\min }{\mathrm{Target}}_2$$s.t.C_1^{},C_2^{},C_3^{}.$

(42) In practice, the method for dynamically allocating resources in an SDN/NFV network based on load balancing with respect to multimedia services is explained in detail with reference to FIG. 3. At step 1, node data information needed is collected within the network. At step 2, a value of the objective function is calculated according to collected node data information. At step 3, a node to which a subtask is mapped is determined according to the calculated value of the objective function. At step 4, link data information needed is collected within the network. At step 5, a value of the objective function is calculated according to collected link data information. At step 6, a manner in mapping a virtual link is calculated according to this value of the objective function.

(43) Referring to FIGS. 4-7, the load balancing of servers in allocating subtasks is verified. Ten servers are provided to perform the subtasks. The method according to the present application allows load balancing of the server nodes while using as few severs as possible. A simulation result is shown in the figures. In the case that the balancing is taken into consideration, only 6 servers are used. The usages of the CPUs stay in the range from 65% to 85%, and the usages of the memories stay in the range from 70% to 85%. In the case that the balancing is not taken into consideration, all of the 10 servers are used to perform the service. The usages of the CPUs and the usages of the memories vary significantly from server to server, and the loads across the servers are unbalanced.

(44) Next, referring to FIG. 8, the load balancing in mapping the virtual links is verified. The verification is carried out in 50 links. The mapping for virtual links is achieved by the method with the load balancing of the link taken into consideration. The usage of each link stays in the range from 68% to 78%. In the case that the balancing is not taken into account, the usages of the links vary greatly, fluctuating at 53%-93%. The non-balancing of the links severely affects the QoS of the current service, and will affect the quality of a service to be carried. Therefore, the balancing of the link being taken into consideration is of great importance for improving the carrying capability of the network.

(45) Finally, referring to FIG. 9, the impact exerted by the link balancing on the QoS of the carried service is verified through experiments. In the case that the balancing is considered, the QoS value of the service is smaller than that in the case where the load balancing is not considered. This indicates that in the case of link balancing, the time delay, jitter and packet loss rate of the service are relatively small. Moreover, when service traffic increases, a network with the load-balanced link may contribute a lot to good service quality.

(46) The present application is not limited to the specific implementations that have just been described in detail. Variations and adjustments of operations and data made by those skilled in the art based on the concept of the technical solutions of the present application all should fall within the protection scope of the present application.