基于链路优先的快速协同虚拟网络映射算法

doi:10.11959/j.issn.1000-436x.2015063

通信学报 ›› 2015, Vol. 36 ›› Issue (3): 95-103.doi: 10.11959/j.issn.1000-436x.2015063

基于链路优先的快速协同虚拟网络映射算法

熊文成,王颖,邱雪松,李文璟

北京邮电大学网络与交换技术国家重点实验室，北京 100876

出版日期:2015-03-25 发布日期:2017-06-21
基金资助:
国家高技术研究发展计划（“863”计划）基金资助项目;国家自然科学基金资助项目;中央高校基本科研业务费专项基金资助项目

Link-first based quick coordinated virtual network embedding algorithm

Wen-cheng XIONG,Ying WANG,Xue-song QIU,Wen-jing LI

State Key Lab of Networking and Switching, Beijing University of Posts and Telecommunications, Beijing 100876, China

Online:2015-03-25 Published:2017-06-21
Supported by:
The National High Technology Research and Development Program of China (863 Program);The National Natural Science Foundation of China;Fundamental Research Funds for the Central Universities

摘要/Abstract

摘要：

在网络虚拟化环境中，为了减少链路映射成本和提高收益，提出了一种链路优先的协同映射算法。该算法交替映射链路和节点，并使用贪心思想优先将带宽资源需求较大的虚拟链路映射到跳数较少的物理路径上，最终达到降低虚拟网络平均消耗和提高虚拟网络接受率的目的。仿真结果表明，与已有算法相比，所提算法节约了链路映射的成本，提高了虚拟网络接受率和物理网络收益，算法运行时间也有效缩短。

关键词: 网络虚拟化, 虚拟网络映射算法, 链路优先, 资源评估, 接受率, 低消耗

Abstract:

In order to reduce costs of link embedding and increase revenue, a coordinated embedding algorithm based on link-first is proposed. The algorithm embeds link and node alternately, and embeds the virtual link that with greater band-width requirement first to the physical path that with fewer link hops by using the greedy method, and ultimately aims at re-ducing average costs of virtual network embedding and improving acceptance rate of virtual network. Simulation results show that, compared with the existing algorithms, this embedding algorithm saves link cost significantly, improves accep-tance rate of virtual network and revenue of the physical network, and can effectively shorten the running time.

Key words: network virtualization, virtual network embedding algorithm, link first, resource assessment, acceptance rate, low cost

熊文成,王颖,邱雪松,李文璟. 基于链路优先的快速协同虚拟网络映射算法[J]. 通信学报, 2015, 36(3): 95-103.

Wen-cheng XIONG,Ying WANG,Xue-song QIU,Wen-jing LI. Link-first based quick coordinated virtual network embedding algorithm[J]. Journal on Communications, 2015, 36(3): 95-103.

图/表 13

图1

表1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

参考文献 13

[1]	ANDERSON T , PETERSON L , SHENKER S , et al. Overcoming the Internet impasse through virtualization[J]. Computer, 2005,38(4):34-41.
[2]	FEAMSTER N , GAO L , REXFORD J . How to lease the Internet in your spare time[J]. ACM SIGCOMM Computer Communication Review, 2007,37(1):61-64.
[3]	CHOWDHURY N M , BOUTABA R . A survey of network virtualization[J]. Computer Networks, 2010,54(5):862-876.
[4]	YU M , YI Y , REXFORD J , et al. Rethinking virtual network embed-ding: substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008,38(2):17-29.
[5]	CHOWDHURY N M M K , RAHMAN M R , BOUTABA R , et al. Virtual network embedding with coordinated node and link mapping[A]. IN-FOCOM 2009[C].IEEE, 2009.783-791.
[6]	FISCHER A , BOTERO J , BECK M , et al. Virtual network embedding:a survey[J]. Browse Journals ＆ Magazines, 2013,15(4):1888-1906.
[7]	CHOWDHURY M , RAHMAN M R , BOUTABA R . ViNEYard:Virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE ACM Transactions on Networking (TON), 2012,20(1):206-219.
[8]	BUTT N F , CHOWDHURY M , BOUTABA R . Topology-awareness and reoptimization mechanism for virtual network embedding[M]. Springer: Berlin Heidelberg, 2010.
[9]	CHENG X , SU S , ZHANG Z , et al. Virtual network embedding through topology-aware node ranking[J]. ACM SIGCOMM Computer Communication Review, 2011,41(2):38-47.
[10]	ZHANG S , QIU X . A novel virtual network mapping algorithm for cost minimizing[J]. Cyber Journals: Journal of Selected Areas in Telecommunications (JSAT), 2011.
[11]	BAVIER A , FEAMSTER N , HUANG M , et al. In VINI veritas:real-istic and controlled network experimentation[A]. ACM SIGCOMM Computer Communication Review[C].ACM, 2006,36(4):3-14.
[12]	ZEGURA E W , CALVERT K L , BHATTACHARJEE S . How to model an internetwork[A]. Fifteenth Annual Joint Conference of the IEEE Computer Societies Networking the Next Generation[C]. 1996,2:594-602.
[13]	AHUJA R K , MAGNANTI T L , ORLIN J B . Network flows: theory, algorithms, and applications[M]. Library of Gangers Cataloging-in publication Data[C]. 1993.

符号	含义
G^S	物理网络
N^S,L^S	物理节点集合，物理链路集合
	物理节点的属性，表示节点n^S的可用计算能力
	物理链路的属性，表示链路l^S 的可用带宽
G^V	虚拟网络
N^V,L^V	虚拟节点集合，虚拟链路集合
	虚拟节点的需求，表示节点n^V 的计算能力需求
	虚拟链路的需求，表示虚拟链路l^V 的带宽需求
N_u,L_u	未映射的虚拟节点集合和未映射的虚拟链路集合
N_m,L_m	已映射的虚拟节点集合和已映射的虚拟链路集合

[1]	王汝言,高毅爽,陈霄. 带有区分保护的虚拟化FiWi网络可靠传输机制[J]. 通信学报, 2019, 40(3): 36-47.
[2]	王汝言,徐宁宁. 带有混合能量供电的TWDM-PON与C-RAN联合架构资源分配机制[J]. 通信学报, 2018, 39(9): 94-109.
[3]	黄韬,刘江,张晨,魏亮,刘韵洁. 基于SDN的网络试验床综述[J]. 通信学报, 2018, 39(6): 155-168.
[4]	王健,赵国生,李志新. 面向SDN的虚拟网络映射算法研究[J]. 通信学报, 2017, 38(10): 26-35.
[5]	曹傧,夏士超,何芳,李云. 无线网络虚拟化中的映射算法研究[J]. 通信学报, 2017, 38(1): 35-43.
[6]	刘光远,安秀芳,苏森. 基于节点可靠性感知和共享路径保护的虚拟网映射算法研究[J]. 通信学报, 2016, 37(8): 51-57.
[7]	刘江,黄韬,张晨,张歌. SDN试验床网络虚拟化切片机制综述[J]. 通信学报, 2016, 37(4): 159-171.
[8]	曹傧,郎文强,陈卓,李云. 无线网络虚拟化中资源共享的功率分配算法[J]. 通信学报, 2016, 37(2): 64-72.
[9]	肖蔼玲,王颖,孟洛明,邱雪松,李文璟. 面向多节点故障的生存性虚拟网络映射方法[J]. 通信学报, 2015, 36(4): 81-88.
[10]	龚水清，陈靖，黄聪会，朱清超. 信任感知的安全虚拟网络映射算法[J]. 通信学报, 2015, 36(11): 180-189.
[11]	刘韵洁，黄韬，张娇，刘江，姚海鹏，谢人超. 服务定制网络[J]. 通信学报, 2014, 35(12): 1-9.
[12]	刘韵洁,黄韬,张娇,刘江,姚海鹏,谢人超. 服务定制网络[J]. 通信学报, 2014, 35(12): 1-9.
[13]	杨宇,陈山枝,李昕. 网络虚拟化环境中底层资源的动态选择研究——一种基于演化博弈的方法[J]. 通信学报, 2012, 33(Z2): 25-34.
[14]	罗娟,刘川川,李仁发. 基于链路可靠性的无线虚拟网络分配方法[J]. 通信学报, 2012, 33(Z1): 88-95.
[15]	朱强,王慧强,吕宏武,王振东. VNE-AFS：基于人工鱼群的网络虚拟化映射算法[J]. 通信学报, 2012, 33(Z1): 170-177.

基于链路优先的快速协同虚拟网络映射算法

Link-first based quick coordinated virtual network embedding algorithm

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 13

相关文章 15

Metrics

推荐阅读 0