WIXLIB

1708Fig. 1.IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 69, NO. 2, FEBRUARY 2020The NFV network architecture.The up to date developments and challenges of NFV is surveyedin [11]. In [12], a new model for enhancing virtual machineapplications performance is proposed. In [13], the authors propose an architecture involving both mobile edge computing(MEC) and NFV, which enables joint managing applicationsand virtual network functions. The NFV compound effect ofthe system is evaluated. An adaptive memory load management scheme for the server running on the virtual machine inthe cloud data center is proposed in [14], which can preventthe memory overload. In [15], the authors jointly minimize thepower consumption considering servers and switches, whichgenerates the optimal VNFs placement. In [16], the authorsmodeled the VNF allocation problem by queuing system withconstraints and solve the Markov decision process to find theoptimal policy. In [17], a new dynamic resource pooling andtrading mechanism in network virtualization are proposed andsolved by the Stackelberg game. Most of the literature solvedthe problems using heuristic methods which cannot guaranteethe global optimal.Nowadays, NFV/SDN architecture is popular for its flexibility. In [18], the software-defined and network virtualizationnetworking is surveyed, as well as the SDN applied on OpenADN in a multi-cloud environment. The SDN-NFV mobilenetworks are modeled in [19] to minimize equipment failurerisks as well as fast recovery of network nodes after a disasterhappens. A service function chaining embedding problem forSDN-NFV is presented in [20], which is solved by splittingthe traffic to several VNFs in the service chain. In [21], theauthors introduce SDN and NFV including service chains. SFCis introduced in the NFV, which connects several services andenables a single network to achieve many services. ClusteredNFV service chaining is adopted to obtain the optimal number ofclusters in [22], which can minimize the end-to-end service timein MEC RANs. The function chains can be customized which isstated in [23]. Vehicles are playing a major role in the distributedmobile scenario. In [24], the authors propose an intelligent VNFsselection strategy in Vehicular Cloud Network (VCN), whichutilizes deep neural network (DNN) and Multi-Grained CascadeForest (gcForest) to distinguish service behaviors. In [25], theauthors elaborate the potential use of the NFV service for theheterogeneous vehicles with many benefits. In [26], the authorpropose a theoretical framework to evaluate the performance ofa Long-Term Evolution (LTE) virtualized mobility managemententity (vMME) hosted in a data center. In [27], the authorsdiscuss the new trends of applying NFV in 5G network tomanage the wireless/mobile broadband (5G WMB).Distributed solutions become more and more important sincethe networks become denser and denser [28]–[30]. There areplenty of algorithms have been taken into consideration in thedistributed applications. In [31], distributed algorithms for bigdata applications are introduced. Game theory is widely used inresource allocation of distributed networks. In [32], the authorsanalyze the congestion mitigation problem in NFV for bothcentralized and distributed methods using game theory. A Stackelberg game is adopted as the approach to solve the resourcemanagement problem in LTE unlicensed in [33]. In [34], a hierarchical game approach is presented for generating optimal strategies of visible light communication and D2D heterogeneousnetwork in a distributed manner. Benders decomposition is firstproposed in [35] and it is well studied by many researchers. In[35], Benders decomposition is introduced in details. The marketrisk management problem is modeled as a stochastic linearcomplementarity problem in [36], and Benders decompositionis adapted to this equilibrium models. Benders decomposition issuitable for solving mixed integer programming. In [37], a jointbase station (BS) association and power control algorithm is proposed based on Benders decomposition. The size and schedule inmicrogrids operation are studied using Benders decompositionin [38]. However, most of the papers only provide centralizedsolutions for the mixed integer programming. In addition togame theory and Benders decomposition, ADMM is anotherpowerful decomposition tool. ADMM is useful for breakingconvex optimization problems into small parts to achieve distributed methods, which is elaborated in [39]. In [40], the revenuemaximization problem for mobile data offloading in SDN ishandled by ADMM. Multi-block ADMM is surveyed in [41]for big data optimization problems in the smart grid. In [42], theauthors investigate resource allocation in network virtualizationusing ADMM in both parallel and distributed fashions. Theoptimal large-scale scheduling of microgrids using ADMM isproposed in [43].Although much research has been done in literature, ourwork is distinctive. For solving the mixed-integer programmingproblem which is often formulated in the NFV resource allocation, we propose a novel algorithm framework. The frameworkis composed of Benders decomposition and ADMM. Bendersdecomposition is designed for decomposing the continuous andinteger problem. ADMM is introduced to give a distributedsolution for the continuous problem. Both sub-algorithms takeadvantage of dual information. By adopting the proposed framework, large-scale mixed-integer programming problems can besolved in a distributed manner. As an alternative to the other existing heuristic algorithms studied in the literature, our algorithmhas the remarkable performance, effectiveness, and universality.III. SYSTEM MODEL AND PROBLEM FORMULATIONA. System ModelWe consider a virtualization network with N VMs and Llinks, as shown in Fig. 2. In this paper, we assume that theVMs are already placed on certain physical machines, and theAuthorized licensed use limited to: University of Houston. Downloaded on December 14,2020 at 21:50:04 UTC from IEEE Xplore. Restrictions apply.

YU et al.: NETWORK FUNCTION VIRTUALIZATION RESOURCE ALLOCATION BASED ON JOINT BENDERS DECOMPOSITION AND ADMM1709B. Problem FormulationOur main interest is to minimize the cost of the powerconsumption for the network by VNF placement and resourceallocation. In this paper, we consider the cost can be dividedinto two part. One is VNF placement and the other is trafficexpenditure. We assume that the data flow for each virtual linkis lossless. In the previous work of other papers, the powerconsumption for implementing VNFs have been pointed out. Weassume that the cost for each VNF is various, and it is denoted asξkm for implementing one instance of fkm in the k th SFC. Thus,the total cost for VNF placement is formulated asQp Fig. 2.The model of the network.memk ξk ,(3)k 1input and output nodes are fixed. The VM placement problemcan be solved similarly, which is beyond the scope of thispaper. Each VM has the capacity to achieve a series of VNFs;however, the capacity is limited. For the nth VM, the capacityis presented as Cn . Moreover, each VNF can be implementedin different VMs at the same time, considering utilizing theresources flexibly. We denote that the VNF set for the network isF {f1 , . . . , fI }, and the VNF set for each VM is a subset of F.We also assume that each VM can only process one VNF at thesame time. The SDN controller and the NFV MANO are themain central processors, and they have different functions.The SDN controller determines the logic of the traffic and passesthe status information to the NFV MANO. The NFV MANO canbe divided into three part: the orchestrator, VNFs managers, andvirtualized infrastructure managers. The placement of the VNFand the optimization of the traffic path are accomplished by theNFV MANO.Service function chain (SFC) is defined as a set of VNFs in acertain order to achieve different services. We assume M SFCsare required to traverse through the network, and the VNF set form m fk F}. Inthe mth SFC is expressed as F m {f1m , . . . , fKaddition, each VNF requests a data rate requirement, denotingas Rk . During each SFC period, the network resource allocationorchestration is invariant. For each VNF, the input and outputdata rates may change because of the specific processing. Thus,we denote the input-output ratio of fk as μfk .The existence of VNF fkm for the nth VM is defined as abinary variable, which can be denote as 1, if fkm is implemented on VM n,mδn,k (1)0, otherwise.For the data flow of the SFC, there may have many paths for oneVNF to another. We define the number of the instances of fkm isemk , and it can be calculated asemk K N mδn,k.(2)n 1mthIn other words, emk is a variable depending on δn,k . For the kthmVNF of the m SFC, we define vn,k as the traffic volume.Another cost is produced by the traffic for each VNF, anddifferent types of VNF have different cost coefficients, denotingas γk for the k th VNF. We assume that the cost is depend linearlyon the traffic volume of VNF. Thus, the cost can be formulatedasQt K γkN m mδn,kvn,k .(4)n 1k 1Therefore, the total cost function isQtotal Qp Qt .(5)From above, we can formulate the problem asminδ m(l) vm,(l)Qtotals.t 1 (6)N mδn,k N k, m,(7)m mδn,kvn,k φk Cn n, m,(8)mvn,k Rk k,(9)n 1K k 1N n 1 Nn 1μ f k Nmvn,k 1n 1mvn,k k,m {0, 1} m, n, k.δn,k(10)(11)Here, (7) indicates that all the VNF in the SFC should exist inthe network; however, it should not be implemented on everyVM. (8) is the constraint for the VM’s capacity for holdingthe VNF set, and φk is the resource cost for the unit traffic ofVNF. (9) is the constraint for the requested traffic of each VNF.(10) indicates the previous VNF output cannot exceed the latterVNF’s traffic volume. Finally, (11) is the binary constraint.Although this problem can be solved in a centralized manner,the computation task for the controller is arduous as an NP-hardproblem. The controller must deal with the same sized integervariables and continuous variables. Thus, the decentralized algorithm is necessary. In the following section, we propose analgorithm based on joint Benders decomposition and ADMMAuthorized licensed use limited to: University of Houston. Downloaded on December 14,2020 at 21:50:04 UTC from IEEE Xplore. Restrictions apply.

1710IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 69, NO. 2, FEBRUARY 2020to solve the problem in a distributed manner to release thecomputational burden of the controller.IV. ALGORITHM BASED ON BENDERSDECOMPOSITION AND ADMMIn this section, we propose the joint Benders decompositionand ADMM based on the former content. Benders decomposition is popular for separating the mixed integer programminginto continuous subproblems and discrete master problem. Forthe continuous subproblems, we use ADMM to decouple theconstraints with associating all variables to generate a distributedsolution, which is necessary in the NFV network. However,ADMM is known for solving convex problems distributedly. Ifthe convexity of the problem cannot be satisfied, the convergenceand optimal solution are unreliable. Naturally, we use Bendersdecomposition as the outer loop and use ADMM as the innerloop to solve the subproblem. In the following, we introduceBenders decomposition and ADMM respectively, and show howto integrate them into an algorithm framework. The analysis andimplementation are also presented.A. Benders DecompositionThe problem we formulated is a MILP problem. To solvethe problem, we need to deal with the integer variable first.Benders decomposition is an efficient technique for dealingwith complicating variables (e.g., integer variables). We treatthe Benders decomposition algorithm as the outer loop for ouralgorithm.The principle of the Benders decomposition algorithm isseparating the continuous variable and integer variable andhandling them individually. There are two kinds of problems inthe algorithm, which are the master problem and the subproblem.The master problem aims to solve the pure integer programmingproblem or a small scale mixed integer programming problem.The subproblem is to solve problems only with continuousvariables. Benders decomposition is an iteration algorithm. Firstis the initialization of the problem. Next, the subproblem issolved by involving only continuous variables, because theinteger variables are fixed. Through solving the subproblem,the continuous variables solution and the dual variable solutionassociated with the constraints of fixing the integer variables’value are obtained. After that, the upper and lower bounds aregenerated using the solutions from solving the subproblem. Thedifference between the upper and lower bounds is used for thestopping criterion in the iterations. Then, the master problem issolved. The whole procedure of the algorithm to solve the NFVresource allocation problem is stated as follows.Initialization: Actually, the initialization is generated fromthe trivial solution of the master problem. First we assign loopmis a binarycounter l to 1. In our problem formulation δn,kmm 1 (upper bound) and Lδn,k 0 (lowervariable and Uδn,kbound). Because the coefficient of the corresponding part in them,(l)m .objective function is positive, we simply assign δn,k Lδn,kFurthermore, we introduce a function α as an optimal value ofthe subproblem. The initial value of α(l) is set as αdown , whichshould be determined by the certain circumstances.Subproblem: The subproblem is constructed by fixing thevalue of complicating variables to avoid them. Thus, the subm,(l)problem can be expressed as the problem (12). θn,k is the dualvariable for the constraints that fixing the binary variables’ value.The subproblem is deduced to a problem with only continuousvariables and it is often solved in a distributed manner.minQtm(12)vK s.tm mδn,kvn,k φk Cn n, m,(13)k 1N mvn,k Rk k,n 1 Nn 1μ f k Nmvn,k 1n 1m,(l)mδn,k δn,k(14)mvn,km,(l): θn,k k,(15) m, n, k.(16)In this paper, we adopt ADMM to solve the subproblem whichis illustrated in the next section. By solving the subproblem, wecan acquire vm(l) and θ m,(l) for the following steps.Convergence checking: The convergence checking is significant for the algorithm because it performs as the stoppingcriterion. The upper bound for the primal problem is calculatedasQlup Qltotal (δ m,(l) vm,(l) ).(17)Correspondingly, the lower bound can be generated byQldown Qlp (δ m,(l) ) α(l) .Thus, the stopping criterion is given by Qlup Qldown ε, stop,otherwise,continue,(18)(19)where ε is a pre-defined tolerance for the problem. Once theiteration stops, the optimal solution is obtained as δ m,(l) andvm,(l) .Master problem: The master problem is only related to thebinary variables. After update the loop counter l l 1, theproblem which need to solve is stated as followsminQp αm(20)δ αs.t 1 N mδn,k N k, m,(21)n 1 Qt vm,(j) θ m,(j) δ m δ m,(j) αj 1, . . . , l 1,K m mδn,kvn,k φk Cn n, m,(22)(23)k 1α αdown ,(24)mδn,k(25) {0, 1} m, n, k,Authorized licensed use limited to: University of Houston. Downloaded on December 14,2020 at 21:50:04 UTC from IEEE Xplore. Restrictions apply.

YU et al.: NETWORK FUNCTION VIRTUALIZATION RESOURCE ALLOCATION BASED ON JOINT BENDERS DECOMPOSITION AND ADMMAlgorithm 1: NFV Resource Allocation Based on :sequentiallyx[t 1] : arg minL(x, z[t], λ[t]),(28)z[t 1] : arg minL(x[t 1], z, λ[t]),(29)λ[t 1] : λ[t] ρ (Ax[t 1] Bz[t 1] c) .(30)x(l)m , Lδ m , αInitialize: loop index l, Uδn,kn,kllwhile Qup Qdown ε doSubproblemacquire vm(l) and θ m,(l) using ADMMBounds calculationcalculate upper and lower bound (Qlup andQldown )by (17) and (18)Master problemstep 1: update loop index l l 1step 2: add new Benders cut to the problem (20)step 3: solve the problem in (20) to obtain theoptimal value of δ m and αend whilewhere the constraint (22) is the Benders cuts associated with theformer iterations. In every iteration, the new benders cut willbe added to the constraints of the master problem. The Benderscuts compose l 1 hyperplanes to approximate the objectivefunction of the subproblem from below.After the master problem is solved, the algorithm goes to thenext iteration with solving the subproblem. The whole procedureof the algorithm is presented in the Algorithm 1.zThe iterations stop when a stopping criterion meets.For the proposed subproblem, we need to transform problem(12)–(16) into an equivalent problem. Among the constraints ofthe problem, we can find that (14) and (15) are constraints thatinvolve all the VMs. To generate a distributed algorithm, weintroduce an auxiliary variable asm umvn,kn,k n, k,N umn,k Rk k,μ fkN umn,k n 1N umn,k 1 0 k.(33)n 1Thus, the equivalent problem is formulated asminQtm(34)vK m mδn,kvn,k φk Cn n, m,(35)umn,k Rk k,(36)k 1N n 1μ fkN umn,k n 1N umn,k 1 0 k(37)n 1m,(l)mδn,k δn,km,(l): θn,k m, n, km umvn,kn,k n, k.(38)(39)The augmented Lagrangian function of the problem is givenbyLρ Q t min f (x) g(z)N K m λn,k vn,k umn,kn 1 k 1(26)The optimization problem has variables x and z with the equalityconstraint. The augmented Lagrangian function for the problemis expressed asL(x, z, λ) f (x) g(z) λT (Ax Bz c)ρ Ax Bz c 2 .2(32)n 1s.ts.t. Ax Bz c.(31)mwhere umn,k is a copy of the vn,k . Thus, the constraints in (9) and(10) can be reformulated asB. ADMMFor our designed continuous subproblem, ADMM is the mostsuitable algorithm. For example, dual decomposition is an efficient way to generate a distributed solution. However, it cannotdeal with the constraints coupling with different users. OCD(Optimal Condition Decomposition) is another popular methodin distributed computing. Unfortunately, our problem cannotsatisfy the strong convexity condition (linear programming),which will cause convergence problem. Many other distributedcomputing methods have strict requirements which are inappropriate for our subproblem. Thus, we adopt ADMM for solvingthe subproblem in a distributed manner. ADMM is a method tosolve the problem by decoupling the constraints and breaking itinto many small problems. For the problem with a general formstated as follows1711(27)The Lagrangian multiplier is denoting as λ and ρ is thepenalty parameter. The ADMM iterations proceed as followsρ m2 vn,k umn,k 2 ,2n 1K N(40)k 1where λn is the Lagrangian multiplier and ρ 0 is the penaltyparameter. For the tth iteration, the primal and dual variablesupdate as followu[t 1] arg minLρ (u, v[t], λ[t]),(41)v[t 1] arg minLρ (u[t 1], v, λ[t]),(42)λ[t 1] λ[t] ρ(u[t 1] v[t 1]).(43)Thus, the variables can update sequentially in iterations.Authorized licensed use limited to: University of Houston. Downloaded

trading mechanism in network virtualization are proposed and solved by the Stackelberg game. Most of the literature solved the problems using heuristic methods which cannot guarantee the global optimal. Nowadays, NFV/SDN architecture is popular for its flexi-bility. In [18], the software-defined and network virtualization