Virtual network embedding through topology awareness and optimization

详细信息	查看全文 | 推荐本文 |

• 作者：Xiang Cheng^a ; ^{chengxiang@bupt.edu.cn}  ; [Author Vitae] ; Sen Su^a ; ^{susen@bupt.edu.cn}  ; [Author Vitae] ; Zhongbao Zhang^a ; ^{zhongbaozb@bupt.edu.cn}  ; [Author Vitae] ; Kai Shuang^a ; ^{shuangk@bupt.edu.cn}  ; [Author Vitae] ; Fangchun Yang^a ; ^{fcyang@bupt.edu.cn}  ; [Author Vitae] ; Yan Luo^b ; ^{yan_luo@uml.edu}  ; [Author Vitae] ; Jie Wang^b ; ^{wang@cs.uml.edu}  ; [Author Vitae]
• 关键词：Network virtualization ; Virtual network embedding ; Topology awareness ; Random walk ; Meta-heuristic ; Particle swarm optimization
• 刊名：Computer Networks
• 出版年：2012
• 期刊代码：28_13891286
• 类别：cp
• 出版时间：19 April, 2012
• 卷：56
• 期：6
• 页码：1797-1813
• 文件大小：841 K

摘要

Embedding a sequence of virtual networks (VNs) into a given physical network substrate to accommodate as many VN requests as possible is known to be NP-hard. This paper presents a new approach to studying this problem. In particular, we devise a topology-aware measure on node resources based on random walks and use it to rank a node鈥檚 resources and topological attributes. We then devise a greedy algorithm that matches nodes in the VN to nodes in the substrate network according to node ranks. In most situations there exist multiple embedding solutions, and so we want to find the best embedding that increases the possibility of accepting future VN requests and optimizes the revenue for the provider of the substrate network. We present an integer linear programming formulation for this optimization problem when path splitting is not allowed. We then devise a fast-convergent discrete Particle Swarm Optimization algorithm to approximate this problem. Extensive simulation results show that our algorithms produce near optimal solutions and significantly outperform existing algorithms in terms of the ratio of the long-term average revenue over the VN request acceptance.