高级搜索

留言板

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

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

基于延迟和抖动感知的多播服务功能树嵌入算法

刘亮 陈翔 桂晓菁 徐勇军 杜娅荣 侯泽天 段洁

刘亮, 陈翔, 桂晓菁, 徐勇军, 杜娅荣, 侯泽天, 段洁. 基于延迟和抖动感知的多播服务功能树嵌入算法[J]. 电子与信息学报, 2024, 46(1): 184-194. doi: 10.11999/JEIT230015
引用本文: 刘亮, 陈翔, 桂晓菁, 徐勇军, 杜娅荣, 侯泽天, 段洁. 基于延迟和抖动感知的多播服务功能树嵌入算法[J]. 电子与信息学报, 2024, 46(1): 184-194. doi: 10.11999/JEIT230015
LIU Liang, CHEN Xiang, GUI Xiaojing, XU Yongjun, DU Yarong, HOU Zetian, DUAN Jie. Multicast Service Function Tree Embedding Algorithm Based on Delay and Jitter Awareness[J]. Journal of Electronics & Information Technology, 2024, 46(1): 184-194. doi: 10.11999/JEIT230015
Citation: LIU Liang, CHEN Xiang, GUI Xiaojing, XU Yongjun, DU Yarong, HOU Zetian, DUAN Jie. Multicast Service Function Tree Embedding Algorithm Based on Delay and Jitter Awareness[J]. Journal of Electronics & Information Technology, 2024, 46(1): 184-194. doi: 10.11999/JEIT230015

基于延迟和抖动感知的多播服务功能树嵌入算法

doi: 10.11999/JEIT230015
基金项目: 国家自然科学基金(62171070, 61701058),重庆邮电大学博士启动基金(A2023007)
详细信息
    作者简介:

    刘亮:男,副教授,博士,研究方向为网络功能虚拟化、端边云资源协同管理、天地一体化网络

    陈翔:男,硕士生,研究方向为NFV环境中的多播路由、服务功能链部署和重配置

    桂晓菁:女,讲师,研究方向为内容中心网络

    徐勇军:男,副教授,博士,研究方向为智能超表面、资源分配、机器学习算法

    杜娅荣:女,硕士生,研究方向为服务功能链部署迁移、机器学习算法

    侯泽天:男,硕士生,研究方向为移动环境中虚拟网络资源配置

    段洁:女,博士,副教授,博士,主要研究方向为天地一体化网络、内容中心网络

    通讯作者:

    刘亮 liuliang@cqupt.edu.cn

  • 中图分类号: TN915; TP393

Multicast Service Function Tree Embedding Algorithm Based on Delay and Jitter Awareness

Funds: The National Natural Science Foundation of China (62171070, 61701058),Chongqing University of Posts and Telecommunications Doctoral Initiation Foundation (A2023007)
  • 摘要: 针对软件定义网络/网络功能虚拟化(SDN/NFV)架构中,多播请求流(MRs)需满足严格时延和抖动约束下遍历由多个虚拟网络功能(VNFs)依序组成的服务功能树(SFT)问题。该文提出一种基于最优链路选择函数进行深度优先搜索构建SFT的路由算法。首先,提出网络资源相对成本函数,以保证网络负载自动均衡。其次,联合考虑网络资源、VNF动态放置及多播流延迟和抖动约束,构建SFT动态嵌入问题的整数线性规划模型(ILP)。最后,针对该NP难问题,设计辅助边权图和最优链路选择函数进行路由路径选择,并以最小化资源消耗成本为目标提出具有延迟和抖动感知的SFT嵌入算法(SFT-EA)。仿真结果表明,SFT-EA在吞吐量,流接受率和网络负载均衡方面具有更好的性能。
  • 图  1  多播服务功能树

    图  2  SDN/NFV网络示例

    图  3  辅助边权图$ G_i^\prime $的构造

    图  4  在图$ {\hat G_i} $中解决DJA-DSPR

    图  5  平均流接受率

    图  6  平均吞吐量

    图  7  剩余带宽累积分布

    图  8  剩余流表累积分布

    图  9  剩余CPU的累积分布

    图  10  平均流接受率随SFC长度的变化

    图  11  不同功能节点数下的平均流接受率

    图  12  不同目的节点数下算法的执行时间

    算法1 SFT-EA算法
     输入: $ G(N,L) $,流请求$ {\text{M}}{{\text{R}}_i} $,资源容量,资源剩余率,最大迭
     代次数$ K $。
     输出:多播树$ T $。
     1. 根据2.4.1枚举$ G $中功能节点上所有可能的VNFs
     2. 根据3.1构造$ G_i^\prime $
     3. 基于$ G_i^\prime $构造$ {\hat G_i} $
     4. 求最小时延树$ {T_{{\text{LDT}}}}\leftarrow $KruskalMST($ {\hat G_i} $)
     5. if${D_{ {\text{max} } } }\;{\rm{in}}\;{T_{ {\text{LDT} } } } > R_i^{ {\text{delay} } }$则算法结束
     6. else
     7. while$ (({\Delta _T} \in [\max \left\{ {{D_{\max }},R_i^{{\text{jitter}}}} \right\},R_i^{{\text{delay}}}]) $且$k \le K$)//算法最多迭代$ K $次
     8. $ {T_i} \leftarrow s;V[\hat u] = 0;L[\hat u][\hat v] = 0;V[s] = 1 $,//数组$ V $和$ L $分别用于记录节点和链路是否已被访问
     ${{Pre} }({{s} }) = \emptyset ;\hat u = {\text{s} };{\Delta _T} = \max \left\{ { {D_{\max } },R_i^{ {\text{jitter} } } } \right\}$//$ pre() $函数表示一个节点的前驱
     9.  while $ L[\hat u][\hat v] \ne 1 $
     10.   if $ \hat v \notin {D_i} \cup \{ s\} $ and $ D(\hat u) + d(\hat u,\hat v) \leqslant {\Delta _T} $
     11.   $ N = N \cup \{ \hat v\} $//$ N $记录候选节点
     12.   else if $ \hat v \in {D_i} $且${\Delta _T} - R_i^{ {\text{Jitter} } } \le D(\hat u) + d(\hat u,\hat v) \le {\Delta _T}$
     13. $ N = N \cup \{ \hat v\} $
     14.   end if
     15.    if $ N \ne \emptyset $
     16.     for each $ \hat v \in N $
     17.      if $ D(\hat u) + d(\hat u,\hat v) = = {\Delta _T} $
     18.       if $ \hat v \in {D_i} $
     19.      $ V[\hat v] = 1;L[\hat u][\hat v] = 1;{T_i} = {T_i} \cup \{ \hat v\} $
     20.      else $ L[\hat u][\hat v] = 1 $
     21.     end if
     22.     else if $ D(\hat u) + d(\hat u,\hat v) < {\Delta _T} $
     23. 选择$ f(\hat u,\hat v) $中最小的节点$ \hat v $
     24.     $ {T_i} = {T_i} \cup \{ \hat v\} ;V[\hat v] = 1;L[\hat u][\hat v] = 1;Pre(\hat v) = \hat u$;
           $\hat u = \hat v;L[\hat u][\hat v] = 0; $
     25.     end if
     26.    end for
     27.    else 将$ L[\hat u][\hat v] $为0的链路设置为1,$ \hat u = pre(\hat u) $
     28.   end if
     29.   end while
     30. for each $ \hat v \in {D_i} $
     31. if 所有$ V[\hat v] = = 1 $ 则转到36
     32. else $ {\Delta _T} + + ;k + + $;break;
     33. end if
     34. end for
     35. end while
     36. if $ {T_i} $包含$ {D_i} $中的所有目的节点
     37. 通过将$ {T_i} $中的每条边替换为其在$ G $中对应的路径来映射多播
     树$ T $,并更新$r_{i,{\rm{uv}}}^{ {\text{bw} } }\;,r_{i,u}^{ {\text{ft} } }\;,r_{i,u}^{ {\text{cpu} } }$和$ r_{i,m}^{{\text{cpu}}} $
     38. else 路由失败,$ {\text{M}}{{\text{R}}_i} $请求被拒绝,Return
     39. end if
     40. end if
    下载: 导出CSV
  • [1] 唐伦, 吴婷, 周鑫隆, 等. 一种基于联邦学习资源需求预测的虚拟网络功能迁移算法[J]. 电子与信息学报, 2022, 44(10): 3532–3540. doi: 10.11999/JEIT210743

    TANG Lun, WU Ting, ZHOU Xinlong, et al. A virtual network function migration algorithm based on federated learning prediction of resource requirements[J]. Journal of Electronics &Information Technology, 2022, 44(10): 3532–3540. doi: 10.11999/JEIT210743
    [2] LIU Liang, GUO Songtao, LIU Guiyan, et al. Joint dynamical VNF placement and SFC routing in NFV-enabled SDNs[J]. IEEE Transactions on Network and Service Management, 2021, 18(4): 4263–4276. doi: 10.1109/TNSM.2021.3091424
    [3] 徐勇军, 谷博文, 谢豪, 等. 全双工中继协作下的移动边缘计算系统能耗优化算法[J]. 电子与信息学报, 2021, 43(12): 3621–3628. doi: 10.11999/JEIT200937

    XU Yongjun, GU Bowen, XIE Hao, et al. Energy consumption optimization algorithm for full-duplex relay-assisted mobile edge computing systems[J]. Journal of Electronics &Information Technology, 2021, 43(12): 3621–3628. doi: 10.11999/JEIT200937
    [4] MALI R, ZHANG Xijun, and QIAO Chunming. Benefits of multicasting in all-optical networks[C]. SPIE 3531, All-Optical Networking: Architecture, Control, and Management Issues. Boston, United States, 1998: 209–220.
    [5] Grand View Research. Video streaming market size, share & trends analysis report by streaming type, by solution, by platform, by service, by revenue model, by deployment type, by user, by region, and segment forecasts, 2023 – 2030[EB/OL].https://www.grandviewresearch.com/industry-analysis/video-streaming-market, 2023.
    [6] XIE Yanghao, HUANG Lin, KONG Yuyang, et al. Virtualized network function forwarding graph placing in SDN and NFV-Enabled IoT networks: A graph neural network assisted deep reinforcement learning method[J]. IEEE Transactions on Network and Service Management, 2022, 19(1): 524–537. doi: 10.1109/TNSM.2021.3123460
    [7] XU Zichuan, LIANG Weifa, HUANG Meitian, et al. Approximation and online algorithms for NFV-enabled multicasting in SDNs[C]. 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS), Atlanta, USA, 2017: 625–634.
    [8] MUHAMMAD A, SORKHOH I, QU Long, et al. Delay-sensitive multi-source multicast resource optimization in NFV-enabled networks: A column generation approach[J]. IEEE Transactions on Network and Service Management, 2021, 18(1): 286–300. doi: 10.1109/TNSM.2021.3049718
    [9] 孔紫璇, 李航, 向万, 等. 用户动态接入下的多播业务链部署和调整方法[J]. 北京邮电大学学报, 2022, 45(6): 53–59. doi: 10.13190/j.jbupt.2022-116

    KONG Zixuan, LI Hang, XIANG Wan, et al. Multicast service chain deployment and adjustment method under user dynamic access[J]. Journal of Beijing University of Posts and Telecommunications, 2022, 45(6): 53–59. doi: 10.13190/j.jbupt.2022-116
    [10] WANG Xinhan, XING Huanlai, SONG Fuhong, et al. Dynamic multicast-oriented virtual network function placement with SFC request prediction[C]. 2022 14th International Conference on Communication Software and Networks (ICCSN), Chongqing, China, 2022: 81–88.
    [11] JIA Mike, LIANG Weifa, HUANG Meitian, et al. Routing cost minimization and throughput maximization of NFV-enabled unicasting in software-defined networks[J]. IEEE Transactions on Network and Service Management, 2018, 15(2): 732–745. doi: 10.1109/TNSM.2018.2810817
    [12] XU Zichuan, LIANG Weifa, HUANG Meitian, et al. Efficient NFV-enabled multicasting in SDNs[J]. IEEE Transactions on Communications, 2019, 67(3): 2052–2070. doi: 10.1109/TCOMM.2018.2881438
    [13] REN Bangbang, GUO Deke, SHEN Yulong, et al. Embedding service function tree with minimum cost for NFV-enabled multicast[J]. IEEE Journal on Selected Areas in Communications, 2019, 37(5): 1085–1097. doi: 10.1109/JSAC.2019.2906764
    [14] ASGARIAN M, MIRJALILY G, and LUO Zhiquan. Trade-off between efficiency and complexity in multi-stage embedding of multicast VNF service chains[J]. IEEE Communications Letters, 2022, 26(2): 429–433. doi: 10.1109/LCOMM.2021.3132134
    [15] REN Haozhe, XU Zichuan, LIANG Weifa, et al. Efficient algorithms for delay-aware NFV-enabled multicasting in mobile edge clouds with resource sharing[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(9): 2050–2066. doi: 10.1109/TPDS.2020.2983918
    [16] ALHUSSEIN O, DO P T, YE Qiang, et al. A virtual network customization framework for multicast services in NFV-enabled core networks[J]. IEEE Journal on Selected Areas in Communications, 2020, 38(6): 1025–1039. doi: 10.1109/JSAC.2020.2986591
    [17] REN Cheng, CHEN Xuxiang, XIANG Haiyun, et al. On efficient delay-aware multisource multicasting in NFV-Enabled softwarized networks[J]. IEEE Transactions on Network and Service Management, 2022, 19(3): 3371–3386. doi: 10.1109/TNSM.2022.3188777
    [18] LI Hang, WANG Luhan, ZHU Zhenghe, et al. Multicast service function chain orchestration in SDN/NFV-Enabled networks: Embedding, readjustment, and expanding[J]. IEEE Transactions on Network and Service Management, 2023.
    [19] MIRJALILY G, ASGARIAN M, and LUO Zhiquan. Interference-aware NFV-enabled multicast service in resource-constrained wireless mesh networks[J]. IEEE Transactions on Network and Service Management, 2022, 19(1): 424–436. doi: 10.1109/TNSM.2021.3083798
    [20] Python Community. Networkx 3.1[EB/OL]. https://pypi.org/project/networkx/, 2023.
    [21] Internet topology[EB/OL]. http://topology-zoo.org/maps/, 2022.
    [22] CHENG Yulun and YANG Longxiang. VNF deployment and routing for NFV-enabled multicast: A Steiner tree-based approach[C]. 2017 9th International Conference on Wireless Communications and Signal Processing (WCSP), Nanjing, China, 2017: 1–4.
  • 加载中
图(12) / 表(1)
计量
  • 文章访问数:  345
  • HTML全文浏览量:  131
  • PDF下载量:  47
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-01-12
  • 修回日期:  2023-08-07
  • 录用日期:  2023-08-15
  • 网络出版日期:  2023-08-19
  • 刊出日期:  2024-01-17

目录

    /

    返回文章
    返回