Please wait a minute...
FITEE
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
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
 全文: PDF 
摘要： 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    
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 words: Virtual network embedding    Integer programming    Topology-awareness    Network virtualization
收稿日期: 2013-05-05 出版日期: 2013-12-06
CLC:  TP393  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Bo Lu
Jian-ya Chen
Hong-yan Cui
Tao Huang
Yun-jie Liu

引用本文:

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.

链接本文:

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

[1] 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.
[2] 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.