Node and Link Allocation in Network Virtualization Based on Distributed Constraint Optimization

Virtual Networks (VNs) offer a flexible and economic approach to deploy customer suited networks. However, defining how resources of a physical network are used to support VNs requirements is a NP-hard problem. For this reason, heuristics have been used on mapping of virtual networks. Although heuristics do not ensure the optimal solution, they implement fast solutions and showed satisfactory results. This work presents a modeling of the node and link allocation problem using Distributed Constraint Optimization Problem (DCOP) with factor graphs, which is a formalism widely used in real distributed optimization problems. In our approach, we use the max-sum algorithm to solve the DCOP. Correctness criteria for this approach are discussed and verifications are conducted through model checking.