SCIENCE CHINA Information Sciences, Volume 60, Issue 4: 040308(2017) https://doi.org/10.1007/s11432-016-9015-3

A model for virtual network embedding across multiple infrastructure providers using genetic algorithm

More info
  • ReceivedAug 1, 2016
  • AcceptedJan 18, 2017
  • PublishedMar 20, 2017


Network virtualization is an important aspect in cloud computing, where network is assumed to be consisting of infinite amount of nodes and links. The substrate network (physical network), has limited capacity and so virtual network embedding on the substrate network becomes a problem. Virtual network embedding is a computationally hard problem, considering various constraints on nodes and links. The proposed work applies Genetic Algorithm for the virtual network embedding problem for mapping multiple virtual network requests on infrastructure providers managing multiple substrate networks. Performance evaluation, through simulations, indicates that the proposed model preforms better for the performance metrics such as infrastructure provider revenue, acceptance ratio and node and link utilization in comparison to few other contemporary mapping models.



This work was supported by UGC-UPEII, New Delhi. Also, authors accord their sincere thanks to the anonymous reviewers for the useful suggestions.


[1] Anderson T, Peterson L, Shenker S, et al. Overcoming the Internet impasse through virtualization. Computer, 2005, 38: 34-41 Google Scholar

[2] Zhu Y, Ammar M H. Algorithms for assigning substrate network resources to virtual network components. In: Proceedings of the 25th IEEE International Conference on Computer Communications, Barcelona, 2006. 1--12. Google Scholar

[3] Lischka J, Karl H. A virtual network mapping algorithm based on subgraph isomorphism detection. In: {Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures}, Barcelona, 2009. 81--88. Google Scholar

[4] Lu J, Turner J. Efficient mapping of virtual networks onto a shared substrate. Technical Report WUCSE-2006-35. Washington University, 2006. Google Scholar

[5] Houidi I, Louati W, Zeghlache D. A distributed virtual network mapping algorithm. In: Proceedings of IEEE International Conference on Communications, Beijing, 2008. 5634--5640. Google Scholar

[6] Yu M, Yi Y, Rexford J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration. ACM SIGCOMM Comput Commun Rev, 2008, 38: 17-29 Google Scholar

[7] Chowdhury N M M K, Rahman M R, Boutaba R. Virtual network embedding with coordinated node and link mapping. In: Proceedings of the 28th IEEE International Conference on Computer Communications, Rio de Janeiro, 2009. 783--791. Google Scholar

[8] Melo M, Sargento S, Killat U, et al. Optimal virtual network embedding: Node-link formulation. IEEE Trans Netw Serv Manag, 2013, 10: 356-368 CrossRef Google Scholar

[9] Butt N F, Chowdhury M, Boutaba R. {Topology-awareness and reoptimization mechanism for virtual network embedding}. In: Proceedings of the 9th International IFIP TC 6 Networking Conference, Chennai, 2010. 27--39. Google Scholar

[10] Nogueira J, Melo M, Carapinha J, et al. Virtual network mapping into heterogeneous substrate networks. In: Proceedings of IEEE Symposium on {Computers and Communications (ISCC)}. IEEE: Washington, DC, 2011. 438--444. Google Scholar

[11] Dorigo M, Caro G D, Gambardella L M. Ant algorithms for discrete optimization. Artif Life, 1999, 5: 137-172 CrossRef Google Scholar

[12] Kennedy J. Particle swarm optimization. In: Sammut C, Webb G I, eds. {Encyclopedia of Machine Learning}. New York: Springer US, 2010. 760--766. Google Scholar

[13] Chu S-C, Tsai P-W. Computational intelligence based on the behavior of cats. Int J Innov Comput Inform Control, 2007, 3: 163-173 Google Scholar

[14] Golberg D E. Genetic Algorithms in Search, Optimization, and Machine Learning. Boston: Addison-Wesley Longman Publishing Co., Inc., 1989. Google Scholar

[15] Zhang Z B, Cheng X, Su S, et al. A unified enhanced particle swarm optimization-based virtual network embedding algorithm. Int J Commun Syst, 2013, 26: 1054-1073 CrossRef Google Scholar

[16] Fajjari I, Aitsaadi N, Pujolle G, et al. VNE-AC: virtual network embedding algorithm based on ant colony metaheuristic. In: Proceedings of IEEE International Conference on Communications (ICC), Kyoto, 2011. 1--6. Google Scholar

[17] Mi X M, Chang X L, Liu J Q, et al. Embedding virtual infrastructure based on genetic algorithm. In: Proceedings of the 13th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), Beijing, 2012. 239--244. Google Scholar

[18] Sivanandam S N, Deepa S N. {Introduction to Genetic Algorithms}. Berlin/Heidelberg: Springer-Verlag, 2007. Google Scholar

[19] Spears W M, Jong K A D. An analysis of multi-point crossover. Technical Report, DTIC Document, 1990. Google Scholar

[20] Zhang S, Qian Z Z, Wu J, et al. An opportunistic resource sharing and topology-aware mapping framework for virtual networks. In: Proceedings of the 31st Annual IEEE International Conference on Computer Communications, Orlando, 2012. 2408--2416. Google Scholar

[21] Rahman M R, Boutaba R. SVNE: survivable virtual network embedding algorithms for network virtualization. IEEE Trans Netw Serv Manag, 2013, 10: 105-118 CrossRef Google Scholar

[22] Chowdhury M, Rahman M R, Boutaba R. Vineyard: virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Trans Netw, 2012, 20: 206-219 CrossRef Google Scholar

[23] Hasan M M, Amarasinghe H, Karmouch A. Network virtualization: dealing with multiple infrastructure providers. In: Proceedings of IEEE International Conference on Communications (ICC), Ottawa, 2012. 5890--5895. Google Scholar

[24] Houidi I, Louati W, Ameur W B, et al. Virtual network provisioning across multiple substrate networks. Comput Netw, 2011, 55: 1011-1023 CrossRef Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有