FINAL Article.pdf (725.13 kB)

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

Download (725.13 kB)
journal contribution
posted on 16.02.2018 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

Published in

IEEE Transactions on Network and Service Management


CAO, H. al., 2017. A novel optimal mapping algorithm with less computational complexity for virtual network embedding. IEEE Transactions on Network and Service Management, 15 (1), pp.356-371.


© Institute of Electrical and Electronics Engineers (IEEE)


AM (Accepted Manuscript)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at:

Publication date



Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.