A forwarding graph embedding algorithm exploiting regional topology information

Hong-chao HU; Fan ZHANG; Yu-xing MAO; Zhen-peng WANG

doi:10.1631/FITEE.1601404

Your Location：

Home >

Browse articles >

A forwarding graph embedding algorithm exploiting regional topology information

Regular Papers | Updated：2022-05-19

- A forwarding graph embedding algorithm exploiting regional topology information
- 一种基于区域拓扑信息的转发图映射算法
- Frontiers of Information Technology & Electronic Engineering Vol. 18, Issue 11, Pages: 1854-1866(2017)
- Affiliations：
  
  National Digital Switching System Engineering & Technological R & D Center, Zhengzhou 450002, China
- Author bio：
  
  Hong-chao HU, E-mail: huhongchao@gmail.com
- Funds：
- DOI：10.1631/FITEE.1601404
  CLC： TP393
- Received：08 July 2016，
  
  Revised：2017-11-24，
  
  Published：2017-11
- Accepted：
Scan QR Code
Hong-chao HU, Fan ZHANG, Yu-xing MAO, et al. A forwarding graph embedding algorithm exploiting regional topology information[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(11): 1854-1866.
DOI：

Hong-chao HU, Fan ZHANG, Yu-xing MAO, et al. A forwarding graph embedding algorithm exploiting regional topology information[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(11): 1854-1866. DOI： 10.1631/FITEE.1601404.

摘要

转网络功能虚拟化（network function virtualization

NFV）是近年提出一种用于动态和有效地构建和管理网络功能的新技术。如何为虚拟网络功能的转发图分配资源是NFV研究中的关键难题之一。本文将转发图映射（forwarding graph embedding

FGE）问题建模为0-1整数规划问题，旨在增加服务提供商的收益并降低开销，同时满足受限资源和虚拟功能需要的约束。接着，设计了量化每个底层节点嵌入潜力的新型区域资源聚类指标，并提出基于拓扑感知的转发图映射算法，即基于区域资源聚类的转发图算法（regional resour cecluster-FGE

RRC-FGE）。最后，通过C++语言实现了该算法，仿真结果表明：服务提供商的收益增加了50多个单位，接受率提高了15%以上，同时成本下降了60多个单位。

Abstract

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.

关键词

Keywords

references

P. Bellavista , , , F. Callegati , , , W. Cerroni , , , 等 . . Virtual network function embedding in real cloud environments . . Comput. Netw. , , 2015 . . 93 ( ( 3 ): ): 506 - - 517 . . DOI: 10.1016/j.comnet.2015.09.034 http://doi.org/10.1016/j.comnet.2015.09.034 . .

S. Bhatia , , , M. Motiwala , , , W. Muhlbauer , , , 等 . . Hosting Virtual Networks on Commodity Hardware . . Technical Report, No. GT-CS-07-10. Georgia Institute of Tech-nology, PA , , 2008 . . .

D. Chen , , , L. Lu , , , M. Shang , , , 等 . . Identifying influential nodes in complex networks . . Phys. A. , , 2012 . . 391 ( ( 4 ): ): 1777 - - 1787 . . DOI: 10.1016/j.physa.2011.09.017 http://doi.org/10.1016/j.physa.2011.09.017 . .

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 . .

M. Chowdhury , , , M. Rahman , , , R. Boutaba , , , 等 . . Vineyard: virtual network embedding algorithms with coordinated node and link mapping . . IEEE/ACM Trans. Netw. , , 2009 . . 20 ( ( 1 ): ): 206 - - 219 . . DOI: 10.1109/TNET.2011.2159308 http://doi.org/10.1109/TNET.2011.2159308 . .

D. Eppstein . . Finding the K shortest paths . . SIAM J. Comput. , , 1998 . . 28 ( ( 2 ): ): 652 - - 673 . . DOI: 10.1137/S0097539795290477 http://doi.org/10.1137/S0097539795290477 . .

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

G. Fagiolo . . Clustering in complex directed networks . . Phys. Rev. E , , 2007 . . 76 ( ( 2 ): ): 12 - - 23 . . DOI: 10.1103/PhysRevE.76.026107 http://doi.org/10.1103/PhysRevE.76.026107 . .

J. Fan , , , M. Ammar . . Dynamic topology configuration in service overlay networks: a study of reconfiguration policies . . Proc. 25th IEEE Int. Conf. on Computer Com-munications , , 2006 . . p.21 - - 32 . . DOI: 10.1109/INFOCOM.2006.139 http://doi.org/10.1109/INFOCOM.2006.139 . .

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

L. Gong , , , Y. Wen , , , Z. Zhu , , , 等 . . Toward profit-seeking virtual network embedding algorithm via global resource capacity . . Proc. IEEE Int. Conf. on Computer Communi-cations , , 2014 . . p.1 - - 9 . . DOI: 10.1109/INFOCOM.2014.6847918 http://doi.org/10.1109/INFOCOM.2014.6847918 . .

Y. Koh , , , R. Knauerhase , , , P. Brett , , , 等 . . An analysis of performance interference effects in virtual environments . . Proc. IEEE Int. Symp. on Performance Analysis of Sys-tems & Software , , 2007 . . p.200 - - 209 . . DOI: 10.1109/ISPASS.2007.363750 http://doi.org/10.1109/ISPASS.2007.363750 . .

J. Lischka , , , H. Karl . . A virtual network mapping algorithm based on subgraph isomorphism detection . . Proc. 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures , , 2009 . . p.81 - - 88 . . DOI: 10.1145/1592648.1592662 http://doi.org/10.1145/1592648.1592662 . .

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

S. Mehraghdam , , , M. Keller , , , H. Karl , , , 等 . . Specifying and placing chains of virtual network functions . . Proc. 3rd IEEE Int. Conf. on Cloud Networking , , 2014 . . p.7 - - 13 . . DOI: 10.1109/CloudNet.2014.6968961 http://doi.org/10.1109/CloudNet.2014.6968961 . .

Y. Mei , , , L. Liu , , , X. Pu , , , 等 . . Performance analysis of network I/O workloads in virtualized data centers . . IEEE Trans. Serv. Comput. , , 2013 . . 6 ( ( 1 ): ): 48 - - 63 . . DOI: 10.1109/TSC.2011.36 http://doi.org/10.1109/TSC.2011.36 . .

X. Pu , , , L. Liu , , , Y. Mei , , , 等 . . Understanding performance interference of I/O workload in virtualized cloud environment . . Proc. 3rd IEEE Int. Conf. on Cloud Com-puting , , 2010 . . p.51 - - 58 . . DOI: 10.1109/CLOUD.2010.65 http://doi.org/10.1109/CLOUD.2010.65 . .

A. Razzaq , , , Rathore M. Siraj . . An approach towards resource efficient virtual network embedding . . Proc. 2nd Int. Conf. on Evolving Internet , , 2010 . . p.68 - - 73 . . DOI: 10.1109/INTERNET.2010.21 http://doi.org/10.1109/INTERNET.2010.21 . .

R. Shea , , , F. Wang , , , H. Wang , , , 等 . . A deep investigation into network performance in virtual machine based cloud environments . . Proc. IEEE Int. Conf. on Computer Communications , , 2014 . . p.1285 - - 1293 . . DOI: 10.1109/INFOCOM.2014.6848061 http://doi.org/10.1109/INFOCOM.2014.6848061 . .

S. Su , , , Z. Zhang , , , X. Cheng , , , 等 . . Energy-aware virtual network embedding through consolidation . . Proc. IEEE Int. Conf. on Computer Communications Workshops , , 2012 . . p.127 - - 132 . . DOI: 10.1109/INFCOMW.2012.6193473 http://doi.org/10.1109/INFCOMW.2012.6193473 . .

Z. Wang , , , J. Wu , , , Y. Wang , , , 等 . . Survivable virtual network mapping using optimal backup topology in vir-tualized SDN . . China Commun. , , 2014 . . 11 ( ( 2 ): ): 26 - - 37 . . DOI: 10.1109/CC.2014.6821735 http://doi.org/10.1109/CC.2014.6821735 . .

S. Xia , , , Y. Zhang , , , H. Green , , , 等 . . Network function placement for NFV chaining in packet/optical data centers . . Proc. European Conf. on Optical Communication , , 2014 . . p.1 - - 3 . . DOI: 10.1109/ECOC.2014.6963925 http://doi.org/10.1109/ECOC.2014.6963925 . .

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

S. Zhang , , , Z. Qian , , , J. Wu , , , 等 . . An opportunistic resource sharing and topology-aware mapping framework for virtual networks . . Proc. IEEE Int. Conf. on Computer Communications , , 2012 . . p.2408 - - 2416 . . DOI: 10.1109/INFCOM.2012.6195630 http://doi.org/10.1109/INFCOM.2012.6195630 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

A virtual service placement approach based on improved quantum genetic algorithm

Related Author

Gang XIONG

Yu-xiang HU

Le TIAN

Ju-long LAN

Jun-fei LI

Qiao ZHOU

Related Institution

National Digital Switching System Engineering & Technological Research Center

Department of Mathematics and Computer Science, University of Antwerp, Antwerp

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.

⁰