Virtual network embedding based on real-time topological attributes*

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

doi:10.1631/FITEE.1400147

Your Location：

Home >

Browse articles >

Virtual network embedding based on real-time topological attributes*

Computer & Automation | Updated：2022-06-06

- Virtual network embedding based on real-time topological attributes*
- 基于实时拓扑属性的虚拟网络映射算法
- Frontiers of Information Technology & Electronic Engineering Vol. 16, Issue 2, Pages: 109-118(2015)
- 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：
- DOI：10.1631/FITEE.1400147
  CLC：
- Received：23 April 2014，
  
  Revised：2015-01-05，
  
  Accepted：08 September 2014，
  
  Published：2015-02
- Accepted：
Scan QR Code
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：

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 .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

An efficient and coordinated mapping algorithm in virtualized SDN networks

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

Related Author

Shui-qing GONG

Jing CHEN

Qiao-yan KANG

Qing-wei MENG

Qing-chao ZHU

Si-yi ZHAO

Qing-long DAI

Guo-chu SHOU

Related Institution

College of Information and Navigation, Air Force Engineering University

Beijing Laboratory of Network System Architecture and Convergence, School of Information and Communication Engineering, Beijing University of Posts and Telecommunications

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰