Full Text:   <727>

Summary:  <149>

CLC number: TP393

On-line Access: 2018-01-12

Received: 2016-07-08

Revision Accepted: 2016-11-10

Crosschecked: 2017-11-24

Cited: 0

Clicked: 1820

Citations:  Bibtex RefMan EndNote GB/T7714


Hong-chao Hu


-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2017 Vol.18 No.11 P.1854-1866


A forwarding graph embedding algorithm exploiting regional topology information

Author(s):  Hong-chao Hu, Fan Zhang, Yu-xing Mao, Zhen-peng Wang

Affiliation(s):  National Digital Switching System Engineering & Technological R&D Center, Zhengzhou 450002, China

Corresponding email(s):   huhongchao@gmail.com

Key Words:  Network function virtualization, Virtual network function, Forwarding graph embedding

Hong-chao Hu, Fan Zhang, Yu-xing Mao, Zhen-peng Wang. A forwarding graph embedding algorithm exploiting regional topology information[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(11): 1854-1866.

@article{title="A forwarding graph embedding algorithm exploiting regional topology information",
author="Hong-chao Hu, Fan Zhang, Yu-xing Mao, Zhen-peng Wang",
journal="Frontiers of Information Technology & Electronic Engineering",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T A forwarding graph embedding algorithm exploiting regional topology information
%A Hong-chao Hu
%A Fan Zhang
%A Yu-xing Mao
%A Zhen-peng Wang
%J Frontiers of Information Technology & Electronic Engineering
%V 18
%N 11
%P 1854-1866
%@ 2095-9184
%D 2017
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1601404

T1 - A forwarding graph embedding algorithm exploiting regional topology information
A1 - Hong-chao Hu
A1 - Fan Zhang
A1 - Yu-xing Mao
A1 - Zhen-peng Wang
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 18
IS - 11
SP - 1854
EP - 1866
%@ 2095-9184
Y1 - 2017
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1601404

network function virtualization (NFV) is a newly proposed technique designed to construct and manage network functions dynamically and efficiently. Allocating physical resources to the virtual network function forwarding graph is a critical issue in NFV. We formulate the forwarding graph embedding (FGE) problem as a binary integer programming problem, which aims to increase the revenue and decrease the cost to a service provider (SP) while considering limited network resources and the requirements of virtual functions. We then design a novel regional resource clustering metric to quantify the embedding potential of each substrate node and propose a topology-aware FGE algorithm called ‘regional resource clustering FGE’ (RRC-FGE). After implementing our algorithms in C++, simulation results showed that the total revenue was increased by more than 50 units and the acceptance ratio by more than 15%, and the cost of the service provider was decreased by more than 60 units.


概要:转网络功能虚拟化(network function virtualization, NFV)是近年提出一种用于动态和有效地构建和管理网络功能的新技术。如何为虚拟网络功能的转发图分配资源是NFV研究中的关键难题之一。本文将转发图映射(forwarding graph embedding, FGE)问题建模为0-1整数规划问题,旨在增加服务提供商的收益并降低开销,同时满足受限资源和虚拟功能需要的约束。接着,设计了量化每个底层节点嵌入潜力的新型区域资源聚类指标,并提出基于拓扑感知的转发图映射算法,即基于区域资源聚类的转发图算法(regional resour cecluster-FGE, RRC-FGE)。最后,通过C++语言实现了该算法,仿真结果表明:服务提供商的收益增加了50多个单位,接受率提高了15%以上,同时成本下降了60多个单位。


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


[1]Bellavista, P., Callegati, F., Cerroni, W., et al., 2015. Virtual network function embedding in real cloud environments. Comput. Netw., 93(3):506-517.

[2]Bhatia, S., Motiwala, M., Muhlbauer, W., et al., 2008. Hosting Virtual Networks on Commodity Hardware. Technical Report, No. GT-CS-07-10. Georgia Institute of Technology, PA.

[3]Chen, D., Lu, L., Shang, M., et al., 2012. Identifying influential nodes in complex networks. Phys. A., 391(4):1777-1787.

[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]Chowdhury, M., Rahman, M., Boutaba, R., et al., 2009. Vineyard: virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Trans. Netw., 20(1):206-219.

[6]Eppstein, D., 1998. Finding the K shortest paths. SIAM J. Comput., 28(2):652-673.

[7]ETSI NFVISG (European Telecommunications Standards Institute Network Functions Virtualization Industry Specification Group), 2013. Network Functions Virtualization, White Paper. http://www.esti.org/technologiescluster/technologies/nfv [Accessed on Nov. 2, 2016].

[8]Fagiolo, G., 2007. Clustering in complex directed networks. Phys. Rev. E, 76(2):12-23.

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

[10]Goldberg, D., 2009. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Professional, USA, p.216-236.

[11]Gong, L., Wen, Y., Zhu, Z., et al., 2014. Toward profit-seeking virtual network embedding algorithm via global resource capacity. Proc. IEEE Int. Conf. on Computer Communications, p.1-9.

[12]Koh, Y., Knauerhase, R., Brett, P., et al., 2007. An analysis of performance interference effects in virtual environments. Proc. IEEE Int. Symp. on Performance Analysis of Systems & Software, p.200-209.

[13]Lischka, J., Karl, H., 2009. A virtual network mapping algorithm based on subgraph isomorphism detection. Proc. 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures, p.81-88.

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

[15]Mehraghdam, S., Keller, M., Karl, H., et al., 2014. Specifying and placing chains of virtual network functions. Proc. 3rd IEEE Int. Conf. on Cloud Networking, p.7-13.

[16]Mei, Y., Liu, L., Pu, X., et al., 2013. Performance analysis of network I/O workloads in virtualized data centers. IEEE Trans. Serv. Comput., 6(1):48-63.

[17]Pu, X., Liu, L., Mei, Y., et al., 2010. Understanding performance interference of I/O workload in virtualized cloud environment. Proc. 3rd IEEE Int. Conf. on Cloud Computing, p.51-58.

[18]Razzaq, A., Siraj Rathore, M., 2010. An approach towards resource efficient virtual network embedding. Proc. 2nd Int. Conf. on Evolving Internet, p.68-73.

[19]Shea, R., Wang, F., Wang, H., et al., 2014. A deep investigation into network performance in virtual machine based cloud environments. Proc. IEEE Int. Conf. on Computer Communications, p.1285-1293.

[20]Su, S., Zhang, Z., Cheng, X., et al., 2012. Energy-aware virtual network embedding through consolidation. Proc. IEEE Int. Conf. on Computer Communications Workshops, p.127-132.

[21]Wang, Z., Wu, J., Wang, Y., et al., 2014. Survivable virtual network mapping using optimal backup topology in virtualized SDN. China Commun., 11(2):26-37.

[22]Xia, S., Zhang, Y., Green, H., et al., 2014. Network function placement for NFV chaining in packet/optical data centers. Proc. European Conf. on Optical Communication, p.1-3.

[23]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., 32(2):17-29.

[24]Zhang, S., Qian, Z., Wu, J., et al., 2012. An opportunistic resource sharing and topology-aware mapping framework for virtual networks. Proc. IEEE Int. Conf. on Computer Communications, p.2408-2416.

Open peer comments: Debate/Discuss/Question/Opinion


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