The Knapsack-Based Genetic Algorithm for Solving the Virtual Network Functions Placement and Chaining Problem

Vu Ngoc Hoa; Le Trong Vinh; Ngo Hai Anh

doi:10.48084/etasr.17874

Authors

Vu Ngoc Hoa Graduate University of Science and Technology (GUST), Vietnam Academy of Science and Technology, Hanoi, Vietnam | Hanoi Industrial Economics College, Hanoi, Vietnam
Le Trong Vinh Hanoi University of Industry, Tay Tuu Ward, Hanoi, Vietnam
Ngo Hai Anh Institute of Information Technology, Vietnam Academy of Science and Technology, Hanoi, Vietnam

Volume: 16 | Issue: 3 | Pages: 36600-36607 | June 2026 | https://doi.org/10.48084/etasr.17874

Received: 31 January 2026 | Revised: 22 February 2026, 14 March 2026, and 24 March 2026 | Accepted: 26 March 2026 | Online: 6 June 2026

Corresponding author: Ngo Hai Anh

Abstract

In the context of digital transformation and the advent of 5G/6G networks, Network Function Virtualization (NFV) and Software-Deﬁned Networking (SDN) serve as foundational pillars. However, resource management in such environments introduces significant challenges to the Virtual Network Functions Placement and Chaining (VNF-PC) problem. This problem is NP-hard and requires a careful balance among operational cost, network performance, and quality of service. This paper presents an in-depth study of VNF-PC, thoroughly analyzing existing techniques such as Integer Linear Programming (ILP) models, Benders decomposition, and heuristic algorithms. Building on these foundations, a novel approach is proposed, named the Knapsack-Based Genetic Algorithm (KBGA). This method models the placement of VNFs onto physical servers as a multidimensional knapsack optimization problem, combined with a hybrid initialization strategy to accelerate convergence. Simulation results demonstrate that KBGA improves request acceptance rates by up to 20% compared to traditional greedy algorithms under high-load conditions, while simultaneously reducing network operational costs.

Keywords:

NFV, VNF, VNF-PC, KBGA

References

T. Zhang, H. Qiu, L. Linguaglossa, W. Cerroni, and P. Giaccone, "NFV Platforms: Taxonomy, Design Choices and Future Challenges," IEEE Transactions on Network and Service Management, vol. 18, no. 1, pp. 30–48, Mar. 2021.

H. U. Adoga and D. P. Pezaros, "Network Function Virtualization and Service Function Chaining Frameworks: A Comprehensive Review of Requirements, Objectives, Implementations, and Open Research Challenges," Future Internet, vol. 14, no. 2, Feb. 2022.

Y. Yue et al., "VNF placement in NFV-enabled networks: considering time-varying workloads and multi-tenancy with a throughput optimization heuristic," Computing, vol. 106, no. 11, pp. 3657–3690, Nov. 2024.

I. A. Ikhelef, "Optimization of VNF placement and chaining according to NFV/SDN paradigms," Ph.D. dissertation, Université Paris-Nord - Paris XIII, 2024.

I. A. Ikhelef, M. Y. Saidi, S. Li, and K. Chen, "Multi-Constrained Routing-Based Heuristic for VNF Placement and Chaining," in ICC 2023 - IEEE International Conference on Communications, May 2023, pp. 3363–3369.

P. D. Thien, F. Wu, M. Bekhit, A. Fathalla, and A. Salah, "Optimizing Placement and Scheduling for VNF by a Multi-objective Optimization Genetic Algorithm," International Journal of Computational Intelligence Systems, vol. 17, no. 1, Mar. 2024, Art. no. 43.

A. Ikhelef, M. Y. Saidi, S. Li, and K. Chen, "A Knapsack-based Optimization Algorithm for VNF Placement and Chaining Problem," in 2022 IEEE 47th Conference on Local Computer Networks (LCN), Sept. 2022, pp. 430–437.

Y. Liu and J. Zhang, "Service Function Chain Embedding Meets Machine Learning: Deep Reinforcement Learning Approach," IEEE Transactions on Network and Service Management, vol. 21, no. 3, pp. 3465–3481, June 2024.

M. Anoushee, M. Fartash, and J. Akbari Torkestani, "An intelligent resource management method in SDN based fog computing using reinforcement learning," Computing, vol. 106, no. 4, pp. 1051–1080, Apr. 2024.

M. K. Hassan, S. H. S. Ariffin, S. K. Syed-Yusof, N. E. Ghazali, and K. A. Obeng, "A Short Review on the Dynamic Slice Management in Software-Defined Network Virtualization," Engineering, Technology & Applied Science Research, vol. 13, no. 6, pp. 12074–12079, Dec. 2023.

Y. Zhang, F. He, and E. Oki, "Service Mapping and Scheduling With Uncertain Processing Time in Network Function Virtualization," IEEE Transactions on Cloud Computing, vol. 11, no. 2, pp. 1315–1333, Apr. 2023.

M. Smine, D. Espes, N. Cuppens-Boulahia, and F. Cuppens, "Network Functions Virtualization Access Control as a Service," in Data and Applications Security and Privacy XXXIV, 2020, pp. 100–117.