Abstract:

Due to the exponential growth of service demands, telecommunication networks are populated with a large and increasing variety of proprietary hardware appliances, increasing the cost and the complexity of the network management. The NFV paradigm is proposed to overcome this problem, allowing dynamical allocation of Virtual Network Functions (VNFs) to make network function provision and operation more flexible and cost-effective. A key problem in NFV is the NFV service chaining: given a network where some nodes are connected with computational servers and a set of demands asking for network services composed of a sequence of VNF instances. VNF instances need to be installed on servers and the demands must be routed in such a way that each demand accesses the requested VNFs. Despite thelarge number of research papers, little has been done towards achieving cost-efficient VNFs Placement and demands Routing (VNF-PR). From an optimization point of view, the problem can be modeled as the combination of a facility location problem (for the VNF location and server dimensioning) and a network design problem (for the demands routing). Both problems are widely studied in the literature, but their combination represent a new challenge.

In this thesis, we focus on the VNF-PR problem. Our objective is to study the problem structure and features, analyze and compare the most promising formulations, and finally propose exact and heuristic methods to solve efficiently the problem. In the first stage, we study the VNF-PR problem structures and features. For this, we extend the work in [1] by considering more realistic features and constraints of NFV infrastructures and we propose a linear programming model to solve it. Then, we design a math-heuristic algorithm to scale with multiple objectives, which allows us to study further the mutual impact between classical traffic engineering and NFV infrastructures efficiency goals. We generate scenarios with different VNF forwarding profiles, different cases of demand distribution and different levels of end-to-end latency bound to evaluate the proposed method. Computational results show that our method can provide a stable and close-to-optimum solution for the considered problem and there is a trade-off achievable between classical traffic engineering and NFV infrastructures cost-efficiency goals. In the second stage, our goal is to investigate the problem complexity and properties and to analyze and compare different mathematical programming models. To do so, we move into the theoretical part of the problem. We formalize a simplified, yet significant variant, the VNF-PR with simple path routing (VNF-PR SP ) problem. We prove the NP-completeness of the VNF-PR SP problem. Further, we derive problem properties and use them to help in speeding up the optimization. In order to better understand the behavior of different mathematical programming models, we generate a common test bed with more than 100 different test instances under different capacity settings and topology features, on which we evaluate and compare the two most promising formulations (i.e., PR and SP) proposed in the literature. We prove both theoretically and computationally that the continuous relaxation of SP always provides a bound no worse than the one of PR. Then, we introduce additional inequalities to strengthen the formulations, and we extend the formulations to address more general versions of the problem with multiple VNF types and multiple orders. Finally, we address the problem scalability by proposing exact and heuristic methods to deal with large size instances (with up to 60 nodes and 1800 demands) of the VNF-PR SP problem. In our exact methods, we partially fix the solution and solve the model to complete it. In our heuristic methods, we combine the mathematical programming models with a local search technique, which allows us to explore quickly the reduced solution space to provide a feasible solution. We show that: our exact methods can solve efficiently (e.g., less than 2 seconds under some capacity cases) the small size instances (with less than 30 nodes and 300 demands) of the problem; our proposed heuristic methods can solve efficiently medium size instances (with between 20 and 30 nodes, 300 and 1000 demands) of challenging capacity cases and provide feasible solutions for large size instances of the most difficult capacity cases, for which the models cannot find any feasible solution even with large computational time (i.e., 2hours).

Keywords: Network Function Virtualization (NFV), Resource Allocation, Operations Research