A new algorithm based on the proximity principle for the virtual network embedding problem
Jiang Liu, Tao Huang, Jianya Chen, Yunjie Liu · Frontiers of Information Technology & Electronic Engineering · 2011
The virtual network embedding/mapping problem is a core issue of network virtualization. It is concerned mainly with how to map virtual network requests to the substrate network efficiently. There are two steps in this problem: node mapping and link mapping. Current studies mainly focus on developing heuristic algorithms, since both steps are computationally intractable. In this paper, we propose a new algorithm based on the proximity principle, which considers the distance factor besides the capacity factor in the node mapping step. Thus, the two steps of the embedding problem can be better integrated and the substrate network resource can be used more efficiently. Simulation results show that the new algorithm greatly enhances the performance of the revenue/cost ( R / C ) ratio, acceptance ratio, and runtime of the embedding problem.