Full Text:   <1855>

CLC number: TP393

On-line Access: 2013-12-06

Received: 2013-05-05

Revision Accepted: 2013-08-30

Crosschecked: 2013-11-18

Cited: 2

Clicked: 2777

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2013 Vol.14 No.12 P.899-908


A virtual network mapping algorithm based on integer programming

Author(s):  Bo Lu, Jian-ya Chen, Hong-yan Cui, Tao Huang, Yun-jie Liu

Affiliation(s):  Beijing Key Laboratory of Network System Architecture and Convergence, Beijing University of Posts and Telecommunications, Beijing 100876, China

Corresponding email(s):   billylu@bupt.edu.cn, jychen@bupt.edu.cn

Key Words:  Virtual network embedding, Integer programming, Topology-awareness, Network virtualization

Share this article to: More |Next Article >>>

Bo Lu, Jian-ya Chen, Hong-yan Cui, Tao Huang, Yun-jie Liu. A virtual network mapping algorithm based on integer programming[J]. Journal of Zhejiang University Science C, 2013, 14(12): 899-908.

@article{title="A virtual network mapping algorithm based on integer programming",
author="Bo Lu, Jian-ya Chen, Hong-yan Cui, Tao Huang, Yun-jie Liu",
journal="Journal of Zhejiang University Science C",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T A virtual network mapping algorithm based on integer programming
%A Bo Lu
%A Jian-ya Chen
%A Hong-yan Cui
%A Tao Huang
%A Yun-jie Liu
%J Journal of Zhejiang University SCIENCE C
%V 14
%N 12
%P 899-908
%@ 1869-1951
%D 2013
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1300120

T1 - A virtual network mapping algorithm based on integer programming
A1 - Bo Lu
A1 - Jian-ya Chen
A1 - Hong-yan Cui
A1 - Tao Huang
A1 - Yun-jie Liu
J0 - Journal of Zhejiang University Science C
VL - 14
IS - 12
SP - 899
EP - 908
%@ 1869-1951
Y1 - 2013
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1300120

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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Anderson, T., Peterson, L., Shenker, S., Turner, J., 2005. Overcoming the Internet impasse through virtualization. Computer, 38(4):34-41.

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

[3]Chowdhury, N.M.M.K., Boutaba, R., 2010. A survey of network virtualization. Comput. Netw., 54(5):862-876.

[4]Chowdhury, N.M.M.K., Rahman, M.R., Boutaba, R., 2009. Virtual Network Embedding with Coordinated Node and Link Mapping. IEEE INFOCOM, p.783-791.

[5]Feamster, N., Gao, L.X., Rexford, J., 2007. How to lease the Internet in your spare time. ACM SIGCOMM Comput. Commun. Rev., 37(1):61-64.

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

[7]Liu, J., Huang, T., Chen, J.Y., Liu, Y.J., 2011. A new algorithm based on the proximity principle for the virtual network embedding problem. J. Zhejiang Univ.-Sci. C (Comput. & Electron.), 12(11):910-918.

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

[9]Wang, A.J., Iyer, M., Dutta, R., Rouskas, G.N., Baldine, I., 2013. Network virtualization: technologies, perspectives, and frontiers. J. Lightwave Technol., 31(4):523-537. [10.1109/JLT.2012. 2213796]

[10]Yu, M.L., Yi, Y., Rexford, J., Chiang, M., 2008. Rethinking virtual network embedding: substrate support for path splitting and migration. ACM SIGCOMM Comput. Commun. Rev., 38(2):17-29.

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

[12]Zhang, D., 2012. A Study on Virtual Network Decomposing Mapping Algorithm Based on Network Balance. 4th Int. Conf. on Computational and Information Sciences, p.880-883.

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

[14]Zhu, Y., Ammar, M.H., 2006. Algorithms for Assigning Substrate Network Resources to Virtual Network Components. IEEE INFOCOM, p.1-12.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE