PAME: Evolutionary membrane computing for virtual network embedding

Virtual network embedding is an NP-hard online problem, partially due to diversity effects during mapping. Mapping diversity is critical not only for single virtual network but also for a set of online virtual networks. Two common ways, using heuristic information or using extra constraints, are employed to reduce the problem of hardness. Both restrict diversity during mapping. A preferable technique is executing parallel scatter mapping in the solution space, which can promote mapping quality while maintaining diversity. This technique is challenging due to a nested paralleling. Using membrane computing, we designed a P system with active non-elementary membranes (PAME). With a specific membrane structure, PAME achieves nested paralleling via a dual-parallel mapping stage. The stage couples an inter-increment parallel with an intra-increment one, relying on non-elementary membrane self-division and elementary membrane bootstrap. Simulation experiments showed that PAME outperformed existing algorithms in long-term average revenue, acceptance ratio, and long-term revenue-to-cost ratio.