一种基于区域拓扑信息的转发图映射算法

扈红超; 张帆; 毛宇星; 王祯鹏

doi:10.1631/FITEE.1601404

Your Location：

Home >

Browse articles >

一种基于区域拓扑信息的转发图映射算法

常规文章 | Updated：2022-05-19

- 一种基于区域拓扑信息的转发图映射算法
- A forwarding graph embedding algorithm exploiting regional topology information
- 信息与电子工程前沿（英文） 2017年18卷第11期页码：1854-1866
- Affiliations：
  
  National Digital Switching System Engineering & Technological R & D Center, Zhengzhou 450002, China
- Author bio：
  
  Hong-chao HU, E-mail: huhongchao@gmail.com
- Funds：
  
  Project supported by the National Natural Science Foundation of China (Nos. 61309020 and 61521003)
- DOI：10.1631/FITEE.1601404
  中图分类号： TP393
- 收稿：2016-07-08，
  
  修回：2017-11-24，
  
  纸质出版：2017-11
- Accepted：
Scan QR Code
扈红超, 张帆, 毛宇星, 等. 一种基于区域拓扑信息的转发图映射算法[J]. 信息与电子工程前沿（英文）, 2017,18(11):1854-1866.

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.
扈红超, 张帆, 毛宇星, 等. 一种基于区域拓扑信息的转发图映射算法[J]. 信息与电子工程前沿（英文）, 2017,18(11):1854-1866. DOI： 10.1631/FITEE.1601404.

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

浏览量

Downloads

CSCD

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

Submit

工具集

关联资源

A virtual service placement approach based on improved quantum genetic algorithm