Efficient online embedding of secure virtual networks

Abstract

A virtualização de redes tem se tornado cada vez mais proeminente nos últimos anos. Tal técnica permite a criação de infraestruturas de rede que se adaptam a necessidades específicas de aplicações de rede distintas, além de dar suporte à instanciação de ambientes favoráveis para o desenvolvimento e avaliação de novas arquiteturas e protocolos. Apesar de esforços recentes (motivados principalmente pela busca de mecanismos para avaliar propostas relacionadas à Internet do Futuro) terem contribuído substancialmente para a materialização desse conceito, nenhum preocupou-se em conciliar alocação eficiente de recursos e satisfação de requisitos de segurança (e.g., confidencialidade). É importante ressaltar que, no contexto de redes virtuais, a proteção de infraestruturas de rede compartilhadas constitui condição fundamental para seu uso em larga escala. É de grande importância que o impacto negativo causado pelo aprovisionamento de segurança seja considerado no processo de mapeamento de redes virtuais, de forma a permitir o uso integral dos recursos físicos sem subestimar requisitos de capacidade. Portanto, nesta dissertação, são propostos um modelo ótimo e um al- goritmo heurístico para realizar o mapeamento de redes virtuais em substratos físicos que têm por objetivo otimizar a utilização de recursos físicos garantindo a satisfação de requisitos de segurança. Ambas as abordagens possuem uma modelagem precisa de custos adicionais associados a mecanismos de segurança usados para proteger re- des virtuais, e são capazes de atender requisições de redes virtuais de forma online. Além disso, são apresentados os resultados de um extensivo processo de avaliação realizado, incluindo uma comparação detalhada entre o modelo ótimo e o algoritmo heurístico. Os experimentos revelam que o modelo baseado em Programação Linear Inteira é capaz de alocar redes virtuais de forma ótima em substratos físicos com até cem roteadores, enquanto que o algoritmo heurístico é capaz de adaptar-se a infraestruturas maiores, provendo mapeamentos sub-ótimos em um curto espaço de tempo.

Network virtualization has become increasingly prominent in recent years. It enables the creation of network infrastructures that are specifically tailored to the needs of distinct network applications and supports the instantiation of favorable en- vironments for the development and evaluation of new architectures and protocols. Although recent efforts (motivated mainly by the search for mechanisms to eval- uate Future Internet proposals) have contributed substantially to materialize this concept, none of them has attempted to combine efficient resource mapping with ful- fillment of security requirements (e.g., confidentiality). It is important to note that, in the context of virtual networks, the protection of shared network infrastructures constitutes a fundamental condition to enable its use in large scale. Considering the negative impact of security provisions in the virtual network embedding process is of paramount importance in order to fully utilize physical re- sources without underestimating capacity requirements. Therefore, in this thesis we propose both an optimal model and a heuristic algorithm for embedding virtual networks on physical substrates that aim to optimize physical resource usage while meeting security requirements. Both approaches feature precise modeling of over- head costs of security mechanisms used to protect virtual networks, and are able to handle virtual network requests in an online manner. In addition, we present the results of an extensive evaluation we carried out, including a detailed comparison of both the optimal model and the heuristic algorithm. Our experiments show that the Integer Linear Programming (ILP) model is capable of optimally embedding virtual networks on physical infrastructures with up to a hundred routers, while the heuristic algorithm is capable of scaling to larger infrastructures, providing timely, sub-optimal mappings.