Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/50541
Type: | Tese |
Title: | Algoritmos para o problema de posicionamento e encadeamento de funções virtuais de rede |
Authors: | Samuel Moreira Abreu Araujo |
First Advisor: | Geraldo Robson Mateus |
First Co-advisor: | Fernanda Sumika Hojo de Souza |
First Referee: | Luiz Fernando Luiz Fernando Bittencourt |
Second Referee: | Rafael Augusto de Melo |
Third Referee: | Michele Nogueira Lima |
metadata.dc.contributor.referee4: | Thiago Ferreira de Noronha |
Abstract: | Impulsionada pelo crescimento da internet, é gerada uma nova onda de aplicações e dados que podem ser acessados de qualquer lugar. Nesse meio, as redes virtuais emergem como tecnologias inovadoras, propiciando a implementação de novas funcionalidades de rede, com um baixo custo, e facilitando o gerenciamento de recursos. O problema abordado nesta tese é relativo ao posicionamento e encadeamento de funções virtuais de rede em um ambiente online em relação à chegada de requisições. Por se tratar de um problema combinatório NP-difícil, enquanto o número de componentes da rede cresce linearmente, o processamento computacional e o tempo de execução aumentam exponencialmente. Em um ambiente online, o provedor precisa lidar de maneira rápida com as requisições à medida que elas chegam, em vez de atender a um conjunto de requisições conhecidas de uma só vez (offline). Tais características aumentam a dificuldade de sua resolução em virtude do grande número de componentes processados. O objetivo deste trabalho é definir modelos, apresentá-los, bem como discutir e resolver o problema de posicionamento e encadeamento de funções virtuais de rede com diferentes algoritmos. Em uma linha clássica de otimização, são propostos um algoritmo exato, baseado em Programação Linear Inteira; e outro heurístico. São propostos mecanismos de hibridização entre técnicas de Aprendizado de Máquina e algoritmos clássicos de otimização. São aplicadas técnicas de clusterização para se reduzir o espaço de soluções e, consequentemente, o tempo de resolução do problema. Complementarmente aos algoritmos propostos, alguns trabalhos da literatura são pesquisados para identificar serviços de rede comumente usados e utilizados nas experimentações. Aplicando um algoritmo exato, percebe-se que reotimizar todo o modelo é custoso computacionalmente e inviável. Experimentos com a heurística geraram resultados promissores, como altos lucros e taxa de aceitação, com um baixo tempo de execução. Experimentos com as técnicas de clusterização confirmam a hipótese de que um espaço de soluções menor diminui consideravelmente o tempo de convergência do algoritmo exato proposto. |
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. |
Subject: | Computação – Teses Virtualização das funções de rede – Teses Otimização matemática -Teses Aprendizado do computador – Teses |
language: | por |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/50541 |
Issue Date: | 9-Feb-2023 |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
tese_texto_final_pdfA.pdf | 26.57 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.