基于实时拓扑属性的虚拟网络映射算法

Ding Jian; Huang Tao; Liu Jiang; Liu Yun-jie

doi:10.1631/FITEE.1400147

Your Location：

Home >

Browse articles >

基于实时拓扑属性的虚拟网络映射算法

计算机与自动化 | Updated：2022-06-06

- 基于实时拓扑属性的虚拟网络映射算法
- Virtual network embedding based on real-time topological attributes*
- 信息与电子工程前沿（英文） 2015年16卷第2期页码：109-118
- Affiliations：
  
  State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
- Author bio：
  
  †E-mail:buptsky@gmail.com
- Funds：
  
  *Project supported by the National Basic Research Program (973) of China (No. 2012CB315801), the National Natural Science Foundation of China (Nos. 61302089 and 61300184), and the Fundamental Research Funds for the Central Universities, China (No. 2013RC0113)
- DOI：10.1631/FITEE.1400147
  中图分类号：
- 收稿：2014-04-23，
  
  修回：2015-01-05，
  
  录用：2014-09-08，
  
  纸质出版：2015-02
- Accepted：
Scan QR Code
基于实时拓扑属性的虚拟网络映射算法[J]. 信息与电子工程前沿（英文）, 2015,16(2):109-118.

Ding Jian, Huang Tao, Liu Jiang, et al. Virtual network embedding based on real-time topological attributes*[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(2): 109-118.
基于实时拓扑属性的虚拟网络映射算法[J]. 信息与电子工程前沿（英文）, 2015,16(2):109-118. DOI： 10.1631/FITEE.1400147.

Ding Jian, Huang Tao, Liu Jiang, et al. Virtual network embedding based on real-time topological attributes*[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(2): 109-118. DOI： 10.1631/FITEE.1400147.

摘要

目的

基于虚拟网络请求和底层物理网络实时拓扑属性，提出一种高效的两步式虚拟网络映射算法。

创新

分别利用中介中心性和物理节点相关性对虚拟网络请求和底层物理网络中节点进行重要性评估，在此基础上给出一种两步式映射算法（算法1

2）。

方法

首先给出中间中心性、接近中心性以及节点相关性计算模型，结合节点本地资源分别提出虚拟网络请求和物理网络中节点排名计算方式。当虚拟网络请求到达后，根据虚拟节点排名，将其映射到拥有足够资源的物理节点中排名最靠前的节点。节点映射完成后，使用

-th最短路径算法进行链路映射。映射过程中采用文献（Yu

et al

2008）中所使用的时间窗口模式进行接入控制。

结论

利用节点本地资源，针对性分析虚拟网络请求和物理网络实时拓扑属性，提出两步式映射算法。该算法提高请求接受率、开销收益比的同时减少算法映射时间，取得更好的映射效果（图3-10）。

Abstract

As a great challenge of network virtualization

virtual network embedding/mapping is increasingly important. It aims to successfully and efficiently assign the nodes and links of a virtual network (VN) onto a shared substrate network. The problem has been proved to be NP-hard and some heuristic algorithms have been proposed. However

most of the algorithms use only the local information of a node

such as CPU capacity and bandwidth

to determine how to map a VN

without considering the topological attributes which may pose significant impact on the performance of the embedding. In this paper

a new embedding algorithm is proposed based on real-time topological attributes. The concept of betweenness centrality in graph theory is borrowed to sort the nodes of VNs

and the nodes of the substrate network are sorted according to the correlation properties between the former selected and unselected nodes. In this way

node mapping and link mapping can be well coupled. A simulator is built to evaluate the performance of the proposed virtual network embedding (VNE) algorithm. The results show that the new algorithm significantly increases the revenue/cost (R/C) ratio and acceptance ratio as well as reduces the runtime.

关键词

Keywords

references

DG Andersen . Theoretical Approaches to Node Assignment , 2002 . Sept. 20, 2010 Available from http://www.cs.cmu.edu/~dga/papers/andersen-assign.ps http://www.cs.cmu.edu/~dga/papers/andersen-assign.ps .

T Anderson , L Peterson , S Shenker , 等 . Overcoming the Internet impasse through virtualization . IEEE Comput Mag , 2005 . 38 ( 4 ): 34 - 41 . .

A Bavier , N Feamster , M Huang , 等 . In VINI veritas: realistic and controlled network experimentation . ACM SIGCOMM Comput Commun Rev , 2006 . 36 ( 4 ): 3 - 14 . DOI: 10.1145/1151659.1159916 http://doi.org/10.1145/1151659.1159916 .

X Cheng , S Su , Z Zhang , 等 . Virtual network embedding through topology-aware node ranking . ACM SIGCOMM Comput Commun Rev , 2011 . 41 ( 2 ): 38 - 47 . DOI: 10.1145/1971162.1971168 http://doi.org/10.1145/1971162.1971168 .

X Cheng , S Su , Z Zhang , 等 . Virtual network embedding through topology awareness and optimization . Comput Netw , 2012 . 56 ( 6 ): 1797 - 1813 . DOI: 10.1016/j.comnet.2012.01.022 http://doi.org/10.1016/j.comnet.2012.01.022 .

NMMK Chowdhury , MR Rahman , R Boutaba . Virtual network embedding with coordinated node and link mapping . 2009 . Proc. 28th IEEE Int. Conf. on Computer Communications . 783 - 791 . DOI: 10.1109/INFCOM.2009.5061987 http://doi.org/10.1109/INFCOM.2009.5061987 .

J Fan , MH Ammar . Dynamic topology configuration in service overlay networks: a study of reconfiguration policies . 2006 . Proc. 25th IEEE Int. Conf. on Computer Communications . 1 - 12 . DOI: 10.1109/INFOCOM.2006.139 http://doi.org/10.1109/INFOCOM.2006.139 .

A Fischer , JF Botero , M Till Beck , 等 . Virtual network embedding: a survey . IEEE Commun Surv Tutor , 2013 . 15 ( 4 ): 1888 - 1906 . DOI: 10.1109/SURV.2013.013013.11055 http://doi.org/10.1109/SURV.2013.013013.11055 .

XL Li , HM Wang , CG Guo , 等 . Topology awareness algorithm for virtual network mapping . J Zhejiang Univ-Sci C (Comput & Electron) , 2012 . 13 ( 3 ): 178 - 186 . DOI: 10.1631/jzus.C1100282 http://doi.org/10.1631/jzus.C1100282 .

J Liu , T Huang , JY Chen , 等 . A new algorithm based on the proximity principle for the virtual network embedding problem . J Zhejiang Univ-Sci C (Comput & Electron) , 2011 . 12 ( 11 ): 910 - 918 . DOI: 10.1631/jzus.C1100003 http://doi.org/10.1631/jzus.C1100003 .

J Lu , J Turner . Efficient Mapping of Virtual Networks onto a Shared Substrate . Technical Report No. WUCSE-2006-35 , 2006 . : USA Washington University , .

R Ricci , C Alfeld , J Lepreau . A solver for the network testbed mapping problem . ACM SIGCOMM Comput Commun Rev , 2003 . 33 ( 2 ): 65 - 81 . DOI: 10.1145/956981.956988 http://doi.org/10.1145/956981.956988 .

Z Wang , Y Han , T Lin , 等 . Virtual network embedding by exploiting topological information . 2012 . Proc. IEEE Global Communications Conf. . 2603 - 2608 . DOI: 10.1109/GLOCOM.2012.6503509 http://doi.org/10.1109/GLOCOM.2012.6503509 .

M Yu , Y Yi , J Rexford , 等 . Rethinking virtual network embedding: substrate support for path splitting and migration . ACM SIGCOMM Comput Commun Rev , 2008 . 38 ( 2 ): 17 - 29 . DOI: 10.1145/1355734.1355737 http://doi.org/10.1145/1355734.1355737 .

EW Zegura , KL Calvert , S Bhattacharjee . How to model an internetwork . 1996 . Proc. IEEE 15th Annual Conf. on Computer Communications Jointly with the IEEE Computer and Communications Societies . 594 - 602 . DOI: 10.1109/INFCOM.1996.493353 http://doi.org/10.1109/INFCOM.1996.493353 .

Y Zhu , M Ammar . Algorithms for assigning substrate network resources to virtual network components . 2006 . Proc. 25th IEEE Int. Conf. on Computer Communications . 1 - 12 . DOI: 10.1109/INFOCOM.2006.322 http://doi.org/10.1109/INFOCOM.2006.322 .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

An efficient and coordinated mapping algorithm in virtualized SDN networks

Performance improvement for applying network virtualization in fiber-wireless (FiWi) access networks