A tecnologia de virtualização de redes é um novo paradigma de redes que permite a múltiplas redes virtuais (VNs) compartilharem de uma forma eficiente e eficaz a mesma rede de infraestrutura denominada rede de substrato (SN). A implementação e o desenvolvimento de novos protocolos, testes de novas soluções e arquiteturas para a Internet atual e do futuro podem ser tratadas por meio da virtualização de redes. Com a virtualização de redes surge um desafio denominado problema VNE. O problema de virtualização de redes embutidas (VNE) consiste em realizar o mapeamento dos nós virtuais e o mapeamento dos enlaces virtuais sobre uma rede de substrato (SN). O problema é conhecido como NP-Hard e a sua solução é realizada por meio de algoritmos heurísticos e aproximados que realizam o mapeamento de nós e enlaces virtuais em dois estágios de forma independente ou coordenada. A presente tese tem o objetivo de resolver o mapeamento dos enlaces virtuais do problema VNE com a utilização da álgebra de caminhos. A solução apresentada fornece o melhor desempenho quando comparada com as demais soluções de virtualização de redes encontradas na literatura. Os resultados obtidos nas simulações para o problema VNE foram avaliados e analisados com a utilização do algoritmo desenvolvido nesta tese denominado Path Algebra for Virtual Link Mapping (PAViLiM), que utiliza a álgebra de caminhos para realizar o mapeamento de enlaces virtuais para caminhos na rede de substrato. A álgebra de caminhos é poderosa e flexível. Tal flexibilidade permite que ocorra uma exploração detalhada do espaço de soluções e a identificação do melhor critério e política que devem ser utilizados para a virtualização de redes. / The network virtualization technology is a new paradigm of network that allows multiple virtual networks (VNs) share in an efficient and effective way the same network infrastructure called substrate network (SN). The implementation and the development of new protocols, testing of new solutions and architectures for current and future Internet can be addressed through network virtualization. With the network virtualization arises a challenge called VNE problem. The problem of virtual network embedded (VNE) is to conduct the mapping of the virtual nodes and mapping of the virtual links over a substrate network (SN).The problem is known as NP-Hard and its solution is accomplished by means of approximate and heuristic algorithms that perform the mapping of virtual nodes and links in two stages independently or coordinated. This thesis aims to solve the mapping of virtual links for VNE problem using the paths algebra. The solution presented provides the best performance when compared with other networks virtualization solutions from the literature. The results of simulation for the VNE problem were evaluated and analyzed using the algorithm developed in this thesis called Path Algebra for Virtual Link Mapping (PAViLiM), which uses the paths algebra to perform the mapping of virtual links to paths in substrate network. The paths algebra is powerful and flexible. This flexibility allows the occurrence of a detailed exploration for identifying the best solutions and political criteria to be used for network virtualization.

A tecnologia de virtualização de redes é um novo paradigma de redes que permite a múltiplas redes virtuais (VNs) compartilharem de uma forma eficiente e eficaz a mesma rede de infraestrutura denominada rede de substrato (SN). A implementação e o desenvolvimento de novos protocolos, testes de novas soluções e arquiteturas para a Internet atual e do futuro podem ser tratadas por meio da virtualização de redes. Com a virtualização de redes surge um desafio denominado problema VNE. O problema de virtualização de redes embutidas (VNE) consiste em realizar o mapeamento dos nós virtuais e o mapeamento dos enlaces virtuais sobre uma rede de substrato (SN). O problema é conhecido como NP-Hard e a sua solução é realizada por meio de algoritmos heurísticos e aproximados que realizam o mapeamento de nós e enlaces virtuais em dois estágios de forma independente ou coordenada. A presente tese tem o objetivo de resolver o mapeamento dos enlaces virtuais do problema VNE com a utilização da álgebra de caminhos. A solução apresentada fornece o melhor desempenho quando comparada com as demais soluções de virtualização de redes encontradas na literatura. Os resultados obtidos nas simulações para o problema VNE foram avaliados e analisados com a utilização do algoritmo desenvolvido nesta tese denominado Path Algebra for Virtual Link Mapping (PAViLiM), que utiliza a álgebra de caminhos para realizar o mapeamento de enlaces virtuais para caminhos na rede de substrato. A álgebra de caminhos é poderosa e flexível. Tal flexibilidade permite que ocorra uma exploração detalhada do espaço de soluções e a identificação do melhor critério e política que devem ser utilizados para a virtualização de redes. / The network virtualization technology is a new paradigm of network that allows multiple virtual networks (VNs) share in an efficient and effective way the same network infrastructure called substrate network (SN). The implementation and the development of new protocols, testing of new solutions and architectures for current and future Internet can be addressed through network virtualization. With the network virtualization arises a challenge called VNE problem. The problem of virtual network embedded (VNE) is to conduct the mapping of the virtual nodes and mapping of the virtual links over a substrate network (SN).The problem is known as NP-Hard and its solution is accomplished by means of approximate and heuristic algorithms that perform the mapping of virtual nodes and links in two stages independently or coordinated. This thesis aims to solve the mapping of virtual links for VNE problem using the paths algebra. The solution presented provides the best performance when compared with other networks virtualization solutions from the literature. The results of simulation for the VNE problem were evaluated and analyzed using the algorithm developed in this thesis called Path Algebra for Virtual Link Mapping (PAViLiM), which uses the paths algebra to perform the mapping of virtual links to paths in substrate network. The paths algebra is powerful and flexible. This flexibility allows the occurrence of a detailed exploration for identifying the best solutions and political criteria to be used for network virtualization.