Virtual Network Functions Placement and Routing Problem: Path formulation

Network Functions Virtualization (NFV) and Software Defined Networking (SDN) are two promising techniques for the next generation telecommunication networks. Their introduction allows time, energy and cost minimization. Placing Virtual Network Functions (VNFs) on network nodes and routing data through these nodes is a very challenging combinatorial optimization problem. Obviously, the problem becomes even more difficult, if in addition, the data have to be routed using the concept of Service Functions Chaining (SFC) in which VNFs are chained according to a pre-defined order associated to each service. In this paper we study the Virtual Network Functions Placement and Routing problem in Software Defined Networks, in which a set of source-destination pairs representing clients demand and a set of VNFs are given. The problem consists in finding a routing path for each demand and the optimal associated placement of functions while minimizing functions installation and node activation costs. In this work, we propose a path-based MILP formulation to model the problem and we also demonstrate how to efficiently use it to derive high-quality heuristic solutions within a short computational time. We provide a case study derived from a set of scenarios in which we vary relevant problem parameters, including arc latency, input demand and node capacities. The study is conducted on a benchmark set of realistic telecommunication instances from the SNDlib library. To test the efficiency of our approach, we also compare the obtained results with a compact MILP formulation. Our computational study indicates that the path-based formulation outperforms the compact model both in terms of computing time and overall solution quality.