A Constraint Optimization Based Mapping Method for Virtual Network

Virtual network mapping problem, which attempts to map different virtual networks on the same substrate network, is an extremely challenging problem. A constraint optimization based mapping method is proposed to solve the problem. In this method, the process of solving the problem is divided into two phases, node mapping phase and link mapping phase, which are all NP-hard. The former phase maps the virtual nodes to the substrate nodes, and the latter phase maps the virtual links to the substrate paths. Node-mapping algorithm and link-mapping algorithm are proposed to solve the node mapping phase and the link mapping phase, respectively. Node-mapping algorithm adopts the thinking of greedy algorithm, mainly considering the available resources which are supplied by substrate nodes and distances among the nodes, in order to maintain load balancing. Meanwhile, an access control mechanism is also proposed to filter the unmoral virtual networks for the purpose of increasing the resource utilization. Link-mapping algorithm is based on the result of node mapping phase, and it adopts the thinking of distributed constraint optimization problem in artificial intelligence. The algorithm can guarantee the optimal solution, namely the minimum cost of mapping the virtual links. Finally, simulation experiments are conducted and the results show that the method performs very well.