Virtual Network Function Migration Algorithm Based on Deep Belief Network Prediction of Resource Requirements
-
摘要: 针对5G网络场景下缺乏对资源需求的有效预测而导致的虚拟网络功能(VNF)实时性迁移问题,该文提出一种基于深度信念网络资源需求预测的VNF动态迁移算法。该算法首先建立综合带宽开销和迁移代价的系统总开销模型,然后设计基于在线学习的深度信念网络预测算法预测未来时刻的资源需求情况,在此基础上采用自适应学习率并引入多任务学习模式优化预测模型,最后根据预测结果以及对网络拓扑和资源的感知,以尽可能地减少系统开销为目标,通过基于择优选择的贪婪算法将VNF迁移到满足资源阈值约束的底层节点上,并提出基于禁忌搜索的迁移机制进一步优化迁移策略。仿真表明,该预测模型能够获得很好的预测效果,自适应学习率加快了训练网络的收敛速度,与迁移算法结合在一起的方式有效地降低了迁移过程中的系统开销和服务级别协议(SLA)违例次数,提高了网络服务的性能。Abstract: To solve the problem of real-time migration of Virtual Network Function (VNF) caused by lacking effective prediction in 5G network, a VNF migration algorithm based on deep belief network prediction of resource requirements is proposed. The algorithm builds firstly a system cost evaluation model integrating bandwidth cost and migration cost,and then designs a deep belief network prediction algorithm based on online learning which adopts adaptive learning rate and introduces multi-task learning mode to predict future resource requirements. Finally, based on the prediction result as well as the perception of network topology and resources, the VNFs are migrated to the physical nodes that meet the resource threshold constraints through greedy selection algorithm with the goal to optimize system cost,and then a migration mechanism based on tabu search is proposed to further optimize the migration strategy.The simulation results show that the prediction model can obtain good prediction results and adaptive learning rate accelerates the convergence speed of the training network.Moreover, the combination with the migration algorithm reduces effectively system cost and the number of Service Level Agreements (SLA) violations during the migration process, and improves the performance of network services.
-
Key words:
- Virtual Network Function (VNF) /
- Prediction /
- Migration /
- Deep learning
-
表 1 基于拓扑感知的动态局部迁移算法(TPLDM-DBN)
算法1 基于拓扑感知的动态局部迁移算法(TPLDM-DBN) 输入:过载的物理节点${S_s}$以及它上面的VNF集合VNFList 输出:需要迁移的${\rm{VN}}{{\rm{F}}_m}$和迁移的目标物理节点${S_d}$ ${C_{\rm min}}[1,2,·\!·\!·,|{\rm{VNF}}|]$表示VNFList中每个虚拟机上的
${\rm{VN}}{{\rm{F}}_i}$最小的系统开销$D[1,2,·\!·\!·,|{\rm{VNF}}|]$: ${D_i}$表示给${\rm{VN}}{{\rm{F}}_i}$带来最小系统开销最小
的物理节点(1) ${C_{\rm min}} \leftarrow \infty $ (2) for each ${\rm{VN}}{{\rm{F}}_i} \in {\rm VNFList}$ do (3) For each ${S_j} \in S$ do (4) If ${\rm{Check}}\_{\rm{constraints}}({\rm{VN}}{{\rm{F}}_i},{S_j}) = {\rm False}$ (5) Continue; (6) endif (7) Add ${S_j}$ to ${S_{{\rm{VN}}{{\rm{F}}_i}}}$ (8) Endfor (9) 对于选出的符合资源约束的物理节点集合${S_{{\rm{VN}}{{\rm{F}}_i}}}$,通
过拓扑感知计算出${\rm{VN}}{{\rm{F}}_i}$迁移的最小系统开销${C_i}$,并
将迁移的目标物理节点用${D_i}$表示(10) If ${C_i} < {C_{\rm min}} $ and $ {D_i} \ne {S_s}$ then
(11) $\begin{array}{l}{C_{\rm min}} \leftarrow {C_i}\\{\rm{VN}}{{\rm{F}}_m} \leftarrow {{\rm VNF}_i}\\{S_d} \leftarrow {D_i}\end{array}$(12) Endif (13) Endfor (14) Return $({\rm{VN}}{{\rm{F}}_m},{S_d})$ 表 2 基于拓扑感知的动态全局迁移算法(TPGDM-DBN)
算法2 基于拓扑感知的动态全局迁移算法(TPGDM-DBN) (1) 输入所有过载的物理节点集合SList以及它们上面的VNF集合 VNFList: (2) for each ${S_i} \in {\rm SList}$ do (3) 执行算法1选出迁移的VNF (4) while ${S_i}$仍然过载 (5) 继续执行算法2选出系统开销次小的VNF进行迁移 (6) Endwhile (7) Endfor (8) 输出需要迁移的VNF集合以及相对应的目标迁移物理节点 表 3 基于禁忌搜索的迁移优化算法(TADM-DBN)
算法3:基于禁忌搜索的迁移优化算法(TADM-DBN) (1) 初始解: $Z = {Z_0},{Z^*} = {Z_0},T = \phi $,定义特赦值为
$A({Z^*}) = C_{{\rm tot}}^t({Z^*})$(2) While 不符合终止准则 do (3) 产生$N(Z)$的一个候选集W,在候选集中选取最优解
${X^*}$,更新$C_{{\rm tot}}^t({X^*})$(4) If $C_{{\rm tot}}^t(X) < A({Z^*}),X \in T\,$且$C_{{\rm tot}}^t(X) < C_{{\rm tot}}^t({X^*})$ (5) 令${X^*} = X$ (6) 更新$C_{{\rm tot}}^t({X^*})$ (7) Endif//破禁检查 (8) If $C_{{\rm tot}}^t({X^*}) < C_{{\rm tot}}^t({Z^*})$ (9) ${Z^*} = {X^*},C_{{\rm tot}}^t({Z^*}) = C_{{\rm tot}}^t({X^*}),A({Z^*}) = C_{{\rm tot}}^t({Z^*})$ (10) Endif; (11) 更新禁忌表$T\;$, $T = T \,\cup {X^*}$ (12) 令$Z = {X^*}$ (13) Endwhile (14) Return ${Z^*}$ -
MAHMOOD N H, LAURIDSEN M, BERARDINELLI G, et al. Radio resource management techniques for eMBB and mMTC services in 5G dense small cell scenarios[C]. Proceedings of the 84th Vehicular Technology Conference, Montreal, Canada, 2017: 1–5. 唐伦, 张亚, 梁荣, 等. 基于网络切片的网络效用最大化虚拟资源分配算法[J]. 电子与信息学报, 2017, 39(8): 1812–1818. doi: 10.11999/JEIT161322TANG Lun, ZHANG Ya, LIANG Rong, et al. Virtual resource allocation algorithm for network utility maximization based on network slicing[J]. Journal of Electronics &Information Technology, 2017, 39(8): 1812–1818. doi: 10.11999/JEIT161322 RAHMAN M M, DESPINS C, and AFFES S. Design optimization of wireless access virtualization based on cost & QoS trade-off utility maximization[J]. IEEE Transactions on Wireless Communications, 2016, 15(9): 6146–6162. doi: 10.1109/TWC.2016.2580505 QU Long, ASSI C, SHABAN K, et al. A reliability-aware network service chain provisioning with delay guarantees in NFV-enabled enterprise datacenter networks[J]. IEEE Transactions on Network and Service Management, 2017, 14(3): 554–568. doi: 10.1109/TNSM.2017.2723090 RIGGIO R, BRADAI A, HARUTYUNYAN D, et al. Scheduling wireless virtual networks functions[J]. IEEE Transactions on Network and Service Management, 2016, 13(2): 240–252. doi: 10.1109/TNSM.2016.2549563 LUIZELLI M C, BAYS L R, BURIOL L S, et al. Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions[C]. Proceedings of 2015 IFIP/IEEE International Symposium on Integrated Network Management, Ottawa, Canada, 2015: 98–106. XIA Jing, CAI Zhiping, and XU Ming. Optimized virtual network functions migration for NFV[C]. Proceedings of 2016 IEEE International Conference on Parallel and Distributed Systems, Wuhan, China, 2016: 340–346. ERAMO V, MIUCCI E, AMMAR M, et al. An approach for service function chain routing and virtual function network instance migration in network function virtualization architectures[J]. IEEE/ACM Transactions on Networking, 2017, 25(4): 2008–2025. doi: 10.1109/TNET.2017.2668470 MIJUMBI R, HASIJA S, DAVY S, et al. Topology-aware prediction of virtual network function resource requirements[J]. IEEE Transactions on Network and Service Management, 2017, 14(1): 106–120. doi: 10.1109/TNSM.2017.2666781 DEUTSCH J and HE D. Using deep learning-based approach to predict remaining useful life of rotating components[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018, 48(1): 11–20. doi: 10.1109/TSMC.2017.2697842 PATI J, KUMAR B, MANJHI D, et al. A comparison among ARIMA, BP-NN, and MOGA-NN for software clone evolution prediction[J]. IEEE Access, 2017, 5: 11841–11851. doi: 10.1109/ACCESS.2017.2707539 GIL H J and BOTERO J F. Resource allocation in NFV: A comprehensive survey[J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 518–532. doi: 10.1109/TNSM.2016.2598420 MA Wenrui, MEDINA C, and PAN Deng. Traffic-aware placement of NFV middleboxes[C]. Proceedings of 2015 IEEE Global Communications Conference, San Diego, USA, 2015: 1–6. doi: 10.1109/GLOCOM.2015.7417851. CARUANA R. Multitask learning[J]. Machine Learning, 1997, 28(1): 41–75. doi: 10.1023/a:1007379606734 MASHINCHI M H, MASHINCHI M R, and MASHINCHI M. Tabu search solution for fuzzy linear programming[C]. Proceedings of the 7th IEEE/ACIS International Conference on Computer and Information Science, Portland, USA, 2008: 82–87.