Virtualização permite o compartilhamento de uma rede física entre uma ou mais redes virtuais. O Problema de Mapeamento de Redes Virtuais é um dos principais desafios na virtualização de redes. Esse problema consiste em mapear uma rede virtual em uma rede física, respeitando restrições de capacidade. O presente trabalho mostra que encontrar uma solução factível para esse problema é NP-Difícil. Mesmo assim, muitas instâncias podem ser pode ser resolvidas na prática através da exploração de sua estrutura. Nós apresentamos um algoritmo de Branch & Price aplicado a instâncias de diferentes topologias e tamanhos. Os experimentos realizados sugerem que o algoritmo proposto é superior ao modelo de programação linear resolvido com CPLEX. / Virtualization allows one or more virtual networks to share physical infrastructures. The Virtual Network Embedding problem (VNEP) is one of the main challenges in the virtualization of physical networks. This problem consists in mapping a virtual network into a physical network while respecting capacity constraints. This work shows that finding a feasible solution for this problem is NP-Hard. However, many instances can be solved up to optimality in practice by exploiting the problem structure. We present a Branch & Price algorithm applied to instances of different topologies and sizes. The experimental results suggest that the proposed algorithm is superior to the Integer Linear Programming model solved by CPLEX.

Orientador: Prof. Dr. Carlos Alberto Kamienski / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Engenharia da Informação, 2016. / O conceito de Cidades Inteligentes, com a rápida urbanização e adoção de tecnologias como Internet das Coisas (IoT), smartphones e outras tecnologias de computação pervasiva, já é realidade. Esse cenário apresenta uma nova classe de problemas computacionais e de infraestrutura de telecomunicações, exigindo o equacionamento das variáveis flexibilidade, qualidade de serviço e custo, tanto financeiro como ambiental. Tecnologias como Virtualização de Funções de Rede (NFV), Computação em Nuvem e Redes Definidas por Software (SDN) estão em evidência nos últimos anos como promessa para solucionar essas demandas. Este trabalho utiliza a abordagem NFV para solucionar o problema de fornecimento dinâmico e elástico de acesso público à internet nas grandes cidades. Os resultados obtidos demonstram níveis significativos de desempenho e flexibilidade, além da escolha de métricas e comparação de desempenho do KVM, XEN e containers LXC na virtualização de funções de rede. / The concept of Smart Cities is already a reality with rapid urbanization and adoption of technologies like Internet of Things (IoT), smartphones and other pervasive computing technologies. This scenario presents a new class of computational and telecom infrastructure problems, requiring match flexibility, quality of service and cost, both financial and environmental. Technologies like Network Functions Virtualization (NFV), Cloud Computing and Software Defined Networks (SDN) are in evidence in recent years as a promise to address these demands. This paper uses the NFV approach to solving the problem of dynamic and elastic supply of public Internet access in major cities. The results show significant levels of performance and flexibility in addition to the choice of metrics and KVM, XEN and LXC container performance comparison in NFV.

Em ambientes virtualizados, como nuvens computacionais, a capacidade efetiva de transmissão de dados via rede tende a ser inferior à de ambientes não virtualizados quando aplicações que fazem uso intensivo da rede são executadas. Uma das principais causas para essa diferença na capacidade de transmissão é a arquitetura da virtualização de rede, que adiciona passos para o sistema operacional transmitir e receber um pacote. Esses passos adicionais acarretam em maior utilização de memória e de processamento. Em ambientes virtualizados com o sistema operacional GNU/Linux, a New Application Programming Interface (NAPI) é utilizada para reduzir os impactos negativos da virtualização por meio de agregação de interrupções. Nesta dissertação de mestrado, são estudados mecanismos que modificam a configuração da NAPI. Experimentos mostram que esses mecanismos afetam o desempenho de máquinas virtuais e tem consequências diretas nas aplicações que fazem uso intensivo de rede e que são executadas em ambientes com os softwares de virtualização Xen, VMware e VirtualBox. / In virtualized environments, such as cloud computing, the effective capacity of data transmission via network cards tends to be lower than that in non-virtualized environments, when network intensive applications are executed. A major cause for this difference in the transmission capacity is the architecture of network virtualization, which adds some steps to be performed by the system when packets are transmitted or received. These additional steps cause more memory and processing usage. In virtualized environments with the GNU/Linux operating system, the New Application Programming Interface (NAPI) is used to reduce the negative impacts of virtualization through interrupt coalescence. In this dissertation, mechanisms that modify the configuration of NAPI are studied. Experiments show that these mechanisms affect the performance of virtual machines and have direct effects in applications that make intensive use of the network in environments with Xen, VMware and VirtualBox.

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.

A virtualização de redes é um mecanismo que permite a coexistência de múltiplas redes virtuais sobre um mesmo substrato físico. Um dos desafios de pesquisa abordados na literatura é o mapeamento eficiente de recursos virtuais em infraestruturas físicas. Embora o referido desafio tenha recebido considerável atenção, as abordagens que constituem o estado-da-arte apresentam alta taxa de rejeição, i.e., a proporção de solicitações de redes virtuais negadas em relação ao total de solicitações efetuadas ao substrato é elevada. Nesta dissertação, caracteriza-se, inicialmente, a relação entre a qualidade dos mapeamentos de redes virtuais e as estruturas topológicas dos substratos subjacentes. Avalia-se as soluções exatas de um modelo de mapeamento online sob diferentes classes de topologias de rede. A partir do entendimento dos fatores topológicos que influenciam diretamente o processo de mapeamento de redes virtuais, propõe-se uma estratégia para planejar a expansão de redes de provedores de infraestrutura de forma a reduzir consistentemente a taxa de rejeição de requisições de redes virtuais e melhor aproveitar os recursos ociosos da mesma. Os resultados obtidos evidenciam que grande parte das rejeições de redes virtuais ocorre em situações em que há grande disponibilidade de recursos, mas alguns poucos já saturados acabam inviabilizando, em função de características de conectividade do substrato, o atendimento de novas requisições. Ademais, os resultados obtidos utilizando a estratégia proposta evidenciam que o fortalecimento de partes-chave da infraestrutura levam a uma ocupação muito mais satisfatória. Uma expansão de 10% a 20% dos recursos da infraestrutura contribui para um aumento sustentado de até 30% no número de redes virtuais aceitas e de até 45% no aproveitamento dos recursos em comparação com a rede original. / Network virtualization is a mechanism that allows the coexistence of multiple virtual networks on top of a single physical substrate. One of the research challenges addressed recently in the literature is the efficient mapping of virtual resources on physical infrastructures. Although this challenge has received considerable attention, state-of-the-art approaches present, in general, a high rejection rate, i.e., the ratio between the number of denied virtual network requests and the total amount of requests is considerably high. In this thesis, we characterize the relationship between the quality of virtual network mappings and the topological structures of the underlying substrates. Exact solutions of an online embedding model are evaluated under different classes of network topologies. From the understanding of the topological factors that directly influence the virtual network embedding process, we propose an expansion strategy of physical infrastructure in order to suggest adjustments that lead to higher virtual network acceptance and, in consequence, to improved physical resource utilization. The obtained results demonstrate that most of rejections occur in situations in which a significant amount of resource is available, but a few saturated devices and links, depending on connectivity features of the physical substrate, hinder the acceptance of new requests. Moreover, the obtained results using the proposed strategy evidence that an expansion of 10% to 20% of the infrastructure resources leads to a sustained increase of up to 30% in the number of accepted virtual networks and of up to 45% in resource usage compared to the original network.

Virtualização permite o compartilhamento de uma rede física entre uma ou mais redes virtuais. O Problema de Mapeamento de Redes Virtuais é um dos principais desafios na virtualização de redes. Esse problema consiste em mapear uma rede virtual em uma rede física, respeitando restrições de capacidade. O presente trabalho mostra que encontrar uma solução factível para esse problema é NP-Difícil. Mesmo assim, muitas instâncias podem ser pode ser resolvidas na prática através da exploração de sua estrutura. Nós apresentamos um algoritmo de Branch & Price aplicado a instâncias de diferentes topologias e tamanhos. Os experimentos realizados sugerem que o algoritmo proposto é superior ao modelo de programação linear resolvido com CPLEX. / Virtualization allows one or more virtual networks to share physical infrastructures. The Virtual Network Embedding problem (VNEP) is one of the main challenges in the virtualization of physical networks. This problem consists in mapping a virtual network into a physical network while respecting capacity constraints. This work shows that finding a feasible solution for this problem is NP-Hard. However, many instances can be solved up to optimality in practice by exploiting the problem structure. We present a Branch & Price algorithm applied to instances of different topologies and sizes. The experimental results suggest that the proposed algorithm is superior to the Integer Linear Programming model solved by CPLEX.

A virtualização de redes é uma solução proposta para superar a chamada ossificação da Internet pois permite o desenvolvimento de novas arquiteturas de rede de forma flexível e controlada. Com a virtualização de redes, é possível criar múltiplas redes virtuais operando simultaneamente em uma infraestrutura física compartilhada. No entanto, o gerenciamento de redes com suporte a virtualização apresenta desafios que precisam ser resolvidos para obter um ambiente de rede confiável e funcional. Um dos principais aspectos relacionados ao gerenciamento de ambientes de virtualização de redes diz respeito ao aprovisionamento de redes virtuais. O aprovisionamento de redes virtuais define como os recursos de rede virtuais (nós e enlaces) são alocados na infraestrutura física. O aprovisionamento de redes virtuais é comumente baseado em algoritmos de mapeamento que possuem objetivos bem definidos como reduzir o custo de alocação, realizar balanceamento de carga ou minimizar o consumo de energia. Embora redes virtuais compartilhem a mesma infraestrutura, elas tipicamente são utilizadas para hospedar várias aplicações que possuem diferentes objetivos. Infelizmente, as soluções de aprovisionamento atuais focam em um único ou em um conjunto muito limitado de objetivos que podem não ser capazes de satisfazer os requisitos de um número cada vez mais crescente de aplicações. Novas aplicações podem exigir objetivos diferentes dos que são suportados pelo sistema de aprovisionamento que está em operação em uma infraestrutura de virtualização de redes. Nesta tese, o problema de Aprovisionamento de Redes Virtuais Orientado à Aplicação é formulado e um arcabouço de aprovisionamento adaptativo para redes virtualizadas que considera as caracteristicas de várias aplicações bem como seus requisitos de desempenho é proposto. O arcabouço proposto é baseado no conceito de paradigma de alocação, que é um conjunto de políticas de aprovisionamento que guiam o processo de alocação de recursos. Um paradigma traduz objetivos de Provedores de Infraestrutura e Provedores de Serviço para ações de alocação individuais que criam as redes virtuais. Uma linguagem de políticas para paradigmas é também definida para expressar o relacionamento entre paradigmas, objetivos e ações. Para determinar a eficiência de um paradigma de alocação, é proposto um modelo para quantificar o desempenho de redes virtuais que é baseado em dados coletados de sistemas de benchmarking aplicados no contexto de ambientes virtualizados. O modelo proposto é capaz de calcular o desempenho das redes virtuais alocadas e influenciar mudanças em paradigmas de alocação. Simulações foram conduzidas para verificar a viabilidade da solução proposta e comparar diferentes paradigmas de alocação. Resultados mostram que o uso de paradigmas de alocação pode ajudar administradores de ambientes de virtualização de redes a escolher a melhor estratégia de alocação dado um conjunto de objetivos definidos pelos Provedores de Infraestrutura e pelos Provedores de Serviço. / Network virtualization is a feasible solution to tackle the so-called Internet ossification by enabling the deployment of novel network architectures in a flexible and controlled way. With network virtualization, it is possible to have multiple virtual networks (VNs) running simultaneously on top of a shared physical infrastructure. Network management with virtualization support, however, poses challenges that need to be addressed in order to fully achieve an effective and reliable networking environment. One of the main aspects related to the management of network virtualization environments is virtual network provisioning. Virtual network provisioning defines how virtual network resources (nodes and links) are allocated in the physical infrastructure. VN provisioning often relies on embedding algorithms that aim to achieve well defined objectives, such as reducing allocation cost, load balancing, or minimizing energy consumption. Although VNs share the same infrastructure, they typically host diverse applications with different goals. Unfortunately, current provisioning solutions focus on a single or a limited set of objectives that may not simultaneously match the requirements of an increasing number of applications deployed in networks everyday. Novel applications may require different objectives that are not supported by the active provisioning system. In this thesis, we formulate the Application-Aware Virtual Network Provisioning Problem (AVNP) and propose an adaptive provisioning framework for virtualized networks that takes into consideration the characteristics of multiple applications and their distinct performance objectives. The proposed framework is based on the concept of allocation paradigm, which is defined as a set of provisioning policies that guide the resource allocation process. A paradigm translates objectives from both Infrastructure Providers (InPs) and Service Providers (SPs) to individual allocation actions that actually provision VNs. A policy language is also defined to express the relationship between paradigms, objectives, and actions. To determine the efficiency of a particular paradigm, we propose a virtual network performance computation model based on data measured from existing virtualization benchmarks. The model is able to quantify the performance of allocated VNs and guide paradigm changing decisions. Extensive simulations were performed to verify the viability of the proposed solution and compare different paradigms. Results show the feasibility of allocation paradigms in helping network providers to select the best provisioning strategy given a set of InP/SP objectives.

Em ambientes de virtualização de redes (NVEs – Network Virtualization Environments), a infraestrutura física é compartilhada entre diferentes usuários (ou provedores de serviços) que criam múltiplas redes virtuais (VNs – Virtual Networks). Como parte do aprovisionamento de VNs, roteadores virtuais (VRs – Virtual Routers) são criados dentro de roteadores físicos que suportam a virtualização. Atualmente, o gerenciamento de NVEs é quase sempre realizado por soluções proprietárias, normalmente baseadas em interfaces de linha de comando (CLI – Command Line Interface). NVEs heterogêneos (i.e., com equipamentos e tecnologias diferentes) são difíceis de gerenciar, devido à falta de soluções de gerenciamento padronizadas. Como primeiro passo para conseguir a interoperabilidade de gerenciamento, bom desempenho e alta escalabilidade, foram implementadas, avaliadas e comparadas cinco interfaces de gerenciamento de roteadores físicos que hospedam roteadores virtuais. As interfaces são baseadas em SNMP (v2c e v3), NETCONF, e RESTful Web Services (sobre HTTP e HTTPS), e são projetadas para realizar três operações básicas de gerenciamento de VRs: criação de VR, recuperação de informações de VR e remoção de VR. Essas interfaces foram avaliadas em relação às seguintes métricas: tempo de resposta, tempo de CPU, consumo de memória e uso da rede. Os resultados mostram que a interface baseada no SNMPv2c é a mais adequada para pequenos NVEs, sem rigorosos requisitos de segurança, e o NETCONF é a melhor escolha para compor uma interface de gerenciamento para ser implantada em cenários mais realistas, onde a segurança e a escalabilidade são as principais preocupações. / In network virtualization environments (NVEs), the physical infrastructure is shared among different users (or service providers) who create multiple virtual networks (VNs). As part of VN provisioning, virtual routers (VRs) are created inside physical routers supporting virtualization. Currently, the management of NVEs is mostly realized by proprietary solutions, usually based on Command Line Interfaces (CLI). Heterogeneous NVEs (i.e., with different equipment and technologies) are difficult to manage due to the lack of standardized management solutions. As a first step to achieve management interoperability, good performance, and high scalability, we implemented, evaluated, and compared five management interfaces for physical routers that host virtual ones. The interfaces are based on SNMP (v2c and v3), NETCONF, and RESTful Web Services (over HTTP and HTTPS), and are designed to perform three basic VR management operations: VR creation, VR information retrieval, and VR removal. We evaluate these interfaces with regard to the following metrics: response time, CPU time, memory consumption, and network usage. Results show that the SNMPv2c interface is the most suitable one for small NVEs without strict security requirements and NETCONF is the best choice to compose a management interface to be deployed in more realistic scenarios, where security and scalability are major concerns.

Em ambientes de virtualização de redes (NVEs – Network Virtualization Environments), a infraestrutura física é compartilhada entre diferentes usuários (ou provedores de serviços) que criam múltiplas redes virtuais (VNs – Virtual Networks). Como parte do aprovisionamento de VNs, roteadores virtuais (VRs – Virtual Routers) são criados dentro de roteadores físicos que suportam a virtualização. Atualmente, o gerenciamento de NVEs é quase sempre realizado por soluções proprietárias, normalmente baseadas em interfaces de linha de comando (CLI – Command Line Interface). NVEs heterogêneos (i.e., com equipamentos e tecnologias diferentes) são difíceis de gerenciar, devido à falta de soluções de gerenciamento padronizadas. Como primeiro passo para conseguir a interoperabilidade de gerenciamento, bom desempenho e alta escalabilidade, foram implementadas, avaliadas e comparadas cinco interfaces de gerenciamento de roteadores físicos que hospedam roteadores virtuais. As interfaces são baseadas em SNMP (v2c e v3), NETCONF, e RESTful Web Services (sobre HTTP e HTTPS), e são projetadas para realizar três operações básicas de gerenciamento de VRs: criação de VR, recuperação de informações de VR e remoção de VR. Essas interfaces foram avaliadas em relação às seguintes métricas: tempo de resposta, tempo de CPU, consumo de memória e uso da rede. Os resultados mostram que a interface baseada no SNMPv2c é a mais adequada para pequenos NVEs, sem rigorosos requisitos de segurança, e o NETCONF é a melhor escolha para compor uma interface de gerenciamento para ser implantada em cenários mais realistas, onde a segurança e a escalabilidade são as principais preocupações. / In network virtualization environments (NVEs), the physical infrastructure is shared among different users (or service providers) who create multiple virtual networks (VNs). As part of VN provisioning, virtual routers (VRs) are created inside physical routers supporting virtualization. Currently, the management of NVEs is mostly realized by proprietary solutions, usually based on Command Line Interfaces (CLI). Heterogeneous NVEs (i.e., with different equipment and technologies) are difficult to manage due to the lack of standardized management solutions. As a first step to achieve management interoperability, good performance, and high scalability, we implemented, evaluated, and compared five management interfaces for physical routers that host virtual ones. The interfaces are based on SNMP (v2c and v3), NETCONF, and RESTful Web Services (over HTTP and HTTPS), and are designed to perform three basic VR management operations: VR creation, VR information retrieval, and VR removal. We evaluate these interfaces with regard to the following metrics: response time, CPU time, memory consumption, and network usage. Results show that the SNMPv2c interface is the most suitable one for small NVEs without strict security requirements and NETCONF is the best choice to compose a management interface to be deployed in more realistic scenarios, where security and scalability are major concerns.

Virtualização permite o compartilhamento de uma rede física entre uma ou mais redes virtuais. O Problema de Mapeamento de Redes Virtuais é um dos principais desafios na virtualização de redes. Esse problema consiste em mapear uma rede virtual em uma rede física, respeitando restrições de capacidade. O presente trabalho mostra que encontrar uma solução factível para esse problema é NP-Difícil. Mesmo assim, muitas instâncias podem ser pode ser resolvidas na prática através da exploração de sua estrutura. Nós apresentamos um algoritmo de Branch & Price aplicado a instâncias de diferentes topologias e tamanhos. Os experimentos realizados sugerem que o algoritmo proposto é superior ao modelo de programação linear resolvido com CPLEX. / Virtualization allows one or more virtual networks to share physical infrastructures. The Virtual Network Embedding problem (VNEP) is one of the main challenges in the virtualization of physical networks. This problem consists in mapping a virtual network into a physical network while respecting capacity constraints. This work shows that finding a feasible solution for this problem is NP-Hard. However, many instances can be solved up to optimality in practice by exploiting the problem structure. We present a Branch & Price algorithm applied to instances of different topologies and sizes. The experimental results suggest that the proposed algorithm is superior to the Integer Linear Programming model solved by CPLEX.