Using DCOP to Solve Virtual Network Allocation Problems

Author

Gularte, Alexander R. ; Machado Mendizabal, Odorico ; de Miranda Barbosa, Raquel ; Adamatti, Diana Francisca

Author_Institution

Programa de Pos-Grad. em Comput.-Centro de Cienc. Computacionais, Univ. Fed. do Rio Grande (FURG), Rio Grande, Brazil

fYear

2013

Firstpage

116

Lastpage

120

Abstract

Virtual Networks (VN) offer a flexible and economic approach to deploy customer suited networks. However, defining how resources of a physical network are used to support VNs demands is a NP-hard problem. For this reason, heuristics have been proposed for providing satisfactory allocation of resources in an efficient way. This work presents a modeling of the VN allocation problem using Distributed Constraint Optimization Problem (DCOP) with factor graphs. The max-sum algorithm is employed to solve the DCOP. Correctness criteria for this approach are discussed and verifications going to be conducted through model checking.

Keywords

computer networks; formal verification; graph theory; network theory (graphs); optimisation; resource allocation; virtualisation; DCOP; NP-hard problem; VN allocation problem; correctness criteria; customer suited networks; distributed constraint optimization problem; economic approach; factor graphs; max-sum algorithm; model checking; physical network; resource allocation; virtual network allocation problems; Approximation algorithms; Constraint optimization; Distributed algorithms; Model checking; Resource management; Vectors; Virtualization; DCOP; Virtual Network Embedding; max-sum;

fLanguage

English

Publisher

ieee

Conference_Titel

Theoretical Computer Science (WEIT), 2013 2nd Workshop-School on

Conference_Location

Rio Grande

Type

conf

DOI

10.1109/WEIT.2013.17

Filename

6778576