A novel optimal mapping algorithm with less computational complexity for virtual network embedding
journal contributionposted on 16.02.2018, 15:42 by Haotong Cao, Yongxu Zhu, Gan Zheng, Longxiang Yang
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.
This paper is partly supported by the National Basic Research Program of China (973 Program) under Grant 2013CB329104, the National Natural Science Foundation of China under Grant 61372124 and 61427801. The work of G. Zheng was supported by the UK EPSRC under grant number EP/N007840/1.
- Mechanical, Electrical and Manufacturing Engineering