Full Text:   <1615>

Summary:  <756>

CLC number: TP393

On-line Access: 2015-01-29

Received: 2014-04-23

Revision Accepted: 2014-09-08

Crosschecked: 2015-01-05

Cited: 7

Clicked: 3277

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Jiang LIU

http://orcid.org/0000-0002-0729-1299

Jian Ding

http://orcid.org/0000-0002-9147-8119

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2015 Vol.16 No.2 P.109-118

http://doi.org/10.1631/FITEE.1400147


Virtual network embedding based on real-time topological attributes


Author(s):  Jian Ding, Tao Huang, Jiang Liu, Yun-jie Liu

Affiliation(s):  State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Corresponding email(s):   buptsky@gmail.com

Key Words:  Virtual network embedding (VNE), Real-time topological attributes, Betweenness centrality, Correlation properties, Network virtualization


Jian Ding, Tao Huang, Jiang Liu, Yun-jie Liu. Virtual network embedding based on real-time topological attributes[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(2): 109-118.

@article{title="Virtual network embedding based on real-time topological attributes",
author="Jian Ding, Tao Huang, Jiang Liu, Yun-jie Liu",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="16",
number="2",
pages="109-118",
year="2015",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1400147"
}

%0 Journal Article
%T Virtual network embedding based on real-time topological attributes
%A Jian Ding
%A Tao Huang
%A Jiang Liu
%A Yun-jie Liu
%J Frontiers of Information Technology & Electronic Engineering
%V 16
%N 2
%P 109-118
%@ 2095-9184
%D 2015
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1400147

TY - JOUR
T1 - Virtual network embedding based on real-time topological attributes
A1 - Jian Ding
A1 - Tao Huang
A1 - Jiang Liu
A1 - Yun-jie Liu
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 16
IS - 2
SP - 109
EP - 118
%@ 2095-9184
Y1 - 2015
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1400147


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.

Generally, this paper is a good contribution to the virtual network embedding problem because it is the first time that the topological attributes: betweenness and closeness centrality are included to solve the problem.

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

目的:基于虚拟网络请求和底层物理网络实时拓扑属性,提出一种高效的两步式虚拟网络映射算法。
创新:分别利用中介中心性和物理节点相关性对虚拟网络请求和底层物理网络中节点进行重要性评估,在此基础上给出一种两步式映射算法(算法1,2)。
方法:首先给出中间中心性、接近中心性以及节点相关性计算模型,结合节点本地资源分别提出虚拟网络请求和物理网络中节点排名计算方式。当虚拟网络请求到达后,根据虚拟节点排名,将其映射到拥有足够资源的物理节点中排名最靠前的节点。节点映射完成后,使用K-th最短路径算法进行链路映射。映射过程中采用文献(Yu et al.,2008)中所使用的时间窗口模式进行接入控制。
结论:利用节点本地资源,针对性分析虚拟网络请求和物理网络实时拓扑属性,提出两步式映射算法。该算法提高请求接受率、开销收益比的同时减少算法映射时间,取得更好的映射效果(图3-10)。

关键词:虚拟网络映射;实时拓扑属性;中介中心性;相关性;网络虚拟化

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Andersen, D.G., 2002. Theoretical Approaches to Node Assignment. Available from http://www.cs.cmu.edu/~dga/ papers/andersen-assign.ps [Accessed on Sept. 20, 2010].

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

[3]Bavier, A., Feamster, N., Huang, M., et al., 2006. In VINI veritas: realistic and controlled network experimentation. ACM SIGCOMM Comput. Commun. Rev., 36(4):3-14.

[4]Cheng, X., Su, S., Zhang, Z., et al., 2011. Virtual network embedding through topology-aware node ranking. ACM SIGCOMM Comput. Commun. Rev., 41(2):38-47.

[5]Cheng, X., Su, S., Zhang, Z., et al., 2012. Virtual network embedding through topology awareness and optimization. Comput. Netw., 56(6):1797-1813.

[6]Chowdhury, N.M.M.K., Rahman, M.R., Boutaba, R., 2009. Virtual network embedding with coordinated node and link mapping. Proc. 28th IEEE Int. Conf. on Computer Communications, p.783-791.

[7]Fan, J., Ammar, M.H., 2006. Dynamic topology configuration in service overlay networks: a study of reconfiguration policies. Proc. 25th IEEE Int. Conf. on Computer Communications, p.1-12.

[8]Fischer, A., Botero, J.F., Till Beck, M., et al., 2013. Virtual network embedding: a survey. IEEE Commun. Surv. Tutor., 15(4):1888-1906.

[9]Li, X.L., Wang, H.M., Guo, C.G., et al., 2012. Topology awareness algorithm for virtual network mapping. J. Zhejiang Univ.-Sci. C (Comput. & Electron.), 13(3):178-186.

[10]Liu, J., Huang, T., Chen, J.Y., et al., 2011. A new algorithm based on the proximity principle for the virtual network embedding problem. J. Zhejiang Univ.-Sci. C (Comput. & Electron.), 12(11):910-918.

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

[12]Ricci, R., Alfeld, C., Lepreau, J., 2003. A solver for the network testbed mapping problem. ACM SIGCOMM Comput. Commun. Rev., 33(2):65-81.

[13]Wang, Z., Han, Y., Lin, T., et al., 2012. Virtual network embedding by exploiting topological information. Proc. IEEE Global Communications Conf., p.2603-2608.

[14]Yu, M., Yi, Y., Rexford, J., et al., 2008. Rethinking virtual network embedding: substrate support for path splitting and migration. ACM SIGCOMM Comput. Commun. Rev., 38(2):17-29.

[15]Zegura, E.W., Calvert, K.L., Bhattacharjee, S., 1996. How to model an internetwork. Proc. IEEE 15th Annual Conf. on Computer Communications Jointly with the IEEE Computer and Communications Societies, p.594-602.

[16]Zhu, Y., Ammar, M., 2006. Algorithms for assigning substrate network resources to virtual network components. Proc. 25th IEEE Int. Conf. on Computer Communications, p.1-12.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE