Please wait a minute...
Front. Inform. Technol. Electron. Eng.  2013, Vol. 14 Issue (12): 899-908    DOI: 10.1631/jzus.C1300120
    
A virtual network mapping algorithm based on integer programming
Bo Lu, Jian-ya Chen, Hong-yan Cui, Tao Huang, Yun-jie Liu
Beijing Key Laboratory of Network System Architecture and Convergence, Beijing University of Posts and Telecommunications, Beijing 100876, China
Download:   PDF(0KB)
Export: BibTeX | EndNote (RIS)      

Abstract  The virtual network (VN) embedding/mapping problem is recognized as an essential question of network virtualization. The VN embedding problem is a major challenge in this field. Its target is to efficiently map the virtual nodes and virtual links onto the substrate network resources. Previous research focused on designing heuristic-based algorithms or attempting two-stage solutions by solving node mapping in the first stage and link mapping in the second stage. In this study, we propose a new VN embedding algorithm based on integer programming. We build a model of an augmented substrate graph, and formulate the VN embedding problem as an integer program with an objective function and some constraints. A factor of topology-awareness is added to the objective function. The VN embedding problem is solved in one stage. Simulation results show that our algorithm greatly enhances the acceptance ratio, and increases the revenue/cost (R/C) ratio and the revenue while decreasing the cost of the VN embedding problem.

Key wordsVirtual network embedding      Integer programming      Topology-awareness      Network virtualization     
Received: 05 May 2013      Published: 06 December 2013
CLC:  TP393  
Cite this article:

Bo Lu, Jian-ya Chen, Hong-yan Cui, Tao Huang, Yun-jie Liu. A virtual network mapping algorithm based on integer programming. Front. Inform. Technol. Electron. Eng., 2013, 14(12): 899-908.

URL:

http://www.zjujournals.com/xueshu/fitee/10.1631/jzus.C1300120     OR     http://www.zjujournals.com/xueshu/fitee/Y2013/V14/I12/899


A virtual network mapping algorithm based on integer programming

The virtual network (VN) embedding/mapping problem is recognized as an essential question of network virtualization. The VN embedding problem is a major challenge in this field. Its target is to efficiently map the virtual nodes and virtual links onto the substrate network resources. Previous research focused on designing heuristic-based algorithms or attempting two-stage solutions by solving node mapping in the first stage and link mapping in the second stage. In this study, we propose a new VN embedding algorithm based on integer programming. We build a model of an augmented substrate graph, and formulate the VN embedding problem as an integer program with an objective function and some constraints. A factor of topology-awareness is added to the objective function. The VN embedding problem is solved in one stage. Simulation results show that our algorithm greatly enhances the acceptance ratio, and increases the revenue/cost (R/C) ratio and the revenue while decreasing the cost of the VN embedding problem.

关键词: Virtual network embedding,  Integer programming,  Topology-awareness,  Network virtualization 
[1] Shui-qing Gong, Jing Chen , Qiao-yan Kang, Qing-wei Meng, Qing-chao Zhu , Si-yi Zhao. An efficient and coordinated mapping algorithm in virtualized SDN networks[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(7): 701-716.
[2] Jian Ding, Tao Huang, Jiang Liu, Yun-jie Liu. Virtual network embedding based on real-time topological attributes[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(2): 109-118.
[3] Qing-long Dai, Guo-chu Shou, Yi-hong Hu, Zhi-gang Guo. Performance improvement for applying network virtualization in fiber-wireless (FiWi) access networks[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(11): 1058-1070.
[4] Xiao-ling Li, Huai-min Wang, Chang-guo Guo, Bo Ding, Xiao-yong Li, Wen-qi Bi, Shuang Tan. Topology awareness algorithm for virtual network mapping[J]. Front. Inform. Technol. Electron. Eng., 2012, 13(3): 178-186.
[5] Jiang Liu, Tao Huang, Jian-ya Chen, Yun-jie Liu. A new algorithm based on the proximity principle for the virtual network embedding problem[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(11): 910-918.