Please wait a minute...
Front. Inform. Technol. Electron. Eng.  2011, Vol. 12 Issue (11): 910-918    DOI: 10.1631/jzus.C1100003
    
A new algorithm based on the proximity principle for the virtual network embedding problem
Jiang Liu, Tao Huang*, Jian-ya Chen, Yun-jie Liu
Key Laboratory of Universal Wireless Communications of Ministry of Education, Beijing University of Post and Telecommunications, Beijing 100876, China
Download:   PDF(700KB)
Export: BibTeX | EndNote (RIS)      

Abstract  The virtual network embedding/mapping problem is a core issue of network virtualization. It is concerned mainly with how to map virtual network requests to the substrate network efficiently. There are two steps in this problem: node mapping and link mapping. Current studies mainly focus on developing heuristic algorithms, since both steps are computationally intractable. In this paper, we propose a new algorithm based on the proximity principle, which considers the distance factor besides the capacity factor in the node mapping step. Thus, the two steps of the embedding problem can be better integrated and the substrate network resource can be used more efficiently. Simulation results show that the new algorithm greatly enhances the performance of the revenue/cost (R/C) ratio, acceptance ratio, and runtime of the embedding problem.

Key wordsVirtual network embedding      Proximity      Revenue/cost (R/C) ratio      Acceptance ratio      Runtime     
Received: 01 January 2011      Published: 04 November 2011
CLC:  TP393  
Cite this article:

Jiang Liu, Tao Huang, Jian-ya Chen, Yun-jie Liu. A new algorithm based on the proximity principle for the virtual network embedding problem. Front. Inform. Technol. Electron. Eng., 2011, 12(11): 910-918.

URL:

http://www.zjujournals.com/xueshu/fitee/10.1631/jzus.C1100003     OR     http://www.zjujournals.com/xueshu/fitee/Y2011/V12/I11/910


A new algorithm based on the proximity principle for the virtual network embedding problem

The virtual network embedding/mapping problem is a core issue of network virtualization. It is concerned mainly with how to map virtual network requests to the substrate network efficiently. There are two steps in this problem: node mapping and link mapping. Current studies mainly focus on developing heuristic algorithms, since both steps are computationally intractable. In this paper, we propose a new algorithm based on the proximity principle, which considers the distance factor besides the capacity factor in the node mapping step. Thus, the two steps of the embedding problem can be better integrated and the substrate network resource can be used more efficiently. Simulation results show that the new algorithm greatly enhances the performance of the revenue/cost (R/C) ratio, acceptance ratio, and runtime of the embedding problem.

关键词: Virtual network embedding,  Proximity,  Revenue/cost (R/C) ratio,  Acceptance ratio,  Runtime 
[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] Kai-sheng Luo, Zheng Shi, Xiao-lang Yan, Zhen Geng. SVM based layout retargeting for fast and regularized inverse lithography[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(5): 390-400.
[4] Bo Lu, Jian-ya Chen, Hong-yan Cui, Tao Huang, Yun-jie Liu. A virtual network mapping algorithm based on integer programming[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(12): 899-908.
[5] 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.
[6] Bin Lin, Xiao-lang Yan, Zheng Shi, Yi-wei Yang. A sparse matrix model-based optical proximity correction algorithm with model-based mapping between segments and control sites[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(5): 436-442.