Repositório Digital

A- A A+

Branch & price for the virtual network embedding problem

.

Branch & price for the virtual network embedding problem

Mostrar registro completo

Estatísticas

Título Branch & price for the virtual network embedding problem
Outro título Branch & price para o problema de mapeamento de redes virtuais
Autor Moura, Leonardo Fernando dos Santos
Orientador Buriol, Luciana Salete
Data 2015
Nível Mestrado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Programa de Pós-Graduação em Computação.
Assunto Rede virtual
Sistemas embarcados
[en] Branch & price
[en] Exact algorithms
[en] Network virtualization
[en] Virtual network embedding
Abstract 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.
Resumo 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.
Tipo Dissertação
URI http://hdl.handle.net/10183/115213
Arquivos Descrição Formato
000963554.pdf (617.4Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.