Traffic Engineering Theory And Algorithms In Software-Defined Mobile Networks

It is envisaged in future mobile networks that the network should support diverse ser-vices with various requirements on high data rates,low latency,seamless coverage,and dense connectivity,etc.To this end,network slicing is put forward to create multiple cus-tomized logical networks for individual services,achieving a flexible and cost-efficient software-defined mobile network?SDMN?.Meanwhile,SDMN can adopt traffic engi-neering?TE?to improve its efficiency and elasticity,by planning network slice's capacity at large time-scale and explicitly regulating flow routing and bandwidth allocation at small time-scale respectively.Although TE has been widely adopted by the Internet and mobile networks,driven by diverse service requirements and enabled by the novel architecture of SDMN,a new paradigm should be established for TE,i.e.,new techniques and solutions are essential.Based on SDN techniques,TE can function via a logically centralized con-troller with its global network view and control capability to further improve the efficiency of the network.Meanwhile,traditional TE methods can be extended to optimize the allo-cation of bandwidth and processing resources for network slices.Nevertheless,there are still many challenges for applying TE to SDMN,such as the complexity of algorithms,the resource allocation mechanisms for co-existing network slices,and the reconfigura-tion of slices,etc.This dissertation mainly studying the incorporating of TE with SDMN by trying to address the aforementioned challenges.First,this dissertation investigates the algorithms of link resource allocation for flows in core and backhaul networks.With the Ideal Flow to Data-Gateway Association?IFDA?strategy?IFDA-TE?,this dissertation designs an improved Fully Polynomial Time Ap-proximation Scheme?i-FPTAS?,to reduce the complexity of solving the multi-commodity flow problem that aims at network load balancing.In order to reduce the cooperation overhead between D-GWs,this dissertation further considers two strategies that associate BSs/flows to D-GWs,formulates the corresponding MBODA-TE and MFODA-TE prob-lems as Mixed Integer Programs?MIP?,and proposes efficient algorithms to solve them.The performance of MFODA-TE is very close to that of the IFDA-TE which does not limit the D-GW association,so that high resource utilization can be guaranteed.Though MBODA-TE has small performance degradation,its high computational efficiency makes it applicable for the resource allocation of large-scale networks.Second,this dissertation investigates the network slice dimensioning problem based on TE methods.This dissertation extends traditional TE problems to achieve network load balancing by optimizing the allocation of both link bandwidth and node processing re-sources.Considering that in SDMN,Network Slice Provider?NSP?and service providers?i.e.,Network Slice Customers,NSCs?are independent and pursue the maximization of their respective profit,slices should be dimensioned according to the resource availability and the economic mechanism in the network,so as to optimize the resource utilization and improve the profit of NSP/NSCs.Therefore,this dissertation study slice dimension-ing with resource pricing as a pricing game,so as to optimize the capacity of slices that are built on un-ordered Service Function Chain?SFC?and serve elastic traffic.This disserta-tion analyzes the optimal price in a simple scenario,while a closed form solution of the optimal price cannot be obtained for complex networks.Hence,this dissertation proposes a usage-based resource pricing algorithm to achieve network load balancing and obtain near-optimal social welfare with profit guarantee for NSP/NSCs.Practical deployment of network slices usually requires that the SFC has a fixed pro-cessing sequence,and flows should avoid being split at forwarding nodes so as to reduce the VNF coordination cost.In order to improve the applicability of our proposed slice di-mensioning scheme,this dissertation investigates the dimensioning of network slices with ordered SFCs.Concerning the ordered SFC,flows are broken down into segments by re-quired network functions?NFs?so that the processing order of NFs conforms to the service logic.In order to dimensioning slices,this dissertation proposes a resource pricing algo-rithm by analyzing the dual problem,which strikes a good trade-off between maximizing NSP's profit and optimizing other metrics including the resource utilization.Finally,considering the influence of reconfiguration on performance and resource consumption in network slicing,this dissertation investigates the reconfiguration of flow resource allocation and slice capacity.To maintain satisfactory user experience and high profit for service providers in a dynamic environment,a slice may need to be reconfig-ured timely according to the varying traffic demand and resource availability.However,frequent reconfigurations incur a certain cost and might cause service interruption.There-fore,this dissertation proposes a Hybrid Slice Reconfiguration?HSR?scheme,where a Fast Slice Reconfiguration?FSR?method reconfigures flows for individual slices at the time scale of flow arrival/departure,while a Dimensioning Slices with Reconfiguration?DSR?method is occasionally performed to adjust allocated resources according to the time-varying traffic demand.In order to maximize the slice's profit,this dissertation for-mulates the problems for FSR and DSR,which are difficult to solve due to the discon-tinuity and non-convexity of the reconfiguration cost function.Hence,this dissertation approximates the reconfiguration cost function with the L₁ norm,which preserves the sparsity of the solution,thus facilitating restricting reconfigurations.This dissertation de-signs an algorithm to schedule FSR and DSR so that DSR is timely triggered according to the traffic dynamics and resource availability to improve the profit of slice.Further-more,this dissertation extends the HSR scheme with a resource reservation?HSR-RSV?mechanism,which reserves partial resources for near future traffic to reduce potential re-configurations.Therefore,the proposed slice reconfiguration framework is effective in achieving high profits for slices and reducing reconfiguration overhead so as to obtain better service quality.Confronted with the rapid growth of traffic demand and diversification of services in future mobile networks,this dissertation analyzes,models,and extends the traffic engi-neering problems in SDMN.Exploiting pricing mechanism in micro-economics and con-vex optimization theory,this dissertation proposes highly efficient algorithms for flow re-source allocation,network slice capacity dimensioning and reconfiguration in large-scale networks,which help to fully exploit the benefits of SDMN and network slicing.