An Exact Virtual Network Embedding Algorithm Based on Integer Linear Programming for Virtual Network Request with Location Constraint  

作　　者：Zeheng Yang Yongan Guo 

机构地区：[1]School of Computer Science and Engineering, University of Electronic Science and Technology of China(UESTC) [2]College of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications

出　　处：《China Communications》2016年第8期177-183,共7页中国通信（英文版）

基　　金：supported by the National Basic Research Program of China(973 Program)under Grant 2013CB329005

摘　　要：Network virtualization is known as a promising technology to tackle the ossification of current Internet and will play an important role in the future network area. Virtual network embedding(VNE) is a key issue in network virtualization. VNE is NP-hard and former VNE algorithms are mostly heuristic in the literature.VNE exact algorithms have been developed in recent years. However, the constraints of exact VNE are only node capacity and link bandwidth.Based on these, this paper presents an exact VNE algorithm, ILP-LC, which is based on Integer Linear Programming(ILP), for embedding virtual network request with location constraints. This novel algorithm is aiming at mapping virtual network request(VNR) successfully as many as possible and consuming less substrate resources.The topology of each VNR is randomly generated by Waxman model. Simulation results show that the proposed ILP-LC algorithm outperforms the typical heuristic algorithms in terms of the VNR acceptance ratio, at least 15%.Network virtualization is known as a promising technology to tackle the ossification of current Internet and will play an important role in the future network area. Virtual network embedding（VNE） is a key issue in network virtualization. VNE is NP-hard and former VNE algorithms are mostly heuristic in the literature. VNE exact algorithms have been developed in recent years. However, the constraints of exact VNE are only node capacity and link bandwidth. Based on these, this paper presents an exact VNE algorithm, ILP-LC, which is based on Integer Linear Programming（ILP）, for embedding virtual network request with location constraints. This novel algorithm is aiming at mapping virtual network request（VNR） successfully as many as possible and consuming less substrate resources. The topology of each VNR is randomly generated by Waxman model. Simulation results show that the proposed ILP-LC algorithm outperforms the typical heuristic algorithms in terms of the VNR acceptance ratio, at least 15%.

关 键 词：network virtualization virtual network embedding exact VNE algorithm integer linear Programming location constraint VNR acceptance ratio 

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