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

Computer Engineering | Updated：2022-05-19

- A virtual network mapping algorithm based on integer programming
- A virtual network mapping algorithm based on integer programming
- Frontiers of Information Technology & Electronic Engineering Vol. 14, Issue 12, Pages: 899-908(2013)
- 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：
- DOI：10.1631/jzus.C1300120
  CLC： TP393
- Received：05 May 2013，
  
  Revised：2013-11-18，
  
  Published：2013-12
- Accepted：
Scan QR Code
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：

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 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Topology awareness algorithm for virtual network mapping

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

Related Author

Xiao-ling LI

Huai-min WANG

Chang-guo GUO

Bo DING

Xiao-yong LI

Wen-qi BI

Shuang TAN

Jiang LIU

Related Institution

National Key Laboratory of Parallel and Distributed Processing, National University of Defense Technology

School of Computer, National University of Defense Technology

China Electronic Systems Engineering Corporation

The Northern Institute of Electronic Equipment of China

Key Laboratory of Universal Wireless Communications of Ministry of Education, Beijing University of Post and Telecommunications

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰