Modelos e algoritmos para o problema de mapeamento de redes virtuais

• Ano de defesa: 2016
• Autor(a) principal: Bráulio Antônio Mesquita Souza
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; Brasil; ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO; Programa de Pós-Graduação em Ciência da Computação; UFMG
• Palavras-chave em Português: Virtualização de redes; Programação linear inteira; Geração de colunas; . Computação – Teses.; Virtualização de redes – Teses.; Programação linear inteira – Teses.
• Link de acesso: http://hdl.handle.net/1843/39113

Network Virtualization has been used to allow that many virtual networks can coexist over a substrate network, sharing its resources. In this scenario, the problem of mapping the virtual networks onto the physical substrate, meeting capacity and quality requirements, emerges. In this work, a compact model based on integer linear programming, which provides optimal solutions, is presented. Two extended models are proposed, with stronger dual bounds than the compact model. Based on these models, we also propose branch-and-price algorithms. Results show that, for instances where geographical location is considered for the nodes, both algorithms achieved, within the time limit, better solutions than the compact model for a greater number of virtual network requests. Moreover, it is performed a study on the impact of different objective functions (mapping cost, delay, and load balancing) and quality of service constraints (geographic location, maximum delay, and resilience) on the solutions