一种基于临近原则的虚拟网络映射算法

doi:10.3969/j.issn.1000-0801.2013.12.006

电信科学 ›› 2013, Vol. 29 ›› Issue (12): 38-44.doi: 10.3969/j.issn.1000-0801.2013.12.006

一种基于临近原则的虚拟网络映射算法

黄胜,吴川川,杨晓非,王辉,张卫

>北京邮电大学计算机学院通信软件工程中心重庆邮电大学光纤通信技术重点实验室重庆400065
重庆邮电大学光纤通信技术重点实验室重庆400065

出版日期:2013-12-20 发布日期:2017-07-04
基金资助:
国家重点基础研究发展计划（“973”计划）基金资助项目;国家自然科学基金资助项目;重庆市科委自然科学基金资助项目;重庆市科委自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;重庆市教委自然科学基金资助项目

A Virtual Network Mapping Algorithm Based on Approaching Principle

Sheng Huang,Chuanchuan Wu,Xiaofei Yang,Hui Wang,Wei Zhang

Key Lab of Optical Fiber Communication Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

Online:2013-12-20 Published:2017-07-04

摘要/Abstract

摘要：

在两阶段虚拟网络映射算法的基础上，针对现有的贪婪策略对节点映射存在盲目性的缺点，提出了一种基于临近原则的虚拟网络映射算法。该算法对节点映射阶段做了优化和改进，在节点映射阶段充分考虑其对链路映射带来的影响，使节点映射到相对集中的区域，降低链路映射阶段的求解难度。仿真结果表明，所提出的算法与已有的算法相比，在虚拟网络请求接受率、平均时间收益和收益开销比等方面均有明显提高。

关键词: 虚拟网络映射, 临近原则, 接受率, 收益开销比

Abstract:

On the basis of two stages virtual network mapping algorithm, pointing at the defects of the blind node mapping of existing greedy strategy, a virtual network mapping algorithm based on approaching principle was proposed. The algorithm optimized and improved the node mapping stage, and it took a full consideration of the impact on link mapping in the node mapping stage, which made the nodes map to the area of relatively concentrated and reduced the difficulty of solving the link mapping stage. Simulation results show that compared with the existing algorithms, the proposed algorithm improves the virtual network request acceptance ratio, average time revenue and revenue/cost（r/c）ratio.

Key words: virtual network mapping, approaching principle, acceptance ratio, revenue/cost ratio

黄胜,吴川川,杨晓非,王辉,张卫. 一种基于临近原则的虚拟网络映射算法[J]. 电信科学, 2013, 29(12): 38-44.

Sheng Huang,Chuanchuan Wu,Xiaofei Yang,Hui Wang,Wei Zhang. A Virtual Network Mapping Algorithm Based on Approaching Principle[J]. Telecommunications Science, 2013, 29(12): 38-44.

图/表 10

图1

图2

表1

图3

图4

图5

图6

图7

图8

图9

参考文献 15

1	程祥，张忠宝，苏森 . 虚拟网络映射问题研究综述. 通信学报， 2011,32（10）:143～150
2	魏晓辉，张忠宝，李洪亮 . 基于优化的同构子图搜索的虚拟网络映射算法. 吉林大学报， 2013,43（1）:165～171
3	李小玲，王怀民，丁博 . 虚拟网络映射问题研究及其进展. 软件学报， 2012,23（10）:3009～3028
4	Chowdhury N M M K , Boutaba R . Network virtualization: state of the art and research challenges. IEEE Communications Magazine, 2009,47（7）:20～26.
5	Lu N J , Turner J . Efficient Mapping of Virtual Networks onto a Shared Substrate. Washington: Washington University Technology Report, 2006
6	Yu N M , Yi Y , Rexford J ， et al. Rethinking virtual network embedding: substrate support for path splitting and migration. Computer Communication Review, 2008,38（2）:17～29
7	Lu N J , Zhang S R , Li Y ， et al. Davinci: dynamically adaptive virtual networks for a customized internet. Proceedings of the ACM CoNEXT Conference, Madrid, Spain, 2008
8	Zhu Y , Ammar M . Algorithms for assigning substrate network resources to virtual network components. Proceedings of the 25th IEEE Int'l Conference on Computer Communications, Barcelona, Catalunya, Spain, 2006
9	Shamsi J , Brockmeyer M . QoSMap: QoS aware mapping of virtual networks for resiliency and efficiency. Proceedings of the IEEE GLOBECOM Workshop, Washington D C, USA, 2007
10	Houidi I , Louati W , Zeghlache D . A distributed virtual network mapping algorithm. Proceedings of IEEE ICC, Beijing, China, 2008
11	Chowdhury N M M K , Rahman M R , Boutaba R . Virtual network embedding with coordinated node and link mapping. Proceedings of IEEE INFOCOM 2009, Rio de Janeiro, Brazil, 2009: 783～791
12	Chowdhury N M M K , Rahman M R , Boutaba R . ViNEYard:virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Transactions on Networking, 2012 （3）
13	Lischka J , Karl H . A virtual network mapping algorithm based on subgraph isomorphism detection. Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems andArchitectures, Barcelona, Spain, 2009: 81～88
14	Liu J , Huang T , Chen J Y . ViNEYard: a new algorithm based on the proximity principle for the virtual network embedding problem. Journal of Zhejiang University-Science C（Computers ＆Electronics）, 2011,12（11）:910～918
15	Eppstein D . Finding the shortest paths. SIAM J Comput, 1998,28（2）:652～673

缩写	算法描述
G-SP^[6]	贪婪式的节点映射结合K最短路径算法的链路映射
G-MCF^[6]	贪婪式的节点映射结合MCF算法的链路映射
A-SP	临近式的节点映射结合K最短路径算法的链路映射
A-MCF	临近式的节点映射结合MCF算法的链路映射

[1]	董晓东,郭志强,陈胜,周晓波,齐恒,李克秋. 面向SDN网络虚拟化平台的控制器放置算法[J]. 电信科学, 2017, 33(4): 56-64.
[2]	曲桦,樊斌,郭涯,王力,赵季红. 应用粒子群优化的绿色虚拟网络映射算法[J]. 电信科学, 2016, 32(1): 11-17.
[3]	樊勇兵,陈天,陈楠,黄志兰,吕翠娥. 云数据中心的虚拟机放置问题[J]. 电信科学, 2015, 31(2): 140-146.
[4]	王力,赵季红,曲桦,郭涯. 软件定义承载网中基于负载均衡的虚拟网络资源分配算法[J]. 电信科学, 2015, 31(11): 36-42.
[5]	曲桦,王丽霞,赵季红,王贺男. 面向差异化业务请求的虚拟网络映射算法[J]. 电信科学, 2014, 30(12): 64-70.

一种基于临近原则的虚拟网络映射算法

A Virtual Network Mapping Algorithm Based on Approaching Principle

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 15

相关文章 5

Metrics

推荐阅读 0