Optimal Embedding Of Hybrid SFC With DAG Abstraction

Currently,the quick creation of new network applications and the booming request of network bandwidth bring critical challenges to the development of the Internet.To satisfy the different requests of transmission performance of the different network applications,different network functions need to be deployed in the network.However,the traditional deployment of network functions is difficult for maintenance and is very expensive.Network Function Virtualization(NFV)is an emerging technology,which enables service agility,flexibility and cost reduction by replacing traditional hardware middleboxes with Virtual Network Functions(VNFs)running on general-purpose servers.Service Function Chain(SFC)constitutes an end-to-end service by organizing a series of VNFs in a specific order.Particularly,hybrid SFC(SFC with parallel VNFs)is proposed to much reduce the traffic delay in sequential SFCs.Nevertheless,how to strategically select VNF instances and links in hybrid SFC embedding remains an open problem.In this paper,we firstly survey the prior work on optimal SFC embedding problem under NFV scenario,then,we target at the cost minimization and address the optimal hybrid SFC embedding problem.We focus on the Optimal Singal Hybrid SFC Embedding Problem(OSHE),which means how to minimize the total cost when embedding a hybrid SFC without exceeding the capacity constraints over a given priced cloud network.Firstly,we develop a novel abstraction model for the hybrid SFC with Directed Acyclic Graph(DAG),which helps convert diverse hybrid SFCs to the standardized DAG-SFC form.Then,we formulate the optimal DAG-SFC embedding problem as an integer optimization model and propose a greedy method(called BBE)to solve the NP-hard problem.MBBE method is developed upon BBE method to further cut down the computation complexity in model solving.Extensive simulation results demonstrate the effectiveness of our approach for cost reduction in hybrid SFC embedding and that MBBE can reduce the complexity of BBE without an apparent performance degradation.We focus on the Online Optimal Multiple Hybrid SFC Embedding Problem(Online OMHE),which means how to minimize the total cost of embedding multiple hybrid SFC in real time,without exceeding the resource capacity over a target priced cloud network.Firstly,we formulate the OMHE problem as an integer optimization model,and illustrate it's an NP-hard problem.Then,we propose the DS-Box architecture based on pre-computing to solve the online OMHE problem.We introduce the main modules of DS-Box,and illustrate the operating mechanism between and within the medules.We evaluate the performance of DSBox in multiple aspects by extensive simulation.The results demonstrate the effectiveness of DS-Box and it can support real time response.Moreover,DS-Box can balance the utilization between network resources,which can ensure the stability of the whole network when embedding multiple SFCs.In a word,this thesis focus more on cost minimization problem of embedding single(multiple)hybrid SFC(s).To the best of our knowledge,this paper is the first work which exploits the optimal hybrid SFC embedding problem under the cloud network scenario.