Orientadores: Eduardo Cândido Xavier, Nelson Luis Saldanha da Fonseca

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação

Resumo: Virtualização de Redes tem recebido recentemente atenção da comunidade científica, uma vez que ela provê mecanismos para lidar com o problema da ossificação da atual arquitetura da Internet. Através da decomposição de Provedores de Serviço de Internet em Provedores de Infraestrutura e...

Resumo: Virtualização de Redes tem recebido recentemente atenção da comunidade científica, uma vez que ela provê mecanismos para lidar com o problema da ossificação da atual arquitetura da Internet. Através da decomposição de Provedores de Serviço de Internet em Provedores de Infraestrutura e Provedores de Serviço, a Virtualização de Redes permite que várias redes virtuais heterogêneas compartilhem o mesmo substrato físico. Um dos principais problemas relacionados à Virtualização de Redes é o Problema do Mapeamento de Redes Virtuais no substrato, que é NP-Difícil. Muitos algoritmos e heurísticas para encontrar bons mapeamentos, de modo a otimizar o uso da banda passante na rede física, têm sido propostos. Neste trabalho, apresentam-se dois novos algoritmos baseados na metaheurística Busca Tabu, o VNE-TS e o VNE-TS-Clustering. Propõe-se também um algoritmo de seleção de redes virtuais, o 2ks-VN-Selector, que se baseia no Problema da Mochila Bidimensional, cujo objetivo é aumentar o rendimento em Provedores de Infraestrutura. Os resultados obtidos pelos uso das heurísticas VNE-TS e VNE-TS-Clustering, são comparandos com os resultados obtidos pelo algoritmo VNE-PSO,uma das melhores heurísticas de mapeamento proposta na literatura para o Problema do Mapeamento de Redes Virtuais. São comparados, também, os resultados da política de seleção 2ks-VN-Selector com os obtidos pela política Most Prize First. Resultados mostram tanto VNE-TS quanto VNE-TS-Clustering rejeitam menos requisições do que o VNE-PSO e que o algoritmo de seleção 2ks-VN-Selector é capaz de aumentar o rendimento de Provedores de Infraestrutura em relação ao algoritmo Most Prize First

Abstract: In recent years, network virtualization has gained considerable attention from the scientific community, since it provides mechanisms to overcome the ossification problem of the current Internet architecture. Through separation of Internet Service Providers into Infrastructure Providers...

Abstract: In recent years, network virtualization has gained considerable attention from the scientific community, since it provides mechanisms to overcome the ossification problem of the current Internet architecture. Through separation of Internet Service Providers into Infrastructure Providers and Service Providers, network virtualization allows multiple heterogeneous virtual networks to share the same physical substrate. One of the main problems regarding network virtualization is the Network Embedding Problem, which is NP-Hard. Several algorithms and heuristics to find a set of good mappings that optimize the use of the bandwidth in substrate networks have been proposed. In this work, we present two new embedding heuristics based on the Tabu Search metaheuristic: the VNE-TS and VNE-TS-Clustering. We also propose a virtual network selection policy, the 2ks-VN-Selector, based on the Bidimensional Knapsack Problem, which aims to increase the profit of Infrastructure Providers. We compare the results obtained by using the VNE-TS and VNE-TS-Clustering heuristics, to those obtained by using the VNE-PSO, one of the best heuristics proposed in the literature for the Embedding Problem. We also compare the effects of the 2ks-VN-Selector with those obtained by using another well known selection policy: Most Prize First. Results show that both VNE-TS and VNE-TS-Clustering reject less virtual network requests than VNE-PSO and that the selection algorithm 2ks-VN-Selector is able to increase the profit of Infrastructure Providers when compared to the Most Prize First algorithm