A novel optimal mapping algorithm with less computational complexity for virtual network embedding

IEEE Network Virtualization (NV) is widely accepted as one enabling technology for future network, which enables multiple Virtual Networks (VNs) with different paradigms and protocols to coexist on the shared Substrate Network (SN). One key challenge in network virtualization is Virtual Network Embedding (VNE), which maps a virtual network onto the shared SN. Since VNE is NP-hard, existing efforts mainly focus on proposing heuristic algorithms that try to achieve feasible VN embedding in reasonable time, consequently the resulted embedding is not optimal. To tackle this difficulty, we propose a candidate assisted (CAN-A) optimal VNE algorithm with lower computational complexity. The key idea of the CAN-A algorithm lies in constructing the candidate substrate node subset and the candidate substrate path subset before embedding. This reduces the mapping execution time substantially without performance loss. In the following embedding, four types of node and link constraints are considered in the CAN-A algorithm, making it more applicable to realistic networks. Simulation results show that the execution time of CAN-A is hugely cut down compared with pure VNE-MIP algorithm. CAN-A also outperforms the typical heuristic algorithms in terms of other performance indices, such as the average virtual network request (VNR) acceptance ratio and the average virtual link propagation delay.