Research On Virtual Network Embedding Algorithm In Network Virtualization Environment

In foreseeable future,various and novel network services and applications will emerge.Due to the ossification of traditional Internet,demands of these emerging network services cannot be fulfilled.Network virtualization technology is introduced by both academia and industry so as to deal with the Internet ossification.In virtualization research,the key issue of efficiently mapping multiple heterogeneous virtual network services onto the whole underlying physical network demands to be solved.This issue is called as virtual network embedding in the literature.Owing to the fact that virtual network embedding contains multiple dimensions of resource constraints,the virtual network embedding problem is proved to be NP-hard.A survey of network virtualization technology,virtual network embedding problem and embedding algorithm is conducted in the first place.This doctoral dissertation conducts a detailed introduction of the origin,related technologies and business model of network virtualization.Then,this doctoral dissertation models the virtual network embedding problem carefully,in terms of underlying physical network,virtual network request,embedding function,embedding goal,performance metric and so on.A brief survey on existing embedding algorithms is conducted,too.According to their adopted optimization strategies,all existing embedding algorithms can be categorized into three main types: exact algorithm type,heuristic algorithm type,and meta-heuristic algorithm type.By researching the advantages and disadvantages of existing exact and meta-heuristic algorithms,this doctoral dissertation finds their existing problems and research bottlenecks.Since exact and meta-heuristic algorithms have the flaw of high computation complexity and heuristic algorithms can achieve virtual network embedding solution within polynomial time,it is of great research and application values to develop the heuristic algorithm.In addition,future network services are unpredictable,dynamic and variable.Hence,each proposed virtual network service is requested to be deployed and implemented as soon as possible.Based on above research backgrounds,this doctoral dissertation focuses on the research of heuristic algorithm.According to specific mapping goals,this doctoral dissertation proposes four different heuristic algorithms.The novelty of this doctoral dissertation concentrates on the following four isolated aspects:Firstly,this doctoral dissertation proposes one heuristic algorithm that is based on multiple network topology attributes and global network resources.Previous heuristic algorithms just consider single node topology attribute and local network resources,leading to the flaw of low virtual network service acceptance ratio.Topology attributes considered in this proposed heuristic algorithm are: node degree,node distance,node strength,node closeness,link strength,and link interference.Considered global network resources are: node capacity and link bandwidth.By quantifying these topology attributes and resources and adopting the Google page-ranking method,stable node ranking values can be achieved.Existing virtual network embedding studies indicate the fact that higher node ranking value,stronger node embedding ability.Therefore,the proposed heuristic algorithm can select the nodes having strong embedding abilities and coordinate the entire virtual network embedding.Simulation results reveal that the proposed heuristic algorithm performs better than previous heuristic algorithms,in terms of virtual network acceptance ratio,revenue to cost ratio,node capacity utilization,and link bandwidth utilization.Secondly,this doctoral dissertation proposes one energy efficient heuristic algorithm that enables to conduct the virtual network embedding among multiple inter-domain physical networks.Previous heuristic algorithms mostly focus on improving virtual network service acceptance ratio while ignoring the energy cost of underlying physical networks.In addition,proposed energy saving algorithms in the literature just consider conducting the virtual network embedding in one single physical network.By analyzing the energy cost of different network elements and electricity price in different regions,the reasonable energy cost model for virtual network embedding is firstly formulated.The doctoral dissertation then proposes the energy saving algorithm for multiple inter-domain physical networks.The proposed energy saving algorithm not only includes network topology and energy related attributes,but also adopting the consolidation method.The goal of this energy saving algorithm is to minimize the energy cost for virtual network embedding while ensuring the virtual network service acceptance ratio high.Simulation results show that the proposed energy saving algorithm outperform existing energy related algorithms.Extra energy cost can be saved while conducting the virtual network embedding among multiple inter-domain physical networks.Thirdly,a dynamic and adjustment heuristic algorithm is proposed,aiming at dynamically adjusting certain mapped virtual network elements and optimizing initial virtual network embedding results.Exiting heuristic algorithms are static and simply focus on fulfilling virtual resource demands.Once mapped,no virtual network element can be adjusted,leading to the problem of virtual network Qo S performance not guaranteed.The proposed algorithm consists of two sub-algorithms: multiple topology attributes and global resources sub-algorithm and dynamically adjustment sub-algorithm.While the initial mapping of the virtual network is completed,the proposed algorithm will check the embedding results.If the Qo S metric of certain virtual element is not guaranteed,the proposed algorithm will start to adjust the initial results.The adjustment is done until all virtual resource and Qo S demands are fulfilled.Simulation results reveal that the proposed algorithm performs better than the dynamic algorithms,in terms of long-term virtual network service acceptance ratio,underlying physical resource utilization and virtual network Qo S performance.At last,the issue of how to conduct the customized mapping of virtual network,having its own specific topology and resource demands,is well worthy further research.All existing virtual network embedding algorithms adopt the ‘one fits all' scheme to serve requested virtual network services.These algorithms will lead to poor embedding quality and low physical network resource utilization.The doctoral dissertation creatively proposes one customized service oriented heuristic mapping algorithm.When certain end user requests one virtual network service,the proposed algorithm adopt the category sub-algorithm in order to determine the type of the virtual network service.This virtual network service may be the delay priority type,the resource priority type or the ordinary type.After completing the virtual network classification,the proposed algorithm will select the proper mapping sub-algorithm to conduct the virtual network embedding and resource allocation.Simulation results show that the proposed customized service oriented algorithms outperforms existing heuristic algorithms,in terms of the long-term virtual network service acceptance ratio,and physical resource utilization.