JZUS - Journal of Zhejiang University SCIENCE

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

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.

Reference

[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

<1>

Similar articles

- Go to

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

Reference