Heuristic Solutions of Virtual Network Embedding： A Survey  

作　　者：Haotong Cao Han Hu Zhicheng Qu Longxiang Yang 

机构地区：[1]College of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China [2]College of lntemet of Things, Nanjing University of Posts and Telecommunications, Nanjing 210003, China [3]Jiangsu Key Laboratory of Wireless Communications, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

出　　处：《China Communications》2018年第3期186-219,共34页中国通信（英文版）

基　　金：supported by the National Natural Science Foundation of China under Grants 61372124 and 61401225;the National Science Foundation of Jiangsu Province under Grant BK20140894;the Postgraduate Research&Practice Innovation Program of Jiangsu Province under Grant KYCX17_0784

摘　　要：Network virtualization(NV) is considered as an enabling tool to remove the gradual ossification of current Internet. In the network virtualization environment, a set of heterogeneous virtual networks(VNs), isolated from each other, share the underlying resources of one or multiple substrate networks(SNs) according to the resource allocation strategy. This kind of resource allocation strategy is commonly known as so called Virtual Network Embedding(VNE) algorithm in network virtualization. Owing to the common sense that VNE problem is NP-hard in nature, most of VNE algorithms proposed in the literature are heuristic. This paper surveys and analyzes a number of representative heuristic solutions in the literature. Apart from the analysis of representative heuristic solutions, a taxonomy of the heuristic solutions is also presented in the form of table. Future research directions of VNE, especially for the heuristics, are emphasized and highlighted at the end of this survey.Network virtualization（NV） is considered as an enabling tool to remove the gradual ossification of current Internet. In the network virtualization environment, a set of heterogeneous virtual networks（VNs）, isolated from each other, share the underlying resources of one or multiple substrate networks（SNs） according to the resource allocation strategy. This kind of resource allocation strategy is commonly known as so called Virtual Network Embedding（VNE） algorithm in network virtualization. Owing to the common sense that VNE problem is NP-hard in nature, most of VNE algorithms proposed in the literature are heuristic. This paper surveys and analyzes a number of representative heuristic solutions in the literature. Apart from the analysis of representative heuristic solutions, a taxonomy of the heuristic solutions is also presented in the form of table. Future research directions of VNE, especially for the heuristics, are emphasized and highlighted at the end of this survey.

关 键 词：network virtualization virtual net-work embedding NP-HARD heuristic solution 

分 类 号：TP393.01[自动化与计算机技术—计算机应用技术]