高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于深度强化学习的服务功能链可靠部署算法

唐伦 曹睿 廖皓 王兆堃

唐伦, 曹睿, 廖皓, 王兆堃. 基于深度强化学习的服务功能链可靠部署算法[J]. 电子与信息学报. doi: 10.11999/JEIT190969
引用本文: 唐伦, 曹睿, 廖皓, 王兆堃. 基于深度强化学习的服务功能链可靠部署算法[J]. 电子与信息学报. doi: 10.11999/JEIT190969
Lun TANG, Rui CAO, Hao LIAO, Zhaokun WANG. Reliable Deployment Algorithm of Service Function Chain Based on Deep Reinforcement Learning[J]. Journal of Electronics and Information Technology. doi: 10.11999/JEIT190969
Citation: Lun TANG, Rui CAO, Hao LIAO, Zhaokun WANG. Reliable Deployment Algorithm of Service Function Chain Based on Deep Reinforcement Learning[J]. Journal of Electronics and Information Technology. doi: 10.11999/JEIT190969

基于深度强化学习的服务功能链可靠部署算法

doi: 10.11999/JEIT190969
基金项目: 国家自然科学基金(6157073),重庆市教委科学技术研究项目(KJZD-M201800601)
详细信息
    作者简介:

    唐伦:男,1973年生,教授,博士生导师,研究方向为新一代无线通信网络、异构蜂窝网络、软件定义无线网络等

    曹睿:男,1994年生,硕士生,研究方向为5G网络切片中的资源分配、可靠性

    廖皓:男,1993年生,硕士生,研究方向为5G网络故障检测、自愈合、机器学习

    王兆堃:男,1995年生,硕士生,研究方向为5G网络故障检测、自愈合、机器学习

    通讯作者:

    曹睿 1280139234@qq.com

  • 中图分类号: TN929.5

Reliable Deployment Algorithm of Service Function Chain Based on Deep Reinforcement Learning

Funds: The National Natural Science Foundation of China (61571073), The Science and Technology Research Program of Chongqing Municipal Education Commission (KJZD-M201800601)
  • 摘要: 针对当前关于服务功能链(SFC)的部署问题都未考虑到虚拟网络功能(VNF)的失效重要度,该文提出了基于深度强化学习的SFC可靠部署算法。首先建立VNF和虚拟链路可靠映射模型,为重要的VNF设置高可靠性需求,并通过链路部署长度限制尽可能保证虚拟链路可靠性需求。其次,以负载均衡为资源协调原则,与VNF可靠性联合优化,最终使用深度强化学习得到服务功能链部署策略。另外,提出了基于重要度的节点备份和链路备份策略,用于应对部署过程中VNF/链路可靠性难以满足的情况。仿真结果表明,本文的可靠部署算法在保证可靠性需求的基础上能够有效减少SFC失效损失,同时使虚拟网络更加稳定可靠。
  • 图  1  系统场景图

    图  2  深度强化算法示意图

    图  3  SFC请求接受率对比

    图  4  SFC备份消耗对比

    图  5  SFC失效损失对比

    图  6  学习率对收敛效果的影响

    表  1  基于深度强化学习的服务功能链可靠部署算法

     算法1 基于深度强化学习的服务功能链可靠部署算法
     经验回放池初始化为空,随机初始化主网络的参数,并复制给目标网络,探寻环境信息基于式(6)~式(9)得到${w_I}$,${u'_k}$
     for episode=1, 2, ···, E do
     初始化状态为${{{s}}_1} = \{ {{{B}}_{{\rm{left}}}}{{,}}{{{C}}_{{\rm{left}}}}{{,}}{{{b}}_{{\rm{map}}}}{{,}}{{{c}}_{{\rm{map}}}}\} $, ${{{b}}_{{\rm{map}}}}{{,}}{{{c}}_{{\rm{map}}}}$为空
     for t=1,2…D do
     确定可选动作集${N'_{k{n_i}}}$,${N''_{k{n_i}}}$随机产生0到1的数$\tau $
     if $\tau < \varepsilon $:先从${ {{N'} }_{k{n_i} } }$中选择动作${a_t}$,若为空则根据算法2在${ {{N''} }_{k{n_i} } }$中选择${a_t}$,都无动作选择则${a_t}$为空
     else:依据主神经网络估值${\pi ^*}(s) = {{\arg }}\max\limits_{a'} Q({{{s}}_t},{{{a'}}_t})$选取动作。end if
     执行动作${{{a}}_t}$,获得奖励${r_t}$、下一状态${{{s}}_{t + 1}}$,将向量$[{{{s}}_t},{{{a}}_t},{r_t},{{{s}}_{t + 1}}]$放入经验回放池。
     随机取出小批量样本向量$[{{{s}}_t},{{{a}}_t},{r_t},{{{s}}_{t + 1}}]$组成样本向量集${\upsilon _t}$
     for $[{{{s}}_t},{{{a}}_t},{r_t},{{{s}}_{t + 1}}]$ in ${\upsilon _t}$ do
     $L{{(}}\theta {{)}} = {(\tilde Q({{{s}}_t},{{{a}}_t}|{\theta ^ - }) - Q({{{s}}_t},{{{a}}_t}|\theta ))^2}$,$\theta \leftarrow \theta - {\lambda _{{\rm{SGD}}}}\nabla L(\theta )$ end for
     在θ更新T次后将主网络参数复制给目标网络。end for end for
     通过主网络得到每个VNF的策略${\pi ^*}(s)$
     if累计奖励$Q({s_t},{a_t}) < - 100$:拒绝该请求
     else if 部署结果不满足链路可靠性需求:执行算法3 end if
    下载: 导出CSV

    表  2  基于虚拟网络功能重要度节点备份算法

     算法2:基于虚拟网络功能重要度的节点备份算法
     初始化节点部署方案$g'(v_I^k)$为空
     repeat:
     if ${\omega _I} < 1/D$:搜寻${N''_{k{n_i}}}$已作为备份节点的节点集$V_{I'}^k$
     if $V_{I'}^k$非空:$g'(v_I^k)$←从$V_{I'}^k$中寻找备份节点,从${{{N''}}_{k{n_i}}}/V_{I'}^k$中寻
     找部署节点
     else:$g'(v_I^k)$←从${N''_{k{n_i}}}$中选出2个节点。可靠性最高的为部署节
     点,另一备份。endif
     else:$g'(v_I^k)$←从${N''_{k{n_i}}}$中选出2个节点。可靠性最高的为部署节
     点,另一备份。endif
     until $RN(g'(v_I^k)) > {(R_k^{{\rm{req}}})^{{w_I}}}$or 已遍历所有组合
     return 节点部署方案$g'(v_I^k)$
    下载: 导出CSV

    表  3  基于链路备份重要度的链路备份算法

     算法3:基于链路备份重要度的链路备份算法
     基于$\gamma _{I,J}^k$对虚拟链路链路$l_{I,J}^k \in L_v^k$排序
     for 排过序的链路链路$l_{I,J}^k \in L_v^k$
     if 链路可靠性不满足:
     确定$l_{I,J}^k$映射的段物理起始节点${n_i}$和终止节点${n_j}$:${p_{I,J}}$
     $p{{ = \{ }}{\ell _{i,j}}|{L'_{k{l_{i,j}}}}/{p_{I,J}}\} $,部署方案增加链路P
     else: break
     end for
     return 部署方案
    下载: 导出CSV
  • [1] AYOUBI S, ZHANG Yanhong, and ASSI C. A reliable embedding framework for elastic virtualized services in the cloud[J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 489–503. doi:  10.1109/TNSM.2016.2581484
    [2] 汤红波, 邱航, 游伟, 等. 基于联合备份的服务功能链可靠性保障的部署方法[J]. 电子与信息学报, 2019, 41(12): 3006–3013. doi:  10.11999/JEIT190013

    TANG Hongbo, QIU Hang, YOU Wei, et al. A reliability-guarantee method for service function chain deployment based on joint backup[J]. Journal of Electronics &Information Technology, 2019, 41(12): 3006–3013. doi:  10.11999/JEIT190013
    [3] 季新生, 赵硕, 艾健健, 等. 异构备份式的虚拟网映射方法研究[J]. 电子与信息学报, 2018, 40(5): 1087–1093. doi:  10.11999/JEIT170730

    JI Xinsheng, ZHAO Shuo, AI Jianjian, et al. Research on heterogeneous-backup virtual network embedding[J]. Journal of Electronics &Information Technology, 2018, 40(5): 1087–1093. doi:  10.11999/JEIT170730
    [4] 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
    [5] SUN Jian, ZHU Guangyang, SUN Gang, et al. A reliability-aware approach for resource efficient virtual network function deployment[J]. IEEE Access, 2018, 6: 18238–18250. doi:  10.1109/ACCESS.2018.2815614
    [6] DINH N T and KIM Y. An efficient reliability guaranteed deployment scheme for service function chains[J]. IEEE Access, 2019, 7: 46491–46505. doi:  10.1109/ACCESS.2019.2908185
    [7] 刘光远, 安秀芳, 苏森. 基于节点可靠性感知和共享路径保护的虚拟网映射算法研究[J]. 通信学报, 2016, 37(8): 51–57. doi:  10.11959/j.issn.1000-436x.2016155

    LIU Guangyuan, AN Xiufang, and SU Sen. Virtual network mapping algorithm with node reliability awareness and shared-path protection[J]. Journal on Communications, 2016, 37(8): 51–57. doi:  10.11959/j.issn.1000-436x.2016155
    [8] European Telecommunications Standards Institute. Network Functions Virtualisation (NFV); Reliability; Report on models and features for end-to-end reliability[R]. ETSI GS NFV-REL 003 V1.1.1, 2016.
    [9] TANG Xiaoyong, LI Kenli, QIU Meikang, et al. A hierarchical reliability-driven scheduling algorithm in grid systems[J]. Journal of Parallel and Distributed Computing, 2012, 72(4): 525–535. doi:  10.1016/j.jpdc.2011.12.004
    [10] BIJWE S, MACHIDA F, ISHIDA S, et al. End-to-End reliability assurance of service chain embedding for network function virtualization[C]. 2017 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN), Berlin, Germany, 2017: 1–4. doi: 10.1109/NFV-SDN.2017.8169853.
    [11] KUO Tungwei, LIOU B Hheng, LIN K C J, et al. Deploying Chains of virtual network functions: On the relation between link and server usage[J]. IEEE/ACM Transactions on Networking, 2018, 26(4): 1562–1576. doi:  10.1109/TNET.2018.2842798
    [12] 魏亮, 黄韬, 张娇, 等. 基于强化学习的服务链映射算法[J]. 通信学报, 2018, 39(1): 90–100. doi:  10.11959/j.issn.1000-436x.2018002

    WEI Liang, HUANG Tao, ZHANG Jiao, et al. Service Chain mapping algorithm based on reinforcement learning[J]. Journal on Communications, 2018, 39(1): 90–100. doi:  10.11959/j.issn.1000-436x.2018002
    [13] CAO Haotong, ZHU Yongxu, ZHENG Gan, et al. A novel optimal mapping algorithm with less computational complexity for virtual network embedding[J]. IEEE Transactions on Network and Service Management, 2018, 15(1): 356–371. doi:  10.1109/TNSM.2017.2778106
    [14] ZHANG Xin, QIAN Zhuzhong, ZHANG Sheng, et al. Pattern-aware reliable virtual network function chain deployment[C]. 2017 IEEE International Symposium on Parallel and Distributed Processing with Applications and 2017 IEEE International Conference on Ubiquitous Computing and Communications (ISPA/IUCC), Guangzhou, China, 2017: 335–342. doi: 10.1109/ISPA/IUCC.2017.00055.
    [15] SHAHRIAR N, AHMED R, CHOWDHURY S R, et al. Generalized recovery from node failure in virtual network embedding[J]. IEEE Transactions on Network and Service Management, 2017, 14(2): 261–274. doi:  10.1109/TNSM.2017.2693404
  • [1] 陈前斌, 管令进, 李子煜, 王兆堃, 杨恒, 唐伦.  基于深度强化学习的异构云无线接入网自适应无线资源分配算法, 电子与信息学报. 2020, 42(6): 1468-1477. doi: 10.11999/JEIT190511
    [2] 翟东, 孟相如, 康巧燕, 胡航, 韩晓阳.  面向时延与可靠性优化的服务功能链部署方法, 电子与信息学报. 2020, 42(10): 2386-2393. doi: 10.11999/JEIT200023
    [3] 陈卓, 冯钢, 何颖, 周杨.  运营商网络中基于深度强化学习的服务功能链迁移机制, 电子与信息学报. 2020, 42(9): 2173-2179. doi: 10.11999/JEIT190545
    [4] 汤红波, 邱航, 游伟, 季新生.  基于联合备份的服务功能链可靠性保障的部署方法, 电子与信息学报. 2019, 41(12): 3006-3013. doi: 10.11999/JEIT190013
    [5] 刘焕淋, 胡浩, 熊翠连, 陈勇, 向敏, 马跃.  基于时频联合碎片感知的资源均衡虚拟光网络映射算法, 电子与信息学报. 2018, 40(10): 2345-2351. doi: 10.11999/JEIT171208
    [6] 刘焕淋, 吕磊, 陈勇, 蔚承英, 胡浩.  节点重要性感知的透明虚拟光网络协同映射策略, 电子与信息学报. 2018, 40(8): 1978-1984. doi: 10.11999/JEIT171096
    [7] 李晨溪, 曹雷, 陈希亮, 张永亮, 徐志雄, 彭辉, 段理文.  基于云推理模型的深度强化学习探索策略研究, 电子与信息学报. 2018, 40(1): 244-248. doi: 10.11999/JEIT170347
    [8] 刘彩霞, 李凌书, 汤红波, 王晓雷, 卢干强.  基于子图同构的vEPC虚拟网络分层协同映射算法, 电子与信息学报. 2017, 39(5): 1170-1177. doi: 10.11999/JEIT160642
    [9] 刘焕淋, 杜君丹, 易鹏飞, 陈勇, 张明佳.  弹性光网络中面向可靠性的链路故障概率保护与保护资源重配置策略, 电子与信息学报. 2017, 39(11): 2579-2586. doi: 10.11999/JEIT170150
    [10] 跨域虚拟网络映射问题研究, 电子与信息学报. 2016, 38(3): 728-734. doi: 10.11999/JEIT150656
    [11] 尚新文, 李鑫伟, 曹林林, 肖刘, 苏小保.  X波段脉冲空间行波管输出结构可靠性研究, 电子与信息学报. 2016, 38(10): 2674-2680. doi: 10.11999/JEIT160003
    [12] 龚水清, 陈靖, 王崴.  面向节点异构的能耗感知虚拟网络映射算法, 电子与信息学报. 2015, 37(8): 2021-2027. doi: 10.11999/JEIT141527
    [13] 梁家荣, 白杨, 王新阳.  评估交换超立方体网络可靠性的一种新方法, 电子与信息学报. 2015, 37(3): 693-699. doi: 10.11999/JEIT140557
    [14] 胡升泽, 包卫东, 王博, 乐俊, 葛斌.  无线传感器网络基于多元簇首的分簇数据收集算法, 电子与信息学报. 2014, 36(2): 403-408. doi: 10.3724/SP.J.1146.2013.00731
    [15] 江逸茗, 兰巨龙, 周慧琴.  网络虚拟化环境下的资源监控策略, 电子与信息学报. 2014, 36(3): 708-714. doi: 10.3724/SP.J.1146.2013.00755
    [16] 熊飞, 乔迪, 王宏祥, 赵子岩, 杨洪, 沈亮.  一种基于有序二元决策图和布尔函数性质计算网络可靠性的算法, 电子与信息学报. 2014, 36(11): 2786-2790. doi: 10.3724/SP.J.1146.2014.00176
    [17] 蔡进科, 顾华玺, 卢冀, 余晓杉.  基于Openflow网络的高可靠性虚拟网络映射算法, 电子与信息学报. 2014, 36(2): 396-402. doi: 10.3724/SP.J.1146.2013.00367
    [18] 王志明, 汪斌强, 王保进.  基于拓扑影响度和回溯迁移的虚拟网可靠性映射方案, 电子与信息学报. 2012, 34(12): 2898-2904. doi: 10.3724/SP.J.1146.2012.00101
    [19] 齐宁, 王保进, 汪斌强, 张栋.  均衡虚拟网构建算法研究, 电子与信息学报. 2011, 33(6): 1301-1306. doi: 10.3724/SP.J.1146.2010.01130
    [20] 张剑贤, 周端, 杨银堂, 赖睿, 高翔.  处理器可靠性约束的电压频率岛NoC能耗优化, 电子与信息学报. 2011, 33(9): 2205-2211. doi: 10.3724/SP.J.1146.2010.01266
  • 加载中
  • 图(6) / 表ll (3)
    计量
    • 文章访问数:  272
    • HTML全文浏览量:  131
    • PDF下载量:  17
    • 被引次数: 0
    出版历程
    • 收稿日期:  2019-12-03
    • 修回日期:  2020-06-08
    • 网络出版日期:  2020-07-11

    目录

      /

      返回文章
      返回

      官方微信,欢迎关注