A virtual network mapping algorithm based on integer programming

Bo LU; Jian-ya CHEN; Hong-yan CUI; Tao HUANG; Yun-jie LIU

doi:10.1631/jzus.C1300120

Your Location：

Home >

Browse articles >

A virtual network mapping algorithm based on integer programming

计算机工程 | Updated：2022-05-19

- A virtual network mapping algorithm based on integer programming
- A virtual network mapping algorithm based on integer programming
- 信息与电子工程前沿（英文） 2013年14卷第12期页码：899-908
- Affiliations：
  
  Beijing Key Laboratory of Network System Architecture and Convergence, Beijing University of Posts and Telecommunications, Beijing 100876, China
- Author bio：
  
  [ "Bo LU, E-mail: billylu@bupt.edu.cn" ]
  Jian-ya CHEN, E-mail:jychen@bupt.edu.cn
- Funds：
  
  Project supported by the National Basic Research Program (973) of China (Nos. 2011CB302901 and 2012CB315801) and Fundamental Research Funds for the Central Universities, China (No. 2011RC0118)
- DOI：10.1631/jzus.C1300120
  中图分类号： TP393
- 收稿：2013-05-05，
  
  修回：2013-11-18，
  
  纸质出版：2013-12
- Accepted：
Scan QR Code
A virtual network mapping algorithm based on integer programming[J]. 信息与电子工程前沿（英文）, 2013,14(12):899-908.

Bo LU, Jian-ya CHEN, Hong-yan CUI, et al. A virtual network mapping algorithm based on integer programming[J]. Frontiers of Information Technology & Electronic Engineering, 2013, 14(12): 899-908.
A virtual network mapping algorithm based on integer programming[J]. 信息与电子工程前沿（英文）, 2013,14(12):899-908. DOI： 10.1631/jzus.C1300120.

Bo LU, Jian-ya CHEN, Hong-yan CUI, et al. A virtual network mapping algorithm based on integer programming[J]. Frontiers of Information Technology & Electronic Engineering, 2013, 14(12): 899-908. DOI： 10.1631/jzus.C1300120.

摘要

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 (

) ratio and the revenue while decreasing the cost of the VN embedding problem.

关键词

Keywords

references

T. Anderson , , , L. Peterson , , , S. Shenker , , , J. Turner . . Overcoming the Internet impasse through virtualization . . Computer , , 2005 . . 38 ( ( 4 ): ): 34 - - 41 . . DOI: 10.1109/MC.2005.136 http://doi.org/10.1109/MC.2005.136 . .

N.F. Butt , , , M. Chowdhury , , , R. Boutaba . . Topology- awareness and reoptimization mechanism for virtual network embedding . . Networking , , 2010 . . 6091 27 - - 39 . . . .

N.M.M.K. Chowdhury , , , R. Boutaba . . A survey of network virtualization . . Comput. Netw. , , 2010 . . 54 ( ( 5 ): ): 862 - - 876 . . DOI: 10.1016/j.comnet.2009.10.017 http://doi.org/10.1016/j.comnet.2009.10.017 . .

N.M.M.K. Chowdhury , , , M.R. Rahman , , , R. Boutaba . . Virtual Network Embedding with Coordinated Node and Link Mapping . . IEEE INFOCOM , , 2009 . . p.783 - - 791 . . DOI: 10.1109/INFCOM.2009.5061987 http://doi.org/10.1109/INFCOM.2009.5061987 . .

N. Feamster , , , L.X. Gao , , , J. Rexford . . How to lease the Internet in your spare time . . ACM SIGCOMM Comput. Commun. Rev. , , 2007 . . 37 ( ( 1 ): ): 61 - - 64 . . DOI: 10.1145/1198255.1198265 http://doi.org/10.1145/1198255.1198265 . .

A. Fischer , , , J.F. Botero , , , M. Duelli , , , D. Schlosser , , , X. Hesselbach , , , H. de Meer . . ALEVIN—a framework to develop, compare, and analyze virtual network embedding algorithms . . Electron. Commun. EASST , , 2011 . . 37 1 - - 12 . . . .

J. Liu , , , T. Huang , , , J.Y. Chen , , , Y.J. Liu . . A new algorithm based on the proximity principle for the virtual network embedding problem . . J. Zhejiang Univ.-Sci. C (Comput. & Electron.) , , 2011 . . 12 ( ( 11 ): ): 910 - - 918 . . DOI: 10.1631/jzus.C1100003 http://doi.org/10.1631/jzus.C1100003 . .

A. Schrijver . . Theory of Integer and Linear Programming . . John Wiley & Sons, NewYork, USA. , , 1986 . . .

A.J. Wang , , , M. Iyer , , , R. Dutta , , , G.N. Rouskas , , , I. Baldine . . Network virtualization: technologies, perspectives, and frontiers . . J. Lightwave Technol. , , 2013 . . 31 ( ( 4 ): ): 523 - - 537 . . . .

M.L. Yu , , , Y. Yi , , , J. Rexford , , , M. Chiang . . Rethinking virtual network embedding: substrate support for path splitting and migration . . ACM SIGCOMM Comput. Commun. Rev. , , 2008 . . 38 ( ( 2 ): ): 17 - - 29 . . DOI: 10.1145/1355734.1355737 http://doi.org/10.1145/1355734.1355737 . .

E.W. Zegura , , , K.L. Calvert , , , S. Bhattacharjee . . How to Model an Internetwork . . IEEE INFOCOM , , 1996 . . p.594 - - 602 . . . .

D. Zhang . . A Study on Virtual Network Decomposing Mapping Algorithm Based on Network Balance . . 4th Int. Conf. on Computational and Information Sciences , , 2012 . . p.880 - - 883 . . DOI: 10.1109/ICCIS.2012.55 http://doi.org/10.1109/ICCIS.2012.55 . .

M. Zhang , , , C.M. Wu , , , Y. Hang , , , Q. Yang , , , B. Wang , , , M. Jiang . . Robust dynamical virtual network provisioning . . Chin. J. Electron. , , 2013 . . 22 ( ( 1 ): ): 151 - - 154 . . . .

Y. Zhu , , , M.H. Ammar . . Algorithms for Assigning Substrate Network Resources to Virtual Network Components . . IEEE INFOCOM , , 2006 . . p.1 - - 12 . . DOI: 10.1109/INFOCOM.2006.322 http://doi.org/10.1109/INFOCOM.2006.322 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

Topology awareness algorithm for virtual network mapping

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