Disaster Prediction-based Survivable Virtual Optical Network Mapping for Multi-Area Faults
-
摘要:
生存性虚拟光网络映射是提高光网络应对灾难故障的重要技术保障措施。为解决灾难性多区域故障导致弹性光网络的带宽容量损失问题,该文提出基于灾难预测故障模型的蚁群优化虚拟光网络映射 (DFM-ACO-VNM)算法。在该算法中,设计基于光节点资源和相邻链路的全局潜在故障概率的光节点排序映射准则,并设计启发式信息公式实现多区域故障下最小带宽容量损失的虚拟节点和虚拟链路协同映射。仿真结果表明,该文所提算法在多区域故障时能降低带宽容量损失,减少带宽阻塞率和提高频谱利用率。
Abstract:Survivable virtual optical network mapping is an important technology to improve the optical network response to disaster failures. In order to solve the problem of bandwidth capacity loss caused by multi-area faults resulted from disasters in Elastic Optical Networks (EONs), a multi-area disaster fault model of survivable virtual network based on risk assessment is established, and a Disaster Fault Model based Ant Colony Optimization for Virtual Network Mapping (DFM-ACO-VNM) algorithm is proposed in the paper. An optical node ranking mapping criterion based on node resources and global potential failure probability of adjacent links in EONs is designed. Then, a heuristic information formula is designed to realize cooperative mapping of virtual nodes and virtual links with minimum bandwidth capacity loss under multi-area faults. The simulation results show that the proposed algorithm can decrease the bandwidth capacity loss, reduce the bandwidth blocking probability and improve the spectrum utilization in multi-area faults.
-
表 1 DFM-ACO-VNM算法
输入:输入底层网络${{{G}}_{\rm{s}}}({{{N}}_{\rm{s}}},{{{{\rm E}}}_{\rm{s}}})$和灾难事件F,虚拟网络请求${{{G}}_{\rm{v}}}({{{N}}_{\rm{v}}},{{{E}}_{\rm{v}}})$。 输出:Antbest,即虚拟网络的虚拟节点映射,虚拟链路映射和频谱资源分配结果。 (1) 初始化信息素浓度矩阵τ[n][m],启发式信息矩阵η[n][m],转移概率矩阵P[n][m],初始化${A_{{\rm{best}}}} = 1000000$, n为Nv集合的虚拟节点
数,m为Ns集合的光节点数,设置蚁群算法最大迭代次数Gmax,迭代变量j=0; Aj为虚拟网络蚁群映射第j轮结果;(2) 根据灾难集合F,计算EONs区域A灾难概率${p_A}\left( {{f_i}} \right)\;$,根据式(7)计算各光纤链路es的灾难评估$M({e_{\rm{s}}})$值; (3) 根据式(5),对虚拟网络中的虚拟节点降序排列在集合${R_{{n_{\rm{v}}}}}$中; (4) For(j =0, j+1, j <Gmax) (5) For 从排序第1个虚拟节点到第n个虚拟节点 (6) 执行EBCL-VNM映射算法(表2),构造虚拟网络映射解Aj; (7) End for (8) If ${{\rm{E}}_{{\rm{BCL}}}}({A_{{\rm{best}}}})$ > ${{{E}}_{{\rm{BCL}}}}({A_j})$ (9) 令${{{E}}_{{\rm{BCL}}}}({A_{{\rm{best}}}})$ = ${{{E}}_{{\rm{BCL}}}}({A_j})$ (10) End if (11) 根据式(10),更新信息素浓度矩阵 (12) if converge (13) Break; (14) end if (15) end for (16) Return ${{\rm{E}}_{{\rm{BCL}}}}({A_{{\rm{best}}}})$ and ${A_{{\rm{best}}}}$ 表 2 EBCL-VNM 算法
(1) 初始化虚拟网络请求的虚拟节点、链路映射结果集合和资源分配结合,即A0 = Φ; (2) 根据式(6),排序EONs中光节点在集合${R_{{n_{\rm{s}}}}}$中; (3) 选择顺序列表${R_{{n_{\rm{v}}}}}$中的第1个虚拟节点$n_{\rm{v}}^0$; (4) 选择顺序列表${R_{{n_{\rm{s}}}}}$中的第1个光节点$n_{\rm{s}}^0$; (5) 将满足资源约束的$n_{\rm{v}}^0$映射到$n_{\rm{s}}^0$,记录已映射节点信息,并从集合${R_{{n_{\rm{v}}}}}$中删除$n_{\rm{v}}^0$; (6) For 依次映射集合${R_{{n_{\rm{v}}}}}$的剩余虚拟节点 (7) 当前拟映射虚拟节点$n_v^i$加入已映射虚拟节点和虚拟链路集合时,根据式(8)结果确定需要新映射的虚拟链路; (8) 找出满足虚拟节点资源约束条件的候选光节点集合$n_{\rm{s}}^{i{\rm{ - C}}}$; (9) For 对所有候选光节点集合$n_{\rm{s}}^{i{\rm{ - C}}}$依次执行 (10) 运行多商品流算法映射各虚拟链路的K条候选光路路由和资源光路带宽分配; (11) 根据式(8)计算启发式信息矩阵η[$n_{\rm{v}}^i$][$n_{\rm{s}}^j$]; (12) 根据式(9)计算转移概率矩阵P[$n_{\rm{v}}^i$][$n_{\rm{s}}^j$]; (13) 将虚拟节点i按式(9)计算值,概率地选择映射到光节点j; (14) End for (15) 更新虚拟节点和虚拟链路映射集合; (16) End for (17) Return 虚拟节点映射、虚拟链路映射和资源分配结果。 -
鲍宁海, 苏国庆, 陈静波. 恢复时间敏感的光网络混合通路保护算法[J]. 重庆邮电大学学报: 自然科学版, 2017, 29(3): 313–319. doi: 10.3979/j.issn.1673-825X.2017.03.005BAO Ninghai, SU Guoqing, and CHEN Jingbo. Recovery-time aware hybrid path protection algorithm in optical networks[J]. Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition, 2017, 29(3): 313–319. doi: 10.3979/j.issn.1673-825X.2017.03.005 LIU Huanlin, DU Jundan, CHEN Yong, et al. A coordinated virtual optical network embedding algorithm based on resources availability-aware over elastic optical networks[J]. Optical Fiber Technology, 2018, 45: 391–398. doi: 10.1016/j.yofte.2018.08.021 ELMIRGHANI J M H, KLEIN T, HINTON K, et al. GreenTouch greenMeter core network energy-efficiency improvement measures and optimization[J]. Journal of Optical Communications and Networking, 2018, 10(2): A250–A269. doi: 10.1364/JOCN.10.00A250 PAOLUCCI F, CUGINI F, FRESI F, et al. Superfilter technique in SDN-controlled elastic optical networks[Invited][J]. Journal of Optical Communications and Networking, 2015, 7(2): A285–A292. doi: 10.1364/JOCN.7.00A285 LU Shuaibing, WU Jie, ZHENG Huanyang, et al. On maximum elastic scheduling in cloud-based data center networks for virtual machines with the hose model[J]. Journal of Computer Science and Technology, 2019, 34(1): 185–206. doi: 10.1007/s11390-019-1890-3 LIN Rongping, LUO Shan, ZHOU Jingwei, et al. Column generation algorithms for virtual network embedding in flexi-grid optical networks[J]. Optics Express, 2018, 26(8): 10898–10913. doi: 10.1364/OE.26.010898 DUBOIS D J and CASALE G. Autonomic provisioning and application mapping on spot cloud resources[C]. 2015 International Conference on Cloud and Autonomic Computing, Boston, USA, 2015: 57–68. doi: 10.1109/ICCAC.2015.21. XIE Weisheng, JUE J P, ZHANG Qiong, et al. Survivable virtual optical network mapping in flexible-grid optical networks[C]. 2014 International Conference on Computing, Networking and Communications, Honolulu, USA, 2014: 221–225. doi: 10.1109/ICCNC.2014.6785335. ZHANG Huibin, WANG Wei, ZHAO Yongli, et al. Shared protection based virtual network mapping in space division multiplexing optical networks[J]. Optical Fiber Technology, 2018, 42: 63–68. doi: 10.1016/j.yofte.2017.12.004 XUAN Hejun, WANG Yuping, XU Zhanqi, et al. Virtual optical network mapping and core allocation in elastic optical networks using multi-core fibers[J]. Optics Communications, 2017, 402: 26–35. doi: 10.1016/j.optcom.2017.05.065 GALDAMEZ C and YE Zilong. Resilient virtual network mapping against large-scale regional failures[C]. 2017 IEEE Conference of Wireless and Optical Communication, Newark, USA, 2017: 1–4. doi: 10.1109/WOCC.2017.7928978. FERDOUSI S, DIKBIYIK F, FARHAN HABIB M, et al. Disaster-aware datacenter placement and dynamic content management in cloud networks[J]. IEEE OSA Journal of Optical Communications and Networking, 2015, 7(7): 681–694. doi: 10.1364/JOCN.7.000681 GOUR R, KONG Jian, ISHIGAKI G, et al. Survivable routing in multi-domain optical networks with geographically correlated failures[C]. 2017 IEEE Global Communications Conference, Singapore, 2017: 1–6. doi: 10.1109/GLOCOM.2017.8254775. 刘焕淋, 易鹏飞, 陈勇, 等. 一种最小故障风险损失的弹性光网络多链路故障概率保护策略[J]. 电子与信息学报, 2017, 39(8): 1819–1825. doi: 10.11999/JEIT161159LIU Huanlin, YI Pengfei, CHEN Yong, et al. Multi-link failure probability protection strategy based on minimum fault risk loss in elastic optical networks[J]. Journal of Electronics &Information Technology, 2017, 39(8): 1819–1825. doi: 10.11999/JEIT161159 刘焕淋, 林振宇, 王欣, 等. 弹性光网络中基于安全性感知的差异化虚拟光网络的映射策略[J]. 电子与信息学报, 2019, 41(2): 424–432. doi: 10.11999/JEIT180335LIU Huanlin, LIN Zhengyu, WANG Xin, et al. A diverse virtual optical network mapping strategy based on security awareness in elastic optical networks[J]. Journal of Electronics &Information Technology, 2019, 41(2): 424–432. doi: 10.11999/JEIT180335 POURVALI M, BAI Hao, CRICHIGNO J, et al. Multicast virtual network services embedding for improved disaster recovery support[J]. IEEE Communications Letters, 2018, 22(7): 1362–1365. doi: 10.1109/LCOMM.2018.2822739 WANG Ying, LIU Xiao, QIU Xuesong, et al. Prediction-based survivable virtual network mapping against disaster failures[J]. International Journal of Network Management, 2016, 26(5): 336–354. doi: 10.1002/nem.1939 朱颢东, 孙振, 吴迪, 等. 基于改进蚁群算法的移动机器人路径规划[J]. 重庆邮电大学学报: 自然科学版, 2016, 28(6): 849–855. doi: 10.3979/j.issn.1673-825X.2016.06.017ZHU Haodong, SUN Zhen, WU Di, et al. Path planning for mobile robot based on improved ant colony algorithm[J]. Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition, 2016, 28(6): 849–855. doi: 10.3979/j.issn.1673-825X.2016.06.017 ZHENG Hongkun, LI Jingjing, GONG Yuejiao, et al. Link mapping-oriented ant colony system for virtual network embedding[C]. 2017 IEEE Congress on Evolutionary Computation, San Sebastian, Spain, 2017: 1223–1230. doi: 10.1109/CEC.2017.7969445. 谢晖. 抗毁SDN光网络资源优化调度研究[J]. 激光杂志, 2019, 40(4): 97–101. doi: 10.14016/j.cnki.jgzz.2019.04.097XIE Hui. Research on optimal scheduling of SDN optical network resources[J]. Laser Journal, 2019, 40(4): 97–101. doi: 10.14016/j.cnki.jgzz.2019.04.097 DU Xiaowu and MA Lisheng. Backup path provisioning for service protection against disaster failures in telecom networks[C]. 2017 International Conference on Networking and Network Applications, Kathmandu, Nepal, 2017: 220–224. doi: 10.1109/NaNA.2017.40.