Network softwarization makes it easy to quickly deploy various and different network services with the composition of virtual network functions (VNFs) that can be launched, modified and stopped at any time. Nowadays, several VNF servers supporting different types of VNFs exist. Therefore, to minimize the cost of deploying network services, VNFs should not only be placed on the best servers but also chained in an optimal way. In this paper, we propose a new approach to solve the NP-hard VNF placement and chaining problem (VNFPC problem). After proving that VNFPC problem can be transformed to a variant of the multi-constrained routing problem where the number of additive metrics is part of the problem, we proposed efficient heuristic reducing the worst-case time complexity while ensuring high quality solutions. Simulation results show that our constrained shortest paths-based heuristics allows to determine solutions close to the optima by keeping small number of paths on nodes.

During the last decade, we are witnessing the emergence of NFV and SDN to reduce CAPEX and OPEX. Under the SDN paradigm and thanks to NFV, a service can be swiftly deployed by the chaining of several VNFs forming an SFC running on a virtualized infrastructure. Nowadays, there are still quite a number of issues related to SFCs, among them, the optimal placement of SFC components. In this paper, we focused on the variant of the resource allocation cost optimization problem of VNF placement and chaining for limited resources on the servers. After proving that the problem of VNF placement is NP-Hard and equivalent to the multiple knapsack problem, we proposed a genetic algorithm-based meta-heuristic to solve large instance of our VNF placement and chaining problem variant. Simulation results show that our genetic algorithms are efficient since they reduce the SFC mean cost and improve the accepted requests ratio.