Computer and Knowledge Engineering

Computer and Knowledge Engineering

Uncertain Virtual Network Embedding Using Neighborhood Information Based Edge Prediction

Document Type : Computer Networking-Amin Hosseini

Author
Arezoo Jahani
‎F‎aculty of Electrical ‎Engineering, Sahand University of ‎Technology,‎ Tabriz, Iran
10.22067/cke.2025.93455.1159
Abstract
Network virtualization is a key technology for efficient resource sharing in modern data centers, particularly with the advent of paradigms like Software-Defined Networking (SDN) that enable flexible and centralized control. However, virtual network users cannot always express their exact requirements, leading to uncertainties in topology and resource demands. We model such requests as uncertain virtual networks (UVNs). In this paper, we describe such networks as uncertain virtual networks (UVN) and use uncertain graphs to model them. This paper proposes UVNE (uncertain virtual network embedding), which is a three-step algorithm to embed the UVNs. (1) Extracting a certain virtual network from multiple versions of an uncertain virtual network using a proposed edge prediction algorithm based on the SOM (self-organizing map) classifier. (2) Clustering the extracted virtual network with the HCS (highly connected subgraph) clustering algorithm. (3) Embedding the extracted virtual network with a one-step embedding algorithm. The proposed algorithm is compared with edge prediction and virtual network embedding algorithms. The results demonstrate the strength of the edge prediction algorithm, the benefit, and the reduction of the cost of the embedding.
Keywords
Uncertain virtual network
Edge prediction
SOM classifier
Neighborhood information
Graph clustering
Subjects
  1.  
  1. Sun, D. Liao, D. Zhao, Z. Sun, & V. Chang. (2018). Towards provisioning hybrid virtual networks in federated cloud data centers. Future Generation Computer Systems. [Online]. 87, pp. 457–469. Available: https://doi.org/10.1016/j.future.2017.09.065
  2. Jahani, “Virtual network embedding based on univariate distribution estimation,” In Proceeding 11th Internatinal Conference Computer Engineering and Knowledge (ICCKE), 2021, pp. 284–289. [Online]. Available: https://doi.org/10.1109/ICCKE54056.2021.9721444
  3. Jahani, L. M. Khanli, M. T. Hagh, & M. A. Badamchizadeh. (2019). Green virtual network embedding with supervised self-organizing map. Neurocomputing. [Online]. 351, pp. 60–76. Available: https://doi.org/10.1016/j.neucom.2019.04.090
  4. Aguilar-Fuster & J. Rubio-Loyola. (2021). A novel evaluation function for higher acceptance rates and more profitable metaheuristic-based online virtual network embedding. Computer Networks. [Online]. 195, p. 108191. Available: https://doi.org/10.1016/j.comnet.2021.108191
  5. Jiang & P. Zhang. (2021). Incorporating energy and load balance into virtual network embedding process. Springer. [Online]. 129, pp. 245–268. Available: https://doi.org/10.1016/j.comcom.2018.07.027
  6. Jahani and L. M. Khanli, “CATA-VN: Coordinated and topology-aware virtual network service provisioning in data centers network,” in 2017 7th International Conference on Computer and Knowledge Engineering (ICCKE), Mashhad, Iran, 2017, pp. 353–358. https://doi.org/10.1109/ICCKE.2017.8167904
  7. A. Souza, G. R. Mateus, & F. S. Souza. (2018). Compact and extended formulations for the virtual network embedding problem. Electronic Notes in Discrete Mathematics. [Online]. 64, pp. 205–214. Available: https://doi.org/10.1016/j.endm.2018.01.022
  8. R. Chowdhury, R. Ahmed, M. M. A. Khan, N. Shahriar, R. Boutaba, J. Mitra, & F. Zeng. (2016). Dedicated protection for survivable virtual network embedding. IEEE Transactions on Network and Service Management. [Online]. 13(4), pp. 913–926. Available: https://doi.org/10.1109/TNSM.2016.2574239
  9. Lei, T. Zhang, Y. Liu, Y. Zha, & X. Zhu. (2015). SGEESS: Smart green energy-efficient scheduling strategy with dynamic electricity price for data center. Journal of Systems and Software. [Online]. 108, pp. 23–38. Available: https://doi.org/10.1016/j.jss.2015.06.026
  10. Triki, N. Kara, M. El Barachi, & S. Hadjres. (2015). A green energy-aware hybrid virtual network embedding approach. Computer Networks. [Online]. 91, pp. 712–737. Available: https://doi.org/10.1016/j.comnet.2015.08.016
  11. Arnone, A. Barberi, D. La Cascia, E. R. Sanseverino, & G. Zizzo. (2017). Green data centres integration in smart grids: New frontiers for ancillary service provision. Electric Power Systems Research. [Online]. 148, pp. 59–73. Available: https://doi.org/10.1016/j.epsr.2017.03.017
  12. A. Z. Soltani, S. A. H. Seno, & A. Mohajerzadeh. (2025). Optimizing SDN resource allocation using fuzzy logic and VM mapping technique. Computing. [Online]. 107(1). Available: https://doi.org/10.1007/s00607-024-01360-4
  13. M. A. Khan, N. Shahriar, R. Ahmed, & R. Boutaba. (2016). Multi-path link embedding for survivability in virtual networks. IEEE Transactions on Network and Service Management. [Online]. 13(2), pp. 253–266. Available: https://doi.org/10.1109/TNSM.2016.2558598
  14. Wang, Y. Zhao, R. He, X. Yu, J. Zhang, H. Zheng, Y. Lin, & J. Han. (2016). Continuity-aware spectrum allocation schemes for virtual optical network embedding in elastic optical networks. Optical Fiber Technology. [Online]. 29, pp. 28–33. Available: https://doi.org/10.1016/j.yofte.2016.01.008
  15. He, L. Zhuang, S. Tian, G. Wang, & K. Zhang. (2020). DROi: Energy-efficient virtual network embedding algorithm based on dynamic regions of interest. Computer Networks. [Online]. 166, p. 106952. Available: https://doi.org/10.1016/j.comnet.2019.106952
  16. Ullah, Q. Ali, M. Ashraf, and Y.-H. Han, “Advanced virtual network embedding: Combining graph attention network and DRL for optimal resource utilization,” in 2025 International Conference on Artificial Intelligence in Information and Communication (ICAIIC), South Korea, 2025, pp. 550–555. Available: https://doi.org/10.1109/ICAIIC64266.2025.10920877
  17. Mangili, F. Martignon, & A. Capone. (2016). Performance analysis of content-centric and content-delivery networks with evolving object popularity. Computer Networks. [Online]. 94, pp. 80–98. Available: https://doi.org/10.1016/j.comnet.2015.11.019
  18. Zhan, N. Chen, S. V. N. S. Kumar, G. Kibalya, P. Zhang, & H. Zhang. (2025). Edge computing network resource allocation based on virtual network embedding. International Journal of Communication Systems. [Online]. 38(1). Available: https://doi.org/10.1002/dac.5344
  19. Esposito, D. D. Paola, & I. Matta. (2016). On distributed virtual network embedding with guarantees. IEEE/ACM Transactions on Networking. [Online]. 24(1), pp. 569–582. Available: https://doi.org/10.1109/TNET.2014.2375826
  20. Wang, Q. Hu, L. Nguyen, & M. Jalalitabar. (2023). Minimum-cost embedding of virtual networks: An iterative decomposition approach. Computer Networks. [Online]. 234, p. 109907. Available: https://doi.org/10.1016/j.comnet.2023.109907
  21. Sun, H. Yu, L. Li, V. Anand, Y. Cai, & H. Di. (2012). Exploring online virtual networks mapping with stochastic bandwidth demand in multi-datacenter. Photonic Network Communications. [Online]. 23(2), pp. 109–122. Available:  https://doi.org/10.1007/s11107-011-0341-z
  22. Jian, H. Tao, W. Jian, W. Hu, L. Jiang, & Y. Li. (2015). Virtual network embedding through node connectivity. The Journal of China Universities of Posts and Telecommunications. [Online]. 22(1), pp. 17–56. Available: https://doi.org/10.1016/S1005-8885(15)60620-3
  23. Wang, G. Liu, and Y. Yuan, “A novel method for virtual network embedding with incentive convergence mechanism,” in Third International Conference on Advanced Cloud and Big Data (CBD), Yangzhou, China, 2015, pp. 275–281. Available: https://doi.org/10.1109/CBD.2015.51
  24. Zhang, J. Wu, and S. Lu, “Virtual network embedding with substrate support for parallelization,” in IEEE Global Communications Conference (GLOBECOM), 2013, pp. 2615–2620. [Online]. Available: https://doi.org/10.1109/GLOCOM.2012.6503544
  25. Zhang, Z. Luo, N. Kumar, M. Guizani, H. Zhang, & J. Wang. (2024). CE-VNE: Constraint escalation virtual network embedding algorithm assisted by graph convolutional networks. Journal of Network and Computer Applications. [Online]. 221, p. 103736. Available: https://doi.org/10.1016/j.jnca.2023.103736
  26. Gong, Y. Wen, Z. Zhu, and T. Lee, “Toward profit‑seeking virtual network embedding algorithm via global resource capacity,” in Proceeding IEEE INFOCOM, 2014, pp. 1–9. Available: https://doi.org/10.1109/INFOCOM.2014.6847918
  27. Wang & M. Hamdi. (2016). Presto: Towards efficient online virtual network embedding in virtualized cloud data centers. Computer Networks. [Online]. 106, pp. 196–208. Available: https://doi.org/10.1016/j.comnet.2016.06.036
  28. Haeri & L. Trajković. (2017). Virtual network embedding via Monte Carlo tree search. IEEE Transactions on Cybernetics. [Online]. 48, pp. 510–521. Available: https://doi.org/10.1109/TCYB.2016.2645123
  29. T. Beck, A. Fischer, J. F. Botero, C. Linnhoff-Popien, & H. de Meer. (2015). Distributed and scalable embedding of virtual networks. Journal of Network and Computer Applications. [Online]. 56, pp. 124–136. Available: https://doi.org/10.1016/j.jnca.2015.06.012
  30. F. Botero & X. Hesselbach. (2013). Greener networking in a network virtualization environment. Computer Networks. [Online]. 57(9), pp. 2021–2039. Available: https://doi.org/10.1016/j.comnet.2013.04.004
  31. Guan, B. Y. Choi, & S. Song. (2015). Energy-efficient virtual network embedding for green data centers using data center topology and future migration. Computer Communications. [Online]. 69, pp. 50–59. Available: https://doi.org/10.1016/j.comcom.2015.05.003
  32. R. Oliveira, D. S. Marcon, L. R. Bays, M. C. Neves, L. P. Gaspary, D. Medhi, & M. P. Barcellos. (2015). Opportunistic resilience embedding (ORE): Toward cost-efficient resilient virtual networks. Computer Networks. [Online]. 89, pp. 59–77. Available: https://doi.org/10.1016/j.comnet.2015.07.010
  33. Chowdhury, M. R. Rahman, & R. Boutaba. (2012). Vineyard: Virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Transactions on Networking. [Online]. 20(1), pp. 206–219. Available: https://doi.org/10.1109/TNET.2011.2159308
  34. Cheng, S. Su, Z. Zhang, H. Wang, F. Yang, Y. Luo, & J. Wang. (2011). Virtual network embedding through topology-aware node ranking. ACM SIGCOMM Computer Communication Review. [Online]. 41(2), pp. 38–47. Available: https://doi.org/10.1145/1971162.1971168
  35. Zhang, X. Cheng, S. Su, Y. Wang, K. Shuang, & Y. Luo. (2013). A unified enhanced particle swarm optimization-based virtual network embedding algorithm. International Journal of Communication Systems. [Online]. 26(8), pp. 1054–1073. Available: https://doi.org/10.1002/dac.1399
  36. Hesselbach, J. R. Amazonas, S. Villanueva, & J. F. Botero. (2016). Coordinated node and link mapping VNE using a new paths algebra strategy. Journal of Network and Computer Applications. [Online]. 69, pp. 14–26. Available: https://doi.org/10.1016/j.jnca.2016.02.025
  37. Ogino, T. Kitahara, S. Arakawa, & M. Murata. (2017). Virtual network embedding with multiple priority classes sharing substrate resources. Computer Networks. [Online]. 112, pp. 52–66. Available: https://doi.org/10.1016/j.comnet.2016.10.007
  38. Bienkowski, A. Feldmann, J. Graßler, G. Schaffrath, & S. Schmid. (2014). The wide-area virtual service migration problem: A competitive analysis approach. IEEE/ACM Transactions on Networking. [Online]. 22(1), pp. 165–178. Available: https://doi.org/10.1109/TNET.2013.2245676
  39. F. Butt, M. Chowdhury, and R. Boutaba, “Topology-awareness and reoptimization mechanism for virtual network embedding,” in International Conference on Research in Networking (NETWORKING), Chennai, India, 2010, pp. 27–39. Available: https://doi.org/10.1007/978-3-642-12963-6_3
  40. Soualah, I. Fajjari, M. Hadji, N. Aitsaadi, and D. Zeghlache, “A novel virtual network embedding scheme based on Gomory-Hu tree within cloud’s backbone,” in IEEE/IFIP Network Operations and Management Symposium (NOMS), Istanbul, Turkey, 2016, pp. 536–542. https://doi.org/10.1109/NOMS.2016.7502855
  41. R. Zahedi, S. Jamali, & P. Bayat. (2022). EmcFIS: Evolutionary multi-criteria fuzzy inference system for virtual network function placement and routing. Applied Soft Computing. [Online]. 117, p. 108427. Available: https://doi.org/10.1016/j.asoc.2021.108427
  42. Lischka and H. Karl, “A virtual network mapping algorithm based on subgraph isomorphism detection,” in Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures (VISA), Barcelona, Spain, 2009, pp. 81–88. https://doi.org/10.1145/1592648.1592662
  43. Houidi, W. Louati, W. B. Ameur, & D. Zeghlache. (2011). Virtual network provisioning across multiple substrate networks. Computer Networks. [Online]. 55(4), pp. 1011–1023. Available: https://doi.org/10.1016/j.comnet.2010.12.011
  44. Fajjari, N. A. Saadi, G. Pujolle, and H. Zimmermann, “VNE-AC: Virtual network embedding algorithm based on ant colony metaheuristic,” in IEEE International Conference on Communications (ICC), Kyoto, Japan, 2011, pp. 1–6. Available: https://doi.org/10.1109/icc.2011.5963442
  45. F. Botero, X. Hesselbach, M. Duelli, D. Schlosser, A. Fischer, & H. de Meer. (2012). Energy efficient virtual network embedding. IEEE Communications Letters. [Online]. 16(5), pp. 756–759. Available: https://doi.org/10.1109/LCOMM.2012.030912.120082
  46. Pages, J. Perelló, S. Spadaro, & G. Junyent. (2012). Strategies for virtual optical network allocation. IEEE Communications Letters. [Online]. 16(2), pp. 268–271. Available: https://doi.org/10.1109/LCOMM.2011.120211.111900
  47. Yu, V. Anand, C. Qiao, H. Di, & X. Wei. (2012). A cost-efficient design of virtual infrastructures with joint node and link mapping. Journal of Network and Systems Management. [Online]. 20(1), pp. 97–115. Available: https://doi.org/10.1007/s10922-011-9209-x
  48. Cheng, S. Su, Z. Zhang, K. Shuang, F. Yang, Y. Luo, & J. Wang. (2012). Virtual network embedding through topology awareness and optimization. Computer Networks. [Online]. 56(6), pp. 1797–1813. Available: https://doi.org/10.1016/j.comnet.2012.01.022
  49. Di, H. Yu, V. Anand, L. Li, G. Sun, & B. Dong. (2012). Efficient online virtual network mapping using resource evaluation. Journal of Network and Systems Management. [Online]. 20(4), pp. 468–488. Available: https://doi.org/10.1007/s10922-012-9249-x
  50. Papagianni, A. Leivadeas, S. Papavassiliou, V. Maglaris, C. Cervelló-Pastor, & A. Monje. (2013). On the optimal allocation of virtual resources in cloud computing networks. IEEE Transactions on Computers. [Online]. 62(6), pp. 1060–1071. Available: https://doi.org/10.1109/TC.2013.31
  51. Zhu & H. Wang. (2016). A modified ACO algorithm for virtual network embedding based on graph decomposition. Computer Communications. [Online]. 80, pp. 1–15. Available: https://doi.org/10.1016/j.comcom.2015.07.014
  52. Kollios, M. Potamias, & E. Terzi. (2013). Clustering large probabilistic graphs. IEEE Transactions on Knowledge and Data Engineering. [Online]. 25(2), pp. 325–336. Available: https://doi.org/10.1109/TKDE.2011.243
  53. Ailon, M. Charikar, & A. Newman. (2008). Aggregating inconsistent information: Ranking and clustering. Journal of the ACM (JACM). [Online]. 55(5), Article 23. Available: https://doi.org/10.1145/1411509.1411513
  54. K. TG, S. Tomar, S. K. Addya, A. Satpathy, & S. G. Koolagudi. (2024). EFRAS: Emulated framework to develop and analyze dynamic virtual network embedding strategies over SDN infrastructure. Simulation Modelling Practice and Theory. [Online]. 134, p. 102952. Available: https://doi.org/10.1016/j.simpat.2024.102952
  55. W. Zegura, K. L. Calvert, and S. Bhattacharjee, “How to model an internetwork,” in INFOCOM’96: Fifteenth Annual Joint Conference of the IEEE Computer Societies – Networking the Next Generation, San Francisco, CA, USA, 1996, vol. 2, pp. 594–602. https://doi.org/10.1109/INFCOM.1996.493353
  56. Jahani, L. M. Khanli, M. T. Hagh, & M. A. Badamchizadeh. (2019). EECTA: Energy efficient, concurrent and topology-aware virtual network embedding as a multi-objective optimization problem. Computer Standards & Interfaces. [Online]. 66, p. 103351. Available: https://doi.org/10.1016/j.csi.2019.04.010
  57. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, & S. Lu. (2009). BCube: A high performance, server-centric network architecture for modular data centers. ACM SIGCOMM Computer Communication Review. [Online]. 39(4), pp. 63–74. Available: https://doi.org/10.1145/1592568.1592577
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  
  31.  
  32.  
  33.  
  34.  
  35.  
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
Send comment about this article
Enter Name.
Enter a valid email address.
Enter a vaid affiliation.
Enter comments (At leaset 10 words)
CAPTCHA Image
Enter Security Code Correctly.