Repositório Digital

A- A A+

Algoritmo de branch & bound aplicado ao problema de virtualização de redes

.

Algoritmo de branch & bound aplicado ao problema de virtualização de redes

Mostrar registro completo

Estatísticas

Título Algoritmo de branch & bound aplicado ao problema de virtualização de redes
Outro título Branch & bound algorithm applied to network embedding problem
Autor Meister, Tatiana Costa
Orientador Buriol, Luciana Salete
Co-orientador Moura, Leonardo Fernando dos Santos
Data 2015
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Assunto Redes virtuais
Visualização
[en] Branch & bound
[en] Exact algorithms
[en] Virtualization
[en] Virtual network embedding problem
Resumo O problema de virtualização de redes, o qual surgiu com o compartilhamento de recursos físicos por redes virtuais, consiste em alocar uma ou mais redes virtuais sobre uma rede física respeitando as capacidades de nós e links, bem como atendendo outras restrições do problema. Este problema já foi resolvido heuristicamente, através de metaheurísticas e métodos de arredondamento, e exatamente através do CPLEX e Branch & Price. O presente trabalho apresenta um algoritmo exato para o problema de mapeamento de redes virtuais baseado na técnica de Branch & Bound. Diversos cortes são propostos, reduzindo significativamente o espaço de busca do problema. O algoritmo proposto é comparado experimentalmente com o CPLEX e Branch & Price, considerando diferentes classes de grafos e de tamanhos variados. Nos cenários testados, o algoritmo proposto apresenta desempenho significativamente superior ao CPLEX e Branch & Price.
Abstract The network virtualization problem, which was originated from the sharing of resources among several virtual networks, consists in running one or more virtual networks on top of a physical network respecting the capabilities of nodes and links, as well as meeting other constraints of the problem. This problem was already solved heuristically, using metaheuristics and rounding heuristics, and exactly by CPLEX and Branch & Price. This work presents an exact algorithm for the virtual network embedding problem based on the branch & bound method. Several cuts are proposed, reducing considerably the size of the problem search space. The presented algorithm is experimentally compared with CPLEX and Branch & Price, considering different network topologies and instance sizes. In the tested scenarios, the proposed algorithm presents significantly superior performance to CPLEX and Branch & Price.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/138208
Arquivos Descrição Formato
000988919.pdf (2.400Mb) 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.