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

Abstract

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.

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.