Algoritmos para o problema de posicionamento e encadeamento de funções virtuais de rede

Abstract

The expansion of the internet has resulted in the creation of a new wave of applications and data that can be accessed from anywhere. In this scenario, virtual networks are emerging as a disruptive technology, enabling the implementation of new network functions at low cost and facilitating the management of resources. The research problem approached in this thesis is concerned with Virtual Networks Functions Placement and Chaining in an online environment in relation to the arrival of the requests. Because it is a NP-hard problem, while the quantity of network components grows linearly, the computer processing and execution time for computing tasks have an exponential growth. In an online environment, the provider needs to quickly handle requests as they come in, rather than serving a set of known requests all at once (offline). These features increase its difficulty in solving issues because of the large amount of components being processed. This research is aimed at defining models, presenting them, as well as to analyze and solve the problem referred to virtual network functions placement and chaining through different types of algorithms. In a traditional optimization line, an algorithm based on Integer Linear Programming and another heuristic are proposed. Hybridization between Machine Learning techniques and classical optimization algorithms are proposed. It has been carried out clustering methods to decrease the solution space and, therefore, the time complexity. In terms of complementing the proposed algorithms, some papers from the literature have been reviewed to identify network services that are commonly used and considered in experiments. Regarding the optimal treatment, it has been observed that reoptimizing the entire model is computationally expensive and unfeasible. Experiments using the heuristic showed promising results, with high profits and acceptance rates despite a higher time complexity and running time. Experiments using cluster analysis confirmed the hypothesis that a smaller solution space can significantly reduce the runtime of the exact algorithm proposed.