One-stage and Dual-heuristic Particle Swarm Optimization for Virtual Network Embedding

Virtual network embedding (VNE) is the key technology in network virtualization and has been proven NP-hard. The purpose of VNE is to find the optimal mapping of virtual nodes and links, and minimize the utilization of resources. However, many particle swarm optimization approaches to VNE separate VNE into two independent subproblems (i.e., node mapping and link mapping) and ignore the coordination between node mapping and link mapping. In this paper, a one-stage and dual-heuristic particle swarm optimization (DH-PSO) is devised to solve VNE. To coordinate node mapping and link mapping, firstly, DH-PSO updates positions of particles step by step, and nodes and links are mapped in one stage. Secondly, DH-PSO devises the dual-heuristic strategy to further improve the optimizing capability. The first heuristic strategy is to construct a candidate set and the second strategy is to find the best solution from the candidate set. Hence, not only the network resources but the network paths are taken into account to construct solutions. DH-PSO can be combined with different two-stage approaches to become one stage. DH-PSO is experimentally studied on different instances. The experimental results verify that the proposed DH-PSO is promising.