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

• 学术论文 • 上一篇    下一篇

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

刘光远1, 徐明伟2   

  1. 1. 石家庄铁道大学信息科学与技术学院, 河北石家庄 050043;
    2. 清华大学信息科学技术学院, 北京 100084
  • 收稿日期:2019-04-02 修回日期:2020-01-15 出版日期: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-yuan1, XU Ming-wei2   

  1. 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
    • Supported by:
    • National Key Research and Development Program of China (No.2018YFB1701403); National Natural Science Foundation of China (No.61373160); Natural Science Foundation of Hebei Province,  China (No.F2020210014); Research on Science and Technology in Colleges and Universities of Hebei Province (No.QN2016270)

摘要: 本文研究了可生存虚拟网络多层映射问题,首先对其建立了整数线性规划模型(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

中图分类号: