可生存的虚拟网络多层映射方法研究

doi:10.3969/j.issn.0372-2112.2020.07.012

电子学报 ›› 2020, Vol. 48 ›› Issue (7): 1343-1347.DOI: 10.3969/j.issn.0372-2112.2020.07.012

可生存的虚拟网络多层映射方法研究

刘光远¹, 徐明伟²

1. 石家庄铁道大学信息科学与技术学院, 河北石家庄 050043;
2. 清华大学信息科学技术学院, 北京 100084

收稿日期:2019-04-02 修回日期:2020-01-15 出版日期:2020-07-25 发布日期:2020-07-25
作者简介:刘光远 男,1981年出生,河北石家庄人.于北京邮电大学获得博士学位,现为石家庄铁道大学信息学院教师.主要研究方向为云计算、网络虚拟化.E-mail:gyuanliu@163.com;徐明伟 男,1971年出生,辽宁朝阳人.清华大学教授,主要研究方向为网络体系结构、下一代互联网、网络空间安全.
基金资助:
国家重点研发计划（No.2018YFB1701403）；国家自然科学基金（No.61373160）；河北省自然科学基金（No.F2020210014）；河北省高等学校科学技术研究（No.QN2016270）

Research on Survivable Virtual Network Multi-layers Embedding Method

LIU Guang-yuan¹, XU Ming-wei²

1. School of Information Science and Technology, Shijiazhuang Tiedao University, Shijiazhuang, Hebei 050043, China;
2. School of Information Science and Technology, Tsinghua University, Beijing 100084, China

Received:2019-04-02 Revised:2020-01-15 Online:2020-07-25 Published:2020-07-25

摘要/Abstract

摘要： 本文研究了可生存虚拟网络多层映射问题，首先对其建立了整数线性规划模型（ILP），然后针对较大规模问题提出一种高效的启发式算法VNP-SVNME对其进行求解.实验表明，VNP-SVNME算法的资源映射开销相对ILP仅平均高15%，且优于现有的启发式可生存算法.此外，VNP-SVNME算法的映射时间相对ILP大大降低，可以满足在线虚拟网络映射的需求.

关键词: 虚拟网络多层映射, 可生存, 整数线性规划, 启发式

Abstract: This paper studies the multi-layers embedding problem of survivable virtual networks based on virtual network layer protection.We first establish an integer linear programming (ILP) for the SVNME problem.Then an efficient heuristic algorithm VNP-SVNME is proposed to solve the large-scale problem.Experiments show that the resource mapping cost of the VNP-SVNME algorithm is only 15% higher on average than the optimal solution,but it is better than the state-of-the-art heuristic.In addition,the time complexity is greatly reduced compared to ILP,which can meet the requirements of online virtual network mapping.

Key words: virtual network multi-layers mapping, survivability, integer linear programming, heuristic

中图分类号:

TP393

刘光远, 徐明伟. 可生存的虚拟网络多层映射方法研究[J]. 电子学报, 2020, 48(7): 1343-1347.

LIU Guang-yuan, XU Ming-wei. Research on Survivable Virtual Network Multi-layers Embedding Method[J]. Acta Electronica Sinica, 2020, 48(7): 1343-1347.

[1]	蒋华伟, 郭陶, 杨震. 车辆路径问题研究进展[J]. 电子学报, 2022, 50(2): 480-492.
[2]	吕阳, 钱斌, 胡蓉, 张梓琪. 增强人工蜂群算法求解半导体最终测试调度问题[J]. 电子学报, 2021, 49(9): 1708-1715.
[3]	柴蓉, 谢德胜, 陈前斌. 基于成本及功耗联合优化的SDN虚拟网络映射算法[J]. 电子学报, 2021, 49(8): 1615-1624.
[4]	王蔚龙, 李勇军, 赵尚弘, 辛宁, 赵海燕, 张泰江. 基于两阶段帕累托优化的卫星下行链路功率分配方法[J]. 电子学报, 2021, 49(6): 1101-1107.
[5]	周丰顺, 胡蓉, 钱斌, 张长胜, 向凤红. 超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题[J]. 电子学报, 2021, 49(12): 2419-2427.
[6]	牛当当, 吕帅, 王金艳, 刘斌. 基于MACR和CAL启发式的求差知识编译算法[J]. 电子学报, 2020, 48(2): 285-290.
[7]	牛当当, 吕帅, 王金艳. 基于MOVR启发式的求差知识编译算法[J]. 电子学报, 2019, 47(11): 2299-2303.
[8]	王今雨, 伍卫国, 秦朝楠, 赵东方, 聂世强. UPRFloor:一种动态可重构FPGA建模方法与布局策略[J]. 电子学报, 2018, 46(12): 2862-2869.
[9]	刘艺, 张红旗, 杨英杰. 基于启发式调度的OpenFlow网络规则一致更新方案[J]. 电子学报, 2017, 45(7): 1637-1645.
[10]	王兴茂, 张兴明, 吴毅涛, 潘俊池. 基于启发式聚类模型和类别相似度的协同过滤推荐算法[J]. 电子学报, 2016, 44(7): 1708-1713.
[11]	姚苏, 关建峰, 潘华, 张宏科. 基于APT潜伏攻击的网络可生存性模型与分析[J]. 电子学报, 2016, 44(10): 2415-2422.
[12]	章刚, 陈庆奎. GCTMHA:基于启发式群组命令传输模型[J]. 电子学报, 2016, 44(1): 233-235.
[13]	叶东毅, 陈昭炯. 最小属性约简问题的一个有效的组合人工蜂群算法[J]. 电子学报, 2015, 43(5): 1014-1020.
[14]	常郝, 梁华国, 蒋翠云, 欧阳一鸣, 徐辉. 一种3D堆叠集成电路中间绑定测试时间优化方案[J]. 电子学报, 2015, 43(2): 393-398.
[15]	简平, 邹鹏, 熊伟. 动态扰动下低轨预警卫星系统任务规划问题分析[J]. 电子学报, 2014, 42(10): 1894-1900.

可生存的虚拟网络多层映射方法研究

Research on Survivable Virtual Network Multi-layers Embedding Method

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics