Abstract
With the development of heterogeneous network structure, dynamic user requests as well as complex service types and applications scenarios, current networks may not accommodate the increasingly stringent requirements. As a result, the research of the beyond fifth generation (B5G) or the sixth generation (6G) networks has been put on the agenda. In B5G/6G networks, achieving the automatic, flexible, and cost-effective orchestration and management of network resources is a significant but challenging issue. Network function virtualization (NFV), as a promising paradigm to address this issue, has received considerable attention from both industry and academia. NFV leverages the virtualization technology to decouple network functions from dedicated hardware appliances to software middleboxes or called virtual network functions (VNFs) that run on the commodity servers. The demand for a network service becomes a request for running a set of VNFs deployed on the substrate network. The requested network service is orchestrated in the form of a VNF-forwarding graph (VNF-FG). The problem of embedding the VNF-FG into the substrate network is known as VNF-FG embedding (VNF-FGE). The efficiency and the management cost of a network are highly dependent on the optimization of VNF-FGE. This paper mainly presents a survey on solving the VNF-FGE problem. To this end, we present a general formulation and several objectives of the VNF-FGE problem. In the meanwhile, we summarize its different application scenarios from four perspectives and divide the approaches into four main categories based on the optimization methods. The main challenges and potential future directions due to the appearance of B5G/6G are also discussed.
Similar content being viewed by others
References
Union, I. (2015). Imt traffic estimates for the years 2020 to 2030. Report ITU (p. 2370)
You, X., Wang, C. X., Huang, J., Gao, X., Zhang, Z., Wang, M., Huang, Y., Zhang, C., Jiang, Y., Wang, J., et al. (2021). Towards 6G wireless communication networks: Vision, enabling technologies, and new paradigm shifts. Science China Information Sciences, 64(1), 1–74.
Herrera, J. G., & Botero, J. F. (2016). Resource allocation in NFV: A comprehensive survey. IEEE Transactions on Network and Service Management, 13(3), 518–532.
Group, N., et al. (2013). Network functions virtualisation (NFV) architectural framework. Tech. rep., Technical Report ETSI GS NFV, 002.
Halpern, J. & Pignataro, C., et al. (2015). Service function chaining (SFC) architecture. In RFC 7665.
Bhamare, D., Jain, R., Samaka, M., & Erbad, A. (2016). A survey on service function chaining. Journal of Network and Computer Applications, 75, 138–155.
Xie, Y., Liu, Z., Wang, S., & Wang, Y. (2016). Service function chaining resource allocation: A survey. arXiv preprint arXiv:1608.00095.
Mirjalily, G., & Zhiquan, L. (2018). Optimal network function virtualization and service function chaining: A survey. Chinese Journal of Electronics, 27(4), 704–717.
Wang, X., Han, Y., Leung, V. C., Niyato, D., Yan, X., & Chen, X. (2020). Convergence of edge computing and deep learning: A comprehensive survey. IEEE Communications Surveys & Tutorials, 22(2), 869–904.
Wang, X., Li, X., Pack, S., Han, Z., & Leung, V. C. M. (2020). STCS: spatial-temporal collaborative sampling in flow-aware software defined networks. IEEE Journal on Selected Areas in Communications, 38(6), 999–1013.
Qiu, C., Yao, H., Wang, X., Zhang, N., Yu, F. R., & Niyato, D. (2020). AI-Chain: blockchain energized edge intelligence for beyond 5G networks. IEEE Network, 34(6), 62–69.
Sun, G., Yu, H., Li, L., Anand, V., Cai, Y., & Di, H. (2012). Exploring online virtual networks mapping with stochastic bandwidth demand in multi-datacenter. Photonic Network Communications, 23(2), 109–122.
Zhang, S., Qian, Z., Tang, B., Wu, J., & Lu, S. (2011). Opportunistic bandwidth sharing for virtual network mapping. In 2011 IEEE Global Telecommunications Conference-GLOBECOM 2011, pp. 1–5. IEEE.
Zhang, S., Qian, Z., Wu, J., & Lu, S. (2012). An opportunistic resource sharing and topology-aware mapping framework for virtual networks. In 2012 Proceedings IEEE INFOCOM, pp. 2408–2416. IEEE.
Pei, J., Hong, P., Xue, K., Li, D., Wei, D. S., & Wu, F. (2020). Two-phase virtual network function selection and chaining algorithm based on deep learning in SDN/NFV-enabled networks. IEEE Journal on Selected Areas in Communications, 38(6), 1102–1117.
Agarwal, S., Malandrino, F., Chiasserini, C. F., & De, S. (2019). VNF placement and resource allocation for the support of vertical services in 5G networks. IEEE/ACM Transactions on Networking, 27(1), 433–446.
Wang, S., & Lv, T. (2019). Deep reinforcement learning for demand-aware joint VNF placement-and-routing. In 2019 IEEE Globecom Workshops, pp. 1–6. IEEE.
Pei, J., Hong, P., Pan, M., Liu, J., & Zhou, J. (2020). Optimal VNF placement via deep reinforcement learning in SDN/NFV-enabled networks. IEEE Journal on Selected Areas in Communications, 38(2), 263–278.
Li, W., Wu, H., Jiang, C., Jia, P., Li, N. & Lin, P. (2020). Service chain mapping algorithm based on reinforcement learning. In 2020 International Wireless Communications and Mobile Computing (IWCMC), pp. 800–805. IEEE.
Gu, L., Zeng, D., Li, W., Guo, S., Zomaya, A. & Jin, H. (2019). Deep reinforcement learning based VNF management in geo-distributed edge computing. In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), pp. 934–943. IEEE
Su, S., Zhang, Z., Liu, A. X., Cheng, X., Wang, Y., & Zhao, X. (2014). Energy-aware virtual network embedding. IEEE/ACM Transactions on Networking, 22(5), 1607–1620.
Su, S., Zhang, Z., Cheng, X., Wang, Y., Luo, & Y., Wang, J. (2012). Energy-aware virtual network embedding through consolidation. In 2012 Proceedings IEEE INFOCOM Workshops, pp. 127–132. IEEE.
Zhang, Z., Su, S., Zhang, J., Shuang, K., & Xu, P. (2015). Energy aware virtual network embedding with dynamic demands: Online and offline. Computer Networks, 93, 448–459.
Rivoire, S., Ranganathan, P., & Kozyrakis, C. (2008). A comparison of high-level full-system power models. HotPower, 8(2), 32–39.
Fan, X., Weber, W. D., & Barroso, L. A. (2007). Power provisioning for a warehouse-sized computer. ACM SIGARCH computer architecture news, 35(2), 13–23.
Economou, D., Rivoire, S., Kozyrakis, C. & Ranganathan, P. (2006). Full-system power analysis and modeling for server environments. ACM SIGARCH computer architecture news pp. 70–77
Chiaraviglio, L., Mellia, M., & Neri, F. (2012). Minimizing ISP network energy cost: formulation and solutions. IEEE/ACM Transactions on Networking, 20(2), 463–476.
Li, X. & Qian, C. (2015). The virtual network function placement problem. In 2015 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 69–70. IEEE.
Tastevin, N., Obadia, M., & Bouet, M. (2017). A graph approach to placement of service functions chains. In 2017 IFIP/IEEE Symposium on Integrated Network and Service Management (IM), pp. 134–141. IEEE
Cao, J., Zhang, Y., An, W., Chen, X., Sun, J., & Han, Y. (2017). VNF-FG design and VNF placement for 5G mobile networks. Science China Information Sciences, 60(4), 040302.
Kuo, T. W., Liou, B. H., Lin, K. C. J., & Tsai, M. J. (2018). Deploying chains of virtual network functions: On the relation between link and server usage. IEEE/ACM Transactions On Networking, 26(4), 1562–1576.
Quang, P. T. A., Bradai, A., Singh, K. D., Picard, G., & Riggio, R. (2018). Single and multi-domain adaptive allocation algorithms for VNF forwarding graph embedding. IEEE Transactions on Network and Service Management, 16(1), 98–112.
Tajiki, M. M., Salsano, S., Chiaraviglio, L., Shojafar, M., & Akbari, B. (2018). Joint energy efficient and QoS-aware path allocation and VNF placement for service function chaining. IEEE Transactions on Network and Service Management, 16(1), 374–388.
Wang, W., Hong, P., Lee, D., Pei, J., & Bo, L. (2017). Virtual network forwarding graph embedding based on Tabu search. In 2017 9th International Conference on Wireless Communications and Signal Processing (WCSP), pp. 1–6. IEEE.
Jang, I., Suh, D., Pack, S., & Dán, G. (2017). Joint optimization of service function placement and flow distribution for service function chaining. IEEE Journal on Selected Areas in Communications, 35(11), 2532–2541.
Soualah, O., Mechtri, M., Ghribi, C. & Zeghlache, D. (2018). A green VNF-FG embedding algorithm. In 2018 4th IEEE Conference on Network Softwarization and Workshops (NetSoft), pp. 141–149. IEEE .
Quang, P. T. A., Hadjadj-Aoul, Y., & Outtagarts, A. (2019). A deep reinforcement learning approach for VNF forwarding graph embedding. IEEE Transactions on Network and Service Management, 16(4), 1318–1331.
Soares, J. & Sargento, S. (2015) Optimizing the embedding of virtualized cloud network infrastructures across multiple domains. In 2015 IEEE International Conference on Communications (ICC), pp. 442–447. IEEE
Zhang, Q., Wang, X., Kim, I., Palacharla, P., & Ikeuchi, T. (2016). Service function chaining in multi-domain networks. In 2016 Optical Fiber Communications Conference and Exhibition (OFC), pp. 1–3. IEEE.
Quang, P. T. A., Bradai, A., Singh, K. D. & Hadjadj-Aoul, Y. (2019). Multi-domain non-cooperative VNF-FG embedding: A deep reinforcement learning approach. In IEEE INFOCOM 2019-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 886–891. IEEE.
Sun, J., Huang, G., Sun, G., Yu, H., Sangaiah, A. K., & Chang, V. (2018). A q-learning-based approach for deploying dynamic service function chains. Symmetry, 10(11), 646.
Ruiz, L., Barroso, R. J. D., De Miguel, I., Merayo, N., Aguado, J. C., De La Rosa, R., Fernández, P., Lorenzo, R. M., & Abril, E. J. (2020). Genetic algorithm for holistic VNF-mapping and virtual topology design. IEEE Access, 8, 55893–55904.
Li, H., Wang, L., Wen, X., Lu, Z., & Li, J. (2018). MSV: An algorithm for coordinated resource allocation in network function virtualization. IEEE Access, 6, 76876–76888.
Pei, J., Hong, P., Xue, K., & Li, D. (2018). Efficiently embedding service function chains with dynamic virtual network function placement in geo-distributed cloud system. IEEE Transactions on Parallel and Distributed Systems, 30(10), 2179–2192.
Clayman, S., Maini, E., Galis, A., Manzalini, A. & Mazzocca, N. (2014). The dynamic placement of virtual network functions. In 2014 IEEE Network Operations and Management Symposium (NOMS), pp. 1–9.
Liu, J., Lu, W., Zhou, F., Lu, P., & Zhu, Z. (2017). On dynamic service function chain deployment and readjustment. IEEE Transactions on Network and Service Management, 14(3), 543–553.
Bari, M. F., Chowdhury, S. R., Ahmed, R., & Boutaba, R. (2015) On orchestrating virtual network functions. In: 2015 11th International Conference on Network and Service Management (CNSM), pp. 50–56. IEEE.
Luizelli, M. C., Bays, L. R., Buriol, L. S., Barcellos, M. P., & Gaspary, L. P. (2015). Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions. In 2015 IFIP/IEEE International Symposium on Integrated Network Management, pp. 98–106. IEEE.
Moens, H., & De Turck, F. (2014). VNF-P: A model for efficient placement of virtualized network functions. In 10th International Conference on Network and Service Management (CNSM) and Workshop, pp. 418–423. IEEE.
Riggio, R., Bradai, A., Rasheed, T., Schulz-Zander, J., Kuklinski, S., & Ahmed, T. (2015). Virtual network functions orchestration in wireless networks. In 2015 11th International Conference on Network and Service Management (CNSM), pp. 108–116. IEEE.
Sahhaf, S., Tavernier, W., Rost, M., Schmid, S., Colle, D., Pickavet, M., & Demeester, P. (2015). Network service chaining with optimized network function embedding supporting service decompositions. Computer Networks, 93, 492–505.
Jahromi, N. T., Kianpisheh, S. & Glitho, R. H. (2018). Online VNF placement and chaining for value-added services in content delivery networks. In 2018 IEEE International Symposium on Local and Metropolitan Area Networks (LANMAN), pp. 19–24. IEEE.
Mijumbi, R., Serrat, J., Gorricho, J., Rubio-Loyola, J. & Davy, S. (2015). Server placement and assignment in virtualized radio access networks. In 2015 11th International Conference on Network and Service Management (CNSM), pp. 398–401. IEEE.
Addis, B., Belabed, D., Bouet, M. & Secci, S. (2015). Virtual network functions placement and routing optimization. In 2015 IEEE 4th International Conference on Cloud Networking (CloudNet), pp. 171–177. IEEE.
Marotta, A., & Kassler, A. (2016). A power efficient and robust virtual network functions placement problem. In 2016 28th International Teletraffic Congress (ITC 28), vol. 1, pp. 331–339. IEEE.
Lin, T., Zhou, Z., Tornatore, M., & Mukherjee, B. (2016). Demand-aware network function placement. Journal of Lightwave Technology, 34(11), 2590–2600.
Ghaznavi, M., Shahriar, N., Ahmed, R., & Boutaba, R. (2016). Service function chaining simplified. arXiv preprint arXiv:1601.00751.
Mehraghdam, S., Keller, M., & Karl, H. (2014). Specifying and placing chains of virtual network functions. In 2014 IEEE 3rd International Conference on Cloud Networking (CloudNet), pp. 7–13. IEEE.
Jang, I., Choo, S., Kim, M., Pack, S. & Shin, M. (2016). Optimal network resource utilization in service function chaining. In 2016 IEEE NetSoft Conference and Workshops (NetSoft), pp. 11–14. IEEE.
Khebbache, S., Hadji, M. & Zeghlache, D. (2017). Scalable and cost-efficient algorithms for VNF chaining and placement problem. In 2017 20th conference on innovations in clouds, internet and networks (ICIN), pp. 92–99. IEEE .
Tajiki, M. M., Salsano, S., Shojafar, M., Chiaraviglio, L., & Akbari, B. (2018). Energy-efficient path allocation heuristic for service function chaining. In 2018 21st Conference on Innovation in Clouds, Internet and Networks and Workshops (ICIN), pp. 1–8. IEEE.
Jia, Z., Sheng, M., Li, J., Liu, R., Guo, K., Wang, Y., Chen, D. & Ding, R. (2018). Joint optimization of VNF deployment and routing in software defined satellite networks. In 2018 IEEE 88th Vehicular Technology Conference (VTC-Fall), pp. 1–5. IEEE.
Li, B., Cheng, B., Wang, M., Liu, X., Yue, Y., & Chen, J. (2019). Joint correlation-aware VNF selection and placement in cloud data center networks. In 2019 IEEE 25th International Conference on Parallel and Distributed Systems (ICPADS), pp. 171–176. IEEE.
Yang, K., Zhang, H. & Hong, P. (2016). Energy-aware service function placement for service function chaining in data centers. In 2016 IEEE Global Communications Conference (GLOBECOM), pp. 1–6. IEEE.
Leivadeas, A., Kesidis, G., Falkner, M., & Lambadaris, I. (2017). A graph partitioning game theoretical approach for the VNF service chaining problem. IEEE Transactions on Network and Service Management, 14(4), 890–903.
Kim, S., Park, S., Kim, Y., Kim, S., & Lee, K. (2017). VNF-EQ: dynamic placement of virtual network functions for energy efficiency and QoS guarantee in NFV. Cluster Computing, 20(3), 2107–2117.
Khebbache, S., Hadji, M., & Zeghlache, D. (2018). A multi-objective non-dominated sorting genetic algorithm for VNF chains placement. In 2018 15th IEEE Annual Consumer Communications & Networking Conference (CCNC), pp. 1–4. IEEE.
Luizelli, M. C., da Costa Cordeiro, W. L., Buriol, L. S., & Gaspary, L. P. (2017). A fix-and-optimize approach for efficient and large scale virtual network function placement and chaining. Computer Communications, 102, 67–77.
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., & Riedmiller, M. (2013). Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602.
Kim, S. I., & Kim, H. S. (2017). A research on dynamic service function chaining based on reinforcement learning using resource usage. In 2017 Ninth International Conference on Ubiquitous and Future Networks (ICUFN), pp. 582–586. IEEE.
Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.
Quang, P. T. A., & Hadjadj-Aoul, Y. (2020). Outtagarts: Evolutionary actor-multi-critic model for VNF-FG embedding. In IEEE Consumer Communications & Networking Conference (CCNC 2020), pp. 1–6. IEEE.
Pan, P., Fan, Q., Wang, S., Li, X., Li, J., & Shi, W. (2020). GCN-TD: A learning-based approach for service function chain deployment on the fly. In GLOBECOM 2020-2020 IEEE Global Communications Conference, pp. 1–6. IEEE
Gu, L., Zeng, D., Li, W., Guo, S., Zomaya, A. Y., & Jin, H. (2019). Intelligent VNF orchestration and flow scheduling via model-assisted deep reinforcement learning. IEEE Journal on Selected Areas in Communications, 38(2), 279–291.
Pei, J., Hong, P. & Li, D. (2018). Virtual network function selection and chaining based on deep learning in SDN and NFV-enabled networks. In 2018 IEEE International Conference on Communications Workshops (ICC Workshops), pp. 1–6. IEEE.
Spinnewyn, B., Isolani, P. H., Donato, C., Botero Botero, J. F., & Latré, S. (2018). Coordinated service composition and embedding of 5G location-constrained network functions. IEEE Transactions on Network and Service Management, 15(4), 1488–1502.
Wang, Z., Zhang, J., Huang, T., & Liu, Y. (2019). Service function chain composition, placement, and assignment in data centers. IEEE Transactions on Network and Service Management, 16(4), 1638–1650.
Alameddine, H.A., Qu, L., & Assi, C. (2017). Scheduling service function chains for ultra-low latency network services. In 2017 13th International Conference on Network and Service Management (CNSM), pp. 1–9. IEEE.
Huang, X., Bian, S., Gao, X., Wu, W., Shao, Z., & Yang, Y. (2019). Online VNF chaining and scheduling with prediction: optimality and trade-offs. In 2019 IEEE Global Communications Conference (GLOBECOM), pp. 1–6. IEEE.
Eramo, V., Miucci, E., Ammar, M., & Lavacca, F. G. (2017). An approach for service function chain routing and virtual function network instance migration in network function virtualization architectures. IEEE/ACM Transactions on Networking, 25(4), 2008–2025.
Li, G., Zhou, H., Feng, B., Li, G. & Yu, S. (2018). Automatic selection of security service function chaining using reinforcement learning. In 2018 IEEE Globecom Workshops (GC Wkshps), pp. 1–6. IEEE.
Isg, N. (2016). Network functions virtualisation (nfv); reliability; report on models and features for end-to-end reliability. ETSI Standard GS NFV-REL, 003.
Khezri, H. R., Moghadam, P. A., Farshbafan, M. K., Shah-Mansouri, V., Kebriaei, H., & Niyato, D. (2019). Deep reinforcement learning for dynamic reliability aware NFV-based service provisioning. In 2019 IEEE Global Communications Conference (GLOBECOM), pp. 1–6. IEEE.
Alahmad, Y., & Agarwal, A. (2019). VNF placement strategy for availability and reliability of network services in NFV. In 2019 Sixth International Conference on Software Defined Systems (SDS), pp. 284–289. IEEE.
Wang, X., Wang, C., Li, X., Leung, V. C. M., & Taleb, T. (2020). Federated deep reinforcement learning for internet of things with decentralized cooperative edge caching. IEEE Internet of Things Journal, 7(10), 9441–9455.
Mijumbi, R., Hasija, S., Davy, S., Davy, A., Jennings, B., & Boutaba, R. (2017). Topology-aware prediction of virtual network function resource requirements. IEEE Transactions on Network and Service Management, 14(1), 106–120.
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2008). The graph neural network model. IEEE Transactions on Neural Networks, 20(1), 61–80.
Blenk, A., Kalmbach, P., Zerwas, J., Jarschel, M., Schmid, S. & Kellerer, W. (2018). NeuroViNE: A neural preprocessor for your virtual network embedding algorithm. In IEEE INFOCOM 2018-IEEE Conference on Computer Communications, pp. 405–413. IEEE.
Solozabal, R., Ceberio, J., Sanchoyerto, A., Zabala, L., Blanco, B., & Liberal, F. (2020). Virtual network function placement optimization with deep reinforcement learning. IEEE Journal on Selected Areas in Communications, 38(2), 292–303.
Acknowledgements
This work is supported in part by the Major Special Program for Technical Innovation & Application Development of Chongqing Science & Technology Commission (No. CSTC 2019jscx-zdztzxX0031), the National NSFC (No. 61902044, 62072060, 61902178), the National Key R & D Program of China (No. 2018YFF0214700, 2018YFB2100100), the Chongqing Research Program of Basic Research and Frontier Technology (No. cstc2019jcyj-msxmX0589, cstc2018jcyjAX0340), the Natural Science Foundation of Jiangsu (No. BK20190295), the Leading Technology of Jiangsu Basic Research Plan (No. BK20192003), and the European Union’s Horizon 2020 Research and Innovation Programme under the Marie Skłodowska-Curie Grant Agreement No. 898588.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.