Multi-Constrained Routing-Based Heuristic for VNF Placement and Chaining

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.